FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

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:

  1. Symetrický obchodní cestující (TSP)
  2. 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í:

  1. genetický algoritmus (GA)
  2. hill-climbing algoritmus (HC)
  3. simulované žíhání (SA)
  4. 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:

  1. Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen
  2. Navrhněte a implementujte vhodnou metodu pro inicializaci algoritmu
  3. Implementujte zvolenou metodu selekce
  4. Navrhněte a implementujte operátor křížení
  5. Navrhněte a implementujte operátor mutace
  6. 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í:

  1. výpočet fitness
  2. operátor křížení OX
  3. operátor křížení PMX
  4. operátor mutace dle vlastního výběru
  5. selekci

Můžete implementovat jako bonus:

  1. vylepšení vizualiace
  2. 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:

  1. Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen pro řešení pomocí hill-climbing algoritmu
  2. Navrhněte účelovou funkci
  3. Definujte různé varianty okolí daného stavu
  4. Implementujte metodu na enumeraci stavů v definovaném okolí
  5. 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:

  1. Navrhněte a implementujte vhodné kódování problému TSP resp. N-královen pro řešení pomocí metody simulovaného žíhání.
  2. Navrhněte účelovou funkci
  3. Implementujte pravděpodobnostní schéma pro přijmutí horšího stavu než je aktuální stav
  4. 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