Warranty:
This web page is designed for MS Internet Explorer, an application of another
program than this one (e.g. Mozilla) , may cause problems with downloading
attached files. But these problems are easily overcome if you manually change
in the address the “backslash” symbol ‘\’ by “slash” symbol ‘/’.
Prednáška "Evolučné algoritmy"
SI, šk.r. 2005/06, semester letný
Ročník: inžinierske štúdium, 1. nominálny
ročník, druhý (letný) semester
Rozsah: prednáška – 2 hod, seminár – 2
hod.
Prednášky: utorok o 14.00 – 15.40
hod, poslucháreň DE35
Cvičenie: štvrtok o 14.00 – 15.40
hod, poslucháreň B02
Prednášajúci: Doc. RNDr. Jiří Pospíchal, DrSc.
(garant predmetu)
email:
pospichal(zavináč)fiit(bodka)stuba(bodka)sk
Ústav aplikovanej informatiky FIIT STU, miestnosť D117
telefón (02)60291679, (02)65422707, klapka 117.
Konzultácie s prednášajúcim: dohodnúť vopred emailom.
Podmienky
úspešného absolvovania:
(1) Zápočet – získanie najmenej 20 bodov (zo 45
bodov) z 2 písomiek a z prezentácií
a žiadna neospravedlnená neúčasť
na cvičení.
(2) Skúška – získanie najmenej 56 bodov z
celkového počtu 100 bodov (známka E) takto:
Volne súvisiaca
literatúra:
·
Charles Darwin
"On the Origin of Species" (doc)
· Úvodná kapitola z knihy "Evolutionary Design by Computers", editor Peter J. Bentley ISBN 1-55860-605-X, domovská stránka knihy je na adrese http://www.mkp.com/books_catalog/1-55860-605-x.asp , text kapitoly pdf.
·
Tutoriál od
Prof. Hans-Paul Schwefel "On Natural Life's Tricks to Survive and Evolve"(pdf alebo
ps.zip)
·
Tutorial od Prof.
John Koza (University of Stanford) "Genetic
Programming: Biologically Inspired Computation that Creatively Solves
Non-Trivial Problems" (pdf)
·
Tutorial od
Prof. Darrell Whitley "A Genetic Algorithm Tutorial" (pdf)
Predbežné texty ku knihe "Evolučné
algoritmy"
Jednotlivé kapitoly môžu slúžiť ako
základný text prednášky, kde sú uvedené aj príklady na precvičenie.
Obsah
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)
1. prednáška – Univerzálny
darvinizmus I (21.2.06)
Univerzálny darvinizmus, všeobecné predstavy o darvinovskej evolúcii, chápanie evolúcie ako algoritmu
Priesvitky k prednáške (pdf)
2. prednáška – Univerzálny
darvinizmus II (23.2.06)
Univerzálny darvinizmus, všeobecné predstavy o darvinovskej evolúcii, chápanie evolúcie ako algoritmu
Priesvitky k prednáške (pdf)
Pozri tiež prednášku "Umelá evolúcia" (ps.zip a pdf) (priesvitky ps.zip a pdf), prednesenu na sympóziu „Kognitívne vedy III – CogSci2000)“
Kapitola z pripravovanej knihy „Univerzálny darvinizmus“ (pdf)
Článok: V. Kvasnička and J. Pospíchal: ARTIFICIAL CHEMISTRY AND MOLECULAR DARWINIAN EVOLUTION IN SILICO, Collection of Czechoslovak Chemical Communications 2002 (pdf)
Zadanie na cvičenia na deň 2.3.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Petra
Ledňu (spolu s Mešťaníkom),
ktorí
budú prezentovať tému č. 11
Dynamic
Lab: Tool for Investigating Cellular Automata
and
Discrete Dynamical Networks (pdf)
Milan
Skuhra 10min. prezentácia Hollandovho GA
(pdf)
Michal
Lokša 10min.
prezentácia evolučného algoritmu (pdf)
Michal Moravčík 10min. prezentácia Eigenovej a Schustrovej
teórie molekulárneho darvinizmu (pdf)
Peter
Ledňa 10min. prezentácia Binárne kódivanie a optimalizácia (pdf)
3. prednáška – Binárne
kódovanie, základné stochastické algoritmy (28.2.06)
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 a pdf)
Zadanie na cvičenia na deň 9.3.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Petra
Vojteka a Petra Sýkoru,
ktorí
budú prezentovať tému č. 10
Exploring
Cellular Automata with MCell (pdf)
Peter
Sýkora 10min. prezentácia chemostatu (pdf) (zdroj. kód programu)
Peter Orosi 10min. prezentácia Folding binárnych reťazcov (pdf)
Tomáš Matúšek 10min. prezentácia Tabu search (ppt)
Peter
Mešťaník 10min. prezentácia Stochastické optim. alg. (ppt)
4. prednáška – Genetický
algoritmus (14.3.06)
Základy genetického algoritmy, ruleta, mutácia, kríženie, implementácia,
„messy“ genetický algoritmus. Predmet tejto prednášky odpovedá 4. kapitole
knihy "Evolučné algoritmy".
Priesvitky k prednáške (pdf)
Zadanie na cvičenia na deň 16.3.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Petra
Kasana a Petra Bartalose,
ktorí
budú prezentovať tému č. 7 (pdf)
EINSTein:
A Multiagent Based Model of Combat
Martina
Prázdnovská 10min. prezentácia Mutacie (2,2) do (0,0) bez zníženia fitness (pdf)
Tomáš
Tatranský 10min.
prezentácia Z každého bodu sa dá na vrchol (pdf)
Martin Komara 10min. prezentácia Odkial sa nedá na vrchol
bez zníženia fitness (pdf)
Ján Suchal 10min. prezentácia Minimálny počet mutácií ako
f(x,y) (pdf)
Peter Ledňa 10min. prezentácia Minimálny počet mutácií bez
zníženia fitness (pdf)
Ján Májek 10min. prezentácia Horolezecký algoritmus na
reťazec (pps)
]
5. prednáška – Genetické
programovanie (21.3.06)
Genetické programovanie, syntaktické stromy, kódovanie stromov, operácie nad
kódmi. Predmet tejto prednášky odpovedá
5. kapitole knihy "Evolučné algoritmy".
Priesvitky k prednáške (pdf)
Zadanie na cvičenia na deň 23.3.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Martina
Prázdnovská, Milan Skuhra
ktorí
budú prezentovať tému č. 2
Framsticks:
A platform for modelling, Simulating, and Evolving 3D Creatures (pdf)
Jozef
Kriška 10min. prezentácia Vývojár reťazcov (pdf), (zipped code)
Peter
Kasan 10min. prezentácia Vývojár reťazcov (ppt), (MATLAB code)
Peter
Bartaloš 10min. prezentácia Vývojár reťazcov (ppt)
6. prednáška – Simulované žíhanie (28.3.06)
Simulované žíhanie, základné princípy, fyzikálna teória simulovaného
žíhania, paralelné simulované žíhanie. Predmet tejto prednášky odpovedá 6.
kapitole knihy „Evolučné algoritmy“.
Peter
Orosi 10min. prezentácia Minimálny strom polynómu v GA (pdf)
Priesvitky k prednáške (pdf)
Cvičenie
30.3.2006: 1 kontrolná písomka
50 min Prezentácia: Matúšek – Genepool: Exploring
the interaction between natural selection and sexual selection (ppt)
Zadanie na cvičenia na deň 30.3.2006
(pdf)
Vladimír
Krivuš 10min. prezentácia GP (ppt)
Peter
Bartaloš 10min. prezentácia GP (ppt)
1. kontrolná písomka
7. prednáška – Kombinatoriálne algoritmy
(4. 4. 06)
Použitie evolučných algoritmov k riešeniu kombinatoriálnych optimalizačných problémov, predmet tejto prednášky odpovedá 7. kapitole knihy „Evolučné algoritmy“.
Priesvitky k prednáške (pdf)
Zadanie na cvičenia na deň 6.4.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Martina
Komaru a Jozefa Krišku
ktorí
budú prezentovať tému č. 8 StarLogo:
A
programmable Complex Systems Modelling Environment for Students and Teachers (pdf)
Peter
Vojtek 10min. prezentácia Hľadanie cesty s GA s Roulette wheel (pdf)
Ján
Suchal 10min. prezentácia Hľadanie cesty s Hillclimbingom (pdf)
Peter
Kasan 10min. prezentácia Hľadanie cesty s GA s turnajom (zio_s_ppt_a_zdrojakmi)
Peter
Sýkora 10min. Hľadanie cesty s GA (pdf)
Ján Májek 10min. prezentácia Hľadanie cesty s horolezeckým
algoritmom (pdf)
8. prednáška - Umelý život (11. 4. 06)
Definícia umelého života, význam pre informatiku, ilustračné príklady, význam evolučných algoritmov v umelom živote, predmet tejto prednášky odpovedá 8. kapitole knihy „Evolučné algoritmy“.
Doplnky k prednáške:
Šetrič obrazovky vo forme boidov (scr 90kB)
Film ukazujúci pohyb Simsových umelých bytostí (mpeg 9MB)
Filmy ukazujúce emocionálne výrazy robota Kismet
(mov1 8MB, mov2 6MB, mov3 1MB,
Zadanie na cvičenia na deň 13.4.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Michala
Lokšu
ktorý
bude prezentovať tému č. 5 Sodarace:
Adventures
in Artificial life (ppt)
Peter
Matúšek 10min. prezentácia N Queens SA (ppt)
Peter
Mešťaník 10min. prezentácia N Queens SA binárne reťazce (ppt)
Jozef
Kriška 10min. prezentácia N Queens GA (zip_s_pdf_a_MATLAB_zdrojakmi)
Martin
Komara 10min. prezentácia N Queens GA (zip_s_pdf_a_Mathematica_zdrojakmi)
Vladimír
Krivuš 10min. prezentácia N Queens Tabusearch (ppt)
Zadanie na cvičenia na deň 20.4.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Vladimíra
Krivuša
ktorí
budú prezentovať tému č. 1. Avida (ppt_a_pdf_rar)
Peter
Sýkora 10min. prezentácia Hladanie minimalneho poctu prekrizeni
kompletneho
grafu pomocou GA s gaussovskou mutaciou (pdf) (zip_zdrojak)
Michal
Moravčík 10min. prezentácia Hladanie minimalneho poctu prekrizeni
kompletneho
grafu pomocou GA s gaussovskou mutaciou (pdf_a_zip_zdrojak)
Tomáš
Tatranský 10min. prezentácia Hladanie maximálneho poctu prekrizeni
kompletneho
grafu analýzou problému (pdf)
Peter
Vojtek 10min. prezentácia Hladanie minimalneho poctu prekrizeni
kompletneho
grafu pomocou GA s mutaciou 0.1 (pdf)
Peter
Kasan 10min. prezentácia Hladanie minimalneho poctu prekrizeni
kompletneho
grafu pomocou Hillclimbingu s mutaciou 0.1 (zip_s_ppt_a_zdrojakom)
9. prednáška – Chaos, fraktály (pdf) a sociálne javy (pdf) (25. 4. 06)
Zadanie na cvičenia na deň 27.4.2006
(pdf)
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Petra
Orosiho
ktorý
bude prezentovať tému týkajúcu sa evolúcie umeleckých artefaktov
Michal
Lokša 10min.
prezentácia Koevolucny geneticky algoritmus triediacich sieti (rar_s_ppt_a_zdrojakom)
Milan
Skuhra 10min. prezentácia Life štruktúra s GA (pdf)
Peter
Vojtek 10min. prezentácia Zloduch a kanadská jazdná polícia (pdf)
Peter
Ledňa 10min. prezentácia Ako spolupracovať s tit-for-tat? (pdf)
Martina
Prázdnovská 10min. prezentácia Zanikajúci vzor hry LIFE hillclimbingom (pdf)
Peter
Bartaloš 10min. prezentácia Logistická rovnica (ppt)
Ján Májek 10min. prezentácia Čísla deliaca chémia (pdf)
10. prednáška – Neurónové siete I (2. 5. 06)
História neurónových sietí, konekcionizmus v umelej inteligencii, subsymbolický prístup. Logické neurónové siete podľa McCullocha a Pittsa, univerzilita týchto neurónových sietí.
Texty o neurónových sieťach:
(1) Kapitola
z knihy „Kognitívne vedy“ (pdf)
(2) Priesvitky
z prednášky o konekcionizme v rámci celoUK prednášky „Kog. vedy“
(pdf-1.čast) (pdf-2.časť)
(3) Text
k prednáške na letnej škole „Advanced Control 1997“ (pdf)
(4) Priesvitky k prednáške na letnej škole „Advanced
Control 1997“ (pdf-1.čast) (pdf-2.čast) (pdf-3.čast)
11. prednáška – Neurónové siete II (9. 5. 06)
Viac vrstvové neurónové siete, učenie, výpočet gradientu pomocou metódy spätného šírenia (back propagation), trojvrstvová sieť ako univerzálny aproximátor, náznak dôkazu.
K tejto prednáške sú texty uvedené na predchádzajúcej 10. prednáške
Doplnkom budú:
Rekuretné neurónové siete, Elamnova rekutrentná sieť k adaptácia, ilustračné príklady. Pollackova rekurentná sieť typu RAAN (Recurrent Auto-Associative Memory), adaptácia, ilustračné príklady.
Texty o rekurentných neurónových sieťach:
(1) Text
k prednáške na letnej škole „Advanced Control 1997“ (pdf)
(2) Priesvitky z prednášky na Slovenskej konferencii o umelých neurónových sieťach, Smolenice 1998 (pdf)
Zadanie na cvičenia na deň 11.5.2006
(pdf)
+ zminula Skuhra GA na hru LIFE
s tým,
že každý z uvedených študentov si má pripraviť asi
10
minútovú prezentáciu s priesvitkami v pdf, ktoré
budú po
cvičení "zavesené" na túto stránku, rovnako
ako
slidy (pdf či PowerPoint) k 50 minútovej prezentácii
Michala
Moravčíka
ktorý
bude prezentovať tému č. 6 Escaping the accidents of history (Repast) (pdfrepast_moravcik.pdf)
Milan
Skuhra 10min. prezentácia Pascalov trojuholník a fraktály (pdf)
Jozef Kriška 10min. prezentácia Väzenská dilema (pdf)
Tomáš
Tatranský 10min.
prezentácia Väzenská dilema a votrelecká stratégia (pdf)
Peter
Mešťaník 10min. prezentácia Evolúcia log. funkcií s NN (ppt)
2. kontrolná písomka (16. 5. 06)
Cvičenie 15.5.2006
Ján Suchal 50 minut L systemy_Prusinkievicz (pdf)
Martina Prázdnovská 10min. prezentácia Evolúcia log. funkcií s NN (pdf) (rar_kódu)
Májek,
Tatranský
téma č.
12 Simulated Breeding = A Framework of Breeding Artifacts on the Computer (pdf)
Na jednotlivé projekty je potrebné sa prihlásiť
emailom na hore uvedenej adrese. Po vzájomnej dohode s prednášajúcim sú
možné aj vlastné témy projektov
Skúška sa bude ústna zameraná predovšetkým (nie
výlučne) ne tému projektu.
Termíny predbežne: 16.6, 23.6, 30.6 od 9h v D117,
možno dohovoriť aj iný termín v prípade
viacerých záujemcov o konkrétny termín.