20.500.12556/RUL-103244 Uporabnost in učinkovitost kanoničnega genetskega algoritma delo diplomskega seminarja Applicability and efficiency of the canonical genetic algorithm Genetski algoritem je stohastična optimizacijska metoda za reševanje zahtevnejših oziroma slabše obvladljivih optimizacijskih problemov. V diplomski nalogi 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. Dokazano je, da kanonični algoritem na splošno ne konvergira h globalni rešitvi, kar pa ne velja za njegovi različici, kjer se na vsakem koraku ohranja najboljša najdena rešitev. V prvem primeru je dokazana konvergenca elitnega genetskega algoritma, pri čemer so matrike operatorjev križanja ($K$), selekcije ($S$) in mutacije ($M$) stohastične matrike. Poleg tega za matriko $M$ dodatno velja, da je pozitivna, matrika $S$ pa mora biti stolpično dopustna. Izkaže se, da so zadostni pogoji za konvergenco elitnega genetskega algoritma milejši od prej omenjenih. Matrike $K$, $S$ in $M$ morajo biti še vedno stohastične in imeti pozitivne vrednosti na glavni diagonali, matrika M pa mora biti ireducibilna. Genetic algorithm is a stochastic optimisation method for solving difficult optimisation problems. This bachelor's thesis first discusses its implementation, followed by examples indicating the inconveniences which may appear when dealing with putting genetic algorithm into practise. 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. It is proven that canonical genetic algorithm does not converge to the global optimum, which does not hold for two of its variants maintaining the best solution found over time, without using it to generate new individuals. The first example shows a proof of convergence of an elitist genetic algorithm, where the matrices of crossover operator $K$, selection operator $S$ and mutation operator $M$ are stochastic matrices. Additionaly, matrix $M$ has to be positive and matrix $S$ has to be column allowable. It turns out, as stated in the second proof of convergence, that the sufficient conditions for convergence are not as harsh as mentioned previously. Matrices $K$, $S$ and $M$ have to be stochastic and diagonal-positive, while matrix $M$ has to be irreducible as well. kanonični genetski algoritem konvergenca markovske verige izrek o shemah canonical genetic algorithm convergence Markov chains schema theorem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2018-09-15 07:45:55 2018-09-15 07:46:00 2022-10-11 12:21:26 0000-00-00 00:00:00 2018 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.2 90461 18434905 427.pdf 427.pdf 1 32E2F51EE4177512EDD41F63F0423C9D a3a8a5a94c7e27a82cf355556e16d38895bbf646bddbebd046cbcc693eb20611 bfda59d8-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=113637 431.m 431.m 1 534F7FDE4F3D626A4BBA371025B0DEEB 761b04a7586e0d58e8a636933f48ddb7e5a99fbc5f1e72af7a960b61c3d83870 c0302e1a-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=113642 436.m 436.m 1 BF1C7A26E3F068241E628D4066DB4AF3 925a9789131a3f2fc872e14f9b82a149bf199039d1fb8082d5708df13fff1ecf c0842c56-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=113647 439.m 439.m 1 C5D4FBF1B39F4F0A1B6CA353E1D82437 f50484c39bd2481236b5ed779c8f91f654962f234c4b3ef7622d9cd31b206c2b c0da61b1-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=113652 433.m 433.m 1 309DED103BB15A48E74B8EBFBDB2927E 291d7e387389a378a875a48d4d435b0687c59f8b2ad32a3a89e3e973132dccb3 c0518e85-a1b5-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=113644 Fakulteta za matematiko in fiziko 0 0 0