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". 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.

 Metoodika 
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. 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.

 Algne populatsioon 
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.

 Hindamisfunktsioon 
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.

 Valik 
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.

 Ristsiire 
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.

 Ühe punktiga ristsiire 
pisi|Ühe punktiga ristsiire
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.

 Kahe punktiga ristsire 
pisi|Kahe punktiga ristsiire
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.

 Mutatsioon 
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.

 Lõpetamine 
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.

 Viited 

Kategooria:Algoritmid