izpis_h1_title_alt

Uporabnost in učinkovitost kanoničnega genetskega algoritma : delo diplomskega seminarja
Žumer, Gaja (Avtor), Knez, Marjetka (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (1,39 MB)
.mM - Priloga, prenos (1,15 KB)
.mM - Priloga, prenos (1,97 KB)
.mM - Priloga, prenos (2,65 KB)
.mM - Priloga, prenos (2,57 KB)
.mM - Priloga, prenos (0,62 KB)
.mM - Priloga, prenos (0,58 KB)
.mM - Priloga, prenos (0,87 KB)
.mM - Priloga, prenos (1,20 KB)
.mM - Priloga, prenos (0,92 KB)
.mM - Priloga, prenos (0,97 KB)
.mM - Priloga, prenos (0,95 KB)
.mM - Priloga, prenos (0,36 KB)

Izvleček
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.

Jezik:Slovenski jezik
Ključne besede:kanonični genetski algoritem, konvergenca, markovske verige, izrek o shemah
Vrsta gradiva:Delo diplomslega seminarja/zaključno seminarsko delo/naloga (mb14)
Organizacija:FMF - Fakulteta za matematiko in fiziko
Leto izida:2018
UDK:519.2
COBISS.SI-ID:18434905 Povezava se odpre v novem oknu
Število ogledov:6
Število prenosov:3
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na: Bookmark and Share

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Applicability and efficiency of the canonical genetic algorithm
Izvleček:
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.

Ključne besede:canonical genetic algorithm, convergence, Markov chains, schema theorem

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj