Az utazó ügynök problémája

Voltaképpen könnyen érthető, ám annál nehezebben megoldható logikai-matematikai játék. A probléma (travelling salesman problem, TSP) lényege, hogy az ügynöknek több városon keresztül, a lehető leggyorsabban kell megtennie egy utat. Az összes várost kell érintenie, ám egy adott városban csak egyszer járhat. Melyik a legrövidebb útvonal?

Genetikus algoritmusok

A genetikus algoritmusokon alapuló megoldásban a változók egy bájtnyi (nyolc bit) egységekben tárolódnak, s mivel nullák és egyek lehetnek, értékük nulla és 255 [2 a nyolcadikon (256) mínusz egy] közötti. Mindkét irányban (x, y) nullától 255ig terjedő négyszögletes területet vázol fel, 256szor 256 egységgel. Tetszőlegesen kiválasztunk, és benépesítünk 256 párt, melyek száz karakterláncot formálnak (a nulla és 255 közötti indexek listájából). Egy láncon belüli valamennyi gén egyedi; szorosan kapcsolódik az előző generációhoz. Evolúciós folyamatokon (öröklődésen, mutáción) megy keresztül. Újabb láncok jönnek létre, elpusztulnak a korábbiak.

A szülők kiválasztását, a következő generációban való túlélést rulett-kerék szelekciós algoritmus (roulette wheel selection algorithm) dönti el. Természetesen az alkalmasabb láncoknak nagyobb az esélye. Míg a mutáció egyszerűen megy végbe, s igen ritkán (egyszázalékos gyakorisággal) alkalmazzák, az esetek hetven százalékában bekövetkező kereszteződésnél (crossover) gondosan meg kell határozni, mitől erősebb egy-egy lánc alkalmazkodóképessége. Viszont, ha nincs kereszteződés, az utódok a szülők módosítás nélküli másolatai lesznek.

Az algoritmusokat tesztelve a szemlélődő meggyőződhet, miként fejlődnek merevebbekből véletlenszerűbbekké. A populáció globális alkalmazkodóképessége minden egyes iteráció után nő, és végül megkapjuk az egyetlen legrövidebb útvonalat. Amiről fogalmunk sem volt az elején.

Hangyakolóniák

Az utazó ügynök problémáját legbehatóbban talán Marco Dorigo és munkatársai tanulmányozták eddig. Rájöttek: a hangyák azon képessége, hogy a lehetséges útvonalak közül (feromon-lerakódás alapján) rátalálnak a legrövidebbre, a TSP-re is adhat magyarázatot.

Mesterséges hangyakolónia-rendszerekből (ant colony systems, ACS) indultak ki. A hangyák a TSP-gráfon városról városra mozgó ágensek – véletlenszerűen indulnak el, virtuális feromont hagyva maguk után. Valószínűség és az információként szolgáló, korábban lerakott feromon alapján döntenek. Miután befejeztek egy-egy utat, a gráf élein hagynak nyomot: (értelemszerűen) a rövidebb út mentén többet.

Végül – azt az élt választva, ahol a legtöbb a speciális illatanyag – kialakul az optimális útvonal.

A folyamat sokszori lefuttatását követően egyértelmű, hogy a felhalmozott feromon mennyisége befolyásolja a hangyatársakat. A nyomok lokálisan és globálisan is változnak. A teljes update (mint egy tanulórendszerben) a rövidebb út menti él jutalmazását célozza. A lokális ellentétes előjelű; rendeltetése nyomeltüntetés, az erősebb koncentrációk elkerülése. A hangyák vagy a bejáratott ösvényen haladnak, vagy újabb megoldások, új típusú felfedező stratégiák után kutatnak.

A számítógépes szimuláció bebizonyította, hogy a mesterséges kolóniák a TSP szimmetrikus és aszimmetrikus példáira egyaránt találnak megoldást. A valódi hangyák viselkedésének három főbb elemét vették át: a magasabb feromonszint melletti döntést, azt, hogy a rövidebb utat jelölik meg erőteljesebben, valamint a nyom általi kommunikációt. A kommunikáció egyrészt, meghatározta az együttműködést (synergistic effect), másrészt az optimális lehetőség gyors megtalálásának a valószínűségét növelte.

A mesterséges állatkák természetben élő társaikra nem jellemző, viszont a TSP-alkalmazások során hasznos adottságokkal is rendelkeznek. Meg tudják határozni a városok távolságát, minden út előtt kiürítendő memóriájuk (working memory) van. Utóbbi arra szolgál, hogy emlékezetben tartsák, mely városokban jártak már.

Dorigo és munkatársai az ACS-t más természet által inspirált globális optimalizáló módszerekkel hasonlították össze: szimulált temperálással (simulated annealing), ideghálókkal (önszerveződő térképekkel, elasztikus hálózatokkal), evolúciós számításokkal (genetikus algoritmusokkal, evolúciós programozással), a szimulált temperálás és a genetikus algoritmusok kombinációjával, sőt, a legtávolabbi beillesztés heurisztikával (farthest insertion heuristic) is. Az eredmények őket igazolták.