Genetika – problém obchodního cestujícího

Díl 2

Zajímavý problém obchodního cestujícího (Travelling salesman problem), na který narazíte na mnoha fórech na webu. Jde o to najít nejkratší cestu mezi jednotlivými zastávkami, které musí obchodní cestující projít. Samozřejmě existuje plno metod, které tento matematický oříšek řeší.

Napadlo nás napsat genetický algoritmus, který by dosáhl uspokojivých výsledků. Pro tento projekt jsme museli upravit (rozšířit) i náš základní algoritmus křížení a mutace a přizpůsobit procedury požadovanému zadání. Vytvořili jsme i testovací prostředí, kde si můžete vytvořit vlastní cesty a vyzkoušet si hledání cesty křížením a mutací.

Příprava

Základní genom jsme pojali jako skupinu genů, které obsahují pořadové číslo jednotlivých cílových destinací. Sousedící geny jsou tedy cestou k dalšímu cíli vedle. Poslední gen pak ukazuje cestu k prvnímu genu (cíli).

Křížení

Základní pravidlo křížení nelze použít, protože by duplikoval jednotlivé cíle. Použili jsme tedy logiku kopie určitého úseku v dané pozici (rodič 1) a doplněním o chybějící cíle ve stejném pořadí (rodič 2).

Cross

Výběr pravidla po křížení a mutaci jsme zvolili napevno. 7 nejkratších cest a 2 náhodně vybrané cesty, ze zbývajících, pro rozvážení systému a hledání nových řešení. Tento výběr pak prokřížíme každý s každým.

Mutace

Základní mutace nejde také použít, protože by duplikovala jednotlivé cíle, a dokonce by generovala cíle, které v daném zadání ani neexistují.

Výměna

Nejprve jsme zvolili způsob mutace "výměna", ale tento způsob nebyl dostačující, protože složitější zadání zůstávala v lokálních minimech.

Mutation swap

Rolování

Druhý způsob mutace "rolování" sice rozvažoval lokální minima, ale toto rozvážení bylo převážně vždy k delší cestě, takže systém opět směřoval ke stejnému výběru.

Mutation roll

Obrácení

Poslední způsob mutace "obrácení" se zdál nejlepší a po delším testování směřoval vždy k uspokojivému výsledku. Lokální minima byla totiž vesměs ve stylu obrácením posloupnosti dílčího úseku cesty. Nyní také dochází k dohledání stejně krátké cesty v opačné pořadí průchodu.

Mutation reverse

V aplikaci jsme použili mutaci "výměna" a "obrácení" v poměru 1:1. U výměny dojde u jedince k jedné mutaci a následně s 66% pravděpodobností k další opakované mutaci. U mutace obrácení dojde jen k jedné mutaci.

Aplikace

Popis

V levé části se nachází prostor pro rozmístění cílů. Vpravo je seznam cest (jedinců). Po najetí myší na jednotlivé jedince se zobrazí jeho cesta (posloupnost cílů). Modře se zobrazí právě nejkratší cesta.

Údaje v menu jsou v pořadí – Upath #pořadové číslo jedince, G=číslo generace jedince, L=délka jeho cesty.

Menu vpravo dole:

Clear – vymaže všechny cíle,
Reset – vygeneruje a zamíchá cesty jedincům,
Find path – provede jeden genetický cyklus,
Quit – ukončí aplikaci.

Základní ovládání

Levé tlačítko myši – přidá cíl do pozice myši.
Pravé tlačítko myši – smaže cíl v pozici myši.
Klávesa F – vyvolá další výběr jedinců, křížení a mutaci.

Při přidaní či odebrání cíle se výpočet i cesty vždy resetují.

Stáhnout Ugex Path

(Stažený soubor rozbalte do nějakého adresáře a spusťte UgexPath.exe)

(Projekt Ugex path využívá grafických knihoven HGE Relish Games, tímto moc děkujeme)

Najděte svoji cestu se Shrimphood.net

-fjura-