5. úloha - řešení problému obchodního cestujícího

Tomáš Kubeš - kubest1
FEL-ČVUT PAA (Problémy a algoritmy) LS 2005

Zadání

Navrhněte a implementujte algoritmus řešící problém obchodního cestujícího. Funkčnost algoritmu ověřte na sadě dodaných testovacích příkladů ve variantách - Neexistující hrany (tzn. hrany s hodnotu '0'):

  1. Hrany existují a mají hodnotu 10.
  2. Hrany existují a mají hodnotu 10000.
  3. Hrany neexistují.

Popis úlohy

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 a vrátit se do výchozího města. Nalezněte takovou túru (permutaci měst), aby délka uražené cesty byla co nejmenší. Vstupem je neorientovaný ohodnocený graf.

Užitý algoritmus

Pro řešení jsem se rozhodl využít algoritmu simulovaného ochlazování. Zvažoval jsem ještě možnost využití genetického algoritmu.

Počáteční řešení

Pro nalezení počátečního řešení jsem užil heuristiku, která by se dala popsat jako zjednodušená varianta Posovy heuristiky. Heuristika zvolí náhodné město a vloží jej na začátek túry. Posléze volí libovolné nevložené město sousedící s posledním a přidá jej do túry. Krok se opakuje dokud lze přidávat města. V případě, že město přidat nelze a nevznikla túra (uzavřená), heuristika z túry vyhazuje již vložená města dokud se jí nepodaří přidat to, na kterém prve ztroskotala. Když vyhazování uspěje, tak opět pokračuje. V případě, že se túru nepodaří nalézt na 500 pokusů, heuristika to vzdá.

Heuristika, se ukázala být nejhorší částí programu. V případě, kdy nebylo možné použít hrany 0, na většině řidších grafů nebyla schopná nalézt řešení. V opačných případech nicméně dodala řešení, se kterým si ochlazování již poradilo. Velmi dobře to bylo vidět na případech, kdy měly neexistující hrany hodnotu 10 000, většinou se je podařilo z řešení úplně vyřadit.

V tomto směru jsem se tedy většinu úloh vyřešil když jsem povolil relaxaci. Vzhledem k tomu, že využitá operace nalezení dalšího stavu dokáže projít celý prostor, dával jsem přednost verzi s 10000 penalizací, kdy se dalo na první pohled a jasně určit zda bylo nalezeno řešení užívající pouze existující hrany.

Nalezení nejbližšího souseda

K hledání nejbližšího souseda jsem použil záměnu dvou "náhodných" hran. Postupuje se následovně. Vygeneruje se množina možných měst i a j. Z této množiny se vybírají náhodní kandidáti. Uvažují se pouze ty dvojice, pro které vedou hrany z [i] do [j] a z [i+1] do [j+1] (viz. obrázek). V případech, kdy hrany existují, ale jsou penalizovány, lze fakticky vybrat jakékoliv hrany. Záleží na teplotě, zda je připuštěno zhoršení. Tato operace se ukázala být při dostatku času poměrně velmi silnou. Bohužel v řidších grafech vyžadovala poměrně více času, než se podařilo systematickým testováním najít vhodné kandidáty.

Parametry

Volba parametrů

Vzhledem k tomu, že nám bylo na přednášce sděleno, že výsledek algoritmu nezávisí na přesném průběhu teploty - tj. velkém počtu malých změn nebo menším počtu větších změn, rozhodl jsem se ochlazovací koeficient 0.97 napevno zakódovat do programu. Volba celkového počtu cyklů je prováděna přes počet iterací v jednom ochlazovacím kroku.

Ostatní parametry lze volně zadávat přes příkazovou řádku a lze je tedy snadno měnit s ohledem na průběh řešení konkrétní instance (viz. níže).

Žíhání

Při zkoumání výsledků jsem si všiml, že se může stát, že algoritmus před "vychladnutím" projde výborným řešením, které ovšem opustí a již se k němu nevrátí nebo po snížení teploty zůstane zablokován v jiném horším lokálním minimu.

Zabudoval jsem proto do programu automatické žíhnutí, které nastane v případě, kdy je zjištěn výskyt takovéhoto lepšího řešení a zároveň program zůstává alespoň 10 kroků (ochlazení) v jednom jiném horším řešení. V takovém případě je teplota prudce zvýšena o ˝ počáteční teploty.

Měření

Nejprve jsem ORIENTAČNĚ dávkově spustil program na všechny úlohy s těmito parametry:

  1. cena neexistující hrany - dle zadání: 10, 10 000 a zakázáno použít
  2. počet iterací k v roku ochlazení: 5000
  3. počáteční teplota: 5000
  4. koncová teplota: 0,001
  5. maximální počet žíhnutí: 5
  6. maximální doba běhu: 10 minut

Následně jsem zkoumal výsledky a posuzoval průběh ochlazování a spouštěl program pro danou instanci s upravenými parametry. Parametry jsou vždy uvedeny u každého řešení

Výsledky

Kompletní soubor .xls s výsledky měření je dostupný v sekci soubory. Jak se ukázalo, pro verzi se zakázaným užíváním neexistujících hran naprosto selhala vstupní heuristika a nedokázala najít počáteční řešení pro žádný graf kromě testovacího testik.txt. Také se ukázalo, že heuristika vždy dodala nejhorší řešení, které si ani při super vysokých teplotách nepodařilo nijak zhoršit.

A

Pro tento graf můj program vyloženě selhal. Počáteční řešení pro verzi 0 nenalezl vůbec.

Pro variantu 10 jsem zkoušel mnoho různých voleb parametrů. Ukázalo se, že nad teplotou 100 se algoritmus potácí na stejné kvalitě řešení - snaží se zhoršit nezhoršitelné počáteční řešení a s chladnutím posléze řešení poněkud zlepšuje. Celkové zlepšení je nicméně doslova nepatrné, protože až do teploty 0.0001 (nejnižší dosažitelná teplota) algoritmus zlepší řešení o 1000, což je při ceně 21000 zanedbatelné.

Při řešení varianty 10 algoritmus opět selhal, navíc se dá, že při nejnižší teplotě již začíná být opravdu vychlazeno a řešení sep řestává zlepšovat.

Pro variantu 10000 se také nebylo možné nalézt řešení v rozumném čase.

Poslední slova byla:
2425000; 0.004; 1597468
2430000; 0.004; 1597468
2435000; 0.004; 1597454

Lze proto usoudit, že se algoritmus přiblížil vychladnutí, aniž by se dobral uspokojivého řešení. Na tento graf se ukázal být můj program krátký.

B

Ani zde (a ani v jakékoliv dalším zadání) se nepodařilo řešit úlohu pro variantu - hrany neexistují, protože heuristika nedokázala najít jakákoliv řešení.

Spuštění se standardními parametry nebylo úplně ideální. Zatímco počáteční teplota pro 10 variantu byla zbytečně vysoká, tak pro 10000 variantu byla příliš nízká. Výsledky pro variantu 10:

Výsledek pro první varinatu je nicméně velmi dobrý, bohužel pravděpodobně díky tomu, že užívá nějaké "penalizované hrany". Pro 1000 se parametry ukázaly nepoužitelné, proto jsem se rozhodl spustit program pro variantu 10000 znovu s novými parametry:

Výsledek je o poznání lepší. DOKONCE JE LEPŠÍ NEŽ VÝSLEDEK UVEDENÝ NA STRÁNKÁCH ZADÁNÍ (3095)! A to v tomto případě můžeme s jistotou říci, že v něm není ani jedna neplatná hrana. Ukázalo se, že řešení dodané heuristikou je tak mizerné, že jej již nelze zhoršit ani při super velké teplotě (která byla možná skoro zbytečně vysoká).

C

Na tomto grafu si můj algoritmus vylámal zuby. Počáteční řešení pro 0 nenašel a průběh řešení pro ostatní varianty byl i pro více pokusů maximálně neuspokojivý a navíc velmi pomalý (viz. log soubory).

D

Opět se ukázalo, že pro 10 variantu mělo standardní nastavení zbytečně vysokou počáteční teplotu. Nicméně nakonec výsledky byly docela uspokojivé.

Pro variantu 10000 bylo třeba opakovat měření se zvýšením počáteční teploty. Opět byla skoro o něco vyšší a opět se ukázalo, že na řešením dodaném heuristikou nebylo již co zkazit.

Zde se ukázala zajímavá věc, ačkoliv algoritmus pracoval výrazně déle od vyšší teploty a s vyšším počtem iterací, nalezl horší řešení než v prvém případě (686). Zde by stálo za to spustit program s různým SEED vícekrát a sledovat jak by se choval. Bohatě by stačila počáteční teplota někde kolem 25000.

E

Ukázalo se, že pro variantu 10 standardní parametry docela vyhovují a vykazovala velmi dobré výsledky. Také zafungoval mechanismus žíhání. V tomto případě nicméně bylo žíhnutí zbytečně veliké (bohatě by stačilo poloviční), nicméně i přesto nakonec algoritmus skončil v nejlepším řešení ze všech tří (viz. xls). Bohužel i zde je podezření na užití neexistujících hran.

Řešení pro variantu 3 dlouho zlobilo. Bylo třeba několikrát opakovat spuštění se zvýšením teploty (nakonec až téměř přílišným) a zvýšením počtu iterací, než bylo dosaženo kloudného výsledku.

Příliš malá teplota. Druhé měření - také příliš malá (není obrázek), třetí měření (dole), konečně dost vysoká teplota.

Po několikerém zvýšení teploty jsem jí na potřetí zvýšil prudce. Je vidět, že díky tomu algoritmus nějakou dobu zbytečně pobíhal v katastrofálních řešení, nicméně posléze vydal rozumné výsledky.

F

Na tomto grafu si můj algoritmus vylámal zuby. Počáteční řešení pro 0 nenašel a průběh řešení pro ostatní varianty byl i pro více pokusů maximálně neuspokojivý a navíc velmi pomalý (viz. log soubory).

G

Na tomto grafu si můj algoritmus vylámal zuby. Počáteční řešení pro 0 nenašel a průběh řešení pro ostatní varianty byl i pro více pokusů maximálně neuspokojivý a navíc velmi pomalý (viz. log soubory).

H

Opět se ukázalo, že pro řešení s variantou 10 je standardní vstupní teplota téměř zbytečně vysoká a způsobuje, že algoritmus dlouho zhoršuje řešení, které již nijak zhoršit nelze. Po vychladnutí nicméně podal docela příjemné výsledky.

Pro variantu 10000 jsme spouštěl algoritmus několikrát, avšak nikdy se nepodařilo z řešení vyhodit penalizovanou hranu.

Po několika pokusech jsem nakonec z výsledků zjistil, že řešení neexistuje.

I

Na tomto grafu si můj algoritmus vylámal zuby. Počáteční řešení pro 0 nenašel a průběh řešení pro ostatní varianty byl i pro více pokusů maximálně neuspokojivý a navíc velmi pomalý (viz. log soubory).

J

Na tomto grafu si můj algoritmus vylámal zuby. Počáteční řešení pro 0 nenašel a průběh řešení pro ostatní varianty byl i pro více pokusů maximálně neuspokojivý a navíc velmi pomalý (viz. log soubory).

K

Pro graf K se nepodařilo najít počáteční řešení pro variantu 0 a varianta 10 trvala neúnosně dlouho. Bohužel ani několikeré spuštění pro variantu 10000 nepřineslo uspokojivé výsledky i pro co nejprecizněji nastavené hodnoty parametrů.

Doba vypoctu 743s
Pocet navstivenych stavu 3025000
Pocet akceptovanych stavu 382620
Pocet akceptovanych zhorseni 2847
Cena = 956 858

Ani po přibližně 12 minutách výpočtu se z počátečního řešení nepodařilo vyházet 95 neexistujících hran. Je možné, že by došlo k drobnému vylepšení řešení, nicméně při teplotě 0.001 a uvedeném průběhu nelze očekávat nějaký razantní zlom. Proto jsem již dále úlohu nezkoumal a usoudil, že s ní si algoritmus poradit neumí.

Soubory

Program jsem napsal v pro gcc a v MinGW přeložil pro Windows. Vzhledem k užitým funkcím by měl být výborně přenositelný.

Závěr

Tato úloha byla obtížná, avšak zajímavá. Ukázalo se, že ačkoliv samotný princi simulovaného ochlazování není nijak složitý, vytvořit správně fungující algoritmus a ručit vhodné parametry pro konkrétní úlohy není vůbec jednoduché.

Jednou z nejproblémovějších částí této úlohy je právě nalezení Hamiltonovy kružnice. Zvláště v řídkých grafech je to problém. Existují propracovanější heuristiky, které by jistě zvládly řešit nějaké případy, kde moje selhala. Doufal jsem, že pokud uplatním relaxaci podmínek a povolím užívat neexistující hrany s penalizací, naleznu nakonec potřebné řešení. V hustších grafech skutečně simulované ochlazování s 10000 penalizací nakonec dokázalo najít túru neobsahující zakázané hrany. Bohužel pro menší penalizaci nebo pro řidší grafy již výsledky nebyly tak uspokojivé a nedařilo se nalézt vhodné řešení.

Navíc se ukázalo, že heuristika dává ukázkově špatná řešení, nikdy se totiž počáteční řešení nepodařilo při vysokých teplotách pokazit. To ukazuje, že skutečně užitá funkce je mizerná a bude jí potřeba vylepšit.

Bohužel se ukázalo, že ani ono hledání dalšího stavu není tak silné, jak jsem si nejprve myslel. Na řidších grafech fungovalo pomalu a nepodávalo rozumné výsledky.