[CZ] Problém obchodního cestujícího II - chytré operátory

Na dnešních cvičeních se pokusíme vylepšit vaše řešení TSP z minula. Jako už několikrát i teď se pokusíme vymyslet chytré operátory. K tomu nám mohou pomoci různé heuristiky, které se používají při řešení TSP.

k-OPT

Asi nejznámější heuristikou pro TSP je tzv. 2-OPT. Při něm se vyberou dvě hrany, ty se odeberou a nahradí jinými dvěma hranami (je jen jedna možnost). Nakonec se vybere kratší z obou vzniklých cest. Vlastně se jedná o mutaci, která vezme část cesty a tu vloží do jedince v opačném pořadí. 2-OPT se navíc ještě podívá, jestli je výsledek kratší a přijme ho jen pokud je.

2-OPT se přirozeně dá zobecnit na k-OPT, odstraní se k hran a vzniklé fragmenty se pospojují tak, aby výsledná cesta byla co možná nejkratší.

Nejbližší sousedi

Další varianta, kterou je možné vyzkoušet, je dávat za zvolené město jeho nejbližšího souseda. Tohle se dá zase několikrát zopakovat a tím vytvořit krátké úseky cesty, které obsahují jen blízká města.

Inicializace pomocí aproximačního algoritmu

Můžeme také vyzkoušet inicializovat evoluci pomocí nějakého jiného algoritmu, místo náhodné populace na začátku. Nabízí se různé aproximační algoritmy, které začínají tím, že najdou nejmenší kostru. Je ale třeba dát pozor na to, že takhle inicializovaná populace může představovat lokální optimum, ze kterého se algoritmus těžko dostane.

Last modified: Monday, 17 December 2018, 9:36 AM