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)
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)
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).
(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