Geneetiline algoritm

Geneetiline algoritm (GA) on informaatikas otsingumeetod (algoritm), mis on inspireeritud looduslikust valikust, mida kirjeldas Darwini evolutsiooniteooria. 
Geneetilise algoritmi leiutas John Henry Holland. Aastal 1975 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.

Meetodika

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

Peale 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

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.

Kahe punktiga ristsire

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