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

2017. május 09. 00:01

Az utazó ügynök problémája különböző tudományokban merül fel, számos területen alkalmazzák a megoldásokat. Az MI-kutatásban szintén igen népszerű, gyakran születnek izgalmas javaslatok, például genetikus algoritmusok vagy a rajintelligencia alkalmazása.

2017. május 09. 00:01
Admin

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.

Összesen 1 komment

A kommentek nem szerkesztett tartalmak, tartalmuk a szerzőjük álláspontját tükrözi. Mielőtt hozzászólna, kérjük, olvassa el a kommentszabályzatot.
Sorrend:
Csigorin
2017. június 08. 01:44
Annyiban hadd kossek bele, hogy nem kell kikotni az utazo ugynoknel hogy egy varosban nem jarhat ketszer, csak azt, hogy az osszeset meg kell latogatnia. Elvegre ha netan ugy jonne ki a legrovidebb ut, hogy egyet ketszer is erint, az nem zavarja a fonokot...
Jelenleg csak a hozzászólások egy kis részét látja. Hozzászóláshoz és a további kommentek megtekintéséhez lépjen be, vagy regisztráljon!