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 
 Genetické programovanie

 Externé odkazy 
 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  (anglicky)

Kategória:Umelá inteligencia
Kategória:Algoritmy

sv:Genetisk programmering#Genetisk algoritm