Genetický algoritmus
Genetický algoritmus je nedeterministická metóda riešenia problému, vychádzajúca z princípov Darwinovej evolučnej teórie.
Každé riešenie úlohy (aj "zlé") sa nazýva chromozóm a je tvorené binárnym reťazcom o danej dĺžke, ktorá je rovnaká pre všetky chromozómy danej populácie. Populácia je konečná množina chromozómov. Základná populácia resp. nultá generácia populácie je začiatočný stav riešenia. Vývoj k optimálnemu riešeniu prebieha prirodzeným vývojom populácií. Nultá generácia je vygenerovaná náhodne, vygenerované chromozómy, musia byť riešením problému.
Proces reprodukcie:
- Výber chromozómov na kríženie či mutáciu (pseudonáhodný výber podľa pravdepodobnosti úmernej jeho fitnes)
- Kríženie chromozómov (výmena podreťazcov, kde môže prebiehať kríženie jednobodovo, či viacbodovo)
- Mutácia, náhodne zmutujú niektoré gény, mutuje sa s malou pravdepodobnosťou, aby zostala zachovaná genetická informácia
Náhodnosť sa zaisťuje pomocou generovania pseudonáhodných čísel.
Každá populácia sa pomocou reprodukcie zdokonaľuje a to na základe ohodnotenia chromozómov pomocou funkcie f(x) nazývanej fitness. V procese riešenia pomocou genetických algoritmov ide o hľadanie globálneho maxima funkcie fitness, teda ide o to nájsť najlepšie ohodnotené riešenie problému v stavovom priestore.
Pre každú novú generáciu platí:
- počet chromozómov je rovnaký
- krížením a mutáciou vznikajú nové chromozómy
- chromozómy s nízkym fitness ohodnotením sú nahradené chromozómami s vyšším ohodnotením
Niekedy sa najlepšie chromozómy z predchádzajúcej generácie zachovávajú.
Riešenie sa zastaví buď po dosiahnutí nejakej cieľovej hodnoty, alebo po dopredu stanovenom počte generácií.
Pozri aj
[upraviť | upraviť zdroj]Externé odkazy
[upraviť | upraviť zdroj]- Petr Luner: Jemný úvod do genetických algoritmů
- RNDr. Jaroslav Teda, Ph.D.: Genetické algoritmy a jejich aplikace v praxi
- Jiří Šíma, Roman Neruda: Teoretické otázky neuronových sítí (oddiely 14.3 a 14.4 sa zaoberajú genetickými algoritmami)
- Marek Obitko: Introduction to Genetic Algorithms, s interaktívnými Java appletmi (anglicky)
- Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming (anglicky)
- Weise, T., Global Optimization Algorithms - Theory and Application Archivované 2008-09-11 na Wayback Machine (anglicky)