Skúška z prednášky "Evolučné algoritmy" bude udelená na základe vypracovanej "case study" z oblastí uvedených nižšie. "Case study" je písomná práca v rozsahu približne 7-10 strán (page size A4, font size 10, line spacing single), obsahuje teoretický popis použitej metódy a získané numerické výsledky, ktoré sú ilustrované tabuľkami a grafmi. Integrálnou prílohou "case study" bude aj fungujúci program, pomocou ktorého bola vypracovaná jej aplikačná časť.

Téma 1. Horolezecký algoritmus pre funkciu f(x) definovanú v

pre xÎ [-10,10]. Premenná x je binárne reprezentovaná tak v štandardnom kódovaní, ako aj v Grayovom kódovaní. Pokúste sa optimalizovať parametre c₀ a P_mut tak, aby ste skoro so 100% istotou dostali globálne minimum s čo najmenším počtom iteračných krokov.

Téma 2. Metóda zakázaného hľadania aplikovanú na TSP (riešenie obchodného cestujúceho), pričom cesta nech je vyjadrená pomocou permutácie. Transformačné operátory tÎ S sú realizované ako permutácie transpozícií dvoch objektov. Operátor t_ij pôsobí na permutáciu P ako transpozícia objektov i a j,

pre i<j. Ako testovací príklad použite ortogonálnu mriežku bodov - miest, kde sa vzdialenosť počíta pomocou Hammingovej metriky (pozri príklad 8.2). Pokúste sa o optimalizáciu veľkosti "s" zakázaného zoznamu T (tabu listu) a maximálneho počtu iterácií time_max pre rôzne hodnoty N dimenzie ortogonálnej mriežky bodov, N=4,5,...,10, tak , aby ste s 95% pravdepodobnosťou dostali korektný výsledok. Podobné úvahy vykonajte aj pre suboptimálne výsledky, ktoré sa líšia len niekoľko málo jednotiek od optimálneho výsledku.

Téma 3. Metóda zakázaného hľadania aplikovaná na úlohu N dám na šachovnici. Hľadá sa také umiestnite N dám na šachovnici N´ N tak, aby v každom riadku, stĺpci a diagonále bola umiestnená práve jedna dáma (t.j. neexistuje kolízne postavenie medzi dámami). Zložitosť riešenia tohto problému silne závisí od zvolenej reprezentácie postavenia dám na šachovnici. Jednoduchá reprezentácia postavenia dám je pomocou permutácie P=(p₁, p₂, ..., p_N). Potom dámy na šachovnici sú umiestnené takto: v 1. stĺpci na p₁-tom riadku, v 2. stĺpci na p₂-tom riadku, atď. Táto jednoduchá reprezentácia rozmiestnenia dám na šachovnici pomocou permutácií má výhodu v tom, že v každom stĺpci a riadku šachovnice sa nachádza práve jedna dáma. Každej permutácii N objektov priradíme celé nezáporné číslo col(P), ktoré odpovedá počtu diagonálnych kolízií. Riešenie problému je potom taká permutácia P, ktorá má nulový počet kolízií, col(P)=0. Funkcia col(P) je určená vzťahom

kde d (i,j) je Kroneckerovo delta, d (i,j)=1, pre i=j, d (i,j)=0, pre i¹ j.

pre xÎ [-10,10]. Premenná x je binárne reprezentovaná tak v štandardnom kódovaní, ako aj v Grayovom kódovaní. Pokuste sa nájsť minimálnu veľkosť populácie a také hodnoty pravdepodobností P_cross a P_mut, aby ste skoro so 100% istotou dostali globálne minimum s predpísaným minimálnym počtom krokov.

Téma 5. Genetický algoritmus pre úlohu obchodného cestujúceho na ortogonálnej štvorcovej mriežke. Použite oba prístupy na kódovanie cesty, tak priamo pomocou permutácie, ako aj pomocou binárneho reťazca (pozri cvičenie 7.1 z kapitoly Kombinatoriálne optimalizačné problémy). Porovnajte efektívnosť týchto dvoch rôznych prístupov.

Téma 6. Genetický algoritmus pre úlohu Number Partitioning Problem. Použite oba prístupy na kódovanie zobrazenia p , tak priamo pomocou N-tice celých čísel, ako aj pomocou binárneho reťazca (pozri cvičenie 7.1 z kapitoly Kombinatoriálne optimalizačné problémy). Porovnajte efektívnosť týchto dvoch rôznych prístupov.

Téma 8. Evolučná stratégia (1+1). Metódu aplikujete na hľadanie globálneho minima funkcie

pre xÎ [-10,10], ktorá je zovšeobecnená pre viacrozmerný prípad takto

Použite pravidlo zmeny s 1/5 úspešnosti a nakreslite graf, kde na vodorovnej osi bude počet generácií a na zvislej aktuálna funkčná hodnota rodiča.

Téma 9. Genetické programovanie: Implementuje genetický algoritmus (pozri algoritmus 3.5) tak, že chromozómy budú určené ako Readove lineárne kódy s ohodnotením vrcholov podľa (5.18-19). Toto ohodnotenie nech je vykonané tak, že syntaktické stromy budú odpovedať Boolovským funkciám (t.j. funkčné vrcholy sú operácia and, or, xor, a not, a terminálové vrcholy sú jednotlivé Boolovské premenné). Účelová funkcia (5.24) nech je rozšírená o pokutový člen, ktorý bude preferovať syntaktické stromy s menším počtom vrcholov

kde a je malá kladná konštanta a symbol |t| vyjadruje počet vrcholov v strome t. Modifikujete napísanú implementáciu tak že bude odpovedať horolezeckému algoritmu. Porovnajte efektívnosť týchto troch rozdielnych metód pri konštrukcii funkcií, ktoré reprodukujú predpísanú regresnú tabuľku.

Téma 10. Použitie genetického algoritmu na adaptáciu neurónovej siete. Implementujte neurónovú sieť s dopredným šírením signálu, ktorá obsahuje jednu vrstvu skrytých neurónov a so sigmoidálnou prechodovou funkciou. Použitím genetického algoritmu adaptujte túto neurónovú sieť (t.j. váhy a prahové koeficienty) siete tak, aby s čo najmenšou chybou produkovala rôzne Boolovské funkcie, pričom z numerických dôvodov namiesto hodnoty Boolovských premenných 0 a 1 budeme brať 0.1 a 0.9.

Téma 11. L-systém (tvorba "kríka") je daný nasledovnými pravidlami: (1) štartovný bod F, (2) produkčné pravidlo F ® F [+F][-F], kde F znamená "nakresli čiaru" (začíname kolmou čiarou z počiatočného bodu so súradnicami 0,0 do koncového bodu so súradnicami 0,10). Symbol [ znamená zapamätať si súradnice koncového bodu a zodpovedajúcu zmenu súradníc

dx= x koncový - x počiatočný , dy= y koncový - y počiatočný

x koncový = x počiatočný + 0.7 (cos(40^o) dx - sin(40^o) dy)

y koncový = y počiatočný + 0.7 (sin(40^o) dx + cos(40^o) dy)

Symbol - znamená otočiť sa doprava (použili sme prepis pre súradnice nového bodu

x koncový = x počiatočný + 0.7 (cos(33^o) dx + sin(33^o) dy)

y koncový = y počiatočný + 0.7 (sin(33^o) dx - cos(33^o) dy)

Vytvorte obrázok trojrozmerného stromčeka, kde jednotlivé vetvy sa nebudú skracovať faktorom 0.7, ale náhodným číslom s gaussovským rozložením pravdepodobnosti so stredom napr. v 0.7, kde aj hrúbka kmeňa sa bude zmenšovať a bližšie vetvy budú vyzerať hrubšie, kde uhly vetiev v priestore tiež budú dané náhodne. Vyskúšajte aj iné produkčné systémy, napr. počet vetiev bude daný náhodným číslom od 2 do 3.

Téma 12. Namodelujte priebehy množstva dravcov a koristi ukázané v nasledujúcich obrázkoch podľa rovníc

dN₁(t)/dt = N₁(r_1- b₁N₂ )

dN₂(t)/dt = N₂(- r₂+b₂N₁

kde N₁(t) je počet kusov koristi (alebo hostiteľa) a N₂(t) je počet kusov dravcov (alebo parazitov) v čase t. Predpokladáme, že za neprítomnosti dravcov sa korisť rozmnožuje rýchlosťou r₁, zatiaľ čo za absencie koristi dravci hynú rýchlosťou r₂. Nech b₁ zodpovedá schopnosti dravcov požierať korisť a b₂ vplyvu množstva koristi (a teda nasýtenia dravcov) na ich rozmnožovanie. Nech r₁= 1.5, b₁=0.1 r₂= 0.25 b₂= 0.01 a N₁(0)= 15 a N₂(0)=20. Znázornite priebeh, nie však pomocou klasického riešenia pomocou diferenciálnych rovníc, ale vytvorením stochastického modelu, kde množstvá dravcov a koristi a ich prírastky/úbytky budú dané celými číslami; v prípade, že zmena nie je vyjadrená celým číslom, berte neceločíselnú časť ako pravdepodobnosť a rozhodnite o zaokrúhlení nahor/nadol na základe porovnania tejto pravdepodobnosti s náhodným číslom z intervalu (0,1) – použite analógiu algoritmov 10.1 a 10.2 z kapitoly o umelom živote. Numericky modelujte a diskutujte pravdepodobnosť zániku jedného či obidvoch druhov v závislosti na počiatočných množstvách jedincov a na ostatných parametroch.

Prvá závislosť ukazuje oscilácie počtu dravcov a množstva koristi v čase, druhý obrázok je trajektóriou sústavy diferenciálnych rovníc (10.4).

Téma 13. Vytvorte program pre animáciu pohybu žubrienok (pozri priložený obrázok), kde veľký kruh je prekážka, "hlavička žubrienok" predstavuje umiestnenie žubrienky v dvojrozmernom priestore a dĺžka a smer chvostíka určujú rýchlosť a smer pohybu žubrienky. Počítačový model sa má riadiť troma základnými vlastnosťami:

Téma 14. Standing Ovation. (Homework from Miching State University, see homepage http://zia.hss.cmu.edu/econ/homework95). Consider the following situation: Agents are seated in an auditorium listening to a brilliant economics lecture. At the end of the talk, after wiping away the tears, the applause begins, and perhaps a standing ovation ensues.

Model, using whatever techniques you desire, the process of a standing ovation.

• Explicitly state your model.
• Summarize any results.
• Suggest some potentially interesting future directions for the model.

Suggest some in nature appearing scenarios that could be usefully modeled using such a process.