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