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 thebackslash” symbol ‘\’ by “slash” symbol ‘/’.

Prednáška "Evolučné algoritmy" LS 2010/2011

Stará prednáška SI, šk.r. 2006/07, semester letný (klasická www)

 Stará prednáška SI, šk.r. 2007/08, semester letný (modle)

Stará prednáška SI, šk.r. 2008/09, semester letný (klasická www)

Stará prednáška SI, šk.r. 2009/10, semester letný (klasická www)

 

Ročník: inžinierske štúdium, 1. nominálny ročník, druhý (letný) semester

 

Rozsah: prednáška – 2 hod, cvičenie – 2 hod.

Prednášky: pondelok o 11.00 – 12.40 hod, poslucháreň c802

Cvičenie: útorok o 7.00 – 8.40 hod, 9.00-10.40, 11.00 – 12.40 hod poslucháreň DE35

Prednášajúci: Prof. RNDr. Jiří Pospíchal, DrSc. (garant predmetu)

email: pospichal(zavináč)fiit(bodka)stuba(bodka)sk 

Ústav aplikovanej informatiky  FIIT STU, miestnosť C018

telefón (02)60291679

Konzultácie s prednášajúcim: dohodnúť vopred emailom.

Cvičiaci: Ing. Matej Makula, PhD.

Ing. Peter Trebatický, PhD.

Podmienky úspešného absolvovania:

(1)   Zápočet – získanie najmenej 20 bodov (zo 45 bodov) z prezentácií na cvičeniach
        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:

(2.1) max 45 bodov za prezentácie na cvičení v priebehu semestra

           (3x8=24 bodov za tri 12-minútové prezentácie,

                      21 bodov za 50 minútovú prezentáciu zo zvoleného ALIFE software z knihy

                                    

                                    Resp. 2 vydanie z r. 2009, pozri avaxhome.ws, resp. library.nu

         Priradenie tém:

1 Avida

2 Framsticks: A platform for modelling, Simulating, and Evolving 3D Creatures

3 (Nerve garden) alternatívny výber - L systemy_Prusinkievicz, alebo systém BREVE z 2. vydania

4 Genepool: Exploring the interaction between natural selection and sexual selection z 1. vydania, alebo NETLOGO z 2. vydania

5 Sodarace: Adventures in Artificial life

6 Escaping the accidents of history (Repast)

7 EINSTein: A Multiagent Based Model of Combat

8 StarLogo: A programmable Complex Systems Modelling Environment for Students and Teachers

9 (Sonic) alternatívny výber zo zvyšných simulátorov na stránke alife

10 Exploring Cellular Automata with MCell

11 Dynamic Lab: Tool for Investigating Cellular Automata and Discrete Dynamical Networks

12 Simulated Breeding = A Framework of Breeding Artifacts on the Computer

13 (Enriching Aesthetic with artificial life)

      alternatívny výber zo zvyšných simulátorov na stránke alife

Problémy k vyriešeniu na prezentáciách budú vždy vyvesené na tejto www pri pdf slidoch prednášok. 12 minútové prezentácie musia byť do cvičenia uploadované do is systému fakulty, miesta odovzdania v AISe. Je to v:

EA / Rozpisy tem a miesta odovzdania / Vsetci studenti + Vybrat

Sú tam tri miesta odovzdania, každé na jednu malú prezentáciu s termínom uzatvorenia po semestri, aby to tam mohli priebežne nahrávať. (Kliknutím na ikonu sa dá miesto otvoriť/uzatvoriť pre odovzdávanie, resp. v detaile sa dajú meniť pokyny a pod, odovzdané súbory sa dajú stiahnuť ako veľký zip archiv)

 

(2.2) max 55 bodov za písomnú skúšku a projekt (max 25 bodov za písomnú skúšku + 30 bodov za prezentáciu a písomné vypracovanie projektu)   

 

Volne súvisiaca literatúra:

·         Úvodná kapitola z knihy "Evolutionary Design by Computers", editor Peter J. Bentley ISBN 1-55860-605-X, 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)

Upozornenie: Zadanie na seminár sa budú v priebehu semestra meniť,

uvedené zadania zatiaľ slúžia iba ako ilustračné.

Predbežný plán prednášok, môže sa v priebehu semestra čiastočne meniť,

zadanie na cvičenia sú aktuálne až týždeň pred vlastným cvičením.

1. prednáška – Univerzálny darvinizmus I (14.2.11)

Univerzálny darvinizmus, všeobecné predstavy o darvinovskej evolúcii, chápanie evolúcie ako algoritmu

Priesvitky k prednáške (ppt

)

K nedokonalosti oka pozri blind spot test

 

Zadanie na cvičenia na deň 15.2.2011

(neboli, cvičenie prevodu binárnych čísel, Grayov kód

a kód mutácie, kríženia a základov evolučného algoritmu)

 

2. prednáška – Univerzálny darvinizmus II (21.2.11)

Univerzálny darvinizmus, všeobecné predstavy o darvinovskej evolúcii, chápanie evolúcie ako algoritmu

Priesvitky k prednáške (ppt)

Pozri tiež prednášku "Umelá evolúcia"  (ps.zip a pdf) (priesvitky ps.zip a pdf), prednesenu na sympóziu „Kognitívne vedy IIICogSci2000)“

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ň 22.2.2011 (pdf)

3. prednáška – Binárne kódovanie, základné stochastické algoritmy (28.2.11)

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

 

Zadanie na cvičenia na deň 1.3.2010 (pdf)

 

4. prednáška – pozor 7.3. nepojde elektrika, oprava trafostanice

Zadanie na cvičenia na deň 8.3.2011 (pdf)

4. prednáška – Genetický algoritmus (14.3.11)

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

 

Zadanie na cvičenia na deň 15.3.2011 (pdf)

 

5. prednáška – Genetické programovanie (21.3.11)

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

Zadanie na cvičenia na deň 22.3.2011 (pdf)

 

6. prednáška – Simulované žíhanie (28.3.11)

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“.

Priesvitky k prednáške (ppt)

 

Zadanie na cvičenia na deň 29.3.2011 (pdf)

 

7. prednáška – Kombinatoriálne algoritmy (4. 4. 11)

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

 

Zadanie na cvičenia na deň 5.4.2011 (pdf)

 

8. prednáška - Umelý život (11. 4. 11)

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“.

Priesvitky k prednáške (ppt)

(a)               Priesvitky k prednáške (docpdf) (tieto priesvitky sú pripravené pomocou  8.  kapitola pripravovaného učebného textu „Informatika pre sociálne vedy“ (docpdf),

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,

             mov4 3MB, mov5 14MB)

 

 

Zadanie na cvičenia na deň 12.4.2011 (pdf)

 

9. prednáška -  Chaos, fraktály (18. 4. 11) (ppt)

 

 

Zadanie na cvičenia na deň 19.4.2011 (pdf)

veľká noc

 

10. prednáška – Sociálne javy (ppt) (2. 5. 11)

 

Zadanie na cvičenia na deň 3.5.2011 (pdf)

 

11. prednáška – Neurónové siete I  (9. 5. 11)

História neurónových sietí, konekcionizmus v umelej inteligencii, subsymbolický prístup. Logické neurónové siete podľa McCullochaPittsa, 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)

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.

 

 

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ň 10.5.2011 (pdf)

 

12. prednáška – Swarm intelligence (ant colony + particle swarm optimisation) (ppt) (16. 5. 11)

Zadanie na cvičenia na deň xx.5.2011 (pdf)

 

Zadanie projektov (-zatiaľ na ukážku staré case studies html)

Zadanie projektov (trocha novšie case studies html)

Na jednotlivé projekty je potrebné sa prihlásiť (podrobnosti budú upresnené, na 1 tému maximálne 1 študent z danej skupiny, musíte si  kontrolovať či už niekto nemá projekt pridelený). Po vzájomnej dohode s prednášajúcim sú možné aj vlastné témy projektov.

Vypracované "case study" spolu so zdrojovým kódom pošlete svojim cvičiacim alebo e-mailom ako attachment do konca semestra, alebo do ais podľa dohody so cvičiacim, a musíte sa uistiť, že súbory dostali v poriadku, alebo sa dohodnete 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ú volne prístupné pre poučenie budúcich generácií. U zdrojových súborov nebude kontrolovaná kvalita, ale pôvodnosť.

Pokiaľ bude case study odoslaná po konci semestra 16.5., za každý deň oneskorenia sa strháva 1 bod (až do týždňa po písomnej skúške, kedy študijné oddelenie vyžaduje odovzdanie výsledkov, pokiaľ by neukončenie hodnotenia kvôli neskorému odovzdaniu robilo problém s ukončením štúdia, je to na zodpovednosť študenta, ktorý mal odovzdať načas).

 

 

 

 

Skúška sa bude písomná, termín XX.X.2011XXXX hod,

Opravné XXX

Príklady tém na písomku:

Horolezecky algoritmus, s učením, evolučné stratégie

Transformácie reálnych čísel, Grayov kód

Genetický algoritmus, schéma

Genetické programovanie, kódovanie stromov

Grafová postupnosť

Väzenská dilema

Logistická rovnica

Logické neuróny

Celulárne automaty

Siete na triedenie