Uporabnost in učinkovitost kanoničnega genetskega algoritma

delo diplomskega seminarja

Gaja Žumer (Author), Marjetka Krajnc (Mentor)

Abstract

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.

Keywords

matematika;kanonični genetski algoritem;konvergenca;markovske verige;izrek o shemah;

Data

Language:	Slovenian
Year of publishing:	2018
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FMF - Faculty of Mathematics and Physics
Publisher:	[G. Žumer]
UDC:	519.2
COBISS:	18434905
Views:	580
Downloads:	781
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Applicability and efficiency of the canonical genetic algorithm
Secondary 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.
Secondary keywords:	mathematics;canonical genetic algorithm;convergence;Markov chains;schema theorem;
Type (COBISS):	Final seminar paper
Study programme:	0
Thesis comment:	Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages:	40 str.
ID:	10959820