XII. Problém obchodního cestujícího

O problému

Problém obchodního cestujícího (TSP) byl už zmíněn v jedné z předchozích kapitol. Pro zopakování: máme města a dané vzdálenosti mezi nimi. Obchodní cestující musí navštívit všechna města a přitom urazit co nejmenší vzdálenost. Úkolem je najít takovou posloupnost měst, která minimalizuje celkovou uraženou vzdálenost. Jinými slovy hledáme minimální Hamiltonovskou kružnici v úplném grafu o N uzlech.

Implementace

Používá se populace 16 chromozomů. Tyto chromozomy využívají permutační kódování - v kapitole o kódování si můžete přečíst, jak zakódovat permutaci měst pro TSP. TSP je řešen na úplném grafu (tj. každý uzel je spojen se všemi ostatními) s eukleidovskými vzdálenostmi. Všimněte si, že po přidání nebo smazání města je nutné vytvořit nové chromozomy a restartovat celý genetický algoritmus.

Můžete si zvolit typ křížení a mutace. Jejich význam je popsán níže.

Křížení

  • Jednobodové - zkopíruje se část prvního rodiče a zbytek se vezme ve stejném pořadí jako u druhého rodiče
  • Dvoubodové - zkopírují se dvě části prvního rodiče a úsek mezi nimi se vezme ve stejném pořadí jako u druhého rodiče
  • Žádné - žádné křížení; potomek je přesná kopie rodičů

Mutace

  • Běžná náhodná - vybere se několik měst a ta se prohodí
  • Náhodná, pouze zlepšující - náhodně se vybere a prohodí několik měst jen tehdy, pokud se řešení zlepší (zvýší se hodnota účelové funkce)
  • Systematická, pouze zlepšující - města se systematicky vybírají a prohazují jen tehdy, pokud se řešení zlepší (zvýší se hodnota účelové funkce)
  • Náhodná zlepšující - stejně jako "náhodná, pouze zlepšující", ale nejprve se provede "běžná náhodná" mutace
  • Systematická zlepšující - stejně jako "systematická, pouze zlepšující", ale nejprve se provede "běžná náhodná" mutace
  • Žádná - žádná mutace

Příklad

Následující demonstrace ukazuje, jak GA řeší TSP. Tlačítko "Change View" přepíná mezi zobrazením celé populace a nejlepšího řešení. Města můžete přidávat a odebírat kliknutím do grafu. Po přidání nebo smazání města se objeví náhodná trasa, protože je třeba vytvořit novou populaci s novými chromozomy. Všimněte si také, že TSP řešíme na úplném grafu.
Zkuste spustit GA s různým nastavením křížení a mutace a sledujte, jak se mění jeho výkonnost (a rychlost - přidejte více měst a rozdíl uvidíte).