Geneetiline algoritm
From Wikipedia, the free encyclopedia
Remove ads
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]
Remove ads
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.[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
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
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
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
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
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
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
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
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]
Remove ads
Viited
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads