Algoritmický svet je nádherný s rozmanitými stratégiami a nástrojmi, ktoré sa neustále vyvíjajú, aby vyhovovali potrebe vysokovýkonnej výpočtovej techniky. V skutočnosti, keď sú algoritmy inšpirované prírodnými zákonmi, sú pozorované zaujímavé výsledky. Evolučné algoritmy patria do takejto triedy algoritmov. Tieto algoritmy sú navrhnuté tak, aby napodobňovali určité správanie, ako aj evolučné črty ľudského genómu. Navyše, takýto algoritmický návrh nie je obmedzený len na ľudí, ale môže byť inšpirovaný aj prirodzeným správaním určitých zvierat. Základným cieľom tvorby takýchto metodológií je poskytnúť realistické, relevantné a pritom niektoré nízkonákladové riešenia problémov, ktoré sú doteraz konvenčnými prostriedkami neriešiteľné.

Na základe takýchto evolučných algoritmov sa teda vyvinuli rôzne optimalizačné techniky, čím sa otvorila oblasť metaheuristiky. Metaheuristický bol odvodený z dvoch gréckych slov, a to Meta význam o úroveň vyššie a heuriskein význam nájsť . Algoritmy ako Particle Swarm Optimization (PSO) a Ant Colony Optimization (ACO) sú príkladmi rojovej inteligencie a metaheuristiky. Cieľom rojovej inteligencie je navrhnúť inteligentné multiagentové systémy na základe inšpirácie z kolektívneho správania sociálneho hmyzu, ako sú mravce, termity, včely, osy a iné živočíšne spoločenstvá, ako sú kŕdle vtákov alebo húfy rýb.

Pozadie:

Technika optimalizácie kolónií mravcov je čisto inšpirovaná hľadanie potravy správanie mravčích kolónií, ktoré prvýkrát predstavil Marco Dorigo v 90. rokoch 20. storočia. Mravce sú eusociálny hmyz, ktorý uprednostňuje prežitie a udržanie komunity skôr ako jednotlivé druhy. Komunikujú medzi sebou pomocou zvuku, dotyku a feromónu. Feromóny sú organické chemické zlúčeniny vylučované mravcami, ktoré spúšťajú sociálnu reakciu u členov rovnakého druhu. Sú to chemikálie schopné pôsobiť ako hormóny mimo tela vylučujúceho jedinca a ovplyvniť správanie prijímajúcich jedincov. Keďže väčšina mravcov žije na zemi, využívajú povrch pôdy na zanechanie feromónových stôp, ktoré môžu nasledovať (zapáchať) inými mravcami.
Mravce žijú v komunitných hniezdach a základným princípom ACO je pozorovať pohyb mravcov z ich hniezd, aby si čo najkratšou cestou hľadali potravu. Spočiatku sa mravce začnú náhodne pohybovať pri hľadaní potravy okolo svojich hniezd. Toto náhodné vyhľadávanie otvára viacero ciest z hniezda k zdroju potravy. Teraz, na základe kvality a množstva potravy, mravce na svojej spiatočnej ceste prenášajú časť potravy späť s potrebnou koncentráciou feromónov. V závislosti od týchto feromónových pokusov by pravdepodobnosť výberu špecifickej cesty nasledujúcimi mravcami bola vodiacim faktorom pre zdroj potravy. Je zrejmé, že táto pravdepodobnosť je založená na koncentrácii, ako aj na rýchlosti vyparovania feromónu. Je tiež možné pozorovať, že keďže rýchlosť vyparovania feromónu je tiež rozhodujúcim faktorom, dĺžka každej cesty sa dá ľahko vypočítať.

Na vyššie uvedenom obrázku boli pre zjednodušenie uvažované iba dve možné cesty medzi zdrojom potravy a hniezdom mravcov. Etapy možno analyzovať takto:

Fáza 1: Všetky mravce sú vo svojom hniezde. V prostredí nie je žiadny obsah feromónov. (Pre algoritmický návrh možno uvažovať o zvyškovom množstve feromónu bez zásahu do pravdepodobnosti.) Fáza 2: Mravce začínajú svoje hľadanie s rovnakou (0,5 každý) pravdepodobnosťou pozdĺž každej cesty. Je zrejmé, že zakrivená dráha je dlhšia, a preto čas, ktorý mravce potrebujú na dosiahnutie zdroja potravy, je dlhší ako druhý. Fáza 3: Mravce kratšou cestou dosiahnu zdroj potravy skôr. Teraz očividne čelia podobnej selekčnej dileme, ale tentoraz vďaka feromónovej stope po už dostupnej kratšej ceste je pravdepodobnosť selekcie vyššia. Fáza 4: Viac mravcov sa vracia kratšou cestou a následne sa zvyšujú aj koncentrácie feromónov. Navyše v dôsledku odparovania sa koncentrácia feromónov v dlhšej dráhe znižuje, čím sa znižuje pravdepodobnosť výberu tejto dráhy v ďalších fázach. Preto celá kolónia postupne využíva kratšiu cestu vo vyšších pravdepodobnostiach. Optimalizácia cesty je teda dosiahnutá.

Algoritmický dizajn:

Vzhľadom na vyššie uvedené správanie mravcov je teraz možné vyvinúť algoritmický návrh. Pre jednoduchosť sa uvažovalo o jedinom zdroji potravy a jednej kolónii mravcov len s dvoma cestami možného prechodu. Celý scenár je možné realizovať prostredníctvom vážených grafov, kde kolónia mravcov a zdroj potravy pôsobia ako vrcholy (alebo uzly); dráhy slúžia ako okraje a hodnoty feromónov sú hmotnosti spojené s okrajmi.
Nech je ten graf G = (V, E) kde V, E sú hrany a vrcholy grafu. Vrcholy podľa našej úvahy sú V_s (Zdrojový vrchol – kolónia mravcov) a V_d (Cieľový vrchol – Zdroj potravy), Dve hrany sú A₁ a A₂ s dĺžkami L₁ a L₂ pridelené každému. Teraz možno predpokladať, že súvisiace hodnoty feromónov (indikujúce ich silu) sú R₁ a R₂ pre vrcholy E₁a E₂resp. Pre každého mravca je teda počiatočná pravdepodobnosť výberu cesty (medzi E₁a E₂) možno vyjadriť takto:

Je zrejmé, že ak R₁>R₂, pravdepodobnosť výberu E₁je vyššia a naopak. Teraz, keď sa vraciate touto najkratšou cestou, povedzte E_i, hodnota feromónu sa aktualizuje pre zodpovedajúcu cestu. Aktualizácia sa vykonáva na základe dĺžky dráh, ako aj rýchlosti odparovania feromónu. Aktualizáciu je teda možné realizovať postupne takto:

Podľa dĺžky cesty -

Vo vyššie uvedenej aktualizácii slúži ako parameter modelu i = 1, 2 a „K“. Aktualizácia navyše závisí od dĺžky cesty. Čím je cesta kratšia, tým vyšší je pridaný feromón. Podľa rýchlosti odparovania feromónu -

Parameter ‚v‘ patrí do intervalu (0, 1], ktorý reguluje odparovanie feromónov. Ďalej i = 1, 2.

Pri každej iterácii sú všetky mravce umiestnené na zdrojový vrchol V_s(kolónia mravcov). Následne sa mravce sťahujú z V_sdo V_d(zdroj potravy) po kroku 1. Ďalej všetky mravce vykonávajú svoju spiatočnú cestu a posilňujú svoju zvolenú cestu na základe kroku 2.

Pseudokó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>

Aktualizáciu feromónov a výpočty kondície vo vyššie uvedenom pseudokóde možno nájsť prostredníctvom vyššie uvedených krokových implementácií.
Zaviedlo sa teda zavedenie techniky optimalizácie ACO. Aplikácia ACO môže byť rozšírená na rôzne problémy, ako sú známe TSP (problém obchodného cestujúceho) .

Referencie:
https://www.ics.uci.edu/~welling/teaching/271fall09/antcolonyopt.pdf