b'\n_START_ARTICLE_\nGeneetiline algoritm\n_START_PARAGRAPH_\nGeneetiline algoritm (GA) on informaatikas otsingumeetod (algoritm), mis on inspireeritud looduslikust valikust, mida kirjeldas Darwini evolutsiooniteooria. _NEWLINE_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 \xc3\xbcle v\xc3\xb5etud m\xc3\xb5isteid, nagu populatsioon, isend, geen, kromosoom, mutatsioon, ristsiire ja valik. Geneetilist algoritmi kasutatakse optimeerimis- ja otsimisprobleemidele k\xc3\xb5rgetasemeliste lahenduste loomiseks.\n_START_SECTION_\nMeetodika\n_START_PARAGRAPH_\nGeneetilises algoritmis nimetatakse populatsiooniks v\xc3\xb5imalikke lahendusi probleemile. \xc3\x9chte 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\xc3\xa4rglasi, millel on geenid m\xc3\xb5lemalt vanemalt, ja nendest moodustub j\xc3\xa4rgmine generatsioon. Kromosoom esitatakse tavaliselt kahends\xc3\xbcsteemi numbrite jadana. Geneetiline algoritm koosneb viiest osast: algne populatsioon, hindamisfunktsioon, valik, ristsiire ja mutatsioon.\n_START_SECTION_\nAlgne populatsioon\n_START_PARAGRAPH_\nPopulatsiooni suurus s\xc3\xb5ltub probleemist, mida p\xc3\xbc\xc3\xbctakse lahendada. Tavaliselt koosneb populatsioon 700\xe2\x80\x931000 isendist. Sageli genereeritakse populatsioon juhuslikult, mis v\xc3\xb5imaldab otsida sobivat lahendust k\xc3\xb5ikide v\xc3\xb5imalike lahenduste hulgast. Vahepeal valitakse algne populatsioon variantide hulgast, kus t\xc3\xb5en\xc3\xa4oliselt asub ka parim lahendus.\n_START_SECTION_\nHindamisfunktsioon\n_START_PARAGRAPH_\nHindamisfunktsiooni rakendatakse k\xc3\xb5ikidele isenditele ja sellega saab teada, kui h\xc3\xa4sti \xc3\xbcks isend antud probleemi lahendab. Mida k\xc3\xb5rgem tulemus, seda t\xc3\xb5en\xc3\xa4olisem on, et selle isendi j\xc3\xa4rglased kuuluvad j\xc3\xa4rgmisesse generatsiooni.\n_START_SECTION_\nValik\n_START_PARAGRAPH_\nPeale igat generatsiooni valitakse populatsioonist kindel arv isendeid, kelle j\xc3\xa4rglastest saab uus populatsioon. Isendid valitakse p\xc3\xb5him\xc3\xb5ttel, et isendil, millel on k\xc3\xb5rgem hinnang, on suurem t\xc3\xb5en\xc3\xa4osus valituks osutuda.\n_START_SECTION_\nRistsiire\n_START_PARAGRAPH_\nRistsiire on geneetilise algoritmi k\xc3\xb5ige t\xc3\xa4htsam 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.\n_START_SECTION_\n\xc3\x9che punktiga ristsiire\n_START_PARAGRAPH_\nValitakse \xc3\xbcks juhuslik punkt geenide hulgast. Geenid kuni selle punktini valitakse esimeselt vanemalt ja peale seda punkti teiselt vanemalt ning nendest geenidest saab kromosoom j\xc3\xa4rglasele.\n_START_SECTION_\nKahe punktiga ristsire\n_START_PARAGRAPH_\nValitakse kaks juhuslikku punkti. Geenid kuni esimese punktini v\xc3\xb5etakse esimeselt vanemalt. Geenid, mis j\xc3\xa4\xc3\xa4vad esimese ja teise punkti vahele, v\xc3\xb5etakse teiselt vanemalt, ning geenid, mis on peale teist punkti, v\xc3\xb5etakse esimeselt. Nendest geenidest moodustub kromosoom j\xc3\xa4rglasele.\n_START_SECTION_\nMutatsioon\n_START_PARAGRAPH_\nIsendi kromosoomi m\xc3\xb5jutavad ka mutatsioonid. Geenil on v\xc3\xa4ike v\xc3\xb5imalus muteeruda. See t\xc3\xa4hendab, et iga geen v\xc3\xb5ib mingi t\xc3\xb5en\xc3\xa4osusega (n\xc3\xa4iteks 0,05) muutuda millekski muuks. Seda tehakse sellep\xc3\xa4rast, et populatsiooni mitmekesisus liialt ei langeks.\n_START_SECTION_\nL\xc3\xb5petamine\n_START_PARAGRAPH_\nAlgoritm l\xc3\xb5petab t\xc3\xb6\xc3\xb6, kui leidub isend, mis t\xc3\xa4idab minimaalselt ette antud n\xc3\xb5udeid v\xc3\xb5i kui eelmise generatsiooni ning praeguse generatsiooni erinevus on piisavalt v\xc3\xa4ike.'