Kasutaja:KodanikLinde/liivakast
 | See on kasutaja KodanikLinde liivakast. Kasutaja liivakast on kasutajalehekülje alamleht. Siin kasutaja katsetab või valmistab ette loodavaid artikleid. See ei ole entsüklopeediaartikkel. Enda liivakasti loomiseks klõpsa siia. |
Geneetiline algoritm (GA) on otsingumeetod, mis on inspireeritud looduslikust valikust, mida kirjeldas Darwini evolutsiooniteooria. Geneetilise algoritmi leiutaja on John Henry Holland. Aastal 1975 kirjutas sellest raamatu "Adaption in Natural and Artificial Systems".[1] Geneetilises algoritmis kasutatakse geneetikast pärit operaatore nagu mutatsioon, ristsiire ja valik. Geneetilist algoritmi kasutatakse kõrge kvaliteediga lahenduste loomiseks optimiseerimis- ning otsimisprobleemidele.
Meetodika[muuda | muuda lähteteksti]
Geneetilises algoritmis nimetatakse populatsiooniks võimalike lahendusi probleemile, Ühte lahendust nimetatakse isendiks. Igal isendil on komplekt omadusi ehk geenid. Geenid moodustavad kromosoomi ehk lahenduse probleemile. [2] Geneetiline algoritm algab esialgse populatsiooni valimisega. Isendid toodavad järglasi, millel on geenid mõlemalt vanemalt ja nendest moodustub järgmine generatsioon. Kromosoomi esitakse tavalislt kahendsüsteemi numbrite jadana. Geneetiline algoritm koosneb 5 osast: algne populatsioon, hindamisfunktsioon, valik, ristsiire ja mutatsioon. [3]
Algne populatsioon[muuda | muuda lähteteksti]
Populatsiooni suurus sõltub probleemist, mida püütakse lahendada. Tavaliselt koosneb populatsioon 700-1000 isendist. Sageli genereeritakse populatsioon juhuslikult, mis võimaldab otsida sobivat lahendust kõikide võimalike lahenduste hulgast. Vahepeal valitakse algne populatsioon variantide hulgast, kus tõenäoliselt asub ka parim lahendus. [2]
Hindamisfunktsioon[muuda | muuda lähteteksti]
HIndamisfunktsiooni rakendatakse kõikidele isendidele ja sellega saab teada kui hästi üks isend antud probleemi lahendab. Mida kõrgem tulemus seda tõenäolisem on, et selle isendi järglased kuuluvad järgmisesse generatsiooni. [3]
Valik[muuda | muuda lähteteksti]
Peale igat generatsiooni valitakse populatsioonist kindel arv isendeid, kelle järglastest saab uus populatsioon. Isendid valitakse põhimõttel, et isend, millel on kõrgem hinnang on suurem tõenäosus valituks osutuda. [4]
Ristsiire[muuda | muuda lähteteksti]
Ristsiire on kõige tähtsam osa geneetilise algoritmi juures. Valituks osutunud isendite hulgast koostatakse paarid ehk vanemad, mis moodustab uue isendi. Seda korratakse nii kaua kui uues generatsioonis on sama palju isendeid kui oli eelmises. Ristsiirdel on mitu varianti
1 punktiga ristsiire[muuda | muuda lähteteksti]
Valitakse üks juhuslik punkt geenide hulgast. Geenid kuni selle punktini valitakse esimeselt vanemalt ja peale seda punkti teiselt vanemalt ning nendest geenidest saab kromosoom järglasele.
2. punktiga ristsire[muuda | muuda lähteteksti]
Valitakse kaks juhusliku punkti. Geenid kuni esimese punktini võetakse esimeselt vanemalt. Geenid, mis jäävad esimese ja teise punkti vahele võetakse 2. vanemalt ning geenid, mis on peale 2. punkti võetakse esimeselt. Nendest geenidest moodustub kromosoom järglasele. [5]
Mutatsioon[muuda | muuda lähteteksti]
Isendi kromosoomi mõjutavad ka mutatsioonid. Geenil on väike võimalus muteeruda. See tähendab, et iga geen võib mingi tõenäosusega(näiteks 0.05) muutuda millekski muuks. Seda tehakse sellepärast, et populatsiooni mitmekesisust liialt ei langeks.[3]
Lõpetamine[muuda | muuda lähteteksti]
Algoritm lõpetab töö, kui leidub isend, mis täidab minimaalselt ette antud nõudeid või kui eelmise generatsiooni ning praeguse generatsiooni erinevus on piisavalt väike. [3]
Viited[muuda | muuda lähteteksti]
- ↑ Obitko, M (1998). "Genetic algorithms". Vaadatud 01.11.2018.
- ↑ 2,0 2,1 Whitley, Darrell (1994). ""A genetic algorithm tutorial" (PDF)" (PDF). Vaadatud 02.11.2018.
- ↑ 3,0 3,1 3,2 3,3 Vijini Mallawaarachchi (2017). "Introduction to Genetic Algorithms — Including Example Code". Vaadatud 02.11.2018.
{{netiviide}}: nähtamatu tähemärk (juustühik) parameetris|Pealkiri=positsioonil 35 (juhend) - ↑ Obitko, M (1998). "IX. Selection". Vaadatud 05.11.2018.
- ↑ Obitko, M. (1998). "XI. Crossover and Mutation". Vaadatud 05.11.2018.