Prednášajúci: Prof. V. Kvasnička a Doc. J. Pospíchal {kvasnic@cvt.stuba.sk}

Katedra matematiky CHTF STU,

Semester: zimný

Rozsah: 2-0-0

1. Základné pojmy evolučných algoritmov – optimalizačný problém a jeho kódovanie, binárna reprezentácia reálnej premennej, transformácia spojitého optimalizačného problému na binárny optimalizačný problém.
2. Horolezecké (hill climbing) algoritmy – elementárne stochastické optimalizačné algoritmy, slepý algoritmus a horolezecký algoritmus, horolezecký algoritmus s učením, metóda zakázaného hľadania (tabu search), evolučné programovanie.
3. Genetický algoritmus – darvinovská evolúcia v živej prírode, základné pojmy, populácia a sila (fitness) chromozómov, kríženie chromozómov, implementácia genetického algoritmu, teória genetického algoritmu, Hammingova bariéra, ”messy” chromozómy, paralelná implementácia genetického algoritmu.
4. Genetické programovanie – základné pojmy z teórie grafov, koreňové stromy a Readov kód, symbolická regresia, rekonštrukcia stromov s požadovanými vlastnosťami, kódovanie funkcií pomocou acyklických orientovaných grafov.
5. Simulované žíhanie – základné pojmy, vzťah k štatistickej fyzike, paralelná implementácia.
6. Kombinatoriálne optimalizačné problémy – klasifikácia, základné úlohy z teórie grafov a operačného výskumu, špecifikácie operátorov mutácie a kríženia pre kombinatoriálne optimalizačné problémy.
7. Evolučné stratégie – historické poznámky, stratégia (1+1) - jeden rodič a jeden potomok, distribúcia pravdepodobnosti, generovanie náhodných čísel, viacčlenné stratégie a kovariancie, súvislosti s evolučným programovaním.
8. Neurónové siete – klasifikácia neurónových sietí, neurónové siete s dopredným šírením, rekurentné neurónové siete, parametrická adaptácia neurónových sietí pomocou gradientovej optimalizačnej metódy, adaptácia neurónových sietí ako stochastický optimalizačný problém, štrukturálna adaptácia neurónových sietí pomocou evolučných algoritmov.
9. Umelý život – definície života a umelého života, umelá inteligencia a multiagentové systémy, kognitívne aparáty agentov, darvinovská evolúcia multiagentových systémov, emergencia kooperatívnych vlastnosti. Celulárne automaty, evolúcia pravidieľ, vznik komplexných javov. Kooperácia, súťaženie, altruizmus, dilema väzňov a tragédia spoločného. Emergencia zložitosti, vznik života evolúciou neživého.
10. DNA výpočty – základné pojmy z molekulovej biológie, štruktúra a vlastnosti DNA, teoretické modely výpočtového procesu, experiment L. Adlemana s hľadaním hamiltónovskej cesty v orientovanom grafe pomocou DNA, DNA počítače in vivo.

Literatúra:

1. V. Kvasnička, J.Pospíchal a P. Tiňo: Evolučné algoritmy, Malé centrum, Bratislava (v tlači).
2. T. Bäck: Evolutionary Algorithms in Theory and Practice - Evolutionary Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996.
3. Z. Michaliewicz: Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, Berlin, 1992.
4. W. Banzhaf, P. Nordin, R. E. Keller, and F. D. Francone: Genetic Programming – An Introduction. Morgan Kaufmann Publishers, San Francisco, 1998.

Charles Darwin "On the Origin of Species" (doc)

http://www.mkp.com/books_catalog/1-55860-605-x.asp

text kapitoly pdf.

(pdf alebo ps.zip)

Kapitola 1- Úvodné poznámky (ps.zip alebo pdf)

Kapitola 2 - Základné pojmy evolučných algoritmov (ps.zip alebo pdf)

Kapitola 3 - Horolezecké algoritmy (ps.zip alebo pdf)

Kapitola 4 - Genetické algoritmy (ps.zip alebo pdf)

Kapitola 5 - Genetické programovanie (ps.zip alebo pdf)

Kapitola 6 - Simulované žíhanie (ps.zip alebo pdf)

Kapitola 7 - Kombinatoriálne optimalizačné problémy (ps.zip alebo pdf)

Kapitola 8 - Evolučné stratégie (ps.zip alebo pdf)

Kapitola 9 - Umelý život (ps.zip alebo pdf)

Kapitola 10 - Neurónové siete (ps.zip alebo pdf)

 Všeobecné predstavy o darvinovskej evolúcii, chápanie evolúcie ako algoritmu, význam učenia v evolúcii (Baldwinov efekt), mémy (Dawkins) ako nosič informácie pre chromozómy.

Priesvitky k prednáške (ps.zip alebo pdf)

Pozri tiež pripravovaný článok "Umelá evolúcia" (ps.zip alebo pdf)

 Binárne kódovanie reálnej premenne, transformácia spojitého optimalizačného problému na binárny optimalizačný problém. Slepý algoritmus, horolezecký algoritmus (hill climbing), horolezecký algoritmus a učením, metóda zakázaného prehľadávania (tabo search), evolučné programovanie. Predmet tejto prednášky odpovedá 2. a 3. kapitole knihy "Evolučné algoritmy".

Priesvitky k prednáške (ps.zip alebo pdf)

 Genetické algoritmy, "messy" genetický algoritmus, paralélny genetický algoritmus. Základné princípy genetických algoritmov.

Priesvitky k prednáške (ps.zip alebo pdf)

 Teória genetických algoritmov.

Priesvitky k prednáške (ps.zip alebo pdf)

Genetické programovanie, symbolická regresia.

Priesvitky k prednáške (ps.zip alebo pdf)

Priesvitky k prednáške (ps.zip alebo pdf)

Priesvitky k prednáške (ps.zip alebo pdf)

Priesvitky k prednáške (ps.zip alebo pdf)

Priesvitky k prednáške (ps.zip alebo pdf)

Neurónové siete.

Priesvitky k prednáške (ps.zip alebo pdf)

Podrobnosti o skúške, témy "case studies" (ps.zip alebo pdf)

 Skúška - témy "case studies"

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 meno autora a jeho internetovské koordináty), 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ť.

 Upozornenie: Záujemci o skúšku FTP uploadujú aspoň jeden deň pred konaním skúšky (do 16.00 hod.) vypracovanú "case study" na adresu

ftp://math.chtf.stuba.sk/received/vlado

Ako vytvoriť PS dokument pomocou MS WORD-u: Priradí sa poscriptovská tlačiareň a nechá sa tlačiť do súboru (print to file), takto vznikne PS súbor, je potrebné ho ešte prekontrolovať pomocou GhostView, či sa vytvoril korektne.

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ému vypracuje V. Škopek) 

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ému vypracuje P. Sučanský) 

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.

(tému vypracuje P. Droba, skúška dňa 17.12.1999) 

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ému vypracuje A. Probst, pokus o skúšku dňa 17.12.1999) 

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 M. Zervan) 

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 P. Imrich) 

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 J. Kľuka, skúška dňa 28.1.2000) 

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 M. Kubačák, skúška dňa 21.1.2000) 

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 J. Borovský, skúška dňa 6.4.2000) 

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 O. Lonek, skúška dňa 7.1.2000) 

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

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.

(tému vypracuje P. Malčovský) 

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ému vypracuje A. Kružic) 

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.

(tému vypracuje P. Kolenič, skúška 11. 2. 2000) 

Téma 15. Zobrazte sadu stavov jednorozmerného celulárneho automatu, kde sú bunky iba v jednom riadku (formálne spojenom do cyklu, t.j. začiatok riadku susedí s koncom) a možné stavy buniek 0 = biela, a 1 = čierna. Prechodové pravidlá pre stav buniek berú do úvahy iba momentálny stav bunky (v prostriedku) a jej ľavého a pravého suseda. Pravidlá sú zadané takto: 1,1,1 Ţ 1; 1,1,0 Ţ 1; 1,0,1 Ţ 1; 1,0,0 Ţ 0; 0,1,1 Ţ 1; 0,1,0 Ţ 0; 0,0,1 Ţ 0; 0,0,0 Ţ 1}. Napr. pravidlo 1,1,0 Ţ 1 znamená, že čierna bunka s čiernym ľavým a bielym pravým susedom bude v ďalšom časovom kroku čierna. Zobrazte sadu riadkov v časovej postupnosti, t.j. riadok v čase 0, pod ním riadok v čase 1 atď. Počiatočný stav riadku v čase 0 nech je generovaný náhodne. Zistite, po akej priemernej perióde sa riadky začínajú opakovať v závislosti na počtu buniek v jednom riadku. Vyskúšajte aj s inými sadami pravidiel.

(tému vypracuje Peter Martinovic , skúška 4.2.2000 ) 

Téma 16. Zostrojte model celulárneho automatu so 4 stavmi (na kvalite zobrazenia nezáleží, môže byť rozlíšené rôznofarebnými štvorčekami):

1. Prázdna bunka
2. Mravec
3. Ihličie
4. Mravec s ihličím

Pravidlá: Na počiatku dvojrozmerná mriežka (na okrajoch spojená do toroidu, aby neboli problémy s ohraničením) obsahuje náhodne rozmiestené ihličie a mravce. Mravec sa pohybuje vždy náhodným smerom, no tak, aby dva mravce neboli v jednej bunke. Keď narazí na ihličie, zoberie ho. Keď mravec s ihličím narazí na iné ihličie, upustí svoje ihličie. (Môže tak aj z "kôpky" odoberať.)

(tému vypracuje Peter Lalik, skúška dňa 21. 1. 2000) 

Téma 17. Použite viacčlenné evolučné stratégie pre nájdenie optima Rosenbrockovej funkcie. Program spustite 100´ a vypočítajte priemerný počet generácií, ktorý bol potrebný, aby najlepšia nájdená funkčná hodnota bola nižšia ako 10^-6. Porovnajte to s priemerným počtom generácií, nutným k nájdeniu rovnakej funkčnej hodnoty, ale bez použitia kovariancie, teda bez použitia uhlu a . Podobne skúste odstrániť kríženie pri zachovaní použitia kovariancií a diskutujte vplyv tvaru alebo typu funkcie na efektívnosť použitia kríženia alebo kovariancie pri nájdení minima. (Symetria a multimodálnosť indikujú pravdepodobnú výhodnosť aplikácie kríženia, minimá uložené v ”údoliach” umiestnených naprieč k osiam súradnicového systému budú nájdené rýchlejšie pri použití kovariancií, čo platí aj pre ”viacrozmerné údolia”.)

(tému vypracuje Eva Marinicová, skúška dňa 28.1. 2000) 

Téma 18. Zostrojte Hopfieldovu a Boltzmannovu sieť pre priradenie práce strojom vo fabrike (pozri kapitolu 11. pripravovanej knihy). Nech je M úkolov, N strojov, cena priradenia úkolu k pre stroj i je c_ik . Každý stroj i má celkové množstvo zdrojov b_i, z ktorej sa úkolom k vyčerpá množstvo a_ik. Cieľom je minimalizovať cenu priradenia každého úkolu práve jednému stroju bez toho, že by sa prečerpal zdroj b_i tohto stroja. Tento problém sa dá formálne popísať ako minimalizácia energie E

s obmedzujúcimi podmienkami

,

kde x_ik = 0 alebo 1. Simulujte na počítači pre dáta v tabuľke, kde N=3, M=8, a a_ik = a_k pre všetky i. (Každý uzol u_ik v sieti bude odpovedať priradeniu úkolu k pre stroj i, taký uzol môže byť alebo zapnutý alebo vypnutý). Ideálne optimum je vyznačené podčiarknutými hodnotami c_ik, suma týchto hodnôt je 57. V ideálnom prípade by teda mali byť aktivované uzly odpovedajúce podtrhnutým pozíciám.

(tému vypracuje Svorad Štolc, skúšku absolvoval dňa 6.4.2000.) 

Téma 19. (This case study is taken from the home page of Prof. D. Goldberg). Simulate the convergence of a genetic algorithm with population sizes n = 25, 50, 100, 200 members under proportionate selection (i.e. a probability of selection is proportional to fitness) with simple replacement (no other operators like mutation and/or crossover are involved). The population should be initialized with one individual with fitness f = f_max and the remaining individuals with fitness f = 1. Take f_max = 1.5, 3, 9. Observe the time (in generations) required for the population to converge to n - 1 members of higher fitness. Repeat each run a minimum of 3 times with different random seeds. Repeat for tournament selection (with replacement). For the first set of runs use pairwise tournament selection (s =2) with p_winner = 1 (i.e. winner with a greater functional value is selected deterministically for the next generation) and run for all fitness cases. Thereafter run experiments with s = 1.5, 3, 9, using only f_max = 1.5.

(tému vypracuje Peter Satury, skúšku absolvoval dňa 4.2.2000) 

Téma 20. Zobrazte evolúciu stratégií hry väzenská dilema, ktorá je modelovaná genetickým algoritmom, pričom každá dvojica väzňov bude interagovať vždy 10 krát medzi sebou. Tabuľka platieb je

Napríklad keď prvý väzeň nekooperuje (D) a druhý väzeň kooperuje (C), prvý dostane 5 bodov a druhý 0 bodov. Väzni majú pamäť veľkosti 1, pamätajú si iba posledný ťah súpera. Napríklad stratégia CCD (chromozóm o troch zložkách) znamená: v prvom kroku agent kooperuje (1. položka v chromozóme je C), v ďalších ťahoch kooperuje (2. zložka je C), ak v predchádzajúcom ťahu súper kooperoval, alebo nekooperuje (3. zložka je D), ak súper v predchádzajúcom ťahu nekooperoval. Pri populácii 1000 urobte vždy náhodne 500 skupín po 10, nechajte ich všetky po dvojiciach interagovať medzi sebou, s tým, že sa každému budú sčitovať platby a zoberte do ďalšej generácie iba 2 najlepších. Výsledky má byť graf, kde na osi x bude číslo generácie (teda čas) a na osi y početnosť zástupcov tej ktorej stratégie v generácii.

(tému vypracuje Radoslav Tausinger, skúška dňa 7.1.2000) 

Téma 21. Použitie genetického algoritmu na nájdenie maximálnej nezávislej množiny vrcholov.

Nech G=(V,E) označuje graf kde V je množina vrcholov a E je množina neorientovaných hrán medzi dvojicami vrcholov. Problém je nájsť podmnožinu (maximálnej kardinality) množiny vrcholov, ktorej žiadne dva vrcholy nie sú spojené hranou. Vygenerujte náhodne vygenerované grafy s počtom vrcholov 100 a s predpísanou hustotou (sada 0,1 0,2 0,3 0,4 0,5), zobrazte pre najväčšiu nájdenú veľkosť priemernú, maximálnu a minimálnu hodnotu pre 100 behov programu. Zobrazte grafy pre rôzne parametre genetického algoritmu a pre rôzne typy ohodnocovania fitness pre závislosť počet ohodnotení fitness oproti najlepšej momentálnej hodnote. Diskutujte možnosť preklenúť Hammingov problém pre grafy typu dvoch lineárnych reťazcov typu,

kde sú spojené vrcholy ešte krížom, teda 6-2, 7-3, 8-4, 9-5 a 1-7, 2-8, 3-9, 4-10 a kde množiny V´={1,3,5,6,8,10} a V´={2,4,7,9} sú globálnym a lokálnym minimom.

S. Khuri and Th. Baeck: An Evolutionary Heuristic for the Minimum Vertex Cover Problem (52k), J. Hopf,

editor: Genetic Algorithms within the Framework of Evolutionary Computation, pp. 86-90, Max Planck Institut

für Informatik, Saarbrücken, 1994.

at http://ls11-www.informatik.uni-dortmund.de/people/baeck/ea_application.html

(tému vypracuje Čestmír Hýbl ,skúška dňa 12.4.2000) 

1. Andrej Probst: Genetický algoritmus (ps.zip alebo pdf)

2. Pavol Droba: Tabu Search algoritmus Praca vo formate HTML

3. Peter Martinovič: Jednorozmerný celulárny automat  (ps.zip alebo pdf, kompletná dokumentácia zip)

4. Radoslav Tausinger: Väzeňská dilema  (ps.zip alebo pdf, program v Pascalu pas)

5. Ondrej Lonek: Adaptácia neurónovej siete pomocou genetického algoritmu (ps.zip alebo pdf, zdrojový kód zip, binárny kód zip, príklad zip )

6. M. Kubačák: Evolučná stratégia (1+1) (ps.zip alebo pdf, zdrojový kód pas.zip, príklad zip )

7. Peter Lalík: Model celulárneho automatu so 4 stavmi (ps.zip alebo pdf, zdrojový kód zip)

8. J. Kľuka: Simulované žíhanie pre riešenie úlohy obchodného cestujúceho na ortogonálnej mriežke (ps.zip alebo pdf, zdrojový kód zip)

9. Eva Mariničová: Použite viacčlenné evolučné stratégie pre nájdenie optima Rosenbrockovej funkcie (ps.zip alebo pdf, zdrojový kód zip)

10. Peter Kolenič: Modelovanie "Standing ovations" (ps.zip alebo pdf.zip, zdrojový kód zip, exe súbor zip)

11. Peter Satury: Simulačné výpočty konvergencie GA (ps.zip)

12. Ján Borovský: Genetické programovanie, symbolická regresia a boolovské funkcie (ps.zip alebo pdf)

13. Svorad Štolc: Hopfieldove neurónové siete a ich základné vlastnosti (ps.zip alebo pdf)

14. Čestmir Hýbl: Aproximácia maximálnej nezávislej množiny vrcholov grafu pomocou GA (ps.zip alebo pdf)