Témy "case studies" z predmetu "Evolučné algoritmy"

Skúška z prednášky "Evolučné algoritmy" bude udelená na základe vypracovanej "case study" z oblastí uvedených nižšie, z ktorých je možno získať 70 bodov. "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ť.

            Skúška sa uskutoční na UAI FIIT STU v termínoch, ktoré budú ešte upresnené, na skúšku je potrebné sa prihlásiť emailom na adresu pospichal@fiit.stuba.sk

            Každá téma z "case study" bude mocť byť použitá iba jedným študentom, na tému sa treba prihlásiť a postupné "prideľovanie" bude prebiehať podľa pravidla “kto skôr príde..”. Podstatou skúšky bude diskusia o riešenej úlohe a taktiež všeobecné vedomosti z evolučných algoritmov.

Pokiaľ si niekto vymyslí vlastné zadanie, nech mi ho v rtf pošle na odobrenie.

Upozornenie: Záujemci o skúšku pošlú e-mailom aspoň dva dni pred konaním skúšky ako attachment (do 16.00 hod.) vypracovanú "case study" na adresu pospichal@fiit.stuba.sk, a musia sa uistiť, že som ich súbor dostal v poriadku, alebo sa dohodnú na inom spôsobe dodania súboru. Súbor má byť v PDF formáte, pričom "čitateľnosť" súborov nech je prekontrolovaná pomocou AcrobatReader-u. Práce budú vystavené na tejto stránke pre poučenie budúcich generácií.

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 c0 a Pmut tak, aby ste skoro so 100% istotou dostali globálne minimum s čo najmenším počtom iteračných krokov.

(tému vypracuje Martina Prázdnovská, martina.praznovska(at)gmail.com kod_a_pdf_rar)

 

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 tij 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í timemax 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ému vypracuje Tomáš Matúšek matusek(at)chello.sk pdf)

 

Téma 3. Použite genetický algoritmus pre úlohu N dám na šachovnici N´ N. 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=(p1, p2, ..., pN). Potom dámy na šachovnici sú umiestnené takto: v 1. stĺpci na p1-tom riadku, v 2. stĺpci na p2-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. Úlohu riešte aj pre rôzne N > 8 a výsledky štatisticky spracujte.

(tému vypracuje Milan Skuhra, majnet(at)zoznam.sk on-line prezentácia, pdf, program.zip)

 

Téma 4. Genetický algoritmus pre funkciu

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í Pcross a Pmut, aby ste skoro so 100% istotou dostali globálne minimum s predpísaným minimálnym počtom krokov.

(tému vypracuje Tomáš Tatranský, tomas.tatransky(zavinac)centrum.sk pdf)

 

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ému vypracuje Peter Sýkora, petos(zavinac)apis.sk pdf, program.zip )

 

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ému vypracuje)

 

Téma 7. Algoritmus simulovaného žíhania 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ému vypracuje Peter Ledňa, pledna(at)gmail.com pdf)

 

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ému vypracuje)

 

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ému vypracuje Michal Moravcik, misom(at)mail.t-com.sk )

 

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ému vypracuje Jozef Kriska, jozef.kriska(at|pobox.sk pdf)

 

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ý

Symbol ] znamená vrátiť sa na zapamätané súradnice bodu a zodpovedajúce dx a dy, symbol + znamená otočiť sa doľava (použili sme prepis pre súradnice nového bodu

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

y koncový = y počiatočný + 0.7 (sin(40o) dx + cos(40o) 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(33o) dx + sin(33o) dy)

y koncový = y počiatočný + 0.7 (sin(33o) dx - cos(33o) 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ému vypracuje Vladimír Krivuš, vkrivus(at)gmail.com, kód_s_popisom.rar)

 

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

dN1(t)/dt = N1(r1- b1N2 )

dN2(t)/dt = N2(- r2+b2N1

kde N1(t) je počet kusov koristi (alebo hostiteľa) a N2(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 r1, zatiaľ čo za absencie koristi dravci hynú rýchlosťou r2. Nech b1 zodpovedá schopnosti dravcov požierať korisť a b2 vplyvu množstva koristi (a teda nasýtenia dravcov) na ich rozmnožovanie. Nech r1= 1.5, b1=0.1 r2= 0.25 b2= 0.01 a N1(0)= 15 a N2(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:

·         vyhýbať sa kolízii s okolitými jedincami

·         prispôsobiť rýchlosť okolitým jedincom

·         snažiť sa držať sa blízko okolitých jedincov

Každá žubrienka pritom vidí iba svojich najbližších susedov. Pridajte "dravca", teda inofarebnú žubrienku, ktorá sa pohybuje smerom k ostatným žubrienkam a ktorej sa žubrienky snažia vyhýbať.

 

Zobrazenie ”žubrienok” (čiernych bodov s ”chvostíkom”), ktoré sa pohybujú smerom vpravo nahor a vyhýbajú sa prekážke (kruhu).

(tému vypracuje)

 

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.

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

(tému vypracuje Martin Komara scare(at)ynet.sk zip_s_pdf_a_kodom)

 

Téma 15. Použite simulované žíhanie pre riešenie pohybu koňa na šachovnici, kde zo zadaného poľa máte prebehnúť všetky ostatné poľa, pričom na každé pole vstúpite iba raz. Ako druhú časť úlohy riešte rovnaký problém s podmienkou, že sa kôň musí vrátiť naspäť. Pri riešení použite perturbáciu (mutáciu) toho druhu, že počiatok postupnosti polí do náhodne vybraného počtu polí skopírujete do nového riešenia a zvyšok vygenerujete. Úloha sa dá riešiť aj spätným prehľadávaním, ale len pre malé prípady.

(tému vypracuje Peter Bartalos, bartalos(at)fiit.stuba.sk pdf)

 

Téma 16. (Bin Packing )

Pakovanie je klasickým problémom v optimalizácii. Predpokladajme, že máme nákladný voz schopný uviezť akýkoľvek počet krabíc, pokiaľ ich celková váha neprekročí W. V skladisku máte nelimitované množstvo rozličných typov tovaru. Každý typ položky i má váhu wi a hodnotu vi . Váš problém je určiť, ktorou kombináciou objektov dosiahnete najvyššiu hodnotu bez prekročenia maximálnej povolenej celkovej váhy. Napríklad, keď váhy a hodnoty sú

Položka

váha

hodnota

pomaranče

3

5

 

knihy

8

11

 

potom náklaďák s maximálnou nosnosťou W=200 môže viezť:

pomaranče

knihy

váha

hodnota

30

13

194

293

40

10

200

310

50

6

198

316

60

2

196

322

Najlepšia stratégia je naložiť toľko krabíc s pomarančmi ako sa len dá a zvyšok zaplniť knihami. Vyriešte problém pre väčší počet položiek s náhodne definovanými hodnotami a váhami pomocou genetického algoritmu, s obmedzeným počtom niektorých položiek, vymyslite si vlastnú reprezentáciu problému a k nej odpovedajúce chromozómy, mutácie a kríženie, porovnajte váš algoritmus s kanonickým genetickým algoritmom, a použite pokutovaciu funkciu. (Adaptované z http://www.epcc.ed.ac.uk/epic/ga/intro.html)

(tému vypracuje Ján Májek, jan.majek(at)gmail.com pdf, zdrojaky.rar)

 

Téma 17. Rozvrhovací problém (Scheduling problem)

Rozvrhovací problém je intenzívne v oblasti operačného výskumu už veľa rokov. Jednou z formulácií problému je predpokladať, že máme množinu N úkolov ti, i=1..N, každý z nich vyžaduje niektoré zo zdrojov rj po zadaný čas timei,rj. Našou úlohou je nájsť najrýchlejší rozvrh pre celkové splnenie týchto úkolov, pričom zdroje môžu byť využívané súčasne, ale každý zdroj iným úkolom. Na poradí zdrojov pre úkol nezáleží. Vyriešte problém pre väčší počet úkolov s náhodne definovanými požadovanými zdrojmi a časmi pomocou genetického algoritmu, vymyslite si vlastnú reprezentáciu problému a k nej odpovedajúce chromozómy, mutácie a kríženie, porovnajte váš algoritmus s kanonickým genetickým algoritmom. Použite pokutovaciu funkciu pri nesplnení ohraničení.

(tému vypracuje)

 

Téma 18. Evolúcia sortovacích sietí

(max. fitness = 120)

Vodorovné línie označujú pozície v sekvencii, vertikálne spoje dvoch horizontálnych línií reprezentujú operáciu výmeny zle usporiadanej dvojice (tzv. komparátor). Komparátor porovnáva dve čísla z pozícií určených horizontálnymi líniami, a keď sú zle usporiadané, prehodí ich. vzájomné pozície. Keď chceme vzostupnú sekvenciu a "horné" číslo je väčšia ako "dolné", prehodíme ich navzájom.

·         Príklad: pre hodnoty 4,1,3,2 získaj 1,2,3,4 alebo 4,3,2,1 ako výstup: vertikálna čiara označuje výmenu hodnôt medzi horizontálnymi čiarami, keď je prvá hodnota väčšia/menšia ako tá druhá.

·         Vyskúšaj: veľkosť populácie=10, kríženie=10%, mutácie=0%

·         Vyskúšaj: veľkosť populácie =10, kríženie =10%, mutácie =1% (200 generácií)

·         Vyskúšaj: veľkosť populácie =10, kríženie =80%, mutácie =1% (150 generácií)

·         Vyskúšaj: veľkosť populácie =50, kríženie =90%, mutácie =1%

 

 

Príklad triediacej siete pre testovací príklad - sekvenciu (4,1,3,2), ktorá je korektne usporiadaná na sekvenciu (1,2,3,4). Táto sieť môže byť popísaná ako sekvencia komparátorov [1:2],[3:4],[1:3],[2:4],[2:3], kde čísla v zátvorkách sú indexy spojených línií, na ktorých výmena prebieha.

 

GA vytvára napr. pre prípad zoradenia piatich čísel 5-vstupové sortovacie siete obsahujúce najviac 9 porovnaní-výmen. Existuje 120 fitness prípadov (všetkých 5! permutácií sekvencie 1,2,3,4,5), a korektná sieť ich všetky zoradí bezchybne. Vyskúšaj koevolúciu pre zložitejšie prípady, kde sekvencie hodnôt sa vyvíjajú nezávisle a sú ohodnotené tým lepšie, čím viac sietí na nich zlyháva.

(tému vypracuje Michal Lokša, lokator(at)gmail.com zip_s_pdf_a_kodom)

 

Téma 19. Genetické programovanie pre mravca hľadajúceho cestu

Genetickým programovaním vytvoriť "program" pre mravca pomocou súboru pravidiel. Mravec má zberať potravu rozsiatu na nie celkom súvislej dráhe umiestnenej na toroidálnej mriežke, pričom má iba obmedzené senzory (teda vidí iba na vedľajšie bunky mriežky). Mravec má za daný počet časových krokov zozberať čo najviac potravy. V detailoch zadania sa možno inšpirovať na

http://www2.informatik.uni-erlangen.de/~jacob/Evolvica/GP/Java/html/ant/ant.html).

Úlohou je vygenerovať pravidlá a) pre vlastnú náhodne vygenerovanú dráhu s podobnými vlastnosťami ako je John Muir Trail z vyše uvedenej WWW stránky. b) Vyskúšať vygenerovanie pravidiel, ktoré by platili pre viac dráh súčasne.

(tému vypracuje)

 

20. Simulované žíhanie pre kombinatorickú optimalizácia umiestenia prostriedkov

Tento problém QAP (quadratic assignment problem) podľa C.E. Nugent, T.E. Vollman, and J. Ruml, "An experimental comparison of techniques for the assignment of facilities to locations," Operations Research 16 (1968) pp. 150-173. 15 dielní má byť rozmiestnených do 15 pozícií. Cieľom je minimalizovať cenu transportu dodávok medzi rozmiestnenými oddeleniami. Cena transportu je (veľkosť dodávky * vzdialenosť), kde veľkosť dodávky aj vzdialenosť sú symetrické u ktorejkoľvek dvojice oddelení. V dolu uvedenej tabuľke je veľkosť dodávky medzi dieľňami (dolná polovina matice) a vzdialenosť možných umiestnení dieľní (horná polovina matice). Optimálne riešenie je 575 (alebo 1150 pre dvojnásobok tokov).

  1. Urobte jednoduchý program na simulované žíhanie na riešenie problému. Na to potrebujete zakódovať problém, zadefinovať okolie (mutáciu), zvoliť postup znižovania teploty a ukončovacie kritérium.
  2. Skúste porovnať výsledky tohto jednoduchého simulovaného žíhania s procesom prebiehajúcim na viac "procesoroch" na mriežke toroidu alebo na kružnici, keď s času na čas "procesory" akceptujú prípadné lepšie riešenie zo svojho okolia.

 

(tému vypracuje Peter Mestanik, peter.mestanik(at)gmail.com zip_s_pdf_a_kodom)

 

 21. Minimalizácia štýlových predpisov v jazyku CSS

Pomocou GA sa pokúste minimalizovať veľkosť štýlových predpisov v jazyku CSS, pričom vnútorná sémantika štýlového predpisu sa nezmení. Experimentujte s parametrami ako elitárstvo, pravdepodobnosť mutácie a kríženia, či veľkosť populácie. Dosiahnuté výsledky experimentov zanalyzujte a zdokumentujte.

(tému vypracuje Ján Suchal, johno(zavináč)jsmf.net pdf)

 

 22. Použitie GA na automatickú kategorizáciu slov dokumentu

Použite GA na automatickú kategorizáciu slov dokumentu (t.j. zaraďovanie slov do kategórií podľa ich významu). Testujte vplyv rôznych atribútov vstupného dokumentu (veľkosť dokumentu, jazyk, viac pouzitych jazykov v jednom dokumente), tiež experimentujte s rôznym počtom kategórií.

Vychadzajte z prace M. Lankhorst. Automatic Word Categorization with Genetic Algorithms, In Eiben, A., Manderick, B., and Ruttkay, Z. (Eds.), Proceedings of the ECAI'94 Workshop on Applied Genetic and other Evolutionary Algorithms Amsterdam. Springer Verlag. 1995

http://citeseer.nj.nec.com/lankhorst95automatic.html.

(tému vypracuje Peter Vojtek, peter.vojtek(zavináč)gmail.com, zkúška 24.5.2006, zipped_pdf_and_code)

23. Použitie GA na neurónovú sieť

Pre toroidálnu mriežku N x N vytvorte zberača potravy (táto sa nachádza náhodne rozmiestnená (x kúskov potravy) v tejto mriežke), pričom tento zberač je riadený neurónovou sieťou. Navrhnite túto sieť a vylepšujte zberača pomocou genetického algoritmu (váhy siete tvoria chromozóm). Zberač má obmedzenú oblasť vnímania. Skúmajte vývoj zberačov v mriežke vzhľadom na schopnosť získať čo najviac kúskov potravy pre nejaký maximálny počet krokov v mriežke. Skúmajte schopnosť zlepšovania pre rovnakú mriežku pre všetky generácie a rôznu mriežku pre každú novú generáciu. Príklad: mriežka veľkosti 20x20, počet kúskov potravy 50, maximálny počet krokov 50, oblasť vnímania zberača 5x5 kde zberač je v centre. Zadanie vychádza z problému popísanom v knihe: Kvasnička, Pospíchal: Evolučné algoritmy (str. 124-125).

(tému vypracuje Peter Kasan, peter.kasan(zavináč)zoznam.sk zipped_pdf_and_code)

24. Model virtuálneho vesmieru

Pokuste sa formulovat hypotezu o tom ako zostrojit model virtualneho vesmiru. Rozdiskutujte analogiu virtualny vesmir - realny vesmir.

(tému vypracuje Peter.Orosi, peter.orosi(zavináč)gmail.com) pdf