Řízené křížení v genetických algoritmech
| Thesis title in Czech: | Řízené křížení v genetických algoritmech |
|---|---|
| Thesis title in English: | Directed Mutation in Genetic Algorithms |
| Key words: | genetický algoritmus, křížení, řízené křížení |
| English key words: | genetic algorithm, crossover, directed crossover |
| Academic year of topic announcement: | 2010/2011 |
| Thesis type: | Bachelor's thesis |
| Thesis language: | čeština |
| Department: | Institute of Formal and Applied Linguistics (32-UFAL) |
| Supervisor: | doc. RNDr. Ondřej Bojar, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 13.12.2010 |
| Date of assignment: | 13.12.2010 |
| Date and time of defence: | 06.09.2012 09:00 |
| Date of electronic submission: | 03.08.2012 |
| Date of submission of printed version: | 03.08.2012 |
| Date of proceeded defence: | 06.09.2012 |
| Opponents: | doc. RNDr. David Hoksza, Ph.D. |
| Guidelines |
| Cílem práce je navrhnout a implementovat rozšíření techniky genetických algoritmů o "řízené křížení". Na rozdíl od běžného náhodného generování změn v jedincích bude na základě celé množiny známých jedinců navržen jedinec nový, s ohledem na nejnadějnější rozdíly ve vlastnostech. Pokud např. z populace víme, že několik jedinců s prvním bitem nastaveným na 1 dopadlo v hodnocení podle objektivní funkce lépe než jedinci, kteří jsou stejní až na tento první bit, je vhodným návrhem tento první bit nastavit na 1 i u dalších a zvláště u celkově nejzdatnějších jedinců.
Nedílnou součástí práce je empirické srovnání navržené metody a nějaké "základní" implementace genetických algoritmů na několika málo úlohách z hlediska počtu evaluovaných jedinců a nejvyšší dosažené hodnoty objektivní funkce. Žádoucí je novou techniku zapojit jak v tradičním schématu iterací před generace s křížením i mutací, tak i v "jednogeneračním" hledání podobném klasickému hill-climbing: starší jedince nikdy nezapomeneme, náhodně generujeme pouze počáteční množiny a všechny další jedince již generujeme řízeně, tj. deterministicky, z ní a nových jedinců. Práce by též měla stručně porovnat navrženou metodu s podobnými technikami z literatury. |
| References |
| Bhandari, D. and Pal, N.R. and Pal, S.K.: Directed mutation in genetic algorithms. Information sciences 79 (3-4), pp. 251-270, Elsevier, 1994.
Whitley, Darrell: A genetic algorithm tutorial. Statistics and Computing 2 (4), pp. 65-85, Springer Netherlands, 1994. |