Úvod do simulační optimalizace
Problém obchodního cestujícího

| Úvod a cíle |

# Zadání

Cestující má navštívit 20 různých měst a samozřejmě chce, aby navštívil města v takovém pořadí, aby součet tras jím navštívených měst byl co nejmenší (za předpokladu, že každé město navštíví jen jednou).

# Tipy pro řešení

Návrh řešení

Příkladem využití globální optimalizační metody ukazuje aplikace, která využívá genetického algoritmu. Tuto aplikaci spustíte kliknutím na následující odkaz - Problém obch. cestujícího . Je vhodné zmínit, že skoro všechny globální optimalizační metody, genetický algoritmus nevyjímaje, jsou velmi náchylné na vhodné nastavení parametrů metody. Hodnoty jednotlivých parametrů genetického algoritmu jsou zde proto přednastaveny. Tyto parametry lze libovolně měnit podle Vašeho uvážení. Parametry genetického algoritmu jsou: • Cities - počet měst, které má navštívit obchodní cestující - jsou náhodně generována na mapě. • Pop. size - velikost populace - počet jedinců v populaci. Vyšší číslo znamená větší možnost prozkoumávání možností - větší diverzita jedinců, což vede ke snížení rizika uvíznutí v lokálním extrému - horší řešení. • Parents - počet rodičů v populaci, kteří se mohou pářit. Vybráni budou pouze Ti, kteří jsou lepší než ostatní, tj. splňují specifikované kritérium, které je vyjádřeno ve formě hodnoty fitness - čím lepší, tím vyšší hodnota fitness. • Mutation % - stupeň mutace, šance že jedinec bude pozměněn - reprezentace jiné cesty. • Generations - počet generací - iterací - jak dlouho bude simulace běžet. Každá generace zahrnuje selekci - výběr podle kritéria, křížení, mutaci a "zabití" jedinců, kteří nevyhovují našim specifikovaným kritériím - tj. jejich nahrazení novými "dětmi". Start - tlačítko pro spuštění simulačního experimentu. Pause - tlačítko pro pozastavení simulačního experimentu. Exit - ukončení aplikace. About - informace o verzi aplikace a autorovi. Obrázek 1. Parametry genetického algoritmu obch. cestujícího (http://subsimple.com/delphi.asp) Jak jste si možná všimli, jde o teorii přirozeného výběru podle Darwina. Detailnější popis jednotlivých principů bude následovat v kapitole zabývající se evolučními výpočetními technikami. Další okno aplikace zobrazuje souhrnné informace o prováděných experimentech: Cities, Population size, Parents, Prob. mutation, Max generations - aktuální nastavení předchozích parametrů. Starting distance - vzdálenost, kterou musel obchodní cestující urazit, při vygenerovaném počátečním řešení. Generation - index aktuální populace. Mutations - počet proběhlých mutací. Distance - nejlepší dosažené řešení tj. minimální vzdálenost, kterou musel obchodní cestující urazit. Obrázek 2. Aktuální nastavení a výsledky experimentů V posledním okně je zobrazována aktuální trasa, kterou by musel obchodní cestující mezi městy urazit. Jednotlivá města jsou reprezentovány body a trasa mezi dvěma městy je spojnice mezi dvěma body: Obrázek 3. Trasa měst navštívených obch. cestujícím