Problémy a algoritmy
Řešení problému obchodního cestujícího metodou simulovaného ochlazování
(5. úloha)

Zadání

Je dáno m měst. Některá města jsou propojena silnicemi, délka silnic je známa. Úkolem obchodního cestujícího je navštívit všechna města (právě jednou, aspoň jednou, uvažujte oba případy). Nalezněte takovou túru (permutaci měst), aby délka ujeté cesty byla co nejmenší. Navrhněte a implementujte algoritmus řešící problém obchodního cestujícího (TSP). Funkčnost algoritmu ověřte na sadě dodaných testovacích příkladů.

Poznámka
K řešení jsem zvolil metodu simulovaného ochlazování, která řeší problém pro navštívení všech měst právě jednou, druhá varianta není uvažována

Simulované ochlazování

Metoda simulovaného ochlazování je jednou ze základních iterativních metod pro řešení NPO problémů. Její podstata spočívá v postupném "snižování teploty", přičemž teplota ovlivňuje pravděpodobnost přijmutí nového stavu zhoršujícího optimalizační kritérium současného řešení. Tedy pokud je teplota vysoká, pravděpodobnost akceptace stavu, který má horší optimalizační kritérium než současný stav je vyšší, než pokud je teplota nízká. Základní schéma algoritmu simulovaného ochlazování je následující:

//hlavní cyklus
state = initial_state;	//pocatecni stav
t = t0;			//pocatecni teplota
do {
  do {
    state = try(state, t);
  } while (! equilibrium(state, t, ...) );
  t = cool(t);
} while (! frozen(t, ...) );

//nalezení dalšího stavu
try(state, t) {
  new = random_neighbourhood(state);
  delta = cost(new) - cost(old);
  //zlepseni ci pripustne zhorseni
  if ( (delta < 0) || (random() < exp(-delta/t)) )
    return new;
  return state;
}

Ze schématu je jasné, že metoda je rozsáhle parametrizovaná, a to jak použitými algoritmy, tak počátečními podmínkami. V následujících odstavcích naleznete mojí implementaci pro řešení TSP.

Nalezení počátečního stavu

Metoda simulovaného ochlazování vychází z předpokladu, že počáteční stav je řešením daného problému, a proto není sestavení počátečního řešení zcela triviální - je to problém nalezení libovolné Hamiltonovské kružnice (kružnice procházející všemi městy právě jednou) v zadaném grafu. Výsledné řešení je také na volbě počátečního stavu závislé, ale špatná volba počáteční řešení lze "dohnat" zvýšením počáteční teploty, což nám umožní dostat s z lokálního minima, které počáteční řešení může představovat. Proto bylo mou snahou nalézt libovolné počáteční řešení, nikoliv jeho optimalizace.

Algoritmus pro nalezení Hamiltonovské kružnice je všem (alespoň těm kteří řeší tuto úlohu) relativně známý, proto jen stručně (mou konkrétní implementaci naleznete v přiloženém zdrojáku). Základem algoritmu jsou následující funkce:

• Prodloužení - k existující cestě je přidáno další město, tedy spojení posledního města na cestě s některým z měst, které v cestě nejsou zahrnuty
• Uzavření - spojení posledního města na cestě s městem prvním; provádí se, pokud jsou již všechna města obsažena v cestě
• Modifikace - změna koncového města aktuální cesty; z města pokud z města i na aktuální cestě existuje cesta do koncového (end) města této cesty, pak lze provést přepojení tak, že následníkem města i je end a poté se cesta "vrací" k městu i+1, které se stane novým koncovým městem
      stará cesta:   a ->...-> i -> i+1 ->...-> end-1 -> end
      nová cesta:   a ->...-> i -> end -> end-1 ->...-> i+1
  Při modifikaci lze předcházet volbě nesprávného koncového města zakazováním jeho volby. Při volbě města i je pak testováno, jestli potenciální koncové město i+1 není zakázané (využití viz dále).

Tyto funkce jsou používány ve třech fázích algoritmu:

• Iniciace je volba počátečního města kružnice; případné nalezení či nenalezení řešení není na této volbě závislé
• Prodlužování se provádí, dokud nejsou všechna města zahrnuta do cesty; spočívá v postupném prodlužování cesty a případné modifikaci, pokud z aktuálního koncového města neexistuje cesta do žádného z "nepoužitých" měst (měst, které se na cestě nenacházejí). Pokud z daného koncového města nelze prodloužit, ani nalézt modifikaci, pak Hamilt. kružnice neexistuje.
  Cyklické modifikaci lze snadno zabránit označením města, ze kterého nelze prodloužit za zakázané - množina nepoužitých měst se postupně zmenšuje, takže k případnému povolení daného města nemůže dojít.
• Uzavírání se provádí, pokud cesta již obsahuje všechna města; spočívá ve střídání volání funkcí Uzavři a Modifikuj - po úspěšném uzavření jsme nalezli Hamiltonovskou kružnici, pokud není možna modifikace, Hamilt. kružnice neexistuje.
  Cyklické modifikaci lze opět zabránit zakázáním měst, ze kterých nelze uzavřít (tedy nemají cestu do počátečního města).

Daný popis by měl stačit k pochopení principu algoritmu. Je z něj též patrná případná "parametrizace" algoritmu - volba počátečního měst a algoritmus výběru měst pro prodložení a modifikaci. Já jsem volil cestu nejjednodušší - počátečním městem je město 0 a algoritmus výběru je jednoduchý cyklus procházející postupně všechna města (0..count-1)

Vylepšování řešení simulovaným ochlazováním

Již z popisu algoritmu simulovaného ochlazování je zřejmé, že i zde je výrazná možnost "parametrizace" řešení, a to jak volbou parametrů, tak samotnou implementací metod. Proto se postupně zaměřím na všechny části algoritmu

Volba nového stavu (random_neigbourhood)
Nový je z existujícího stavu tvořen tzv. dvojzáměnou (překřížením), kdy jsou náhodně vybrána města i a j, u kterých existují spojení i->j a i+1->j+1 a platí i<j-1. Pokud je taková dvojice nalezena, provedene se překřížení, tedy spojení i->i+1 nahradí i->j, poté je cesta vedena proti původnímu směru do města i+1, kde je přidána cesta i+1->j+1, čímž zaniká cesta j->j+1. Pro pochopení ještě schéma obou cest
    stará cesta:   a ->...-> i -> i+1 ->...-> j -> j+1 ->...-> a
    nová cesta:   a ->...-> i -> j ->...-> i+1 -> j+1 ->...-> a

Rovnováha vniřního cyklu (equilibrium)
rovnováhy je dosaženo, pokud počet iterací uvnitř cyklu překročí zadanou mez
return iterCount > maxIter;

Rozvrh ochlazování (cool)
teplota je snižována exponenciálně násobením koeficientem alfa
return t * alfa;

Bod zamrznutí (frozen)
teplota klesne pod zadanou hranici
return t < tMin;

Ze zadaného popisu vyplývá, že jsem zvolil nejjednodušší implementaci algoritmu simulovaného ochlazování, ale i ta má možnost nastavení čtyřech parametrů, což je pro testování více než dostatečné. Vstupní parametry mého algoritmu tedy jsou:

• počáteční teplota (t0)
• teplotní koeficient (alfa)
• teplota bodu mrazu (tMin)
• počet iterací ve vnitřním cyklu (maxIter)

Výstupem je délka výsledné cesty a počet iterací potředný k dosažení výsledku.

Implementaci algoritmu naleznete ve zdrojáku. Je umožněno i opakované spouštění s různým nastavení parametrů a výstupem do "tabulky" - výstupního souboru.

Výsledky testů na zkušebních instancích

Nejlepší dosažená řešení

Testik - test parametrů

První část testu zachycuje závislost kvality řešení na počtu iterací (při snižování bodu mrazu, ale i mírné změně ostatních parametrů). Část druhá se naopak snaží zachytit závislost kvality řešení na nastavení parametrů při "konstantním" počtu iterací. Výsledky shrnuje následující tabulka, délka řešení představuje průměr z 5-ti pokusů.
Instance Testik byla zvolena pro její malou velikost a tím vyšší rychlost řešení, která umožnila provést více testů.

První část potvrzuje relativně velkou (a samozřejmě očekávanou) závislost kvality řešení na počtu iterací. Je jasné, že při přibližování se optimálnímu řešení se rozdíly ve kvalitě snižují, ale snižuje se též rozptyl hodnot jednotlivých měření - zvyšuje se zaručení přesnosti řešení.

Druhá část prokazuje, že počáteční teplota by neměla být volena příliš vysoká - umožňuje to vzdálit se optimálnímu řešení výrazným zhoršením, které pak již není možno při nižších teplotách překonat zpět. Mnohem výhodnější se ukazuje volba v podstatě konstantní teploty - stačí relativně nízká počáteční hodnota a její jen mírné snižování.
Je zřejmé, že na kvalitě řešení se nejvýrazněji projevuje celkový počet iterací (ne však lineárně, jak již bylo uvedeno), pokud ovšem neuvažujeme extremní nastavení parametrů metody.
Je však nutno upozornit, že tento závěr je velmi závislý na konkrétní instanci a též na počátečním řešení.

Obecně by se dalo shrnout, že mnohem výhodnější než zvyšování počtu iterací se jeví vícenásobné spuštění řešení a posléze výběr nejlepšího řešení. Ani vysoký počet iterací totiž kvalitní řešení nemusí zajistit.

A - test parametrů

Jako zajímavou pro testování jsem uznal i instanci A, která svojí velkou velikostí neumožňuje zvyšovat počet iterací - pro velký počet je řešení velmi časově náročné. Následující tabulka shrnuje výsledky mých měření

Z výsledků je patrné, že pro tuto instanci se při nízkém počtu iterací jako nejvýhodnější jeví rychlé ochlazení počáteční relativně vysoké teploty. Závislost kvality na počtu iterací se samozřejmě projevuje také.
Je ale nutné upozornit, že testy nebyly prováděny opakovaně a proto je možný znatelný projev náhodnosti v jednotlivých výsledcích.

Závěr

Má implementace simulovaného ochlazování řeší problém obchodního cestujícího s navštívením všech měst právě jednou. Výsledky jsou samozřejmě závislé na zadaných vstupních parametrech, výsledky testů naleznete v předchozí části.

Zdrojový soubor (v C++) naleznete zde.