2. Nesystematické prohledávání stavového prostoru
Datum poslední aktualizace: 22. 2. 2023
Editace a obsah (poslední úpravy): L. Smítková Janků
Úvod
V rámci této úlohy si student zvolí a implementuje JEDNU metodu nesystematického prohledávání stavového prostoru pro řešení JEDNÉ ze dvou nabízených úloh:
- Symetrický obchodní cestující (TSP)
- Problém N královen na šachovnici (N-královen, N-Queens)
Na vybranou úlohu můžete aplikovat některou z následujících metod nesystematického prohledávání:
- genetický algoritmus (GA)
- hill-climbing algoritmus (HC)
- simulované žíhání (SA)
- jiná metoda nesystematického prohledávání stavového prostoru
Celkem se tedy nabízí 8 variant, ze kterých si mohou studenti zvolit. Pro varianty 1+A (tedy TSP pomocí GA) jsou připraveny šablony, které může student využít. Užití šablony není povinné. Student může k implementaci řešení zvolit programovací jazyk dle vlastního výběru.
Symetrická úloha obchodního cestujícího (Symetric Travelling Salesman Problem, TSP)
Je dána množina měst W a matice C vzdáleností mezi dvojicemi měst z W. Úkolem obchodního cestujícího je projít těmito městy a následně se vrátit do výchozího města s minimálními výdaji na cestu a zároveň navštívit každé město právě jednou.
Předpokládejte, že úloha je formulována v Euklidovském prostoru, matice C vzdáleností mezi městy je symetrická, tj. platí c(i,j) = c(j,i) (tj. cestující může mezi městy cestovat oběma směry), a platí trojúhelníková nerovnost c(i,k) < c(i,j) + c(j,k) pro všechna i, j, k z W.
S využitím aparátu teorie grafů může být úloha formulována následovně: nechť G = (V,A) je neorientovaný graf. V označuje množinu vrcholů grafu, tyto vrcholy reprezentují města. A je množina hran s nezápornými ohodnoceními, která odpovídají prvkům matice C vzdáleností mezi městy. Úkolem je v daném grafu nalézt nejkratší kružnici, která prochází všemi vrcholy právě jednou (Hamiltonovské kružnice).
Problém N královen na šachovnici
Je dána šachovnice velikosti NxN a N královen. Královna je velmi silná figurka, může ohrozit jinou figurku horizontálně, vodorovně nebo diagonálně. Úkolem v této úloze je rozmístit královny na dané šachovnici tak, aby se vzájemně neohrožovaly. Základní zadání je pro velikost šachovnice N=8 a stený počet královen. Svoje algoritmy ale implementujte pro obecné N a vyzkoušejte, zda umíte úlohu vyřešit například pro N=10, N=20 nebo N=100.
Varianty 1+A a 2+A: TSP nebo N-královen pomocí genetického algoritmu
Zadání: Navrhněte a implementujte řešení problému obchodního cestujícího pomocí genetického algoritmu.
Dílčí úkoly:
- Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen
- Navrhněte a implementujte vhodnou metodu pro inicializaci algoritmu
- Implementujte zvolenou metodu selekce
- Navrhněte a implementujte operátor křížení
- Navrhněte a implementujte operátor mutace
- V závislosti na zvoleném kódování problému implementujte opravný operátor (tj. implementujte opravný operátor tehdy, je-li zvoleno takové kódování problému, že je opravný operátor potřeba).
PROGRAMOVACÍ JAZYK PRO IMPLEMENTACI ÚLOHY SI VOLÍ STUDENT.
Pro úlohu TSP (varianta úlohy 1+A) je připravena šablona v C++.
Šablona - vizualizace činnosti genetického algoritmu pro úlohu TSP v QT, kterou se můžete nechat inspirovat vizualizace_šablona
V šabloně je implemntováno načtení dat ze souboru csv a jejich kódování, hlavní evoluční cyklus, a dále v ni najdete hlavičky funkcí, do jejichž těla je třeba zapsat potřebné implementace výpočtu fitness a operátorů.
!!!Pokud nebudete používat šabonu, nemusíte implementovat načtení dat z CSV. Postačuje nadefinování matice vzdáleností měst přímo v programu.!!!
Studenti implementují:
- výpočet fitness
- operátor křížení OX
- operátor křížení PMX
- operátor mutace dle vlastního výběru
- selekci
Můžete implementovat jako bonus:
- vylepšení vizualiace
- ERX operátor a odpovídající úpravy náhrady populace
Překlad a spuštění je popsáno v readme. Kód vypisuje do terminálu hodnotu fitness jedince s nejlepší fitness v populaci.
Použití šablony není vyžadováno.
Kromě šablony lze použít vzorový program pro vizualizaci v QT. Tento program umí vizualizovat jedince v populaci v každém kroku. Počet zobrazovaných jedinců je omezen.
Varianty 1+B a 2+B: TSP nebo N-královen pomocí algoritmu Hill-Climbing
Zadání: Navrhněte a implementujte řešení problému obchodního cestujícíco pomocí hill-climbing algoritmu.
Dílčí úkoly:
- Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen pro řešení pomocí hill-climbing algoritmu
- Navrhněte účelovou funkci
- Definujte různé varianty okolí daného stavu
- Implementujte metodu na enumeraci stavů v definovaném okolí
- Implementujte nějakou metodu na únik z lokálního extrému například restarty
Pro cvičení je připravena šablona.
Použití šablony není vyžadováno. Rozhodnete-li se implementovat algoritmus bez šablony, zajistěte vizualizaci průběhu algoritmu v terminálu.
Varianty 1+C a 2+C: TSP nebo N-královen pomocí simulovaného žihání
Zadání: Navrhněte a implementujte řešení problému obchodního cestujícíco pomocí algoritu simulovaného žíhání.
Dílčí úkoly:
- Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen pro řešení pomocí metody simulovaného žíhání.
- Navrhněte účelovou funkci
- Implementujte pravděpodobnostní schéma pro přijmutí horšího stavu než je aktuální stav
- Implementujte schéma snižování teploty
Pro tuto metodu není připravena šablona.
Doporučená literatura k úloze 2
[1] Mausam: Slidy k přednášce o lokálním prohledávání z Univerzity ve Washingtonu PDF
[2] Miloš Hauskrecht: Slidy k přednášce o lokálním prohledávání z Univerzity v Pittsburghu PDF
[3] přednášky BI-ZUM (najdete v nich pseudokódy algoritmů)
[4] Norvig, Russel: Artificial Intelligence: A Modern Approach, PDF
[5] pseudokódy ke kapitolám z dané knihy http://aima.cs.berkeley.edu/algorithms.pdf