Úvod do algoritmov umelej inteligencie #2 - TabuSearch

Horolezecký algoritmus (HillClimb) si vyberá z rôznych možností tú najlepšiu a postupuje podľa nej. Niekedy sa však môže stať, že sa pri opakovanom výbere možností/susedov môžeme "zacykliť". Takéto zacyklenie si môžeme predstaviť napríklad tak, že sa opakovane dostaneme na to isté miesto v labyrinte. Možno naozaj potrebujeme trochu cúvnuť a hľadať inú cestu.

‍

Pozrime sa napríklad na tento labyrint. V jednom bode sa dostaneme do cyklu, z ktorého už nedokážeme vyjsť. Ak si túto križovatku označíme za zakázanú, náš algoritmus zrazu dokáže nájsť riešenie.

Tento algoritmus teda potrebuje ukladať už navštívené riešenia, aby zamedzil ich opakovaniu.

Múdre reči

Teraz by sme mohli začať vyťahovať múdre slovíčka… to ale robím nerád. Detaily sú v tomto prípade nepodstatné a tento algoritmus asi v živote nebudete potrebovať. Ale môžete sa sami zamyslieť nad otázkami:

• Koľko položiek môžem držať v tabu zozname?
• Majú položky v tomto zozname nejakú časovú expiráciu?
• Potrebujem si pri mojom konkrétnom probléme pamätať viac ako len stav? (napríklad počet krokov k danému bodu, čas, iné parametre)

Algoritmus

Poďme si teda spísať náš algoritmus

1. Vytvorme si jedno náhodné riešenie s
2. Vytvorme si zoznam zakázaných riešení tabu
3. Kým nie sme spokojný s riešením s
4. neighbors = susedia aktuálneho riešenia s
5. z neighbors odstránime všetky riešenia, ktoré sa nachádzajú v tabu zozname
6. s = najlepšie riešenie z neighbors
7. pridaj s do tabu zoznamu

Ak si z tohto algoritmu odstránime všetky riadky s textom tabu, dostaneme opäť horolezecký algoritmus 🙂

Praktický problém - 8 dám

Tento problém je mojim najobľúbenejším problémom pre štúdium optimalizačných algoritmov. Jeho znenie je nasledovné: "Na šachovnicu 8x8 rozmiestnite 8 dám tak, aby sa žiadna dvojica dám navzájom neohrozovala" Takýchto riešení je 92 a k prvému riešeniu sa vieme dostať pomerne rýchlo jednoduchou brute-force metódou.

Jedným z týchto riešení je toto:

Teda si toto riešenie vieme reprezentovať ako vektor (pole) veľkosti 8 s indexami riadkov [5, 3, 1, 7, 4, 6, 0, 2] (prvý stĺpec má dámu na 5-tom riadku, druhý na 3-ťom…) Odporúčam však tento problém riešiť aspoň pre 10 dám na šachovnici 10x10. Vtedy uvidíte reálne rozdiely v rýchlosti výpočtu. Toto číslo si označme ako n

Skúsme teda nájsť riešenie pomocou algoritmu tabu search:

1. Vytvorme si náhodné riešenie(1) a tabu zoznam(2):

var solution = randomSolution()
val tabu = mutableListOf<Solution>()

2. Podmienka ukončenia (3) bude nájdenie prvého správneho riešenia (minimalizujeme cenu riešenia cost = počet kolízií medzi kráľovnami):

while (cost(solution) != 0) {}

3. Vytvoríme si n susedov(3a), každý z nich je kópiou pôvodného ale hodnotu na i - tom indexe posunieme jeho hodnotu o + 1.

val neighbors = (0 until n).map { column ->
    val neighbor = solution.copyOf()
    neighbor[column] = (neighbor[column] + 1) % n
    neighbor
}

           3b. Vyfiltrujeme susedov podľa tabu zoznamu.

val filterredNeighbors = filter(neighbors, tabu)

           3c. A vyberieme najlepšieho z nich.

solution = filterredNeighbors.minByOrNull{cost(it)}!!

           3d. Nakoniec aktualizujeme tabu zoznam a sme s algoritmom hotoví.

tabu.add(solution)‍

Celý funkčný program vrátane cost funkcie v jazyku Kotlin.

Poznámka pod čiarou

Pre veľkosť šachovnice 10x10 som pomocou bruteforce metódy našiel riešenie v priebehu 60 sekúnd. TabuSearch metóda zaberala približne 1.5 - 3 sekundy.

Skúste sa zamyslieť, prečo HillClimb nie je správnou voľbou pre riešenie tohto problému a či je TabuSearch vhodný aj pre riešenie šachovnice 20x20.

Ak ste správne uhádli, že TabuSearch problém 20x20 nevyrieši, nabudúce si ukážeme ďalšiu metódu, ktorá to zvládne. Hurá na simulované žíhanie.