Algoritmický svět je krásný s rozmanitými strategiemi a nástroji, které jsou nepřetržitě vyvíjeny, aby odpovídaly potřebám vysoce výkonných počítačů. Ve skutečnosti, když jsou algoritmy inspirovány přírodními zákony, jsou pozorovány zajímavé výsledky. Evoluční algoritmy patří do takové třídy algoritmů. Tyto algoritmy jsou navrženy tak, aby napodobovaly určité chování a také evoluční rysy lidského genomu. Navíc takový algoritmický návrh není omezen pouze na lidi, ale může být inspirován i přirozeným chováním určitých zvířat. Základním cílem vytváření takových metodologií je poskytnout realistická, relevantní a přitom některá nízkonákladová řešení problémů, které jsou dosud konvenčními prostředky neřešitelné.
Různé optimalizační techniky se tak vyvinuly na základě takových evolučních algoritmů a otevřely tak doménu metaheuristiky. Metaheuristický byl odvozen ze dvou řeckých slov, a to Meta význam o úroveň výše a heuriskein význam najít . Algoritmy jako Particle Swarm Optimization (PSO) a Ant Colony Optimization (ACO) jsou příklady rojové inteligence a metaheuristiky. Cílem inteligence roje je navrhnout inteligentní multiagentní systémy na základě inspirace z kolektivního chování sociálního hmyzu, jako jsou mravenci, termiti, včely, vosy a další zvířecí společnosti, jako jsou hejna ptáků nebo hejna ryb.
Pozadí:
Technika optimalizace mravenčí kolonie je čistě inspirována shánění potravy chování mravenčích kolonií, které poprvé představil Marco Dorigo v 90. letech 20. století. Mravenci jsou eusociální hmyz, který preferuje přežití a udržení komunity spíše než jako jednotlivé druhy. Komunikují mezi sebou pomocí zvuku, dotyku a feromonu. Feromony jsou organické chemické sloučeniny vylučované mravenci, které spouštějí sociální reakci u příslušníků stejného druhu. Jsou to chemikálie schopné působit jako hormony mimo tělo vylučujícího jedince a ovlivnit chování přijímajících jedinců. Protože většina mravenců žije na zemi, využívají povrch půdy k zanechání feromonových stop, které mohou následovat (vycítit) jiní mravenci.
Mravenci žijí v komunitních hnízdech a základním principem ACO je pozorovat pohyb mravenců z jejich hnízd za účelem hledání potravy co nejkratší cestou. Zpočátku se mravenci začnou náhodně pohybovat při hledání potravy kolem svých hnízd. Toto náhodné hledání otevírá několik cest z hnízda ke zdroji potravy. Nyní, na základě kvality a množství potravy, mravenci přenášejí část potravy zpět s potřebnou koncentrací feromonů na své zpětné cestě. V závislosti na těchto feromonových pokusech by byla pravděpodobnost výběru konkrétní cesty následujícími mravenci vodítkem ke zdroji potravy. Je zřejmé, že tato pravděpodobnost je založena na koncentraci a také na rychlosti odpařování feromonu. Lze také pozorovat, že protože rychlost odpařování feromonu je také rozhodujícím faktorem, lze délku každé cesty snadno zohlednit.
Na výše uvedeném obrázku byly pro zjednodušení uvažovány pouze dvě možné cesty mezi zdrojem potravy a mravenčím hnízdem. Fáze lze analyzovat následovně:
- Fáze 1: Všichni mravenci jsou ve svém hnízdě. V prostředí není žádný obsah feromonů. (Pro návrh algoritmu může být uvažováno množství zbytkového feromonu bez ovlivnění pravděpodobnosti) Fáze 2: Mravenci začnou hledat se stejnou (0,5 každý) pravděpodobností podél každé cesty. Je zřejmé, že zakřivená dráha je delší, a proto doba, kterou mravenci potřebují k dosažení zdroje potravy, je delší než druhá. Fáze 3: Mravenci se kratší cestou dostanou ke zdroji potravy dříve. Nyní se evidentně potýkají s podobným selekčním dilematem, ale tentokrát díky feromonové stezce po již dostupné kratší cestě je pravděpodobnost selekce vyšší. Fáze 4: Více mravenců se vrací kratší cestou a následně se také zvyšují koncentrace feromonů. Navíc v důsledku odpařování se koncentrace feromonů v delší dráze snižuje, čímž se snižuje pravděpodobnost výběru této cesty v dalších fázích. Celá kolonie proto postupně využívá kratší cestu ve vyšších pravděpodobností. Tak je dosaženo optimalizace cesty.
Algoritmický design:
Vzhledem k výše uvedenému chování mravenců lze nyní vyvinout algoritmický návrh. Pro jednoduchost byl uvažován jediný zdroj potravy a jediná mravenčí kolonie s pouze dvěma cestami možného průchodu. Celý scénář lze realizovat prostřednictvím vážených grafů, kde mravenčí kolonie a zdroj potravy fungují jako vrcholy (nebo uzly); dráhy slouží jako hrany a hodnoty feromonů jsou váhy spojené s hranami.
Nechte graf být G = (V, E) kde V, E jsou hrany a vrcholy grafu. Vrcholy podle naší úvahy jsou Vs (Vertex zdroje – kolonie mravenců) a Vd (Cílový vrchol – Zdroj potravy), Dvě hrany jsou A1 a A2 s délkami L1 a L2 přiřazeny každému. Nyní lze předpokládat, že související hodnoty feromonů (indikující jejich sílu) jsou R1 a R2 pro vrcholy E1a E2respektive. Pro každého mravence je tedy počáteční pravděpodobnost výběru cesty (mezi E1a E2) lze vyjádřit takto:
Je zřejmé, že pokud R1>R2, pravděpodobnost výběru E1je vyšší a naopak. Nyní, když se vracíte touto nejkratší cestou, řekněte Ei, hodnota feromonu se aktualizuje pro odpovídající cestu. Aktualizace se provádí na základě délky drah a také rychlosti odpařování feromonu. Aktualizaci lze tedy provést postupně takto:
- Podle délky cesty -
Ve výše uvedené aktualizaci slouží jako parametr modelu i = 1, 2 a ‚K‘. Aktualizace navíc závisí na délce cesty. Čím kratší cesta, tím vyšší množství přidaného feromonu. Podle rychlosti odpařování feromonu –
Parametr ‚v‘ patří do intervalu (0, 1], který reguluje odpařování feromonů. Dále i = 1, 2.
Při každé iteraci jsou všichni mravenci umístěni na zdrojový vrchol Vs(kolonie mravenců). Následně se mravenci stěhují z Vsk Vd(zdroj potravy) po kroku 1. Dále všichni mravenci provedou zpáteční cestu a zpevní svou zvolenou cestu na základě kroku 2.
Pseudo kód:
Procedure AntColonyOptimization: Initialize necessary parameters and pheromone trials; while not termination do : Generate ant population; Calculate fitness values associated with each ant; Find best solution through selection methods; Update pheromone trial; end while end procedure>
Aktualizaci feromonů a výpočty fitness ve výše uvedeném pseudokódu lze nalézt prostřednictvím výše zmíněných postupných implementací.
Tak bylo zavedeno zavedení optimalizační techniky ACO. Aplikace ACO může být rozšířena na různé problémy, jako jsou slavné TSP (problém cestovního prodejce) .
Reference:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf