UMĚLÁ INTELIGENCE V AUTOMOTIVE / David et al.

je efektivní využití jejich silných stránek a optimalizaci výsledků. Tímto způsobem lze dosáhnout vyváženého přístupu k optimalizaci, který zohledňuje různorodé faktory a poskytuje komplexní řešení. Integrace těchto přístupů umožňuje synergii mezi jed notlivými metodami a přináší takový výsledek, který je většinou efektivnější než pouhé využívání jednotlivých přístupů samostatně. Evoluční algoritmus pro řešení TSP Jak již bylo zmíněno dříve, konvenční algoritmy využívané k řešení TSP se potý kají s určitými, relevantními limitacemi. S nástupem evolučních algoritmů se rodí celá řada inovativních numerických optimalizačních algoritmů. Tato řešení se do určité míry opírají o náhodné vyhledávací algoritmy. [5.17] ACA (optimalizace kolonií mravenců – Ant Colony Optimization – Ant Colony Algorithm) a PSO (Optimalizace rojem částic – Particle Swarm Optimization) jsou běžné paralelní algoritmy, i když nemají možnost garantovat nalezení ideálního řešení v daném časovém rámci, jsou schopné nabídnout uspokojivé výsledky v tolerovatelném časovém intervalu. K určení dopadu řešení pro TSP dosaženého s využitím optimalizujícího algo ritmu je třeba zohlednit vyhledávací kapacity daného vyhledávacího algoritmu. Jako příklad, algoritmus s vysokým stupněm optimalizace bude mít větší účinnost, zatímco algoritmus, který se snadno zasekne v lokálním maximu, často přispívá k nalezení opti málního řešení pro TSP s lokálními vlastnostmi. Jedním z příkladů evolučních algoritmů určených k řešení Problému obchodní ho cestujícího (TSP) je algoritmus kolonie mravenců, známý také jako “Ant Colony Algorithm”. Tento relativně nový evoluční algoritmus byl představen italským vědcem Marco Dorigem. Tento algoritmus využívá inspiraci z chování mravenců při hledání nejkratší cesty k potravě a zpět do mraveniště. Jednotliví mravenci vytvářejí feromonové stopy, které jsou následně využity ostatními mravenci k rozhodování o směru svého pohybu. Tímto způsobem se vytváří komplexní síť feromonových stop, které přispívají k objevení optimální trasy k cíli. V kontextu ACA značí n počet bodů (měst) v TSP a M symbolizuje počet mra venců v kolonii. Významnými faktory jsou také vzdálenosti mezi jednotlivými body (městy), které jsou reprezentovány jako d ij (kde i, j = 1, 2, …, n ), a množství feromonu na trasách mezi body (městy), které je označeno jako τ ij (t) a reprezentuje ho v určitém čase t . Na počátku řešení, v čase t = 0 je feromonová koncentrace na všech trasách shod ná, tedy τ ij (0) = C , kde C je stálá hodnota. V průběhu cestování v mraveništi si každý mravenec ( k = 1, 2, …, m ) vybírá směr podle množství feromonu na jednotlivých tra sách. Veličina daná vztahem (5.13) symbolizuje pravděpodobnost, že se mravenec přesune z místa i na místo j v daném okamžiku t .

70