Izbrane teme sodobne fizike in matematike
Genetski algoritem je stohastična optimizacijska metoda za reševanje zahtevnejših oziroma slabše obvladljivih optimizacijskih problemov. V članku je najprej opisana njegova implementacija, sledeči primeri pa opozarjajo na pasti, ki se lahko pri tem pojavijo. Pri iskanju rezultata genetski algoritem preiskuje območja, za katera je bolj verjetno, da bodo vsebovala globalno optimalno rešitev. O tem govori izrek o shemah, ki nakazuje na mehanizem napredovanja algoritma, ne moremo pa ga uporabiti za analizo konvergence. V ta namen potrebujemo teorijo končnih homogenih markovskih verig. Članek vsebuje komentar na konvergenco kanoničnega genetskega algoritma in dveh njegovih različic.
Genetic algorithm is a stochastic optimisation method for solving difficult optimisation problems. This article first discusses its implementation, followed by examples indicating the inconveniences which may appear when dealing with putting genetic algorithm into practice. When searching for the best solution, genetic algorithm inspects areas with the higher probability of containing a globally optimal solution. Schema theorem tries to explain the mechanics behind genetic algorithm, but it cannot be used for the analysis of its convergence properties. For this purpose, finite homogeneous Markov chains need to be applied. The article comments on convergence of canonical genetic algorithm and two of its versions.