Evolúciós algoritmusok

A tantárgy angol neve: Evolutionary Computing

Adatlap utolsó módosítása: 2016. március 30.

Budapesti Műszaki és Gazdaságtudományi Egyetem
Villamosmérnöki és Informatikai Kar

Villamosmérnöki szak

Mérnök informatikus szak

Egészségügyi mérnöki szak

Gazdaságinformatikus szak

Szabadon választható tantárgy

Tantárgykód Szemeszter Követelmények Kredit Tantárgyfélév
TE92AX46   1/0/1/f 3  
3. A tantárgyfelelős személy és tanszék Dr. Horváth Róbert,
A tantárgy tanszéki weboldala http://www.math.bme.hu/~safaro/genetikus.html
4. A tantárgy előadója Sáfár Orsolya
5. A tantárgy az alábbi témakörök ismeretére épít Valószínűségszámítás és többváltozós függvénytan alapjai, valamint egy szabadon választott programnyelv ismerete.
7. A tantárgy célkitűzése A tárgy célja, hogy bemutassa az evolúciós algoritmusok
működési elvét és alkalmazási területeit. A tárgyat sikeresen elvégző hallgatók
felismerik azon feladatokat, melyek hatékonyan oldhatóak meg ezzel a
módszerrel és képesek a megtervezni és megvalósítani az adott probléma egy
optimális megoldását gyorsan közelítő algoritmust.
8. A tantárgy részletes tematikája

Bevezetés: Optimalizálási feladatok típusai, brute force algoritmusok ellenpéldákkal, a genetikus algoritmus alapötlete: a biológiai párhuzam (gén, öröklődés és evolúció, fitnesz).

A genetikus algoritmusok általános sémája, és megvalósítása a legegyszerűbb esetben. Az evolúcios algoritmusok típusai reprezentáció szerint, operátorok (keresztezés és mutáció) megvalósítása 0-1 bit reprezentáció esetén, rulettkerék és tournament kiválasztás, elitizmus.

Utazóügynök-probléma. A permutáció reprezentáció és a hozzá kapcsolódó operátorok (pmx, ciklikus, edge, order, inverzió, swap, beszúrás, keverés). A fitnesz függvény megválasztása, hatása a szelekciós nyomásra; constrain handling problémája.

Az egyszerű genetikus algoritmusok elmélete: Építőkövek hipotézise és kritikája (Gray kódolás), Szkéma tétel, No free lunch elv.

Evolúciós stratégiák: szimulált hűtés mint ős, genetikus változat (Rechenberg eredeti algoritmusa), keresztezés operátorok (korreláció kérdése). Szimulált hűtés és Rechenberg eredeti algoritmusának összehasonlítása, mutáció operátorok, a többdimenziós normális eloszlás, (mu+lambda) illetve (mu,lambda) kiválasztás.

Paraméterek megválasztása: hangolás-kontroll-(ön)adaptáció. 1/5-ös szabály, alkalmazás a diszkrét reprezentáció esetére. Evolúciós algoritmusok működésének mérőszámai: MBF, SR, AES.

Evolúciós programozás: reprezentáció véges állapotú automatákkal, operátorok megvalósítása. Blondie24. Genetikus programozás: kifejezések reprezentációja fával, keresztezés és mutáció operátorok.
9. A tantárgy oktatásának módja (előadás, gyakorlat, laboratórium) 1+0+1
10. Követelmények A félév folyamán a hetente kiadott házi feladatokat kell megoldani, összesen három különböző témakörből. A határidő a következő óra kezdete. Egy héten legfeljebb 10 pont szerezhető.
11. Pótlási lehetőségek

TVSZ szerint.

A házi feladatokból legfeljebb kettő pótolható a pótlási héten, külön eljárási díj ellenében.

12. Konzultációs lehetőségek Igény szerint a hallgatókkal előre egyeztetett időpontban.
13. Jegyzet, tankönyv, felhasználható irodalom A.E. Eiben, J.E. Smith Introduction to Evolutionary Computing, Springer-Verlag (2015).
14. A tantárgy elvégzéséhez átlagosan szükséges tanulmányi munka
Kontakt óra28
Félévközi készülés órákra14
Felkészülés zárthelyire0
Házi feladat elkészítése48
Kijelölt írásos tananyag elsajátítása 
Vizsgafelkészülés 
Összesen90
15. A tantárgy tematikáját kidolgozta Sáfár Orsolya