Evoluční hyperheuristiky pro Vehicle Routing Problem. Bc. Jaromír Mlejnek

ii

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Diplomová práce

Evoluční hyperheuristiky pro Vehicle Routing Problem Bc. Jaromír Mlejnek

Vedoucí práce: Ing. Jiří Kubalík, Ph.D.

Studijní program: Otevřená Informatika, strukturovaný, Navazující magisterský Obor: Umělá inteligence 11. května 2012

iv

v

Poděkování Na tomto místě bych chtěl především poděkovat Ing. Jiřímu Kubalíkovi, Ph.D. za příkladné vedení této práce, za jeho podnětné nápady a rady, bez kterých by tato práce nemohla vzniknout. Dále bych chtěl poděkovat rodině a přátelům za podporu během studia.

vi

viii

Abstract This work deals with application of hyperheuristic-based approaches for solving the generally known Vehicle Routing Problem. Hyperheuristics, in contrast to the metaheuristics, work on a higher level of abstraction. That means they are less problem-dependent and can cover a wider range of combinatorial optimization problems. Instead of solving the problem directly, they suggest and construct methods which after that solve the problem. The primary goal of hyperheuristics is not to overcome existing metaheuristics, but to generalized methods for solving combinatorial and optimization problems. In this thesis a new hyperheuristic-based algorithm called HyperPOEMS is proposed. This algorithm uses an evolutionary algorithm to develop a sequence of actions which improve the prototype iteration by iteration. The prototype consists of a sequence of units which construct and improve the solution for given problem step by step. In this work the algorithm is used for solving Capacitated Vehicle Routing Problem (CVRP). This algorithm was tested on some standard state-of-the-art benchmarks and the results was compared with results obtained by the hyperheuristic-based algorithm HHC-VRP and with some specialized methods for solving CVRP. The results demonstrate that the proposed algorithm outperforms the HHC-VRP algorithm and for some instances can be compared with stateof-the-art algorithms.

ix

x

Abstrakt Tato práce se zabývá aplikací hyperheuristických přístupů pro řešení obecně známého Vehicle Routing Problému. Hyperheuristiky, na rozdíl od metaheuristik, pracují na vyšší úrovni abstrakce. To znamená, že jsou méně problémově závislé a mohou tak pokrýt širší škálu kombinatorických a optimalizačních problémů. Místo toho, aby přímo řešily daný problém, tak navrhují a tvoří postupy, jejíchž aplikací je následně daný problém vyřešen. Primárním cílem hyperheuristik není překonávat stávající sofistikované metaheuristiky, ale zobecnit způsob řešení kombinatorických a optimalizačních úloh. V rámci této práce je navržen a implementován nový hyperheuristický algoritmus pojmenovaný HyperPOEMS. Tento algoritmus používá evoluční algoritmus pro vývoj sekvencí akcí, které iterativně zlepšují tzv. prototyp. Prototyp je tvořen jako sekvence určitých jednotek, které postupně konstruují a zároveň zlepšují řešení daného problému. V této práci je tento algoritmus použit pro řešení kapacitního Vehicle Routing Problému (CVRP). Tento algoritmus byl otestován na obecně uznávaných datových sadách a výsledky byly porovnány s výsledky dosahovanými hyperheuristickým algoritmem HHC-VRP a některými specializovanými algoritmy pro řešení CVRP. Dosažené výsledky ukazují, že algoritmus HyperPOEMS překonává algoritmus HHC-VRP a pro některé datové instance se vyrovnává i odkazovaným specializovaným algoritmům.

Obsah 1 Úvod 1.1 Cíle práce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 2

2 Vehicle Routing Problem 2.1 Definice VRP . . . . . . . . . . . . . 2.2 Definice CVRP . . . . . . . . . . . . 2.3 Další varianty VRP . . . . . . . . . . 2.4 Heuristické metody pro CVRP . . . 2.4.1 Clark and Wright algoritmus 2.4.2 Mole and Jameson algoritmus 2.4.3 Kilby algoritmus . . . . . . . 2.4.4 Sweep algoritmus . . . . . . . 2.4.5 2,3-opt . . . . . . . . . . . . . 2.4.6 Or-opt . . . . . . . . . . . . . 2.4.7 Node Insertion heuristika . . 2.4.8 Van Breedam heuristiky . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

3 3 4 4 6 6 6 7 7 7 7 8 8

3 Hyperheuristiky 3.1 Definice hyperheuristických metod . . . 3.2 Klasifikace hyperheuristik . . . . . . . . 3.2.1 Předchozí klasifikace . . . . . . . 3.2.2 Shrnutí klasifikace . . . . . . . . 3.3 Algoritmus HHC-VRP . . . . . . . . . . 3.3.1 Reprezentace řešení . . . . . . . 3.3.2 Definice okolí a změnové operace 3.3.3 Hill-climbing prohledávání . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

9 9 12 12 13 14 14 16 16

4 POEMS 4.1 Definice POEMS . . . . . . . . . 4.2 Reprezentace sekvence akcí . . . 4.3 Populace . . . . . . . . . . . . . . 4.4 Změnové operátory . . . . . . . . 4.5 Evoluční model . . . . . . . . . . 4.6 Aplikace POEMS a jeho rozšíření

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

19 19 19 20 21 21 21

. . . . . .

. . . . . .

xi

. . . . . . . . . . . .

. . . . . .

. . . . . .

xii

OBSAH

5 HyperPOEMS 5.1 Definice HyperPOEMS . . . . . . . . . . . . . . . . . . . . . 5.2 HyperPOEMS reprezentace . . . . . . . . . . . . . . . . . . 5.2.1 POEMS prototyp . . . . . . . . . . . . . . . . . . . . 5.2.2 Vygenerování počátečního prototypu . . . . . . . . . 5.2.3 Sekvence POEMS akcí . . . . . . . . . . . . . . . . . 5.2.4 Aplikace sekvence akcí a jejich ohodnocení . . . . . 5.3 Evoluční algoritmus . . . . . . . . . . . . . . . . . . . . . . 5.3.1 Selekční strategie . . . . . . . . . . . . . . . . . . . . 5.3.2 Křížení . . . . . . . . . . . . . . . . . . . . . . . . . 5.3.3 Mutace . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Implementace . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Implementované třídy a rozhraní HyperPOEMS . . 5.4.1.1 Rozhraní ConstructionHeuristic . . . . . . 5.4.1.2 Rozhraní OrderHeuristic . . . . . . . . . . 5.4.1.3 Rozhraní RouteImprovementHeuristic . . . 5.4.1.4 Rozhraní MultiRouteImprovementHeuristic 5.4.1.5 Třída PrototypeCreator . . . . . . . . . . . 5.4.1.6 Třída Prototype . . . . . . . . . . . . . . . 5.4.1.7 Třída Unit . . . . . . . . . . . . . . . . . . 5.4.1.8 Třída CVRPManager . . . . . . . . . . . . 5.4.1.9 Třída CVRPSolution . . . . . . . . . . . . 5.4.1.10 Třída CVRPAction . . . . . . . . . . . . . 5.4.1.11 Třída ActionSequence . . . . . . . . . . . . 5.4.1.12 Třída ASPopulation . . . . . . . . . . . . . 5.4.1.13 Třída POEMS . . . . . . . . . . . . . . . . 5.4.1.14 Třída POEMSAlgorithm . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . .

25 25 26 26 28 28 30 32 32 32 32 33 33 33 33 33 33 33 33 35 35 35 35 35 35 35 35

6 Experimenty 6.1 Testovací data . . . . . . . . . . . . . . . . . 6.2 Testovací konfigurace . . . . . . . . . . . . . . 6.3 Výsledky pro jednotlivé testovací konfigurace 6.4 Zhodnocení výsledků . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

37 37 37 38 42

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 Závěr 45 7.1 Možné budoucí rozšíření . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Literatura

47

A Obsah přiloženého CD

51

Seznam obrázků 2.1

Vztah mezi CVRP a dalšími problémy třídy VRP [32] . . . . . . . . . . . . .

3.1 3.2 3.3 3.4

Struktura hyper-heuristického systému . . . . . . . . Struktura hyperheuristického systému pro generování HHC-VRP reprezentace . . . . . . . . . . . . . . . . Příklad sekvence struktur algoritmu HHC-VRP . . .

4.1

Sekvence akcí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

5.1 5.2 5.3

Struktura HyperPOEMS jednotek . . . . . . . . . . . . . . . . . . . . . . . . 27 Aplikace sekvence akcí na prototyp . . . . . . . . . . . . . . . . . . . . . . . . 31 Diagram tříd HyperPOEMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

xiii

. . . . . . . . . . heuristik pomocí . . . . . . . . . . . . . . . . . . . .

. . . GP . . . . . .

. . . .

5 10 11 14 15

xiv

SEZNAM OBRÁZKŮ

Seznam tabulek 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8

Testovací konfigurace . . . . . . . . . . . . . . . . . . . . . . . . . . Výsledky pro Experiment 1 . . . . . . . . . . . . . . . . . . . . . . Výsledky pro Experiment 2 . . . . . . . . . . . . . . . . . . . . . . Výsledky pro Experiment 3 . . . . . . . . . . . . . . . . . . . . . . Srovnání výsledků provedených experimentů s výsledky HHC-VRP Christofides: Porovnání jednotlivých algoritmů s HyperPOEMS . . Fisher: Porovnání jednotlivých algoritmů s HyperPOEMS . . . . . Taillard: Porovnání jednotlivých algoritmů s HyperPOEMS . . . .

xv

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

38 39 40 41 42 43 44 44

xvi

SEZNAM TABULEK

Kapitola 1

Úvod Velké množství kombinatorických a optimalizačních úloh nachází reálné uplatnění v praxi. To je hlavní důvod, proč se pracuje na algoritmech, které tyto problémy řeší. Velké logistické firmy by si zřejmě již nedokázaly představit jejich provoz, ve kterém by nepoužívaly pro plánování distribuce dodávek nějaký softwarový nástroj, který tento problém řeší za ně. Plánování výroby ve společnostech již také není na bedrech příslušných zaměstnanců, ale plány tvoří plánovací algoritmy. Podobné algoritmy se používají pro plánování směn sester v nemocnicích, pro sestavování školních rozvrhů a pro další problémy. Nebylo by lehké najít oblast lidské působnosti, kde by nehrála alespoň malou roli otázka optimalizace. Stávající algoritmy, které řeší jednotlivé optimalizační úlohy, mají ale jeden nedostatek a to, že jsou dosti problémově závislé. Algoritmus, který dosahuje velmi dobrých výsledků pro jednu problémovou doménu, může pro jinou třídu problémů dávat velmi špatné výsledky. Eliminace tohoto nedostatku je jedním z cílů, které si dávají hyperheuristiky, moderní metody řešení kombinatorických problémů. A právě hyperheuristikami se zabývá tato práce. Struktura této práce je následující. Kapitola 2 je věnována definici a popisu Vehicle Routing Problemu. VRP je zde formalizován v nejobecnější možné podobě a jsou zde uvedeny jeho další varianty a rozšíření, především však Capacitated Vehicle Routing Problém. V závěru této kapitoly jsou stručně popsány a klasifikovány stávající metody řešení CVRP. V Kapitole 3 je definice hyperheuristických metod a jejich klasifikace. V závěru této kapitoly je také popsán algoritmus HHC-VRP, hyperheuristický algoritmus pro řešení CVRP. Kapitola 4 je věnována optimalizační metodě POEMS (Iterative Prototype Optimisation with Evolved Improvement Steps). V Kapitole 5 je popsán návrh a implementace algoritmu HyperPOEMS. Pozornost je věnována jak principiálnímu návrhu hyperheuristiky, tak i jednotlivým implementačním detailům. Experimentálnímu ověření navrženého řešení je věnována Kapitola 6. Zde jsou popsány jednotlivé testovací konfigurace, datové sady, který byly použity pro testování, i obdržené výsledky. Výsledky obdržené jednotlivými testovacími konfiguracemi jsou porovnávány jak mezi sebou, tak i se stávajícími algoritmy pro řešení CVRP (včetně algoritmu HHC-VRP). Práci uzavírá Kapitola 7, ve které jsou zhodnoceny dosažené výsledky a přednesena možná budoucí rozšíření algoritmu HyperPOEMS.

1

2

1.1

KAPITOLA 1. ÚVOD

Cíle práce

Cílem této práce je zmapovat stávající možnosti hyperheuristických algoritmů pro řešení různých kombinatorických problémů a porovnat je se stávajícími heuristickými a metaheuristickými přístupy. Hlavním bodem zájmu je především použití hyperheuristických algoritmů pro řešení VRP problémů. Na základě získaných informací bude následně navrhnut a implementován hyperheuristický algoritmus pro řešení kapacitního Vehicle Routing Problému.

Kapitola 2

Vehicle Routing Problem Úlohy typy Vehicle Routing Problem (VRP) patří mezi jedny z nejčastěji studovaných a řešených kombinatorických problémů současnosti, a to pro jejich praktické uplatnění. Výsledky dosahované v této oblasti nacházejí reálné uplatnění v logistice a dalších přidružených oblastech. V globálním hledisku přináší automatizace procesu plánování distribuce úspory v rozsahu 5 až 20 % z celkových transportních nákladů [32]. Prvně byl VRP zformalizován v roce 1959 v článku [14]. V tomto článku autoři popisují praktický problém distribuce benzínu do palivových stanic. Zároveň je zde zavedena první matematická formalizace VRP a představen algoritmus pro řešení daného problému. Od té doby bylo napsáno mnoho článků, věnujících se této problematice. Zároveň byly zformalizovány další varianty tohoto problému, které do něho přinášejí další optimalizační kritéria a omezení, případně mění stávající definici VRP. VRP leží na průsečíku mezi problémem obchodního cestujícího (Traveling Salesman Problem) a problémem naplňování zásobníku (Bin packing problem), takže se jedná o NPobtížnou úlohu. Obecně je možné rodinu problémů VRP charakterizovat tak, že jde o hledání množiny optimální cest (z hlediska vzdálenosti, transportního času, . . . ) mezi jedním (případně více) centrálním uzlem (depem) a množinou dalších uzlů, které představují zákazníky, přičemž nalezené řešení (rozdělení zákazníků do jednotlivých cest) splňuje všechna kladená omezení.

2.1

Definice VRP

Symetrický Vehicle Routing Problem může být v nejobecnější podobě definován následujícím způsobem. Nechť G = (V, E) je úplný neorientovaný graf, kde V = {0, 1, 2, . . . , n} je množina n + 1 uzlů grafu (v kontextu VRP se místy používá pojem množina lokací) a E je množina hran spojující uzly grafu G. Pro každou hranu e ∈ E = {(i, j) : i, j ∈ V, i < j} je definována nezáporná hodnota ci,j , která určuje cenu přechodu z uzlu i do uzlu j. Smyčky zde nemají smysl, proto platí ci,i = ∞ pro všechny i ∈ V . Jelikož se jedná o symetrickou verzi VRP, tak pro všechny hrany e = (i, j) ∈ E platí ci,j = cj,i a matice vzdáleností mezi jednotlivými lokacemi je symetrická. V případě asymetrického VRP platí, že graf G = (V, E) je orientovaný, a tím pádem je množina hran definována jako E = {(i, j) : i, j ∈ V, i 6= j}. Uzli i = {1 . . . , n} představují zákaznické lokace, uzel i = 0 je centrální depem. Každý ze zákazníků i = {1, . . . , n} má požadavek na doručení qi jednotek určitého zboží z depa. V cen-

3

4

KAPITOLA 2. VEHICLE ROUTING PROBLEM

trálním depu se nachází k vozidel, tj. M = {m1 , m2 , . . . , mk }, které zákazníkům doručují příslušné zboží. Cílem je najít množinu uzavřených cest, kde součet délek jednotlivých cest je minimální, a zároveň platí, že: 1. každý zákaznický uzel je zařazen přesně v jedné cestě a je v rámci dané cesty navštíven přesně jednou, 2. ke každé cestě je přiřazeno přesně jedno vozidlo, 3. každá cesta začíná a končí v depu, 4. suma požadavků jednotlivých zákazníků zařazených v cestách nepřesáhne kapacitu vozidla, 5. délka žádné cesty není delší než předem stanovená hodnota L, 6. jsou splněna případná další omezení. Pokud je nalezeno řešení, které splňuje výše uvedená omezení, tak je toto řešení prohlášeno za přípustné. Pokud dané řešení porušuje jakékoliv z omezení, tak se jedná o řešení nepřípustné. Je potřeba konstatovat, že výše uvedená definice VRP je pouze jednou z možných definic. Specifikace obecného VRP je poměrně volná a může se v různé literatuře v detailech lišit. V článku [24] je například VRP definován tak, že počet vozidel m nemusí být fixní a může se pohybovat v rámci určitého intervalu mL ≤ m ≤ mU .

2.2

Definice CVRP

Capacitated Vehicle Routing Problém je základní verzí obecného VRP. Jde o problém, kde konstantní počet identických vozidel stejné kapacity má doručit jednotlivým zákazníkům určitý počet jednotek stejného zboží. Cílem je minimalizovat sumu délek vytvořených cest pro jednotlivá vozidla, případně počet cest. Z porovnání s obecným VRP definovaným výše vyplývá, že CVRP přidává omezení na jednotnou kapacitu všech vozidel. Zároveň přestává platit omezení na maximální délku cest. Dle této definice je řešení CVRP přípustné, pokud každý ze zákazníků je zařazen přesně v jedné cestě, ke každé cestě je přiřazeno přesně jedno vozidlo, každá cesta začíná a končí v depu, a suma zákaznických požadavků v rámci jedné cesty nepřekročí kapacitu vozidla.

2.3

Další varianty VRP

Na obrázku 2.1 je zobrazen vztah mezi CVRP a dalšími problémy třídy VRP. Mezi další varianty VRP problému patří například:

2.3. DALŠÍ VARIANTY VRP

5

Obrázek 2.1: Vztah mezi CVRP a dalšími problémy třídy VRP [32]

• VRP with Time Windows (VRPTW): V této variantě VRP je pro každou zákaznickou lokaci i definován časový interval hai , bi i, ve kterém může vozidlo navštívit danou lokaci. Horní mez bi je definována buď jako hard constrain, nebo jako soft constrain. Pokud je toto omezení definováno jako soft constrain, tak v případě jeho porušení je dané řešení nějakým způsobem penalizováno. Časové okno je definováno i pro depo, přičemž tyto hodnoty určují, kdy mohou vozy z depa vyjet a do kdy se musí do depa vrátit. • VRP with Backhauls (VRPB): Tato varianta VRP dělí zákaznické lokace do dvou kategorií. První kategorii tvoří zákazníci, kteří požadují doručení určitého zboží z depa. Ve druhé kategorii jsou oproti tomu zákazníci, kteří požadují, aby vozidlo vyzvedlo určité zboží a dopravilo ho zpět do depa. Zároveň musí platit, že sběr zboží, které se má navrátit do depa, bude realizován až po obsloužení všech zákazníků, kteří čekají do doručení zboží. Optimalizačním kritériem je opět nalezení řešení s nejnižšími transportními náklady. • VRP with Pick-Up and Deliveries (VRPPD): V této variantě VRP se předpokládá, že každý zákazník může vyžadovat doručení nějakého zboží z depa, ale i požadovat odvoz nějakého zboží zpět do depa. Pokud navštívený zákazník požaduje oboje, tak nejdříve dojde k vyložení příslušného zboží a pak k nakládce zboží, které se má vrátit do depa. • Multiple Depots VRP (MDVRP): Tato varianta předpokládá, že existuje více než jedno depo, ze kterého vyjíždějí k zákazníkům vozidla. Předpokládá se, že zákaznické lokace

6


nejsou centralizovány u jednotlivých dep, protože v tom případě by bylo možné řešit tento problém jako klasický VRP. Každé vozidlo se vrací do depa ze kterého vyjelo. Cílem je minimalizovat sumu délek jednotlivých cest i samotný počet cest.

2.4

Heuristické metody pro CVRP

Heuristické metody, na rozdíl od exaktních přístupů, nezaručují dosažení přesného řešení daného problému, ale obecně dokáží relativně rychle najít alespoň nějaké řešení (více či méně kvalitní), pokud tedy existuje. Na rozdíl od exaktních metod jsou však aplikovatelné na větší a obtížnější datové instance. Heuristické metody pro řešení CVRP je možné klasifikovat do dvou skupin. První skupinu tvoří konstrukční heuristiky. Tyto heuristiky dostanou na vstupu instanci CVRP problému a jejich výstupem je přípustné řešení určité kvality. Jestliže konstrukční heuristiky tvoří první skupinu heuristických metod pro řešení CVRP, tak druhou skupinou jsou zlepšující heuristiky. Tyto heuristiky dostanou na vstupu řešení a snaží se ho dále zlepšit. Tyto heuristiky je možné dále rozdělit na zlepšující heuristiky, které zlepšují řešení na úrovni jednotlivých cest, a zlepšující heuristiky, které pracují na úrovni více cest. Hlavní nevýhodou těchto jednoduchých heuristik je neschopnost vyváznout ve většině případů z lokálního optima. Navíc prohledávají pouze určitou část prostoru řešení, a proto mohou na některých instancích daného problému pracovat dobře a na jiných nemusí být schopny nalézt žádné řešení.

2.4.1

Clark and Wright algoritmus

Jedná se o konstrukční heuristický algoritmus, který byl v roce 1964 publikován Clarkem a Wrightem v článku [9]. Algoritmus konstruuje řešení na základě tzv. konceptu úspor (v ang. savings concept). Existují dvě verze tohoto algoritmu, sekvenční a paralelní. Paralelní verze pracuje následovně: 1. Každá ze zákaznických lokací i se vloží do jedné cesty, tj. (0, i, 0), kde 0 je depo. 2. Pro všechny různé dvojice zákaznických lokací se spočítají úspory, tj. si,j = ci,0 +c0,j − ci,j . Úspory se vloží v klesajícím pořadí do fronty. 3. Vezme se první úspora si,j z fronty (tedy ta, s nejvyšší hodnotou). Pokud se nyní lokace i a j nachází v různých cestách a první cesta končí lokací i (depo se nebere nyní v úvahu) a druhá začíná lokací j, nebo naopak, tak se tyto cesty mohou sloučit, pokud by sloučením nedošlo k překročení kapacity výsledné cesty. Sloučením cest vznikne cesta (0, · · · , i, j, · · · , 0).

2.4.2

Mole and Jameson algoritmus

Mole and Jameson je sekvenční vkládající metodou, která konstruuje řešení cestu po cestě. Pro nezařazené lokace i ∈ VU , kde VU je množina všech nezařazených lokací, se spočítá dle

2.4. HEURISTICKÉ METODY PRO CVRP

7

následujících rovnic cena jejich vložení mezi dvě stávající lokace a a b dané cesty. α(a, i, b) = ca,i + ci,b − λ · ca,b

(2.1)

β(a, i, b) = µ · c0,i − α(a, i, b)

(2.2)

Do cesty je potom vložena lokace i, která maximalizuje hodnotu β(a, i, b), přičemž λ a µ jsou konfigurační parametry této heuristiky. Pokud z důvodu překročení kapacity není možné vložit do cesty žádnou z nezařazených lokací, tak je vytvořena cesta nová [19].

2.4.3

Kilby algoritmus

Kilby algoritmus vkládá nezařazené zákaznické lokace do stávajících cest tak, aby minimalizoval cenu Cri (a, i, b) = ca,i + ci,b − ca,b (2.3) kde i je vkládanou lokací, ri ∈ Rc je cesta z množiny stávajících cest a a a b jsou stávající lokace cesty ri [19]. Pokud žádná cesta neexistuje nebo není možné vložit danou lokaci do žádné ze stávajících cest, tak je vytvořena cesta nová.

2.4.4

Sweep algoritmus

Sweep algoritmus [25] spadá mezi konstrukční heuristiky označované jako cluster-first, routesecond. Pomyslná přímka, protínající depo a nejvzdálenější zákaznickou lokaci, rotuje ve směru hodinových ručiček a přiřazuje protínané lokace do shluku, dokud součet zákaznických požadavků je menší nebo roven kapacitě vozidla. Pokud se již lokace do shluku nevejde, tak je vytvořen shluk nový. V druhé fázi tohoto algoritmu se řeší problém obchodního cestujícího pro jednotlivé shluky, čímž se vytvoří požadované řešení CVRP.

2.4.5

2,3-opt

Heuristika 2-op pracuje tak, že zruší dvě hrany jedné cesty a vytvoří dvě nové hrany, které propojují cestu jiným způsobem (existuje pouze jeden způsob, jak vytvořit tyto hrany tak, aby výsledná cesta byla validní). Pokud je výsledná cesta kratší než cesta původní, tak se tato změna ponechá, v opačném případě se obnoví původní cesta a vyzkouší se jiná dvojice hran. Tento postup se opakuje tak dlouho, dokud dochází k zlepšování délky cesty. Heuristika 3-opt pracuje na stejném principu jako 2-opt, akorát se odstraňují hrany tři. V tomto případě jsou dvě možnosti, jak vytvořit 3 hrany tak, aby výsledná cesta byla validní. Heuristika se opět aplikuje tak dlouho, dokud zlepšuje řešení [26].

2.4.6

Or-opt

Or-opt je zlepšující heuristika, která se snaží zlepšit jednu cestu řešení tím způsobem, že postupně přesouvá řetězce tří, dvou a jednoho uzlu na jinou pozici v rámci dané cesty. I tato heuristika zlepšuje cestu tak dlouho, dokud to je možné [28].

8


2.4.7

Node Insertion heuristika

Jedná se o jednoduchou zlepšující heuristiku, které se snaží zlepšit řešení VRP problému cestu po cestě. Každou lokaci v cestě zkouší vložit na jinou pozici. Pokud se přesunutím lokace cesta zlepší, tak začíná opět od začátku.

2.4.8

Van Breedam heuristiky

Van Breedam heuristiky (často označované jako Van Breedam moves) patří mezi zlepšující heuristiky, které zlepšují stávající řešení VRP problému přesouváním lokací mezi dvěma cestami. Daná heuristika se aplikuje na dvojici cest tak dlouho, dokud dochází k jejich zlepšování. Těmito heuristikami jsou: • String Cross (SC): Dvě cesty si vymění řetězce po sobě jdoucích lokací tak, že se zkříží dvě hrany mezi lokacemi různých cest. • String Exchange (SE): Dvě cesty si vymění řetězce po sobě jdoucích uzlů (nejvíce k uzlů). • String Relocation (SR): Zřetězení nejvíce k lokací jedné cesty je vloženo do cesty jiné. • String Mix (SM): Aplikuje se buď heuristika SE, nebo heuristika SR, a to dle toho, která více zlepšuje dané dvě cesty. Hodnota parametru k je většinou 1 nebo 2, a to z důvodu časové náročnosti těchto heuristik pro větší hodnoty k a horší výsledky. Dále je možné určit, zda se má provézt první možné zlepšení (First Improvement) nebo zlepšení nejlepší (Best Improvement). Výše uvedená formalizace byla zavedena v disertační práci [3].

Kapitola 3

Hyperheuristiky Heuristické a metaheuristické principy byly úspěšně aplikovány pro řešení celé škály optimalizačních problémů. Mnoho implementací metaheuristik dosáhlo ve své problémové doméně nečekaných výsledků. Jejich nevýhoda je však v tom, že jsou příliš problémově závislé. Jejich uzpůsobení pro řešení jiných tříd kombinatorických problémů je velmi pracné a vyžaduje expertní znalost daných problémových domén. Tyto nedostatky se snaží eliminovat právě hyperheuristické přístupy. Jejich primárním cílem není překonávat tyto sofistikované metaheuristiky, ale zobecnit způsob řešení kombinatorických a optimalizačních úloh.

3.1

Definice hyperheuristických metod

Pod pojmem hyperheuristika se skrývá zobecněná, doménově nezávislá technika pro řešení různých druhů problémů (optimalizačních, kombinatorických, prohledávacích atd.). Hlavním cílem hyperheuristického principu není překonávat zavedené a silně doménově specifické algoritmy, ale poskytovat obecný koncept pro řešení široké škály výpočetních problémů. Hyperheuristiky tedy přímo samy neřeší daný problém, ale navrhují a tvoří přístupy pro jeho řešení, což je odlišuje právě od metaheuristik. I když velkého rozvoje dosahuje tato oblast až v posledních letech, tak první zmínka pochází již z roku 1961, kdy Fisher a Thompson [16] zveřejnili první článek popisující princip hyperheuristik (ještě ne takto pojmenovaný). Poté nastala v této oblasti poměrně dlouhá odmlka a až v 90. letech se opět rozběhl výzkum a začaly se objevovat další hyperheuristické přístupy, přičemž termín „hyperheuristika“ byl zaveden až v roce 1997 v článku [15], kde popisoval způsob kombinace několika jednoduchých metod umělé inteligence při řešení problému automatického dokazování teorémů. V roce 2000 byl stejný termín nezávisle použit v článku [13], kde byl definován jako „heuristiky pro výběr heuristik“. V tomto kontextu jsou hyperheuristiky chápány jako metody, které jsou založeny na kombinování jednoduchých heuristik (tzv. low-level heuristik). Při řešení problému jsou většinou low-level heuristiky vybírány některou z metaheuristik. Cílem je tedy nalézt správnou posloupnost low-level heuristik, které se provedou nad instancí daného problému a po jejich skončení je na výstupu výsledek přijatelné kvality. To je hlavní rozdíl oproti metaheuristikám. Ty pracují na řešení přímo a prohledávají prostor řešení. Hyperheuristiky oproti tomu pracují nad prostorem heuristik. Na obrázku 3.1 lze vidět strukturu hyperheuristického systému. Doména řešeného problému obsahuje množinu jednoduchých heuristik a ohodnocovací funkci, která vyhodnocuje

9

10

KAPITOLA 3. HYPERHEURISTIKY

Obrázek 3.1: Struktura hyper-heuristického systému

kvalitu řešení. Zde je také definována strukturální reprezentace řešení a může se zde vyskytovat i počáteční řešení. Na obrázku lze vidět, že mezi hyperheuristikou a problémovou doménou se nachází doménová bariéra. Ta zde slouží pouze k demonstraci, že hyperheuristika nemá žádnou doménovou znalost. Ví pouze, že má k dispozici n jednoduchých heuristik, které vytvářejí řešení daného problému, a že kvalitu řešení po aplikování heuristik získá prostřednictvím ohodnocovací funkce. Obecnost hyperheuristik tkví v tom, že je možné k nim připojit jinou problémovou doménu a hyperheuristika pak řeší jiný problém bez jakékoliv její úpravy. Pod pojmem hyperheuristiky se však neskrývají pouze „heuristiky pro výběr heuristik“. S rozvojem genetického programování vznikla nová třída hyperheuristik, která by se dala označit jako „heuristiky pro generování heuristik“. Algoritmus genetického programování vytváří nové nízkoúrovňové heuristiky ze stavebních bloků, které se označují jako funkce nebo heuristické komponenty [4]. Funkce jsou velmi problémově specifické, a proto jsou součástí problémové domény, viz. obrázek 3.2. Mohou mít podobu fragmentů stávajících heuristik, případně mohou být vytvořeny expertem v oblasti řešeného problému. Spolu s funkcemi jsou v problémové doméně terminály, což jsou vstupní proměnné. Ty mohou být stanoveny fixně, náhodně nebo dle nějaké heuristiky. Algoritmus genetického programování se poté snaží z těchto komponent vytvořit co možná nejlepší heuristiku z pohledu dané problémové domény. Způsob, jakým je to zajištěno, je podobný klasickému použití genetického programování. Nejprve je vygenerována počáteční populace programů (stromová reprezentace; ekvivalentem chromozomů u genetických algoritmů), která je poté pomocí genetických operátorů1 vyvíjena směrem k lepším programům. Při křížení se pro dva vybrané individuály 1

Oproti genetickým algoritmům existuje v případě genetického programování více genetických operátorů, např. operátor zapouzdření, operátor reprodukce a další.

3.1. DEFINICE HYPERHEURISTICKÝCH METOD

11

určí uzly, které si navzájem vymění, a to včetně případných podstromů. Mutace je unární operátor, který mění strukturu jednoho individuálu (například zavěšením jedné větve grafu pod jiný uzel). Jelikož však všechny vnitřní uzly ve stromové struktuře programu reprezentují funkce, tak je potřeba zajistit, aby všechny provedené změny byly legální. To například znamená, že vnitřní uzel reprezentující funkci se dvěma vstupy musí mít právě dva potomky. Vývoj heuristik končí zpravidla v určité generaci. Z hlediska použitelnosti lze vygenerované heuristiky rozdělit na znovupoužitelné a jednoúčelové [4]. Jednoúčelové heuristiky jsou vytvořeny pouze pro danou instanci daného problému. Znovupoužitelné heuristiky jsou více obecné a jsou vytvořeny za účelem dalšího použití na doposud neviděných instancích daného problému. Zde je ovšem důležité, aby instance daného problému použitá ke konstrukci a verifikaci vyvíjených heuristik byla dostatečně obecná a různorodá.

Obrázek 3.2: Struktura hyperheuristického systému pro generování heuristik pomocí GP

Na obrázku 3.2 lze vidět strukturu hyperheuristického systému pro generování heuristik. Opět se zde nachází doménová bariéra, která odděluje hyperheuristiku od problémově závislé domény. Problémová doména obsahuje množinu funkcí, množinu terminálů, ohodnocovací funkci a případně počáteční řešení (ve formě částečně vytvořené heuristiky). Hyperheuristika konstruuje z jednotlivých funkcí a terminálů heuristiky ve formě programů. Ty se aplikují na data poskytnutá hyperheuristice (instance daného problému) a ohodnocovací funkce vrátí kvalitu získaného řešení. Hyperheuristika tedy nemá žádné znalosti o vytvořených heuristikách. Ví pouze, jak dobře dokáží řešit daný problém, přičemž strukturu ani detaily tohoto problému hyperheuristika znát nepotřebuje. Genetické programování generující jednoduché heuristiky bylo aplikováno na širokou škálu problémů, jako například problém splňování booleovských formulí [4] [5], 2D strip packing problem [5] [6], plánovací problémy a mnoho dalších.

12

3.2


Klasifikace hyperheuristik

Na téma klasifikace a členění hyperheuristických principů lze nalézt nemalé množství odborných článků, které předkládají jejich různé členění. Neexistence jedné všeobecně uznávané kategorizace může zapříčinit nejasnosti při srovnávání jednotlivých metod. Na druhou stranu je nutné konstatovat, že tato oblast prochází intenzivním vývojem a stanovit pevné členění není prakticky možné, protože se stále objevují nové principy a strategie.

3.2.1

Předchozí klasifikace

Jak již bylo uvedeno, tak prací věnujících se členění hyperheuristik je velké množství. V článku [30] jsou hyperheuristiky členěny do dvou kategorií, a to hyperheuristiky s učením a bez učení. Učením se zde myslí to, že jsou během provádění algoritmu dynamicky měněny preference jednotlivých low-level heuristik, přičemž právě dle preferencí jsou jednotlivé heuristiky vybírány a aplikovány výběrovou funkcí. Hyperheuristiky s učením by bylo dále možné klasifikovat dle učícího mechanismu na ty, co využívají genetické algoritmy během učení a ty, co jsou založeny na jiném způsobu učení. Právě genetické algoritmy jsou doposud považovány za nejpoužívanější metaheuristiku využívanou pro výběr low-level heuristik [4]. Hyperheuristiky bez učení aplikují low-level heuristiky podle předem určeného pořadí, případně je aplikují ve zcela náhodném pořadí. Tento jednoduchý selektivní princip dělá tento přístup lehce implementovatelný, ale jednoduchosti odpovídají i nepříliš dobré výsledky. Článek [2] zavádí členění na konstruktivní hyperheuristiky a na ty, které využívají lokální prohledávání. Konstruktivní hyperheuristický přístup je založen postupném vytváření řešení. Low-level heuristiky jsou vybírány dle nějaké strategie a inkrementálně vytváří řešení. Přístup založený na lokálním prohledávání pracuje na úplně jiném principu. Zde se vychází z kompletního inicializačního řešení (nějakým způsobem vygenerovaného) a postupně jsou vybírány heuristiky generující sousední řešení. Pokud je nově vygenerované řešení lepší než stávající, tak se dále pokračuje z něho. Tento princip se v jiných klasifikačních článcích může vyskytovat pod názvem perturbační heuristiky (myšleny právě ony low-level heuristiky generující sousední řešení). Další možnou klasifikaci hyperheuristických metod lze nalézt v přehledovém článku [7]. Zde jsou hyperheuristiky klasifikovány na hyperheuristiky založené na náhodném výběru jednoduchých heuristik, založené na hladovém přístupu (greedy a peckish hyperheuristiky), založené na metaheuristikách a hyperheuristiky využívající učící mechanismy. Přístup založený na náhodném aplikování nízkoúrovňových heuristik patří mezi nejstarší a nejjednodušší. Byl aplikován a odzkoušen na mnoha optimalizačních problémech. Pokud se však heuristiky aplikují jen čistě náhodně, tak výsledky nejsou příliš dobré, protože kvalita řešení záleží pouze na pravděpodobnosti aplikování heuristik ve „správném“ pořadí. Naskýtá se proto možnost aplikovat náhodně vybranou heuristiku pouze v případě, kdy zlepšuje aktuální řešení. To však může způsobit to, že algoritmus může uvíznout v lokálním extrému (zvláště pro malý počet heuristik). Proto je nutné s jistou pravděpodobností použít i heuristiky, které nepřináší žádné zlepšení. Další možností je aplikovat zlepšující heuristiku tak dlouho, dokud zlepšuje řešení. Dále existují například přístupy založené na metodě Monte Carlo [1] nebo na Great Deluge algoritmu [20].

3.2. KLASIFIKACE HYPERHEURISTIK

13

Druhá skupina hyperheuristik definována v článku [7] je založena na tzv. hladovém principu. To znamená, že v každém kroku je vybrána ta heuristika, která nejvíce zlepšuje aktuální řešení. Opět se zde však vyskytuje možnost uváznutí v lokálním extrému, protože nemusí pro aktuální řešení již existovat žádná přínosná heuristika. Proto je lepší použít princip popsaný v článku [12], kde se kombinuje hladový přístup s náhodným výběrem heuristik. V každém kroku se vybírá náhodně heuristika z množiny N nejlepších heuristik. Hlavní nevýhodou hladového přístupu je jeho časová náročnost, protože se musejí všechny heuristiky v každém kroku algoritmu spustit, aby bylo možné určit nejlepší. Hyperheuristiky založené na metaheuristikách jsou patrně nejvíce studovanou oblastí hyperheuristického výzkumu. Velké množství metaheuristik bylo aplikováno jako vysokoúrovňová selektivní funkce pracující na prostoru heuristik. Dle použitého principu lze rozdělit hyperheuristiky na ty, co jsou založené na genetickém algoritmu a na ty, co pracují na jiném metaheuristickém principu, např. simulované žíhání, zakázané prohledávání a další. Poslední skupinou hyperheuristik definovanou v článku [7] jsou hyperheuristiky využívající učící mechanismy. Nejčastěji je učení realizováno tím způsobem, že každá heuristika má určitou váhu. Váha se stanovuje nejčastěji dle předchozího výsledku heuristiky (změna aktuálního řešení po aplikování heuristiky). Vliv na váhu má často také doba běhu nebo některé další technické aspekty dané heuristiky. Výběr heuristik pak probíhá dle těchto vah, přičemž výběr může být realizován například ruletovým kolem, kde pravděpodobnost výběru heuristiky odpovídá její váze. Další možností je, že je vždy vybrána heuristika s maximální vahou (ta nejlepší).

3.2.2

Shrnutí klasifikace

Z předchozí kapitoly vyplývá, že kritérií pro klasifikaci hyperheuristik je více a vzhledem ke stálému vývoji nelze stanovit jedno stále platné členění. Zde jsou alespoň shrnuty kritéria, dle kterých lze aktuální přístupy kategorizovat. Kategorizace dle: • Způsobu práce s jednoduchými heuristikami: 1. Hledání optimálních sekvencí heuristik. 2. Generování heuristik. • Podstaty jednoduchých heuristik: 1. Konstrukční heuristiky. 2. Perturbační heuristiky. 3. Kombinace konstrukčních a perturbačních heuristik. • Použité vysokoúrovňové metody pro práci s jednoduchými heuristikami: 1. Randomizované metody aplikace heuristik. 2. „Hladové“ metody. 3. Metaheuristické přístupy.

14


• Formy zpětné vazby: 1. Bez zpětné vazby. 2. S použitím učících mechanismů.

3.3

Algoritmus HHC-VRP

Algoritmus HHC-VRP představený v roce 2009 v článku [18] je příkladem hyperheuristického algoritmu pro řešení CVRP. Tento algoritmus je jednou z prvních implementací hyperheuristického přístupu pro řešení některého z problémů typu VRP. HHC-VRP je konstrukčně-perturbační hyperheuristikou založenou na hill-climbing prohledávání okolí řešení pomocí změnových operací. Řešení zde však není reprezentováno přímo, ale jako sekvence určitých struktur, které ho dynamicky tvoří.

Obrázek 3.3: HHC-VRP reprezentace

3.3.1

Reprezentace řešení

Řešení je reprezentováno jako sekvence struktur S1 , S2 , . . . Sk , jak je vidět v horní části obrázku 3.3. Každá ze struktur se skládá ze dvou komponent, konstrukční a zlepšující. Konstrukční komponenta je tvořena konstrukční heuristikou Cj , jejím parametrem hj = (Oj , CIj ) a počtem nj ≤ N lokací (uzlů VRP problému), které má daná konstrukční komponenta integrovat do řešení, tj. vložit do cest, přičemž N je celkový počet lokací pro danou instanci CVRP problému. Parametr konstrukční heuristiky hj se skládá z řadící heuristiky Oj a konstrukčně-zlepšující heuristiky CIj . Řadící heuristika seřadí doposud nezpracované lokace, tj. lokace nepřiřazené do cest. Konstrukční heuristika poté vezme prvních nj lokací a zařadí je do cest. Pro ty cesty, které se aplikací konstrukční heuristiky nějak změnily, se následně spustí zlepšující heuristika CIj . Nyní přichází na řadu zlepšující komponenta, která aplikuje zlepšující heuristiku Ij na všechny doposud vytvořené cesty. Po vyhodnocení všech struktur v sekvenci je obdrženo výsledné řešení daného CVRP problému.

3.3. ALGORITMUS HHC-VRP

15

Konstrukčními heuristikami, které algoritmus HHC-VRP používá, jsou algoritmy Clark and Wright, Mole and Jameson, Kilby a Sweep algoritmus. Jako konstrukčně-zlepšující heuristiky jsou použity jednoduché 2-opt, 3-opt a Or-opt heuristiky, tedy heuristiky které se snaží zlepšit řešení pouze na úrovni jednotlivých cest. Zlepšující komponenty používají opět jednoduché heuristiky 2-opt, 3-opt a Or-opt. Navíc jsou zde použity heuristiky, které zlepšují řešení na úrovni dvojic cest. To znamená, že se snaží najít lepší řešení přesouváním lokací mezi dvojicemi cest. Těmito heuristikami jsou String Exchage, String Relocation a String Cross, souhrnně označované jako Van Breedam moves. Jako řadící heuristiky jsou použity jednoduché metody, které řadí lokace dle klesající/rostoucí vzdálenosti od depa, klesajícího/rostoucího požadavku jednotlivých zákazníků, případně dle radiálního úhlu od určitého výchozího bodu (například spojnice depo - nejvzdálenější lokace v dané instanci).

Obrázek 3.4: Příklad sekvence struktur algoritmu HHC-VRP

V horní části obrázku 3.4 je vzorová sekvence tří HHC-VRP struktur. Sekvence se vyhodnocuje zleva doprava a postupně tvoří řešení vzorového CVRP problému. První struktura seřadí všechny lokace daného problému řadící heuristikou označenou jako “5”. Pak vezme první 3 lokace a pomocí Sweep algoritmu je vloží do cest. Aktuálně vytvořené cesty jsou následně zoptimalizovány 2-opt algoritmem a v rámci zlepšující komponenty dále algoritmem String Exchange. Druhá struktura seřadí doposud nezařazené lokace pomocí řadící heuristiky označené jako “3”, vezme 5 prvních lokací a vloží je do řešení pomocí algoritmu Clark and Wright. Cesty modifikované touto strukturou jsou zlepšeny pomocí 3-opt heuristiky, všechny cesty v řešení jsou následně optimalizovány pomocí String Relocation heuristiky. Podobně se pokračuje i třetí strukturou, která vloží do řešení zbývající lokace, čímž se řešení stává kompletní. V dolní části obrázku 3.4 lze vidět odpovídající výsledek po vyhodnocení vzorové sekvence.

16


3.3.2

Definice okolí a změnové operace

Změnové operace modifikují aktuální sekvenci struktur s cílem najít sekvenci, která produkuje lepší řešení problému. Použité změnové operace tedy definují okolí aktuální sekvence struktur, které může být prohlédáno. Operace definované pro tento algoritmus mohou měnit délku sekvence, tj. přidávat či odebírat jednotlivé struktury, měnit pořadí jednotlivých struktur v sekvenci, případně měnit použité heuristiky v jednotlivých strukturách. Použitými operace jsou operace: • Add: Tato operace náhodně vybere strukturu Si v aktuální sekvenci, vytvoří kopii dané struktury (nechť je označena jako Sadd ) a vloží ji do sekvence na pozici i + 1. Zároveň u struktury Sadd změní jednu z použitých heuristik. Počet vkládaných lokací strukturou Sadd je náhodně vybrán z intervalu nadd ∈ h1, ni − 1i. Z důvodu zachování konzistence je následně potřeba upravit počet vkládaných lokací strukturou Si dle rovnice ni = ni − nadd . Použití operace Add zvyšuje možnost nalezení lepšího řešení tím, že mění distribuci lokací v rámci celé sekvence struktur a zároveň modifikuje některou z použitých heuristik. • Delete: Operace Delete vybere náhodně jednu strukturu Si z dané sekvence a odstraní ji. Počet lokací vkládaných odstraněnou strukturou se přičte k předcházející struktuře Si−1 , tj. ni−1 = ni−1 + ni . V článku [18] není popsáno, kam se přidají lokace v případě smazání první struktury v sekvenci. Dá se ale předpokládat, že to bude ke struktuře Si+1 . Tato operace slouží k tomu, aby odstraňovala struktury, které z hlediska celkového řešení nepřinášejí žádné zlepšení. • Replace: Tato operace náhodně vybere jednu ze struktur v sekvenci a náhodně ji změní jednu z použitý heuristik s cílem najít pomocí nové heuristiky lepší řešení. • Reallocate: Operace Reallocate náhodně vybere dvě po sobě jdoucí struktury Si 0 0 a Si+1 . Pro tyto struktury určí náhodně nové počty vkládaných lokací ni a ni+1 tak, 0 0 aby byla zachována rovnost ni + ni+1 = ni + ni+1 . Cílem této operace je měnit distribuci lokací v sekvenci tak, aby bylo dosaženo lepších výsledků. Z popisu použitých akci vyplývá, že se v sekvenci nemohou vyskytovat struktury, který by pouze zlepšovaly řešení, tj. bez toho, aby určitou konstrukční heuristikou vkládaly další lokace do řešení. Maximální počet struktur v sekvenci je tedy roven počtu lokací (uzlů) dané instance CVRP problému. Dále není možné aplikací jedné operace změnit více heuristik u jedné či více struktur.

3.3.3

Hill-climbing prohledávání

Pseudokód 3.1 popisuje způsob použití algoritmu hill-climbing v rámci algoritmu HHC-VRP. Nejprve se pomocí metody CreateBalancedSequence vytvoří počáteční sekvence struktur,

3.3. ALGORITMUS HHC-VRP

17

která se zároveň označí jako doposud nejlepší (SBest ). Tato metoda je implementována tak, aby vytvářela sekvence struktur, ve které jsou obsaženy pokud možno všechny z implementovaných heuristik. Poté se po určitou dobu prohledává okolí dané sekvence struktur. Prohledávání okolí je realizováno tak, že se náhodně a se stejnou pravděpodobností vybere jedna z výše popsaných operací (Add, Delete, Replace nebo Reallocate). Vybraná operace se aplikuje na aktuální sekvenci, čímž vznikne nová sekvence, která se následně vyhodnotí. Pokud je nová sekvence z pohledu fitness funkce alespoň stejně dobrá jako sekvence stávající, tak nová sekvence stávající sekvenci nahradí. Po uplynutí časového limitu se porovná aktuální sekvence se sekvencí SBest , a pokud je lepší, tak ji nahradí. Následně se vygeneruje úplně nová sekvence struktur, která se opět po určitou dobu modifikuje výše popsanými operacemi. Tyto restarty jsou nutné z toho důvodu, aby bylo možné vyváznout z případných lokálních minim. Algorithm 3.1 Algoritmus HHC-VRP ← CreateBalancedSequence(Heuristics) = Sbc = Sbi for i = 1 → N umOf Restarts do time = 0 while time < T imeSlot/N umberOf Restarts do Operator ← SelectM ove(Add, Delete, Replace, Reallocate) 0 Sbc ← ApplyOperation(Operator, Sbc ) 0 if EvaluateSequence(Sbc ) ≤ EvaluateSequence(Sbc ) then 0 Sbc = Sbc end if end while if EvaluateSequence(Sbc ) < EvaluateSequence(SbBest ) then SbBest = Sbc end if Sbi ← CreateBalancedSequence(Heuristics) Sbc = Sbi end for return SbBest

bi 1: S

bBest 2: S 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18:

18


Kapitola 4

POEMS Klasické metody řešení kombinatorických problémů založené na evolučních algoritmech pracují většinou tak, že vyvíjejí populaci kandidátních jedinců. Každý z jedinců reprezentuje celé řešení daného problému. Problémem této přímé reprezentace je však v tom, že prostor řešení, které evoluční algoritmus prohledává, je obrovský. Algoritmus POEMS (Iterative Prototype Optimisation with Evolved IMprovement Steps), popsaný dále v této kapitole, je založen také na evolučním algoritmu, ale ten zde není použit pro vývoj samotného řešení daného problému, nýbrž pro vývoj sekvence akcí, které iterativně zlepšují prototyp řešení daného problému.

4.1

Definice POEMS

POEMS [22] je stochastickým iterativním optimalizačním algoritmem, který v každé iteraci hledá nejlepší sekvenci akcí, které maximálně zlepšuje aktuální řešení, tzv. prototyp. Tento počáteční prototyp je před spuštěním první iterace POEMS vygenerován, a to buď náhodně či nějakou informovanou metodou. S tímto prototypem se poté vstupuje do první iterace algoritmu. V každé iteraci se spouští evoluční algoritmus, jehož cílem je vyšlechtit sekvenci akcí, která nejvíce zlepšuje aktuální prototyp. Na akce je možné nahlížet jako na jednoduché funkce modifikující prototyp. Nejlepší sekvence akcí navrácená evolučním algoritmem se následně aplikuje na prototyp, čímž vznikne nové řešení, tzv. kandidát. Ten se porovná s aktuálním prototype, a pokud je z hlediska hodnotící funkce lepší nebo alespoň stejně dobrý, tak se stane novým prototypem. Pokud je kandidát horší, tak se prototyp nemění. V další iteraci se vezme aktuální prototyp a opět se hledá sekvence akcí, která ho dále zlepšuje. To celé se opakuje po předem stanovený počet iterací, viz. pseudokód 4.1.

4.2

Reprezentace sekvence akcí

Na sekvence akcí vyvíjené evolučním algoritmem je možné nahlížet jako na lineární chromozom určité maximální délky. Každý gen chromozomu je reprezentován jako instance určité elementární akce z množiny definovaných akcí pro daný problém. Kromě klasických akcí, které modifikují řešení daného problému, existuje ještě jedna speciální akce, a to tzv. NOP akce. Tato akce nijak neovlivňuje řešení problému. Slouží pouze k tomu, aby bylo možné

19

20

KAPITOLA 4. POEMS

Algorithm 4.1 POEMS algoritmus 1: P rototype ← generateP rototype() 2: for i = 1 → N umOf Iterations do 3: BestSequence ← run_EA(P rototype) 4: Candidate ← apply(P rototype, BestSequence) 5: if candidateN otW orse(Candidate, P rototype) then 6: P rototype ← Candidate 7: end if 8: end forreturn P rototype

definovat sekvence různých délek, tj. různého počtu aktivních akcí. Instance akce je tvořena typem použité akce, typem aktivní akce a případným polem jejich vstupních atributů. Typ akce může nabývat libovolné hodnoty z množiny akcí pro daný problém a NOP akce. Typ aktivní akce může opět nabývat libovolné hodnoty z množiny akcí pro daný problém, nikoliv však již NOP akce. To je z toho důvodu, že mutace mění aktivní akci na NOP a naopak. Pokud je tedy jedna instance akce zmutována dvakrát, tak nabývá opět původní hodnoty, tj. typ aktivní akce se během výpočtu nemění.

Obrázek 4.1: Sekvence akcí Na obrázku 4.1 je vzorová sekvence akcí délky 4 pro řešení problému obchodního cestujícího, viz. článek [22]. Sekvence obsahuje 3 aktivní akce a jednu NOP akci. Akce move(x, y) přesouvá v cestě město x za město y, invert(x, y) otáčí v cestě pořadí měst mezi městy x a y a akce swap(x, y) prohazuje v cestě pozice měst x a y. Takováto sekvence akcí se poté zleva doprava aplikuje na stávající prototyp reprezentující aktuální řešení dané instance problému obchodního cestujícího. Následně se spočítá fitness modifikovaného řešeni a přiřadí se dané sekvenci.

4.3

Populace

Jak vyplývá z předchozí kapitoly, tak populace chromozomů pro běh evolučního algoritmu je tvořena sekvencemi akcí. Sekvence jsou v populaci rozděleny do tzv. přihrádek. Počet přihrádek je roven maximálnímu počtu akcí v sekvenci. Jednotlivé přihrádky jsou zaplňovány sekvencemi dle počtu jejich aktivních akcí, tj. v přihrádce “1” jsou pouze sekvence s minimálně jednou aktivní akcí, v přihrádce “2” jsou sekvence s minimálně dvěma aktivními akcemi atd. Tato diverzifikace populace do jednotlivých přihrádek najde uplatnění v rámci náhradové strategie a při selekci jedinců pro aplikaci genetických operátorů.

4.4. ZMĚNOVÉ OPERÁTORY

4.4

21

Změnové operátory

Algoritmus POEMS používá klasické genetické operátory křížení a mutace. Do křížení vstupují dva rodičovské chromozomy a z nich se vytvoří dva noví potomci. Každý gen nového chromozomu je kopií náhodně vybraného genu jednoho z rodičů s tím, že každý gen rodičovských chromozomů je v potomcích použit právě jednou. Operátor křížení má tedy podobu tzv. uniform crossover, kde libovolná kombinace genů rodičovských chromozomů produkuji validní potomky. Mutace chromozomů algoritmu POEMS pracuje tak, že se daný chromozom sekvenčně prochází a každý z genů chromozomu se s určitou malou pravděpodobností zmutuje. Mutací genu se myslí buď změna aktivní akce na NOP akci či naopak, nebo změna použité aktivní akce a jejích parametrů.

4.5

Evoluční model

Použitý evoluční model a jeho konfigurace se může u algoritmu POEMS lišit problém od problému. V článku [22] je například popsán generační evoluční model s turnajovou selekcí a elitismem. Zde se nejdříve vygeneruje počáteční populace a najde se nejlepší jedinec, který se vloží do nové populace. Poté se pomocí genetických operátorů vytváří noví jedinci, kteří zaplňují novou populaci. Po vytvoření nové populace se opět vyhledá nejlepší jedinec, který bude automaticky vložen do následující populace, a nová populace nahradí populaci starou. Tento postup se cyklicky opakuje, dokud není splněna ukončující podmínka, kterou může být například maximální počet populačních generací. Pseudokód 4.2 oproti tomu popisuje iterační evoluční model. Ten je založen na tom, že dochází iterativně k modifikaci stávající populace chromozomů. Po předem stanovený počet generací se příslušnou selekční metodou vyberou dva jedinci, kteří se s určitou pravděpodobností zkříží, čímž vzniknou dva noví potomci, kteří se případně ještě zmutují. Pokud nedošlo ke křížení, tak se vybraní jedinci alespoň zmutují, čímž vzniknou opět dva noví potomci. Potomci se následně ohodnotí, aby se zjistila jejich fitness. Poté se pro každého z potomků vyhledá v příslušných přihrádkách populace (dle počtu aktivních akcí, viz. výše) jedinec, který má stejnou nebo horší fitness. První takový jedinec je potom nahrazen daným potomkem. Pokud žádný horší jedinec nalezen není, tak se příslušný potomek do populace nedostane. Jelikož se v rámci algoritmu POEMS spouští evoluční algoritmus opakovaně, tak je potřeba, aby poměrně rychle konvergoval. Díky tomu, že jedinci reprezentují sekvence akcí, nikoliv samotné řešení určitého problému, tak velikost jedinců v populaci je mnohem menší než v případě přímé reprezentace řešení problému. Proto je možné nakonfigurovat evoluční algoritmus tak, aby konvergoval v několika málo generacích.

4.6

Aplikace POEMS a jeho rozšíření

V článku [22] byl použit algoritmus POEMS pro řešení problému obchodního cestujícího a pro řešení problému optimalizace binárních řetězců (binary string optimisation problem), a dosažené výsledky byly porovnány s jinými optimalizačními algoritmy pro tyto problémy. Provedené experimenty ukazují, že algoritmus POEMS dosahuje srovnatelných či lepších výsledků, než porovnávané algoritmy. Článek [21] popisuje aplikaci algoritmu POEMS na

22

Algorithm 4.2 Iterační evoluční model algoritmu POEMS 1: generateP opulation() 2: evaluateP opulation() 3: for i = 1 → N umberOf Generations do 4: {P arent1, P arent2} ← select(P opulation) 5: if rand() < Pcross then 6: {Child1, Child2} ← doCrossover(P arent1, P arent2) 7: if rand() < Pmutation then 8: Child1 ← doM utate(Child1) 9: end if 10: if rand() < Pmutation then 11: Child2 ← doM utate(Child2) 12: end if 13: else 14: Child1 ← doM utate(P arent1) 15: Child2 ← doM utate(P arent2) 16: end if 17: evaluate(Child1) 18: evaluate(Child2) 19: Replacement1 ← f indReplacement(P opulation, Child1) 20: P opulation[Replacement1] ← Child1 21: Replacement2 ← f indReplacement(P opulation, Child2) 22: P opulation[Replacement2] ← Child2 23: end for 24: BestSequence ← f indBest(P opulation) 25: return BestSequence

KAPITOLA 4. POEMS

4.6. APLIKACE POEMS A JEHO ROZŠÍŘENÍ

23

problém optimalizace návrhu řadících sítí (problem of optimal sorting network design). POEMS zde byl srovnáván s (µ + λ) a (1 + λ) evolučními strategiemi. Pro testování byly použity instance řadících sítí s 10-ti, 12-ti, 14-ti a 16-ti vstupy. Provedené experimenty ukázaly, že algoritmus POEMS překonává obě uvedené evoluční strategie. Navíc, pro některé z testovacích instancí, byl schopen nalézt optimální sítě vzhledem k počtu použitých komparátorů. Rozšíření algoritmu POEMS o možnost vícekriteriální optimalizace je popsáno v článku [23]. Algoritmus pojmenovaný mPOEMS je zde experimentálně aplikován na vícekriteriální 0/1 problém batohu. I zde se potvrdilo, že navržený algoritmus překonává ostatní srovnávané algoritmy v dané práci.

24

KAPITOLA 4. POEMS

Kapitola 5

HyperPOEMS HyperPOEMS, hyperheuristický algoritmus navržený a implementovaný v této práci, vychází z algoritmů POEMS (kapitola 4) a HHC-VRP (kapitola 3.3). Algoritmus POEMS je zde použit jako mechanismus pro vývoj sekvencí zlepšujících akcí, které modifikují stávající řešení. S algoritmem HHV-VRP sdílí HyperPOEMS podobnou strukturu reprezentace řešení, ale je více sofistikovanější při výběru a aplikaci zlepšujících akcí. V této kapitole je popsán návrh tohoto algoritmu pro řešení CVRP, a to včetně jednotlivých implementačních detailů.

5.1

Definice HyperPOEMS

HyperPOEMS je konstrukčně-perturbační hyperheuristikou, která je založena na iterativním zlepšování počátečního řešení, tzv. prototypu. Prototyp však nereprezentuje přímo řešení daného kombinatorického problému, ale je tvořen sekvencí tzv. jednotek, které řešení problému sekvenčně tvoří a zároveň ho zlepšují. Pro tento počáteční prototyp se následně iterativně spouští evoluční algoritmus, který po určitý počet generací vyvíjí sekvence akcí, které ho modifikují. Po skončení běhu jedné iterace EA se v populaci sekvencí akcí nalezne z pohledu fitness funkce nejlepší jedinec. Tento jedinec (tato sekvence akcí) se poté aplikuje na stávající prototyp, čímž vznikne tzv. kandidát. Tento kandidát se stejně jako v případě klasického POEMS porovná s aktuálním prototypem, a pokud je alespoň stejně dobrý jako aktuální prototyp, tak ho nahradí. Princip algoritmu HyperPOEMS popisuje pseudokód 5.1. Jak je vidět, tak se tento algoritmus příliš neliší od klasického algoritmu POEMS, viz. 4.1. Jediným rozdílem je zde to, že u HyperPOEMS může být specifikována doba běhu algoritmu. To znamená, že pokud daný počet iterací doběhne před časovým limitem, tak se určí nová hodnota seedu pro generátor náhodných čísel a vygeneruje se nový prototyp, který se opět iterativně zlepšuje. Výstupem algoritmu je pak nejlepší z prototypů. Platí to však i naopak. Pokud časový limit vyprší během procesu iterativního zlepšování prototypu, tak se již do další iterace nevstupuje.

25

26

KAPITOLA 5. HYPERPOEMS

Algorithm 5.1 Algoritmus HyperPOEMS 1: setSeed(Seed) 2: while T ime ≤ T IM E_LIM IT do 3: i←1 4: P rototype ← generate(N umOf P rototypes, N umOf U nits, ConstructT ype) 5: while i ≤ N umOf Iterations & T ime ≤ T IM E_LIM IT do 6: BestSequence ← run_EA(P rototype) 7: Candidate ← apply(P rototype, BestSequence) 8: if F irstN otW orse(Candidate, P rototype) then 9: P rototype ← Candidate 10: end if 11: i←i+1 12: end while 13: if F irstN otW orse(P rototype, BestP rototype) then 14: BestP rototype ← P rototype 15: end if 16: actualizeSeed() 17: end while 18: return BestP rototype

5.2 5.2.1

HyperPOEMS reprezentace POEMS prototyp

V klasické implementaci algoritmu POEMS reprezentuje prototyp řešení daného problému. To znamená, že pro různé kombinatorické problémy bude mít prototyp rozdílné podoby. V případě HyperPOEMS je však prototyp reprezentován jako sekvence jednotek, které teprve tvoří samotné řešení. Řešení je tvořeno postupnou aplikací jednotlivých jednotek ve směru zleva doprava, přičemž počet jednotek v prototypu není nikterak omezen. Struktura HyperPOEMS jednotky je zobrazena na obrázku 5.1. Každá jednotka má přiřazen jedinečný identifikátor ID, který ji označuje. Tyto identifikátory jsou používány při aplikacích sekvencí akcí na prototyp. Pokud by jednotky byly identifikovány dle jejich pozice v prototypu, tak by mohly být sekvence akcí chybně aplikovány. Pokud by jedna z akcí sekvence například vkládala novou jednotku na pozici i = 3 a následující akce měla změnit například konstrukční heuristiku u jednotky na pozici i = 4, tak po vložení oné nové jednotky by se na pozici i = 4 nacházela jiná jednotka, než příslušná změnová akce předpokládala. Zpět však ke struktuře jednotek. Atribut O označuje použitou řadící heuristiku. Řadící heuristika seřadí doposud nezpracovaná lokace dle příslušného řadícího kritéria a navrátí n prvních lokací, kde n je dalším atributem jednotky. Tyto lokace se poté předloží příslušné konstrukční heuristice C, která je buď vloží do některé ze stávajících cest řešení, nebo pro ně vytvoří cesty nové. Oproti algoritmu HHC-VRP je možné, aby jednotka nevkládala do řešení žádné nové lokace, tj. n = 0. Účelem těchto jednotek, které se označují jako čistě zlepšující jednotky, je pouze zlepšit dosavadního řešení. Jednotky, které vkládají do řešení nové lokace, se označují jako konstrukční jednotky. Atribut RI označuje zlepšující heuristiku, která zlepšuje nezávisle jednotlivé cesty dopo-

5.2. HYPERPOEMS REPREZENTACE

27

Obrázek 5.1: Struktura HyperPOEMS jednotek

sud vytvořené konstrukčními heuristikami. Příslušná heuristika se tedy aplikuje na všechny cesty, které byly touto jednotkou, a všemi jednotkami předchozími, vytvořeny. Atribut M RI označuje zlepšující heuristiku, která zlepšuje dosavadní řešení na úrovni dvojic cest. Tato heuristika se opět aplikuje na všechny doposud vytvořené cesty. Posledním atributem každé jednotky je atribut f itness. Ten určuje fitness doposud vytvořeného řešení (v případě CVRP to je délka doposud vytvořených cest) po aplikaci dané jednotky. Tento atribut slouží k tomu, aby bylo možné zjistit, zda daná jednotka nějakým způsobem ovlivňuje řešení. Pokud by se v prototypu nacházela jednotka, která nevkládá do řešení žádnou lokaci a zároveň její zlepšující heuristiky RI a M RI nezlepšují řešení (třeba i částečné), tak se z prototypu odstraní. Fitness poslední jednotky v prototypu určuje fitness celého prototypu. Algoritmus HyperPOEMS používá následující low-level heuristiky: • Řadící heuristiky: řazení zákaznických lokací dle klesající/rostoucí vzdálenosti od depa, klesajícího/rostoucího požadavku jednotlivých zákaznických lokací, dle radiálního úhlu od spojnice depo-nejvzdálenější zákaznická lokace. • Konstrukční heuristiky: Clark and Wright algoritmus, Mole and Jameson algoritmus, Kilby algoritmus, Sweep algoritmus. • Zlepšující heuristiky pro jednotlivé cesty: 2-opt, 3-opt, Or-opt, Node Insertion heuristika. • Zlepšující heuristiky pro dvojice cest: String Relocation, String Cross, String Exchange heuristiky (souhrně označované jako Van Breedam moves). Tyto heuristiky byly vybrány vzhledem k jejich relativně jednoduché implementaci a krátké době běhu. Jednotlivé algoritmy byly implementovány ve standardní podobě. Algoritmus Clark and Wright byl implementován v paralelní verzi, viz. 2.4.1. Požadovaným parametrům algoritmu Mole and Jameson byly nastaveny hodnoty λ = 1 a µ = 1, viz. 2.4.2. U heuristik String Relocation a String Exchange je možné specifikovat, zda se má pro danou

28


dvojici cest provézt první nalezené zlepšení či zlepšení nejlepší. Způsob zlepšení je při každé inicializaci daných heuristik určen náhodně, a to se stejnou pravděpodobností. I když by se mohlo zdát, že výše popsaná struktura jednotek je silně specifická pro problém CVRP a nedovoluje je použít pro řešení jiných tříd problémů, tak opak je pravdou. Jednotlivé části výše popsaných jednotek jsou specifické pro řešení CVRP, ale to je dáno pouze použitými heuristikami. Na jednotky prototypu je dobré nahlížet jako na objekty, které dle nějakého algoritmu iterativně vytvoří částečné/kompletní řešení nějakého problému a zároveň ho zlepšují, přičemž je možné specifikovat dvě zlepšující metody.

5.2.2

Vygenerování počátečního prototypu

Způsob, jakým je vytvářen počáteční prototyp, je popsán v pseudokódu 5.2. Metoda vygeneruje N umOf P rototypes výchozích prototypů a navrátí ten, který má nejlepší fitness. Parametr N umOf U nits určuje výchozí počet jednotek, které bude prototyp obsahovat. Poslední vstupní parametr této metody (parametr ConstructT ype) určuje způsob, jakým bude určen počet vkládaných lokací pro jednotlivé jednotky (atribut n na obrázku 5.1). Implementovány jsou dva možné způsoby. Prvním z nich je rovnoměrná distribuce počtu lokací. Jak název napovídá, tak celkový počet lokací je rovnoměrně rozdělen do všech jednotek. Druhá z možností by mohla být pojmenována jako náhodně-vychýlené rozdělení počtu lokací. Zde se postupuje následujícím způsobem. První jednotce je přiřazen náhodný počet n1 lokací z intervalu h1, CreateM axRate · N umOf Locationsi, kde N umOf Locations je celkový počet zákaznických lokací pro danou instanci CVRP a CreateM axRate je konfiguračním parametrem algoritmu HyperPOEMS. Druhé jednotce je následně přiřazen náhodný počet n2 lokací z intervalu h1, CreateM axRate · (N umOf Locations − n1 )i, pro třetí jednotku je počet lokací vybrán z h1, CreateM axRate · (N umOf Locations − n1 − n2 )i atd. Pokud by již byl celkový počet lokací rozdělen do předchozích jednotek, tak zbývající jednotky nebudou vkládat žádné lokace, tj. budou čistě zlepšujícími jednotkami. Co se týče použitých low-level heuristik, tak ty jsou vybrány pro jednotlivé jednotky počátečního prototypu zcela náhodně. Algorithm 5.2 Metoda generatePrototype pro vygenerování počátečního prototypu 1: BestP rototype ← createN ewP rototype(N umOf U nits, ConstructT ype) 2: for i = 1 → N umOf P rototypes − 1 do 3: P rototype ← createN ewP rototype(N umOf U nits, ConstructT ype) 4: if isBetter(P rototype, BestP rototype) then 5: BestP rototype ← P rototype 6: end if 7: end forreturn BestP rototype I když se počáteční prototyp generuje náhodně, tak nelze řešení produkované tímto prototypem srovnávat s náhodně vygenerovaným řešením daného problému. Zde se náhodně určí heuristiky, které vytváří již poměrně dobré řešení.

5.2.3

Sekvence POEMS akcí

Jak již bylo uvedeno, tak pro různé kombinatorické problémy má POEMS prototyp zpravidla jinou podobu. To však znamená, že pro různé problémy musí být použity různé množiny


29

akcí. Jiné akce jsou použity pro řešení problému obchodního cestujícího a jiné akce se použijí například pro řešení problému batohu. U HyperPOEMS je však možné použít pro různé problémy stejnou množinu akcí, protože akce nemění řešení daného problému přímo. Místo toho modifikují prototyp, který teprve vytváří konkrétní řešení. Algoritmus HyperPOEMS používá následující sadu akcí: • InsertUnit: Tato akce vytvoří novou jednotku a vloží ji do prototypu. Parametrem této akce je ona nová jednotka Unew a pozice v prototypu position, kam se má jednotka vložit. Do prototypu se mohou vkládat jak konstrukční jednotky, tak i jednotky čistě zlepšující, přičemž konstrukční jednotky se mohou vložit do prototypu na libovolnou pozici, ale čistě zlepšující jednotky se nemohou vložit na začátek prototypu (zlepšující heuristiky by nebylo na co aplikovat). Konfigurační parametr pImproveOnlyU nits určuje pravděpodobnost, se kterou se do prototypu vloží čistě zlepšující jednotka. V ostatních případech se vkládají konstrukční jednotky. Pokud se vkládá konstrukční jednotka, tak počet lokací, které jednotka přidává do řešení, je náhodně vybrán z intervalu h1, N umOf Locations · P artOf LocationsT oInserti, kde N umOf Locations je celkový počet zákaznických lokací a P artOf LocationsT oInsert je konfiguračním parametrem HyperPOEMS, který určuje, jaký maximální podíl zákaznických lokací může být přiřazen nové jednotce. Jednotlivé heuristiky pro novou jednotku jsou vybírány náhodně. Oproti generování výchozího prototypu se však používá při výběru jednotlivých heuristik tzv. Tabu seznam1 . Tento seznam slouží k tomu, aby byly jednotlivé heuristiky vybírány rovnoměrně. Vždy, když se při vytváření instance akce vybere nějaká heuristika, tak se odstraní z příslušné množiny dostupných heuristik. Jakmile je množina dostupných heuristik dané kategorie prázdná, tak se opět zaplní všemi příslušnými heuristikami. • DeleteUnit: Jak již název napovídá, tak tato akce slouží ke smazání některé ze stávajících jednotek prototypu. Parametrem této akce je identifikátor jednotky, která se má z prototypu odstranit. Při vytváření instance této akce se náhodně vybere jednotka a její ID se uloží jako parametr akce. • CopyUnit: Tato akce slouží ke kopírování stávajících jednotek prototypu. Opět se náhodně vybere jednotka ze stávajícího prototypu a zkopíruje se. U kopie se nastaví počet vkládaných zákaznických lokací na nulu, tj. atribut n = 0. Tato kopie je prvním z parametrů dané akce. Druhým parametrem je pozice v prototypu, kam se má kopie vložit. Jelikož kopie nevkládá žádné lokace do řešení (je čistě zlepšující jednotkou), tak opět nemůže být vložena na začátek prototypu. • RealocUnit: Akce RealocUnit slouží k přesouvání jednotek v rámci prototypu. Náhodně se vybere jednotka, která se posune na jinou pozici v prototypu. Ostatní jednotky zachovávají svoje pořadí. Parametrem akce je ID přesouvané jednotky a nová pozice, kam se má jednotka umístit. Pokud je prototyp tvořen pouze jednou jednotkou, tak jsou oba parametry nastaveny na -1 a při aplikaci této akce na prototyp se nic neprovede. 1 Tento Tabu seznam se používá i u ostatních akcí, které nějakým způsobem modifikují použité lowlevel heuristiky. Jedná se o akce ChangeOrderHeuristic, ChangeConstructHeuristic, ChangeRouteImprovementHeuristic a ChangeMultiRouteImprovementHeuristic

30


• SwitchUnits: Tato akce slouží, stejně jako akce předchozí, ke změně pořadí jednotek v prototypu. Náhodně se vyberou dvě různé jednotky, které se v prototypu prohodí. Identifikátory vybraných jednotek jsou parametry akce. Pokud je prototyp při inicializaci této akce tvořen pouze jednou jednotkou, tak jsou oba parametry akce nastaveny na -1, stejně jako u předešlé akce. • ChangeNumberOfLocs: Tato akce mění počet vkládaných lokací u jedné ze stávajících jednotek prototypu. Náhodně se vybere jednotka a určí se jí nový počet zákaznických lokací, které má integrovat do řešení. Počet lokací je náhodně vybrán z intervalu h1, N umOf Locations · P artOf LocationsT oInserti, stejně jako při určování počtu lokací pro novou jednotku vytvořenou akcí InsertUnit. • ChangeOrderHeuristic: Tato akce mění u náhodně vybrané jednotky prototypu řadící heuristiku. Parametrem akce je ID vybrané jednotky a instance nové řadící heuristiky. • ChangeConstructHeuristic: Účelem této akce je změnit u náhodně vybrané jednotky konstrukční heuristiku. ID vybrané jednotky a instance nové konstrukční heuristiky jsou parametry této akce. • ChangeRouteImprovementHeuristic: Tato akce slouží ke změně zlepšující heuristiky, která pracuje na úrovni jednotlivých cest. Opět se náhodně vybere jedna z jednotek prototypu, u které se tato heuristika změní. • ChangeMultiRouteImprovementHeuristic: Tato akce, oproti akci předchozí, mění u jedné náhodně vybrané jednotky zlepšující heuristiku, které zlepšuje řešení na úrovni dvojic cest.

5.2.4

Aplikace sekvence akcí a jejich ohodnocení

Sekvence akcí používané algoritmem HyperPOEMS mají stejnou podobu jako u klasického POEMS algoritmu, viz. kapitola 4.2. Tyto sekvence jsou vyvíjeny evolučním algoritmem po určitý počet generací s cílem vyšlechtit sekvenci, které nejvíce zlepšuje aktuální prototyp. Sekvence akcí jsou ohodnocovány dle toho, jak modifikují aktuální prototyp. Ohodnocovací funkce evolučního algoritmu tedy pracuje na tom principu, že aplikuje příslušnou sekvenci na aktuální prototyp, čímž dojde k jeho modifikaci. Změněný prototyp se vyhodnotí, a tak vznikne řešení daného problému (v kontextu CVRP se vytvoří množina cest). Kvalita vytvořeného řešení (u CVRP suma délek jednotlivých cest) poté určuje fitness použité sekvence akcí. Pokud však použitá sekvence akcí prototyp nemění, např. aplikované akce se navzájem vyruší, tak je tato sekvence penalizována nastavením nejhorší možné fitness. Modifikace prototypu zde nejsou trvalé. Slouží pouze pro zjištění fitness dané sekvence akcí. Až po skončení běhu evolučního algoritmu se vezme nejlepší sekvence akcí, která se aplikuje na prototyp, čímž vznikne tzv. kandidát. Pokud je kandidát z pohledu fitness funkce alespoň stejně dobrý jako stávající prototyp, tak ho nahradí. Způsob aplikace a ohodnocení sekvence akcí je zobrazen na obrázku 5.2. Vzorová sekvence obsahuje 3 aktivní akce a jednu NOP akci. První akce modifikuje stávající prototyp přidáním nové jednotky. Druhá akce mění u jednotky s ID = 3 konstrukční heuristiku. Třetí aktivní


Obrázek 5.2: Aplikace sekvence akcí na prototyp

31

32


akce (poslední akce v sekvenci) mění u jednotky s ID = 2 počet lokací z 0 na 2. Příslušná jednotka se tím pádem stává jednotkou konstrukční. Při pohledu na modifikovaný prototyp si lze všimnout, že u posledních dvou jednotek se změnil počet lokací, aniž by jejich počet byl změněn příslušnou akcí. To je z toho důvodu, že se do prototypu vložila nová jednotka, která vkládá do řešení jednu lokaci, a u druhé jednotky se změnil počet vkládaných lokací z 0 na 2. Jelikož suma počtu vkládaných lokací přes všechny jednotky musí být rovna počtu zákaznických lokací dané instance CVRP, tak je potřeba odebrat 3 lokace. Tyto lokace se odebírají z jednotek od konce prototypu. V opačném případě, kdy je potřeba zvýšit počet lokací v prototypu, se příslušný počet přičte k poslední jednotce prototypu.

5.3

Evoluční algoritmus

Evoluční model používaný algoritmem HyperPOEMS odpovídá iteračně evolučnímu modelu dle pseudokódu 4.2. Náhodně vygenerovaná populace sekvencí akcí je po určitý počet generací vyvíjena, přičemž v každé generaci se vyberou dva jedinci, kteří se s určitou pravděpodobností zkříží a zmutují. Tito nově vzniklí potomci nahradí v populaci případné jedince s horší fitness. Stejně jako u klasického algoritmu POEMS, tak i zde je populace rozdělena do jednotlivých přihrádek. Potomci mohou být vloženi pouze do přihrádek, kam spadají dle počtu jejich aktivních akcí. Jako aktivní akce se zde berou všechny akce, které nejsou NOP. Tedy i ty akce, které sice nejsou NOP, ale nemohou být provedeny, např. akce RealocUnit s parametry -1.

5.3.1

Selekční strategie

Jako selekční strategii používá algoritmus HyperPOEMS turnajovou selekci. Princip turnajové selekce zde spočívá v tom, že se náhodně vybere jedna z přihrádek v populaci a z ní se vybere N jedinců, kde N značí počet kol turnaje. Z těchto jedinců se následně vybere ten, který má nejvyšší fitness.

5.3.2

Křížení

Použitý operátor křížení pracuje na stejném principu, jako operátor popsaný v kapitole 4.4. Noví potomci jsou vytvořeni jako náhodná kombinace genů rodičů.

5.3.3

Mutace

Operátor mutace algoritmu HyperPOEMS je implementován tak, že se sekvence akcí, která má být zmutována, iterativně prochází a každá akce se s určitou pravděpodobností zmutuje. Mutace akce pracuje tak, že se s 50-ti procentní pravděpodobností změní typ akce, tj. pokud akce je NOP, tak se změní na aktivní, pokud je aktivní, tak se změní na NOP akci. V ostatních případech se dále s pravděpodobností 75 % změní typ použité aktivní akce a akce se označí jako aktivní. Ve zbývajících případech se změní typ aktivní akce, ale akce se označí jako neaktivní (NOP akce).

5.4. IMPLEMENTACE

5.4

33

Implementace

Algoritmus HyperPOEMS byl implementován v programovacím jazyce Java. Při návrhu a implementaci tohoto algoritmu byl kladen velký důraz na možná budoucí rozšíření tohoto algoritmu. Na obrázku 5.3 je zobrazen návrhový diagram tříd algoritmu HyperPOEMS. Z důvodu celkové přehlednosti jsou zde zobrazeny pouze třídy, které z hlediska popisu algoritmu podstatné. Třídy, které slouží k načítání vstupních dat, ukládání výsledků, další pomocné třídy, zde zobrazeny nejsou.

5.4.1 5.4.1.1

Implementované třídy a rozhraní HyperPOEMS Rozhraní ConstructionHeuristic

Toto rozhraní implementují jednotlivé konstrukční heuristiky. Rozhraní především deklaruje signaturu metody, která vkládá do řešení nové lokace. 5.4.1.2

Rozhraní OrderHeuristic

Rozhraní OrderHeuristic implementují všechny řadící heuristiky. Zde je deklarována metoda, kterou jednotlivé řadící heuristiky implementují a která zajišťuje řazení zákaznických lokací. 5.4.1.3

Rozhraní RouteImprovementHeuristic

Toto rozhraní deklaruje především signaturu metody, kterou implementují jednotlivé zlepšující heuristiky, které zlepšují řešení na úrovni jednotlivých cest. 5.4.1.4

Rozhraní MultiRouteImprovementHeuristic

Podobně jako rozhraní MultiRouteImprovementHeuristic, tak i toto rozhraní deklaruje signaturu metody, kterou implementují jednotlivé zlepšující heuristiky, které pracují pro dvojice cest. 5.4.1.5

Třída PrototypeCreator

Tato třída implementuje metody pro generování počátečního prototypu, pro generování nových jednotek, které se přikládají k příslušným POEMS akcím jako parametry. Jsou zde implementovány metody pro určování heuristik, které se použijí v jednotlivých jednotkách atd. Souhrnně by se dalo říci, že jsou zde implementovány všechny metody pro inicializaci prototypů a jednotek. 5.4.1.6

Třída Prototype

Jak název napovídá, tak tato třída implementuje prototyp algoritmu HyperPOEMS. Tato třída poskytuje metody pro vkládání nových jednotek do prototypu, jejich přesouvání v rámci prototypu, mazání atd. Je zde také implementována metoda, která vytváří pro daný prototyp řešení konkrétního problému tím, že spouští sekvenčně jednotlivé jednotky.

34


Obrázek 5.3: Diagram tříd HyperPOEMS

5.4. IMPLEMENTACE

5.4.1.7

35

Třída Unit

Třída Unit reprezentuje jednotku prototypu. V instancích této třídy jsou zapouzdřeny jednotlivé heuristiky dané jednotky. 5.4.1.8

Třída CVRPManager

Jedna ze stěžejních tříd implementace HyperPOEMS. Tato třída volá metody třídy PrototypeCreator pro vytvoření počátečního prototypu, který potom během celé doby běhu algoritmu spravuje. 5.4.1.9

Třída CVRPSolution

Tato třída dědí od abstraktní třídy Solution. V této třídě je především implementována metoda pro aplikaci sekvence akcí na prototyp. 5.4.1.10

Třída CVRPAction

Tato třída dědí od abstraktní třídy Action. CVRPAction je třída specifická pro problém CVRP. Pro každý problém, který má algoritmus HyperPOEMS řešit, musí být vytvořena příslušná “action” třída, která bude potomkem třídy Action. V této třídě jsou také specifikovány použité akce pro HyperPOEMS, které jsou použitelné pro libovolné kombinatorické problémy. 5.4.1.11

Třída ActionSequence

Tato třída reprezentuje sekvence akcí. Zde jsou implementována metody pro zjišťování fitness jednotlivých sekvencí, pro jejich křížení a mutaci apod. 5.4.1.12

Třída ASPopulation

Tato třída reprezentuje populaci sekvencí akcí, přičemž implementuje metody pro generování počáteční populace, pro ohodnocení celé populace. Zde je implementována selekční metoda a především pak samotný evoluční model. 5.4.1.13

Třída POEMS

Třída POEMS slouží k načítání konfigurace a ke spouštění evolučního algoritmu pro vývoj sekvencí akcí. 5.4.1.14

Třída POEMSAlgorithm

Zde je implementován algoritmus dle pseudokódu 5.1, který spuští samotný algoritmus HyperPOEMS.

36


Kapitola 6

Experimenty V této kapitole jsou popsány provedené experimenty, kde je algoritmus HyperPOEMS aplikován na obecně používané datové sady. Výsledky, kterých tento algoritmus dosáhl, jsou následně porovnány s algoritmem HHC-VRP, jakožto zástupcem hyperheuristických metod, a dalšími stávajícími algoritmy odkazovanými článkem [18], které tvoří tzv. state-of-the-art pro CVRP.

6.1

Testovací data

Pro otestování navrženého algoritmu a jeho srovnání se stávajícími přístupy byly použity všeobecně uznávané datové sady Christofides [8], Taillard [31] a Fisher [17]. Datovou sadu Christofides tvoří 7 instancí CVRP, přičemž nejmenší instance obsahuje 50 zákaznických lokací a největší 199. Zákaznické lokace jsou v jednotlivých instancích buď rovnoměrně distribuovány, nebo tvoří shluky. Z datové sady Taillard je použito 12 instancí daného problému, které obsahují 75 až 150 zákaznických lokací. Datová sada Fisher je tvořena dvěma instancemi CVRP. První z nich obsahuje 71 zákaznických lokací, druhá 134 lokací. V obou instancích se většina zákaznických lokací nachází ve shlucích v okolí depa a se vzrůstající vzdáleností od depa se jejich hustota snižuje [19]. Ve všech případech se pro určování vzdáleností mezi lokacemi používá Euklidovská metrika.

6.2

Testovací konfigurace

V tabulce 6.1 jsou zobrazeny jednotlivé konfigurační údaje pro 3 provedené experimenty. V horní části tabulky jsou uvedeny konfigurační parametry pro POEMS implementovaný v rámci algoritmu HyperPOEMS. Spodní část tabulky obsahuje konfigurační parametry samotného HyperPOEMS, přičemž pro všechny 3 experimenty byla použita stejná konfigurace. Počet vygenerovaných počátečních prototypů, ze kterých se vybírá ten nejlepší, je 10. Počáteční prototyp je tvořen čtyřmi jednotkami, které si rovnoměrně rozdělí počet zákaznických lokací. Případné nové jednotky vkládané do prototypu budou ze 40-ti % čistě zlepšující. Pokud se bude přidávat do prototypu konstrukční jednotka, tak jí bude přiřazeno maximálně 20 % ze zákaznických lokací.

37

38

KAPITOLA 6. EXPERIMENTY Testovací konfigurace POEMS Experiment 1 Experiment 2 maxGenes 10 5 sizeDrawer 10 10 nGenerations 150 100 pActive 85 85 pCrossover 70 70 pMutation 30 30 pBitflip 25 25 nTournaments 2 2 nIterations 25 25 fitnessAssignment min min HyperPOEMS Experiment 1 Experiment 2 nInitPrototypes 10 10 nInitUnits 4 4 pImproveOnlyUnits 40 40 maxTimeLimit [minutes] 10 10 partOfLocationsToInsert 20 20 prototypeConstructType uniform uniform

Experiment 3 10 10 150 85 70 30 25 2 25 min Experiment 3 10 4 40 10 20 uniform

Tabulka 6.1: Testovací konfigurace Konfigurace POEMS se již v rámci jednotlivých experimentů liší. U prvního experimentu (Experiment 1 ) je nastavena délka sekvencí akcí na 10 a sekvence se v každé iteraci vyvíjí po 150 generací. V případě druhého experimentu (Experiment 2 ) je délka sekvencí akcí 5 a sekvence jsou POEMS algoritmem vyvíjeny po 100 generací. Ostatní konfigurační údaje jsou u těchto dvou experimentů stejné. Konfigurační parametry u třetího experimentu (Experiment 3 ) jsou stejné jako u experimentu prvního. V rámci třetího experimentu se však mírně liší implementace algoritmu HyperPOEMS. První modifikací je to, že zde není použita akce pro kopírování jednotek (akce CopyUnit). Druhou změnou je zamezení vkládání a přesouvání jednotek na konec prototypu. Tyto změny byly provedeny s cílem odzkoušet, jak se s těmito omezeními algoritmus HypoerPOEMS vyrovná. Jednotlivé experimenty byly spuštěny pro všech 21 instancí výše popsaných datových sad. Pro každou instanci byl algoritmus HyperPOEMS spuštěn 20 krát s různými seedy1 . Doba běhu algoritmu pro jednu instanci CVRP a jednu hodnotu seedu byla nastavena na 10 minut.

6.3

Výsledky pro jednotlivé testovací konfigurace

V tabulkách 6.2, 6.3 a 6.4 jsou zobrazeny výsledky obdržené algoritmem HyperPOEMS pro jednotlivé testovací konfigurace. V prvním sloupci všech tabulek je název příslušné instance CVRP. Následující čtyři sloupce obsahují postupně aritmetický průměr, medián, minimální 1

Použité hodnoty seedů byly: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 a 71.

6.3. VÝSLEDKY PRO JEDNOTLIVÉ TESTOVACÍ KONFIGURACE

Instance c50 c75 c100 c100b c120 c150 c199 f71 f134 tai75a tai75b tai75c tai75d tai100a tai100b tai100c tai100d tai150a tai150b tai150c tai150d

Avg 524,62 847,11 835,82 819,63 1044,33 1065,73 1359,72 242,72 11654,24 1621,16 1344,72 1292,46 1365,46 2077,61 1950,15 1413,88 1601,93 3157,38 2779,41 2395,44 2719,96

Absolutní Median 524,61 847,51 835,51 819,56 1044,65 1065,17 1360,19 241,97 11654,21 1620,47 1344,63 1291,01 1365,42 2078,31 1951,12 1414,03 1601,29 3148,34 2774,25 2395,02 2721,83

hodnota Min 524,61 836,37 831,29 519,56 1042,12 1047,80 1338,93 241,97 11629,57 1618,36 1344,62 1291,01 1365,42 2063,63 1940,61 1406,20 1591,04 3120,41 2754,39 2369,11 2676,64

Max 524,81 852,79 840,64 820,92 1046,67 1084,37 1384,51 245,38 11705,19 1626,71 1345,30 1300,67 1365,71 2093,51 1958,19 1421,63 1611,66 3245,14 2839,62 2442,17 2767,35

Avg 0,00 1,42 1,17 0,01 0,21 3,63 5,30 2,41 0,29 0,17 0,01 0,11 0,00 1,78 0,53 0,55 1,31 3,34 4,63 2,29 2,82

∆ (%) Median Min 0,00 0,00 1,47 0,13 1,13 0,62 0,00 0,00 0,24 0,00 3,57 1,88 5,34 3,69 2,10 2,10 0,29 0,08 0,13 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,81 1,09 0,58 0,04 0,56 0,00 1,27 0,62 3,05 2,13 4,43 3,69 2,27 1,16 2,89 1,18

39

Max 0,04 2,10 1,76 0,17 0,44 5,44 7,22 3,54 0,73 0,52 0,05 0,75 0,02 2,56 0,94 1,10 1,92 6,22 6,84 4,28 4,61

Best 524.61 835,26 826,14 819,56 1042,11 1028,42 1291,29 237 11620 1618,36 1344,62 1291,01 1365,42 2041,34 1939,90 1406,20 1581,25 3055,23 2656,47 2341,84 2645,39

Tabulka 6.2: Výsledky pro Experiment 1 a maximální hodnotu dosaženou pro danou instanci. Následující čtyři sloupce obsahují opět aritmetický průměr, medián, minimální a maximální hodnotu, nyní však vyjádřenou jako procentuální odchylku od doposud nejlepšího známého řešení pro danou instanci. Tuto odchylku lze vyjádřit jako F ound − Best ∆ (%) = · 100 (6.1) Best kde F ound je ohodnocení řešení získaného algoritmem HyperPOEMS a Best je doposud nejlepší známé ohodnocení dané instance CVRP. Hodnota Best se pro jednotlivé instance nachází v posledním sloupci daných tabulek.

40


KAPITOLA 6. EXPERIMENTY

Avg 524,64 847,38 835,82 819,56 1044,81 1059,92 1355,43 242,14 11645,89 1620,83 1344,81 1292,46 1365,49 2080,95 1948,68 1415,62 1603,43 3133,30 2785,05 2389,03 2711,41


hodnota Min 524,61 838,16 831,70 519,56 1042,12 1045,46 1339,76 241,97 11629,57 1618,36 1344,62 1291,01 1365,42 2064,63 1940,61 1406,92 1596,25 3084,81 2745,05 2367,94 2681,42

Max 524,93 853,11 844,05 819,56 1051,66 1070,12 1369,26 244,92 11686,65 1624,78 1346,63 1300,67 1366,48 2102,66 1958,19 1424,23 1632,76 3224,45 2860,68 2412,12 2780,70

Avg 0,00 1,45 1,17 0,00 0,26 3,06 4,97 2,17 0,22 0,15 0,01 0,11 0,00 1,94 0,45 0,67 1,40 2,56 4,84 2,01 2,50

∆ (%) Median Min 0,00 0,00 1,61 0,35 1,06 0,67 0,00 0,00 0,24 0,00 3,19 1,66 4,92 3,75 2,10 2,10 0,18 0,08 0,13 0,00 0,00 0,00 0,00 0,00 0,00 0,00 1,82 1,14 0,44 0,04 0,70 0,05 1,29 0,95 2,47 0,97 4,34 3,33 1,96 1,11 2,15 1,36

Tabulka 6.3: Výsledky pro Experiment 2

Max 0,06 2,14 2,17 0,00 0,92 4,05 6,04 3,34 0,57 0,40 0,15 0,75 0,08 3,00 0,94 1,28 3,26 5,54 7,69 3,00 5,11

Best 524.61 835,26 826,14 819,56 1042,11 1028,42 1291,29 237 11620 1618,36 1344,62 1291,01 1365,42 2041,34 1939,90 1406,20 1581,25 3055,23 2656,47 2341,84 2645,39

6.3. VÝSLEDKY PRO JEDNOTLIVÉ TESTOVACÍ KONFIGURACE


Avg 524,70 849,02 838,49 819,56 1044,61 1060,06 1360,66 242,64 11667,46 1622,92 1345,14 1291,85 1365,53 2080,52 1953,32 1417,28 1604,24 3176,94 2785,38 2396,71 2718,86


hodnota Min 524,61 841,02 831,93 519,56 1042,80 1047,44 1345,61 241,97 11635,26 1621,64 1344,62 1291,01 1365,42 2071,31 1941,71 1406,26 1598,30 3124,20 2759,00 2379,32 2671,47

Max 524,93 855,96 846,73 819,56 1045,66 1081,75 1381,21 244,54 11745,56 1626,33 1349,47 1297,24 1366,48 2099,92 1965,75 1420,91 1617,43 3250,81 2843,71 2414,44 2750,69

Avg 0,02 1,65 1,50 0,00 0,24 3,08 5,37 2,38 0,41 0,28 0,04 0,06 0,01 1,92 0,69 0,79 1,45 3,98 4,85 2,34 2,78

∆ (%) Median Min 0,00 0,00 1,69 0,69 1,44 0,70 0,00 0,00 0,24 0,07 2,87 1,85 5,30 4,21 2,10 2,10 0,39 0,13 0,29 0,20 0,00 0,00 0,00 0,00 0,00 0,00 1,93 1,47 0,78 0,09 0,97 0,00 1,37 1,08 3,52 2,26 4,35 3,86 2,44 1,60 2,78 0,99

Tabulka 6.4: Výsledky pro Experiment 3

41

Max 0,06 2,48 2,49 0,00 0,34 5,19 6,96 3,18 1,08 0,49 0,36 0,48 0,08 2,87 1,33 1,05 2,29 6,40 7,05 3,10 3,98

Best 524.61 835,26 826,14 819,56 1042,11 1028,42 1291,29 237 11620 1618,36 1344,62 1291,01 1365,42 2041,34 1939,90 1406,20 1581,25 3055,23 2656,47 2341,84 2645,39

42

6.4


Zhodnocení výsledků

V tabulce 6.5 jsou zobrazeny výsledky dosažené algoritmem HyperPOEMS pro jednotlivé experimenty a výsledky, kterých na stejných testovacích datech dosáhl algoritmus HHC-VRP [18]. Algoritmus HHC-VRP byl pro každou instanci CVRP spuštěn 10 krát, doba jeho běhu byla stanovena také na 10 minut, během nichž došlo k 10-ti restartům. Hodnoty v tabulce opět odpovídají procentuální odchylce od nejlepších známých výsledků. Instance c50 c75 c100 c100b c120 c150 c199 f71 f134 tai75a tai75b tai75c tai75d tai100a tai100b tai100c tai100d tai150a tai150b tai150c tai150d Average

HHC-VRP Avg Min 0,00 0,00 1,46 0,62 0,82 0,42 0,00 0,00 0,27 0,19 3,84 2,50 5,93 5,07 2,23 2,10 1,00 0,27 0,29 0,05 0,13 0,05 0,11 0,00 0,29 0,00 2,01 1,51 0,86 0,09 0,89 0,32 1,38 1,14 4,03 2,16 5,69 4,92 2,56 1,86 2,54 1,99 1,73 1,20

Experiment 1 Avg Min 0,00 0,00 1,42 0,13 1,17 0,62 0,01 0,00 0,21 0,00 3,63 1,88 5,30 3,69 2,41 2,10 0,29 0,08 0,17 0,00 0,01 0,00 0,11 0,00 0,00 0,00 1,78 1,09 0,53 0,04 0,55 0,00 1,31 0,62 3,34 2,13 4,63 3,69 2,29 1,16 2,82 1,18 1,52 0,88



Tabulka 6.5: Srovnání výsledků provedených experimentů s výsledky HHC-VRP Vyhodnocení provedených experimentů nad algoritmem HyperPOEMS dokazuje, že nejlepších výsledků, zprůměrovaných přes všechny datové instance, dosahuje konfigurace pro Experiment 2. Na první pohled by mohlo být překvapivé, že nejlepších výsledků nedosahuje konfigurace pro Experiment 1, kde se používaly delší sekvence akcí a tyto sekvence byly vyvíjeny po větší počet generací. Bylo by logické předpokládat, že použití delších sekvencí akcí dokáže více modifikovat prototyp tak, aby prohledal větší část prostoru řešení, případně rychleji vyvázl z lokálního optima. Je však potřeba na to nahlížet i z druhé strany. Vyšší počet generací znamená vyšší počet ohodnocení sekvencí akcí, tedy vícekrát se sekvence aplikují na prototyp, aby se zjistilo, jakou kvalitu má následně vytvořené řešení. To je ale poměrně časově náročná operace. To znamená, že se během 10-ti minut nestihne provézt tolik iterací, jako v případě, kdy se sekvence vyvíjejí po nižší počet generací. S tím souvisí

6.4. ZHODNOCENÍ VÝSLEDKŮ

43

i to, že dojde k nižšímu počtu restartů algoritmu HyperPOEMS. Demonstrovat to může fakt, že pro problém c50 došlo během Experimentu 1 v průměru ke 3,1 restartům, kdežto pro Experiment 2 došlo v průměru k 7-mi restartům během jednoho spuštění algoritmu. Experiment 3 byl proveden s cílem zjistit, jaký vliv bude mít na výsledky odstranění akce pro kopírování jednotek (akce copyUnit) a zamezení vkládání lokací na konec prototypu. Dosažené výsledky dokazují, že i přes tyto limity je schopný algoritmus HyperPOEMS poskytovat relativně dobré výsledky. Dosažené výsledky jsou sice v průměru horší než u prvních dvou experimentů (oproti Experimentu 1 o 0,09 %, oproti Experimentu 2 o 0,18 %), ale oproti algoritmu HHC-VRP jsou o 0,12 % lepší. Z toho tedy vyplývá, že i první dva experimenty překonávají algoritmus HHC-VRP (Experiment 1 o 0,21 %, Experiment 2 o 0,3 %). Algoritmus HHC-VRP překonává nejlepší z testovaných konfigurací HyperPOEMS (Experiment 2 ) pouze na dvou datových instancích (instance c100 a tai100d). Instance c50 c75 c100 c100b c120 c150 c199 Average

USTA [11] 0,00 0,00 0,00 0,00 3,01 0,41 1,90 0,76

Berger [11] 0,00 0,00 0,15 0,00 0,10 0,75 2,54 0,51

GTS [11] 0,00 0,40 0,29 0,00 0,07 0,47 2,09 0,47

VLNS [11] 0,00 0,02 0,16 0,00 0,00 0,76 1,24 0,31

Prins [11] 0,00 0,00 0,00 0,00 0,00 0,31 0,69 0,14

HHC-VRP Avg Min 0,00 0,00 1,46 0,62 0,82 0,42 0,00 0,00 0,27 0,19 3,84 2,50 5,93 5,07 1,76 1,26

HyperPOEMS Avg Min 0,00 0,00 1,45 0,35 1,17 0,67 0,00 0,00 0,26 0,00 3,06 1,66 4,97 3,75 1,56 0,92

Tabulka 6.6: Christofides: Porovnání jednotlivých algoritmů s HyperPOEMS Tabulka 6.6 obsahuje výsledky dosažené stávajícími specializovanými algoritmy odkazovanými v článku [18] pro datovou sadu Christifides. Spolu s nimi jsou zde zobrazeny i výsledky pro algoritmus HHC-VRP a výsledky HyperPOEMS pro Experiment 2, jakožto nejlepší konfiguraci. Popis a konfiguraci algoritmů USTA, Berger, GTS, VLNS a Prins lze dohledat v článku [11]. Je nutné dodat, že výsledky těchto algoritmů, uvedené v tabulce 6.6, byly dosaženy pro dané konfigurace pro jedno spuštění. Výjimkou je algoritmus VLNS, pro který jsou zde uvedeny nejlepší výsledky obdržené během 5-ti spuštění tohoto algoritmu pro jednotlivé datové instance. Ve srovnání se specializovanými algoritmy nevychází HyperPOEMS na první pohled pro tuto datovou sadu příliš dobře, a to i přesto, že během 20-ti spuštění pro jednotlivé instance dosáhl v průměru nejlepších známých výsledků na dvou instancích, pro nejlepší běh dokonce na třech instancích. Lze si dále všimnout, že pro instanci c120 dosahuje nejlepší známé hodnoty a překonává zde tak state-of-the-art algoritmy USTA, Berger a GTS. Celkově vzato dosahuje na této datové sadě HyperPOEMS přijatelných výsledků. V tabulce 6.7 jsou obsaženy výsledky pro datovou sadu Fisher. Zde již dosahuje HyperPOEMS (Experiment 2 ) vynikajících výsledků. Dosažené nejlepší výsledky pro obě datové sady jsou stejně dobré, jako výsledky dosažené algoritmem AGES, což je metaheuristický algoritmus navržený speciálně pro řešení CVRP. Velmi dobré jsou i průměrné hodnoty, které překonávají algoritmus Ejection Chains, a to jak pro průměrné hodnoty, tak i pro nejlepší dosažené.

44


Instance f71 f134 Average

Ejection Chains [10] 2,30 1,32 1,81

Minimum K-trees [17] 2,10 0,14 1,12

AGES [27] 2,10 0,08 1,09

HHC-VRP Avg Min 2,23 2,10 1,00 0,27 1,61 1,18

HyperPOEMS Avg Min 2,17 2,10 0,22 0,08 1,20 1,09

Tabulka 6.7: Fisher: Porovnání jednotlivých algoritmů s HyperPOEMS Co se konfigurace jednotlivých state-of-the-art algoritmů týče, tak algoritmus AGES, stejně jako algoritmus Ejection Chains, byl spuštěn pouze jednou, a to pro nejlepší nalezenou konfiguraci. Výsledky pro datovou sadu Taillard jsou uvedeny v tabulce 6.8. Mezi zde uvedenými algoritmy jasně dominuje algoritmus AGES. Ovšem výsledky, kterých dosáhl algoritmus HyperPOEMS (opět druhá konfigurace) jsou opět slibné. Jak průměrné, tak i nejlepší výsledky dosažené algoritmem HyperPOEMS překonávají algoritmus Ejection Chains. Instance tai75a tai75b tai75c tai75d tai100a tai100b tai100c tai100d tai150a tai150b tai150c tai150d Average

Ejection Chains [10] 0,13 0,76 0,62 0,10 1,80 0,62 1,10 1,34 2,71 5,71 3,43 1,93 1,69

Rochat and Taillard [29] 0,32 0,04 0,09 0,00 0,51 2,90 0,96 0,67 0,69

AGES [27] 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 2,68 0,05 0,00 0,23

HHC-VRP Avg Min 0,29 0,05 0,13 0,05 0,11 0,00 0,29 0,00 2,01 1,51 0,86 0,09 0,89 0,32 1,38 1,14 4,03 2,16 5,69 4,92 2,56 1,86 2,54 1,99 1,73 1,17

HyperPOEMS Avg Min 0,15 0,00 0,01 0,00 0,11 0,00 0,00 0,00 1,94 1,14 0,45 0,04 0,67 0,05 1,40 0,95 2,56 0,97 4,84 3,33 2,01 1,11 2,50 1,36 1,39 0,75

Tabulka 6.8: Taillard: Porovnání jednotlivých algoritmů s HyperPOEMS

Kapitola 7

Závěr Cílem této práce bylo zmapovat stávající možnosti hyperheuristických algoritmů a na základě získaných informací navrhnou a implementovat hyperheuristický algoritmus pro řešení Capacitated Vehicle Routing Problému (CVRP). Výsledkem je HyperPOEMS, algoritmus, který na základě evolučních principů vyvíjí sekvence akcí, které iterativně modifikují tzv. prototyp. Prototyp je objekt, který je tvořen sekvencí určitých jednotek, které souběžně tvoří a zlepšují řešení daného problému. Algoritmus HyperPOEMS byl experimentálně otestován na obecně uznávaných datových sadách pro CVRP a výsledky byly porovnány se stávajícími specializovanými algoritmy, které tvoří state-of-the-art pro CVRP. Dosažené výsledky byly dále porovnány s algoritmem HHC-VRP, což je jiná implementace hyperheuristického přístupu pro řešení CVRP. Výsledky jednotlivých experimentů prokázaly, že HyperPOEMS obecně překonává algoritmus HHC-VRP. Navíc algoritmus HyperPOEMS pro některé z testovacích instancí dosahuje nejlepších známých výsledků. Tím se vyrovnává, případně i překonává, stávající state-of-theart algoritmy pro řešení CVRP.

7.1

Možné budoucí rozšíření

Provedené experimenty prokázaly, že algoritmus HyperPOEMS dosahuje pro CVRP překvapivě dobrých výsledků. Určitě jsou zde však možnosti, jak navržený algoritmus dále rozvíjet a zlepšovat. Co se týká aplikace tohoto algoritmu na problém CVRP, tak by bylo zajímavé vyzkoušet použití jiné sady low-level heuristik. Zajímavé by mohly být také pokusy, ve kterých by se experimentovalo s použitými POEMS akcemi. Největší výzvou je však aplikace HyperPOEMS pro řešení jiných tříd kombinatorických a optimalizačních problémů. Právě to by mohlo ukázat skutečnou sílu tohoto algoritmu a zároveň potvrdilo ideu hyperheuristických algoritmů.

45

46

KAPITOLA 7. ZÁVĚR

Literatura [1] M. Ayob and G. Kendall. A monte carlo hyper-heuristic to optimise component placement sequencing for multi head placement machine. In Proceedings of the 2003 International Conference on Intelligent Technologies (InTech2003), Thailand, pages 135– 141, 2003. [2] R. Bai. An Investigation of Novel Approaches for Optimising Retail Shelf Space Allocation. PhD thesis, Scholl of Computer Science and Information Technology, University of Nottingham, 2005. [3] A. Van Breedam. An analysis of the behavior of heuristics for the vehicle routing problem for a selection of problems with vehicle-related, customer-related, and timerelated constraints. PhD thesis, University of Antwerp, 1994. [4] E.K. Burke, M.R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J.R. Woodward. A classification of hyper-heuristic approaches. Computer science technical report no. nottcs-tr-sub-0907061259-5808, School of Computer Science and Information Technology, University of Nottingham, 2009. [5] E.K. Burke, M.R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J.R. Woodward. Expoloring hyper-heuristic methodologies with genetic programming. Technical report, Collaborative Computational Intelligence, 2009. [6] E.K. Burke, M.R. Hyde, G. Kendall, and J.R. Woodward. A genetic programming hyper-heuristic approach for evolving 2-d strip packing heuristics. In IEEE Transactions on Evolutary Computation. IEEE, 2010. [7] Konstantin Chakhlevitch and Peter Cowling. Hyperheuristics: Recent developments. In C. Cotta et al. (Eds.): Adaptive and Multilevel Metaheuristics, volume SCI 136, pages 3–29, Berlin, Heidelberg, 2008. Springer-Verlag. [8] N. Christofides and J. Beasley. The period routing problem. Networks, 14(2):237–256, 1984. [9] G. Clarke and J.W. Wright. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12:568–581, 1964. [10] J. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J. Sormany. A subpath ejection chain method for the vehicle routing problem. Management Science, 44(10):1447–1459, 1996.

47

48

LITERATURA

[11] J. Cordeau, M. Gendreau, A. Hertz, G. Laporte, and J. Sormany. New heuristics for the vehicle routing problem. Logistics Systems: Design and Optimization, page 279–297, 2005. [12] P. Cowling and K. Chakhlevitch. Hyperheuristics for managing a large collection of low level heuristics to schedule personnel. In Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC 2003), pages 1214–1221, 2003. [13] P. Cowling, G. Kendall, and E. Soubeiga. A hyperheuristic approach for scheduling a sales summit. In Selected Papers of the Third International Conference on the Practice And Theory of Automated Timetabling, PATAT 2000, pages 176–190. Springer-Verlag, 2000. [14] G.B. Datzing and J.H. Ramser. The truck dispatching problem. Management Science, 6(1):80–91, 1959. [15] J. Denzinger, Matthias Fuchs, and Marc Fuchs. High performance atp systems by combining several ai methods. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI 97), pages 102–107, 1997. [16] H. Fisher and G.L. Thompson. Probabilistic learning combinations of local jobshop scheduling rules. In Factory Scheduling Conference, May 10-12, 1961, Carnegie Institute of Technology, 1961. [17] M. Fisher. Optimal solution of vehicle routing problems using minimun k-trees. Operations Research, 42(4):626–642, 1994. [18] Pablo Garrido and Carlos Castro. Stable solving of cvrps using hyperheuristics. In GECCO 2009, Montreal, Quebec, Canada, July 2009. [19] Pablo Garrido and María Cristina Riff. Dvrp: a hard dynamic combinatorial optimisation problem tackled by an evolutionary hyper-heuristic. Journal of Heuristics, 16(6):795–834, December 2010. [20] Graham Kendall and Mazlan Mohamad. Channel assignment in cellular communication using a great deluge hyper-heuristic. In Proceedings of the 2004 IEEE International Conference on Networks (ICON 2004), Singapore, 2004. [21] Jiri Kubalik. Solving the sorting network problem using iterative optimization with evolved hypermutations. In GECCO 2009, Montreal, Quebec, Canada, July 2009. [22] Jiri Kubalik and Jan Faigl. Iterative prototype optimisation with evolved improvement steps. In P. Collet et al. (Eds.): EuroGP 2006, volume LNCS 3905, pages 154–165, Berlin, Heidelberg, 2006. Springer-Verlag. [23] Jiri Kubalik, Richard Mordinyi, and Stefan Biffl. Multiobjective prototype optimization with evolved improvement steps. In J. van Hemert and C. Cotta (Eds.): EvoCOP 2008, volume LNCS 4972, pages 218–229, Berlin, Heidelberg, 2008. Springer-Verlag.

LITERATURA

49

[24] Gilbert Laporte. The vehicle routing problem: An overview of exact and approximate algorithms. In European Journal of Operational Research 59, pages 345–358. Elsevier Science Publishers B.V., 1992. [25] Gilbert Laporte, Michel Gendreau, Jean-Yves Potvin, and Frédéric Semet. Classical and modern heuristics for the vehicle routing problem. International Transactions in Operational Research, 7:285–300, 2000. [26] S. Lin and B. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operational Research, 21(2):498–516, 1973. [27] D. Mester and O. Braysy. Active guided evolution strategies for large-scale vehicle routing problems with time windows. Computers and Operations Research, 36(6):1593–1614, 2005. [28] I. Or. Traveling salesman-type combinatorial optimization problems and their relation to the logistics of regional blood banking. PhD thesis, Northwestern University, Evanston, Illinois, USA, 1976. [29] Y. Rochat and E. Taillard. Probabilistic diversification and intensification in local search for vehicle routing. Journal of Heuristics, 1(1):147–167, 1995. [30] E. Soubeiga. Development and Application of Hyperheuristics to Personnel Scheduling. PhD thesis, School of Computer Science and Information Technology, University of Nottingham, 2003. [31] E. Taillard. Parallel iterative search methods for vehicle routing problem. Networks, 23:661–673, 1993. [32] Paolo Toht and Daniele Vigo. The Vehicle Routing Problem. SIAM monographs on descrete mathematics and applications, University City Science Center, Philadelphia, USA, 3th edition, 2001.

50

LITERATURA

Příloha A

Obsah přiloženého CD Obsah přiloženého CD je následující: • text/Mlejnek_DP.pdf - text diplomové práce • src/CVRP-HyperPOEMS - implementace algoritmu HyperPOEMS • src/matlab_scripts/ - adresář se skripty pro vykreslení CVRP řešení a zpracování výsledků v Matlabu • experiments/ - adresář s jednotlivými experimenty

51

Evoluční hyperheuristiky pro Vehicle Routing Problem. Bc. Jaromír Mlejnek

Recommend Documents