Uporabnost in učinkovitost kanoničnega genetskega algoritma : delo diplomskega seminarja

Žumer, Gaja (author), Knez, Marjetka (mentor)

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.

• Language: Slovenian
• Keywords: kanonični genetski algoritem, konvergenca, markovske verige, izrek o shemah
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2018
• PID: 20.500.12556/RUL-103244
• UDC: 519.2
• COBISS.SI-ID: 18434905
• Publication date in RUL: 15.09.2018

Secondary language

• Language: English
• Title: Applicability and efficiency of the canonical genetic algorithm

Abstract

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.

• Keywords: canonical genetic algorithm, convergence, Markov chains, schema theorem