Problém obchodního cestujícího I - kódování a operátory

Další téma, kterým se na cvičeních budeme zabývat je známý problém obchodního cestujícího. Je dána množina měst a vzdálenosti mezi nimi, cílem je najít takovou cestu, která začíná a končí ve stejném městě, navštíví každé město právě jednou a je co možná nejkratší. Jinými slovy hledáme nejkratší Hamiltonovskou kružnici v úplném grafu. Samozřejmě nás opět bude zajímat, jak takový problém řešit pomocí evolučních algoritmů.

Kódování jedince

Řešení problému obchodního cestujícího je vlastně nějaká permutace měst (ta udává pořadí, v jakém máme města navštívit). Musíme tedy vymyslet, jak kódovat jedince, který permutaci vyjadřuje.

Jednou z možností je použít reálné kódování. Jedinec tedy obsahuje reálná čísla, ta se setřídí a permutace je určena jejich pozicemi před setříděním. Např. když máme jedince [5.4, 1.2, 2.3, 1.7], tak výsledná permutace je [1, 3, 2, 0], protože nejmenší číslo je na pozici 1, druhé nejmenší na pozici 3 atd. (indexujeme od 0). Výhodou tohoto kódování je, že můžeme používat jednoduché operátory a každý jedinec, kterého dostaneme, je platný (tj. dá se dekódovat na permutaci). Nevýhodou naopak je, že některé užitečné operace jsou složitější (např. zařazení zvoleného města na danou pozici v cestě).

Tradičnější evoluční algoritmy kódují jedince přímo jako permutaci. Tedy jedinec je vektor přirozených čísel a operátory musí zajistit, že v něm budou všechna čísla právě jednou.

Operátory pro permutační kódování

Vytvořit mutaci, která zachovává počet jednotlivých čísel v jedinci je jednoduché. Můžeme například prohazovat čísla mezi pozicemi, nebo vzít část jedince a vložit ji jinam. Další možností je vzít část jedince a vložit ji na stejné místo pozpátku.

Křížení je o něco složitější. Jako příklad si můžeme ukázat třeba Order Crossover (OX). To vlastně funguje podobně jako 2-bodové křížení, ale potom musí potomka upravit. Začíná se tím, že se vybere souvislá oblast v jednom rodiči a přesune se do potomka. Ve druhém rodiči se potom škrtnou čísla, která už jsou v potomkovi použita. Zbytek hodnot se doplní v pořadí, v jakém jsou ve druhém rodiči, začíná se na pravém konci vybraného úseku. Pokud chceme druhého potomka, dostaneme ho tak, že prohodíme oba rodiče a postup zopakujeme.

Podobných křížení je spousta, na další příklady se můžete podívat tady.

Dnešní zdrojové kódy

V dnešních zdrojových kódech máme implementovaný jednoduchý evoluční algoritmus pro problém obchodního cestujícího. Nepoužívá žádné křížení, ale jen mutaci. Fitness se počítá jako 1/délka cesty. Města jsou zadaná jako jejich zeměpisné souřadnice, vzdálenost se počítá vzdušnou čarou (spočítá ji funkce distance v tsp.py). Máme několik vstupů: tsp_evropa.in obsahuje souřadnice hlavních měst evropských zemí (včetně Ruska a Islandu). Ostatní vstupy jsou potom náhodně generované po celé Zemi, tsp_std.in obsahuje 100 „měst“, tsp_test.in jich má jen 10 (vhodné pro testování) a tsp_large.in naopak obsahuje 1000 „měst“. Dnešní .best soubory mají příponu .kml a lze je otevřít v Google Earth a podívat se na výslednou nejlepší cestu. Pracujeme v souboru tsp.py.