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
muudaGeneetilises 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
muudaPopulatsiooni 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
muudaHindamisfunktsiooni 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
muudaPä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
muudaRistsiire 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
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
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
muudaIsendi 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
muudaAlgoritm 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- ↑ 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.