Uporabnost in učinkovitost kanoničnega genetskega algoritmaŽumer, Gaja (Avtor) Knez, Marjetka (Mentor) kanonični genetski algoritemkonvergencamarkovske verigeizrek o shemahGenetski 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.20182018-09-15 07:45:55Delo diplomskega seminarja/zaključno seminarsko delo/naloga103244sl