Zenová záhrada
Zadanie č. 2a
Úloha
Zenová záhradka je plocha vysypaná hrubším pieskom (drobnými kamienkami). Obsahuje však aj nepohyblivé väčšie objekty, ako napríklad kamene, sochy, konštrukcie, samorasty. Mních má upraviť piesok v záhradke pomocou hrablí tak, že vzniknú pásy ako na nasledujúcom obrázku.
Pásy môžu ísť len vodorovne alebo zvislo, nikdy nie šikmo. Začína vždy na okraji záhradky a ťahá rovný pás až po druhý okraj alebo po prekážku. Na okraji – mimo záhradky môže chodiť ako chce. Ak však príde k prekážke – kameňu alebo už pohrabanému piesku – musí sa otočiť, ak má kam. Ak má voľné smery vľavo aj vpravo, je jeho vec, kam sa otočí. Ak má voľný len jeden smer, otočí sa tam. Ak sa nemá kam otočiť, je koniec hry. Úspešná hra je taká, v ktorej mních dokáže za daných pravidiel pohrabať celú záhradu, prípade maximálny možný počet políčok. Výstupom je pokrytie danej záhrady prechodmi mnícha. Pokrytie zodpovedajúce presne prvému obrázku (priebežný stav) je napríklad takéto:
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 8 | 9 |
| 0 | 0 | 1 | 0 | 0 | K | 0 | 0 | 10 | 10 | 8 | 9 |
| 0 | K | 1 | 0 | 0 | 0 | 0 | 0 | 10 | 10 | 8 | 9 |
| 0 | 0 | 1 | 1 | K | 0 | 0 | 0 | 10 | 10 | 8 | 9 |
| 0 | 0 | K | 1 | 0 | 0 | 0 | 0 | 10 | 10 | 8 | 9 |
| 2 | 2 | 2 | 1 | 0 | 0 | 0 | 0 | 10 | 10 | 8 | 9 |
| 3 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | K | K | 8 | 8 |
| 4 | 3 | 2 | 1 | 0 | 0 | 0 | 0 | 5 | 5 | 5 | 5 |
| 4 | 3 | 2 | 1 | 0 | 0 | 0 | 11 | 5 | 6 | 6 | 6 |
| 4 | 3 | 2 | 1 | 0 | 0 | 0 | 11 | 5 | 6 | 7 | 7 |
Úlohu je možné rozšíriť tak, že mních navyše zbiera popadané lístie. Listy musí zbierať v poradí: najprv žlté, potom pomarančové a nakoniec červené. Príklad vidno na obrázku nižšie. Listy, ktoré zatiaľ nemôže zbierať, predstavujú pevnú prekážku. Fitness funkcia ostáva rovnaká.
Zadanie
Uvedenú úlohu riešte pomocou evolučného algoritmu. (Je možné použiť aj ďalšie algoritmy, ako sú uvedené v probléme obchodného cestujúceho.) Maximálny počet génov nesmie presiahnuť polovicu obvodu záhrady plus počet kameňov, v našom príklade podľa prvého obrázku 12+10+6=28. Fitnes je určená počtom pohrabaných políčok. Výstupom je matica, znázorňujúca cesty mnícha. Je potrebné, aby program zvládal aspoň záhradku podľa prvého obrázku, ale vstupom môže byť v princípe ľubovoľná mapa.Náčrt algoritmu
Jedná sa o klasický genetický algoritmus, takže na začiatku, po načítaní rozmerov záhrady a pozícií kameňov, sa vytvorí prvá generácia jedincov s náhodne nastavenými génmi. Potom sa všetky jedince ohodnotia, teda pre každého jedinca sa vytvorí matica s prechodmi mnícha a zistí sa, koľko políčok sa podarilo pokryť. Na základe ohodnotenia sa vyberú jedince na tvorbu novej generácie – kríženie a takto vytvorení jedinci môžu s určitou pravdepodobnosťou aj mutovať. Vytvorí sa tak nová generácia a to sa vykonáva dokola, až kým sa nepodarí pokryť všetky políčka alebo sa dosiahne stanovený počet nových generácií.Pre gény je najvhodnejšie, keď reprezentujú priamo miesto na obvode záhrady, kde mních vstúpi (ak môže) a začne hrabať. Zvyšné gény môžu reprezentovať rozhodnutia mnícha, či sa pri najbližšej možnosti voľby dá vpravo alebo vľavo.
Vstupom sú rozmery záhrady a súradnice kameňov, výstupom je mapa pohrabanej záhrady, podobne ako na druhom obrázku. (Kamene môžu byť napríklad –1.)
Použite aspoň dve rôzne metódy výberu jedincov.
Tu je ukážka, ako sa mení pravdepodobnosť výberu zvoleného jedinca od počtu jedincov v turnaji. Pri dvoch jedincoch je závislosť lineárna (tak ako pri selekcii ohodnotením). Viac ako troch jedincov v turnaji zvyčajne nepoužívame, lebo je príliš malá šanca, že sa vyberie nejaký jedinec zo slabšej polovice generácie.
