Warning
This page is located in archive. Go to the latest version of this course pages.

Domácí úloha 1: Problém obchodního cestujícího

Vážení studenti, tato stránka a úloha je nová a není tudíž odladěna na vašich předchůdcích. Pokud by se vám cokoli nezdálo, něco nebylo jasné, nebo něco chybělo, pište ihned na petr.posik@fel.cvut.cz. Díky!

Jsme ve stavu, kdy bychom měli mít implementovány algoritmy lokálního prohledávání a evoluční algoritmus pro problémy s binární a reálnou reprezentací. Cílem 1. domácí úlohy je vyzkoušet tyto algoritmy na problému obchodního cestujícího.

TSP

Problém obchodního cestujícího je problém nalezení nejkratší hamiltonovské kružnice v grafu, jinými slovy problém nalezení nejkratší cesty, která zajistí, že navštívíte všechna místa a vrátíte se zpět do místa, z něhož jste vyrazili.

Různé instance problému

TSP není jediný problém, ale celá třída problémů. Instance se liší tím, kolik míst je třeba projet, a jaké jsou vzdálenosti mezi místy. Instance tedy bývá zadána buď maticí vzdáleností mezi místy, nebo souřadnicemi míst v nějakém metrickém prostoru.

My se soustředíme na symetrické instance (cesta z A do B stojí stejně jako cesta z B do A) z knihovny problémů TSPLIB.

Povinné minimum

Reprezentace

Existuje mnoho reprezentací potenciálních řešení tohoto problému, ale tou nejpřirozenější je asi permutace čísel, která určuje pořadí, v němž místa navštívíte. Zvolte reprezentaci, kterou budete používat.

Inicializace řešení

Vytvořte funkci, která bude umět vytvořit náhodné kandidátské řešení. Toto řešení by mělo být přípustné, tj. mělo by se jednat o platnou permutaci míst (každé by se mělo vyskytnout právě jednou).

Účelová funkce

Vytvořte účelovou funkci, pomocí níž bude možné kandidátské řešení ohodnotit. Měla by využít údaje z matice vzdáleností.

Perturbační/mutační operátor

Vytvořte funkci, která bude mutovat řešení. Výsledkem mutace by mělo být opět platné řešení. Smysluplných mutačních operátorů existuje víc. Implementujte alespoň jeden. Promyslete si:

  • Přesun jednoho místa v sekvenci na jiné.
  • Prohození 2 míst.
  • Převrácení úseku cesty mezi dvěma místy.

Lokální prohledávání

Máte-li vše vhodně naimplementované, mělo by být možné vzít váš algoritmus lokálního prohledávání, poskytnout mu účelovou funkci, inicializační proceduru a mutační operátor a měli byste mít funkční TSP solver. Zkuste jej aplikovat na TSP úlohy, zaznamenávejte si výsledky (nebo lépe, zaznamenávejte si celý časový průběh).

Operátor křížení

Opět existuje více smysluplných operátorů křížení pro TSP. Efektivní operátor křížení ale vyžaduje jisté přemýšlení. Jeho výsledkem by opět mělo být přípustné řešení. Implementujte alespoň jeden. Možnosti:

  • Cycle xover.
  • Order xover.
  • Partially matched xover.
  • Edge recombination xover.

Inspiraci pro operátory křížení můžete najít třeba v článcích naween2013crossoversfortsp.pdf nebo puljic2013crossoversforvrp.pdf.

Evoluční algoritmus

Nyní byste měli mít k dispozici všechny části EA pro TSP. Mělo by stačit EA správně nakonfigurovat a spustit. Zkuste jej aplikovat na různé TSP úlohy a porovnejte ho s výsledky lokálního prohledávání.

Úkoly nad minimální požadavky

Vizualizace

Implementujte funkci, jak si graficky znázornit řešení TSP problému. Ideální by bylo, kdybyste mohli průběh optimalizace sledovat, tj. vidět, jak se postupně nejlepší dosud nalezené řešení vylepšuje.

Memetický algoritmus

O memetických algoritmech jsme se dosud nezmiňovali. Dalo by se říct, že každý EA, který je nějak zkombinován s lokálním prohledáváním, je memetický algoritmus.

Možností, jak EA zkombinovat s LS, je opět víc:

  • Místo náhodně inicializované populace kandidátů poskytnout EA populaci náhodných kandidátů, kteří ale všichni prošli vylepšením pomocí LS.
  • Některé nebo všechny kandidáty vygenerované v průběhu EA vylepšit pomocí LS.
  • Apod.

Pokuste se nějaký memetický algoritmus sestavit a porovnat jej s LS a EA.

Konstruktivní heuristiky

TSP obvykle nebývá tak úplně black-box problém, protože obvykle známe matici vzdáleností mezi místy. To nám umožňuje použít různé konstruktivní heuristiky k rychlému nalezení poměrně dobrého řešení. Tato řešení se opět dají použít pro inicializaci populace EA.

Zkuste nějakou konstruktivní heuristiku vytvořit a použít ji

  1. jako samostatný solver a/nebo
  2. jako metodu pro inicializaci populace EA.

Porovnejte výsledky obou metod, tj. zjistětě, o kolik byl EA schopný ještě vylepšit řešení nalezená pomocí konstruktivní heuristiky.

Úplné prohledávání

Zajímavým experimentem by mohlo být srovnání s úplným prohledáním prostoru možných cest. Velikost prostoru velmi rychle roste a brzy narazíte na limit počtu míst TSP, který jste schopni zvládnout. Pokud nebudete schopni řešit ani nejmenší instance z TSPLIB, zkuste si nagenerovat své, menší.

Úplné prohledání vyžaduje způsob, jak systematicky vygenerovat všechna přípustná řešení. I u něj se ale dá sestavit graf délky nejkratší dosud nalezené cesty v závislosti na počtu dosud využitých ohodnocení a lze jej tedy porovnat s algoritmy typu LS nebo EA.

Hodnocení

Při hodnocení úlohy vám chceme dát jistou volnost v tom, jak moc se do úlohy chcete ponořit. Část úlohy proto tvoří jisté minimální požadavky, jejichž splněním si zajistíte minimální potřebný počet bodů. Každé další vylepšení vám přinese body navíc, až do maximálního počtu 10 bodů.

Minimální požadavky

Abychom tuto úlohu považovali za splněnou, musíte provést porovnání

  • alespoň 1 typu LS a
  • alespoň 1 typu EA
  • na alespoň 3 instancích TSP z TSPLIBu a
  • stručně a adekvátně tyto algoritmy a výsledky popsat v reportu.

Co odevzdat

DO BRUTE do úlohy DU1 Budete odevzdávat ZIP archiv obsahující

  • zdrojové kódy vaší implementace,
  • README soubor, kde popíšete, jak a co zkompilovat a jak a co spustit, pokud chci získat výsledky algoritmu A na instanci B,
  • stručný report s popisem řešení (viz níže).

Součástí hodnocení může být předvedení funkčnosti implementace na některém cvičení. Pokud jste si pro implementaci vybrali jiný jazyk než Python, Javu, nebo C/C++, bude předvedení funkčnosti povinné.

Očekávaný obsah reportu:

  • Adekvátní popis (nikoli výpis zdrojového kódu) algoritmů a použitých operátorů.
  • Popis nastavení experimentu (jak jste porovnávané algoritmy nastavili, kolik prostředků/času/generací/ohodnocení jste jim na optimalizaci dali, kolik opakovaných pokusů jste dělali, apod.).
  • Smysluplné porovnání algoritmů v tabulkové a grafické formě.
  • Upozornění na příp. nedostatky použité experimentální procedury.
  • Explicitní seznam věcí realizovaných nad rámec minimálních požadavků s odkazy na místa ve vašich kódech, kde jejich implementaci nalezneme, a návrh jejich bodového hodnocení.

Bodování

Za úlohu můžete získat maximálně 10 bodů.

Bodů Za co
5 Za splnění minimálních požadavků.
+1 Budou-li v porovnání alespoň 3 LS s různými perturbacemi.
+1 Budou-li v porovnání alespoň 2 EA s různými operátory křížení.
+1 Porovnání na 10 a více instancích.
+1 Vizualizace průběhu optimalizace.
+1 Za memetický algoritmus.
+1 Za použití konstruktivní heuristiky a porovnání s ní.
+1 Za porovnání s dalším typem algoritmu jiným než LS nebo EA.
courses/a0m33eoa/du/du1.txt · Last modified: 2018/10/23 13:51 by xposik