Geneetiline algoritm
Geneetiline algoritm (GA) on informaatikas otsingumeetod (algoritm), mis on inspireeritud looduslikust valikust, mida kirjeldas Darwini evolutsiooniteooria.
Geneetilise algoritmi leiutas John Henry Holland. 1975. aastal kirjutas John Henry Holland sellest raamatu "Adaption in Natural and Artificial Systems".[1] Geneetilises algoritmis kasutatakse bioloogiast ja geneetikast üle võetud mõisteid, nagu populatsioon, isend, geen, kromosoom, mutatsioon, ristsiire ja valik. Geneetilist algoritmi kasutatakse optimeerimis- ja otsimisprobleemidele kõrgetasemeliste lahenduste loomiseks.[2]
Metoodika[muuda | muuda lähteteksti]
Geneetilises algoritmis nimetatakse populatsiooniks võimalikke 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. Kromosoom esitatakse tavaliselt kahendsüsteemi numbrite jadana. Geneetiline algoritm koosneb viiest 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 isenditele 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]
Pärast igat generatsiooni valitakse populatsioonist kindel arv isendeid, kelle järglastest saab uus populatsioon. Isendid valitakse põhimõttel, et isendil, millel on kõrgem hinnang, on suurem tõenäosus valituks osutuda.[4]
Ristsiire[muuda | muuda lähteteksti]
Ristsiire on geneetilise algoritmi kõige tähtsam osa. Valituks osutunud isendite hulgast koostatakse paarid ehk vanemad, mis moodustavad uue isendi. Seda korratakse nii kaua, kui uues generatsioonis on sama palju isendeid, kui oli eelmises. Ristsiirdel on mitu varianti.[5]
Ühe punktiga ristsiire[muuda | muuda lähteteksti]
Valitakse üks juhuslik punkt geenide hulgast. Geenid kuni selle punktini valitakse esimeselt vanemalt ja pärast seda punkti teiselt vanemalt ning nendest geenidest saab kromosoom järglasele.[5]
Kahe punktiga ristsire[muuda | muuda lähteteksti]
Valitakse kaks juhuslikku punkti. Geenid kuni esimese punktini võetakse esimeselt vanemalt. Geenid, mis jäävad esimese ja teise punkti vahele, võetakse teiselt vanemalt, ning geenid, mis on pärast teist 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 mitmekesisus 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 2,2 Whitley, D (1994). "A genetic algorithm tutorial (PDF)" (PDF). Vaadatud 02.11.2018.
- ↑ 3,0 3,1 3,2 3,3 Mallawaarachchi, V (2017). "Introduction to Genetic Algorithms — Including Example Code". Vaadatud 02.11.2018.
- ↑ Obitko, M (1998). "IX. Selection". Vaadatud 05.11.2018.
- ↑ 5,0 5,1 5,2 Obitko, M. (1998). "XI. Crossover and Mutation". Vaadatud 05.11.2018.