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)