Geneetilised algoritmid — mis need on ja kuidas nad optimeerivad otsingut

Looduslikku evolutsiooni võib modelleerida kui mängu, milles hästi mängiva organismi tasu on tema geneetilise materjali edasiandmine järeltulijatele ja jätkuv ellujäämine.^[2] Looduslikus evolutsioonis sõltub see, kui hästi indiviid toimib, sellest, kellega ta koos töötab ja kellega ta konkureerib, samuti keskkonnast. Geneetilised algoritmid on loomuliku valiku simulatsioon optimeerimisprobleemi lahenduskandidaatide (kromosoomide, indiviidide, olendite või fenotüüpide) populatsioonile.

Kandidaate hinnatakse ja ristatakse, et leida häid lahendusi. Sellised lahendused võivad võtta palju aega ja ei ole inimesele ilmselged. Evolutsioonifaasi alustatakse juhuslikult genereeritud olendite populatsiooniga. Igas põlvkonnas hinnatakse iga populatsiooni kuuluva isendi sobivust. Mõned neist valitakse juhuslikult välja praegusest populatsioonist (nende sobivuse alusel) ja muudetakse (rekombineeritakse ja võimalusel mutatakse juhuslikult), et moodustada uus populatsioon. Tsükkel kordub selle uue populatsiooniga. Algoritm lõpeb kas pärast kindlaksmääratud arvu põlvkondade möödumist või kui populatsioon on saavutanud hea sobivuse taseme. Kui algoritm on lõppenud maksimaalse arvu põlvkondade saavutamise tõttu, ei tähenda see tingimata, et on saavutatud hea sobivus.

Selle programmeerimine arvutis

Pseudokood on järgmine:

1. Initsialiseerimine: Luuakse mõned võimalikud lahendused; väga sageli on need juhuslikud väärtused.
2. Hindamine: Sobivusfunktsioon hindab iga lahendust; tulemus on number, mis näitab, kui hästi see lahendus probleemi lahendab.
3. Järgmisi samme tehakse seni, kuni peatamise nõue on täidetud:
1. Valik: Valige lahendused/indiviidid järgmiseks iteratsiooniks.
2. Rekombinatsioon: Kombineerida valitud lahendused
3. Mutatsioon: Muudab juhuslikult äsja loodud lahendusi
4. Hindamine: Kohaldage sobivusfunktsiooni, vt samm 2.
5. Kui peatamise nõue ei ole täidetud, alustage uuesti valimise etapiga.

Näide

Ülaltoodud kirjeldus on abstraktne. Konkreetne näide aitab.

Üldiselt

Geneetilised algoritmid on head probleemide lahendamisel, mis hõlmavad ajakava ja ajakava koostamist. Neid on rakendatud ka inseneriteaduses. Neid kasutatakse sageli globaalsete optimeerimisprobleemide lahendamiseks.

Üldise rusikareeglina võib geneetiline algoritm olla kasulik probleemivaldkondades, millel on keeruline sobivusmaastik, kuna segamine on mõeldud selleks, et viia populatsioon eemale lokaalsetest optimaalsustest, millesse traditsiooniline mäkketõusu algoritm võib takerduda. Tavaliselt kasutatavad ristamisoperaatorid ei saa muuta ühtlast populatsiooni. Mutatsioon üksi võib tagada üldise geneetilise algoritmi protsessi ergodilisuse (vaadelduna Markovi ahelana).

Näiteid geneetiliste algoritmide abil lahendatud probleemidest on näiteks: päikesekollektorile päikesevalguse suunamiseks kavandatud peeglid, kosmoses raadiosignaalide vastuvõtmiseks kavandatud antennid, arvutifiguuride kõndimismeetodid, aerodünaamiliste kehade optimaalne projekteerimine keerulistes vooluväljades.

Skiena soovitab oma Algoritmide disaini käsiraamatus mitte kasutada geneetilisi algoritme mis tahes ülesannete puhul: "On üsna ebaloomulik modelleerida rakendusi geneetiliste operaatorite, nagu mutatsioon ja ristumine, abil bittide jadade peal. Pseudobioloogia lisab teie ja teie probleemi vahele veel ühe keerukuse taseme. Teiseks võtavad geneetilised algoritmid mittetriviaalsete probleemide puhul väga kaua aega. [...] Analoogia evolutsiooniga - kus märkimisväärne edasiminek nõuab [sic] miljoneid aastaid - võib olla üsna asjakohane. [...] Ma ei ole kunagi kokku puutunud ühegi probleemiga, mille lahendamiseks geneetilised algoritmid oleksid mulle tundunud õige viis. Lisaks ei ole ma kunagi näinud ühtegi geneetiliste algoritmide abil saadud arvutustulemust, mis oleks mulle positiivset muljet avaldanud. Jääge oma heuristilise otsingu voodoo vajaduste jaoks simuleeritud lõõmutamise juurde."

Lauamängud

Lauamängud on väga oluline osa geneetiliste algoritmide rakendamisest mänguteooria probleemidele. Suur osa arvutusliku intelligentsuse ja mängude alastest töödest oli suunatud klassikalistele lauamängudele, nagu tic-tac-toe,^[3] male ja kabe.^[4] Laudamänge saab nüüd enamikul juhtudel mängida arvuti kõrgemal tasemel kui parimad inimesed, isegi pimedate ammendavate otsingumeetodite abil. Go on sellest tendentsist märkimisväärne erand, mis on seni masinate rünnakutele vastu pidanud. Parimad Go arvutimängijad mängivad praegu hea algaja tasemel.^[5][6] Go strateegia tugineb väidetavalt suurel määral mustrituvastusele, mitte ainult loogilisele analüüsile, nagu males ja muudes mängudes, mis sõltuvad rohkem mänguosadest. Kvaliteetsete lahenduste leidmiseks vajalik suur efektiivne hargnemiskoefitsient piirab tugevalt eelvaatlust, mida saab kasutada käikude järjestuse otsingu raames.

Arvutimängud

Geneetilist algoritmi saab kasutada arvutimängudes tehisintellekti loomiseks (arvuti mängib teie vastu). See võimaldab realistlikumat mängukogemust; kui inimmängija suudab leida sammude jada, mis viib alati edule, isegi kui seda erinevates mängudes korratakse, siis ei saa enam väljakutset olla. Seevastu kui õppimise tehnika, näiteks geneetiline algoritm strateegile, suudab vältida varasemate vigade kordamist, on mängul rohkem mängitavust.

Geneetilised algoritmid vajavad järgmisi osi:

• Meetod väljakutse lahenduse esitamiseks (nt sõdurite suunamine rünnakus strateegiamängus).
• Sobivus- või hindamisfunktsioon, et määrata instantsi kvaliteeti (nt vastase poolt sellise rünnaku käigus tekitatud kahju mõõtmine).

Sobivusfunktsioon võtab vastu üksuse muteeritud instantsi ja mõõdab selle kvaliteeti. See funktsioon on kohandatud vastavalt probleemivaldkonnale. Paljudel juhtudel, eriti kui tegemist on koodi optimeerimisega, võib sobivusfunktsioon olla lihtsalt süsteemi ajastusfunktsioon. Kui geneetiline representatsioon ja sobivusfunktsioon on määratletud, siis geneetiline algoritm instantseerib esialgseid kandidaate, nagu eespool kirjeldatud, ja seejärel parandab neid mutatsiooni, ristamise, inversiooni ja valikuoperaatorite korduva rakendamise kaudu (nagu on määratletud vastavalt probleemivaldkonnale).

Geneetilise algoritmi kasutamisel on piirangud võrreldes alternatiivsete optimeerimisalgoritmidega:

• Korduv sobivusfunktsiooni hindamine keerukate probleemide puhul on sageli kunstlike evolutsiooniliste algoritmide kõige piiravam segment. Keeruliste probleemide optimaalse lahenduse leidmine nõuab sageli väga kulukaid sobivusfunktsioonide hindamisi. Reaalse maailma probleemide, näiteks struktuurilise optimeerimise probleemide puhul võib ühe funktsiooni hindamine nõuda mitu tundi kuni mitu päeva täielikku simulatsiooni. Tüüpilised optimeerimismeetodid ei saa sellist tüüpi probleemidega hakkama. Sageli on vaja kasutada lähendamist, sest täpse lahenduse arvutamine võtab liiga kaua aega. Geneetilised algoritmid kombineerivad mõnikord erinevaid lähendusmudeleid, et lahendada keerulisi reaalseid probleeme.
• Geneetilised algoritmid ei ole hästi skaleeritavad. See tähendab, et kui muteeritavate elementide arv on suur, suureneb otsinguruumi suurus sageli eksponentsiaalselt. See muudab selle tehnika kasutamise äärmiselt keeruliseks selliste probleemide puhul nagu mootori, maja või lennuki projekteerimine. Geneetiliste algoritmide kasutamiseks selliste probleemide puhul tuleb need jaotada võimalikult lihtsasse esitusviisi. Seetõttu näeme evolutsioonilisi algoritme, mis kodeerivad mootorite asemel ventilaatorite labade projekte, üksikasjalike ehitusplaanide asemel hoonete kujundeid ja tervete lennukikavandite asemel tiibu. Teine keerukuse probleem on küsimus, kuidas kaitsta osasid, mis on evolutsiooniliselt esindanud häid lahendusi, edasise hävitava mutatsiooni eest, eriti kui nende sobivuse hindamine nõuab nende head kombinatsiooni teiste osadega.
• "Parem" lahendus on ainult võrreldes teiste lahendustega. Selle tulemusena ei ole peatumiskriteerium iga probleemi puhul selge.
• Paljude probleemide puhul kipuvad geneetilised algoritmid lähenema pigem lokaalsete optimaalsete või isegi suvaliste punktide kui probleemi globaalse optimaalsuse suunas. See tähendab, et algoritm ei "oska" ohverdada lühiajalist sobivust pikemaajalise sobivuse saavutamiseks. Selle esinemise tõenäosus sõltub sobivusfunktsiooni kujust: teatavate probleemide puhul on globaalse optima leidmine lihtne, teiste puhul võib funktsioonil olla lihtsam leida lokaalseid optimaid. Seda probleemi võib vähendada, kui kasutada teistsugust sobivusfunktsiooni, suurendada mutatsioonikiirust või kasutada valikumeetodeid, mis säilitavad mitmekesise lahenduste populatsiooni. Levinud tehnika mitmekesisuse säilitamiseks on "niššikaristuse" kasutamine: mis tahes piisavalt sarnaste isendite rühmale (nišši raadius) lisatakse karistus, mis vähendab selle rühma esindatust järgmistes põlvkondades, võimaldades teisi (vähem sarnaseid) isendeid populatsioonis hoida. See trikk ei pruugi siiski olla tõhus, sõltuvalt probleemi maastikust. Teine võimalik tehnika oleks lihtsalt asendada osa populatsioonist juhuslikult genereeritud isenditega, kui enamik populatsioonist on liiga sarnane. Mitmekesisus on geneetilistes algoritmides (ja geneetilises programmeerimises) oluline, sest homogeense populatsiooni ületamine ei anna uusi lahendusi. Evolutsioonistrateegiates ja evolutsioonilises programmeerimises ei ole mitmekesisus oluline, sest rohkem toetutakse mutatsioonile.
• Dünaamiliste andmekogumitega töötamine on keeruline, kuna genoomid hakkavad varakult lähenema lahendustele, mis ei pruugi enam kehtida hilisemate andmete puhul. Selle probleemi lahendamiseks on pakutud mitmeid meetodeid, mis suurendavad geneetilist mitmekesisust ja takistavad varajast konvergentsi, kas suurendades mutatsiooni tõenäosust, kui lahenduse kvaliteet langeb (nn käivitatav hüpermutatsioon), või lisades aeg-ajalt geenivarasse täiesti uusi, juhuslikult loodud elemente (nn juhuslikud immigrandid). Evolutsioonistrateegiaid ja evolutsioonilist programmeerimist saab jällegi rakendada nn "komistrateegia" abil, mille puhul vanemaid ei säilitata ja uusi vanemaid valitakse ainult järglaste hulgast. See võib olla dünaamiliste probleemide puhul tõhusam.
• Geneetilised algoritmid ei saa tõhusalt lahendada probleeme, mille ainus sobivusnäitaja on üks õige/vale (nagu otsustusprobleemid), kuna puudub võimalus konvergeeruda lahenduse suunas (ei ole mäge, millele ronida). Sellistel juhtudel võib juhuslik otsing leida lahenduse sama kiiresti kui GA. Kui aga olukord võimaldab edu/ebaõnnestumise katse kordamist, mis annab (võimalik, et) erinevaid tulemusi, siis on sobiv sobivaks sobivusmõõduks õnnestumiste ja ebaõnnestumiste suhe.
• Konkreetsete optimeerimisprobleemide ja probleemiinstallatsioonide puhul võivad teised optimeerimisalgoritmid olla geneetilistest algoritmidest tõhusamad lähenemise kiiruse poolest. Alternatiivsete ja täiendavate algoritmide hulka kuuluvad evolutsioonistrateegiad, evolutsiooniline programmeerimine, simuleeritud lõõmutamine, Gaussi kohandamine, mäe ronimine ja parveintelligentsus (nt: sipelgakoloonia optimeerimine, osakeste parve optimeerimine) ning täisarvulisel lineaarprogrammimisel põhinevad meetodid. Geneetiliste algoritmide sobivus sõltub probleemiga seotud teadmiste hulgast; hästi tuntud probleemidele on sageli olemas paremad, spetsiifilisemad lähenemisviisid.

1950. aastal pakkus Alan Turing välja "õppiva masina", mis oleks paralleelne evolutsiooni põhimõtetega. Evolutsiooni arvutisimulatsioon algas juba 1954. aastal Nils Aall Barricelli tööga, kes kasutas arvutit Princetoni instituudis (Princeton, New Jersey). Tema 1954. aasta publikatsioon ei pälvinud laialdast tähelepanu. Alates 1957. aastast avaldas Austraalia kvantitatiivne geneetik Alex Fraser rea artikleid, mis käsitlesid mõõdetavat omadust kontrollivate mitme lokaaliga organismide kunstliku valiku simulatsiooni. Nendest algustest lähtudes muutus evolutsiooni arvutisimulatsioon bioloogide poolt 1960. aastate alguses tavalisemaks ning meetodeid kirjeldasid Fraser ja Burnell (1970) ning Crosby (1973) raamatutes. Fraseri simulatsioonid sisaldasid kõiki tänapäevaste geneetiliste algoritmide olulisi elemente. Lisaks sellele avaldas Hans-Joachim Bremermann 1960. aastatel rea artikleid, milles võeti samuti kasutusele optimeerimisprobleemide lahendamise populatsioon, mis läbis rekombinatsiooni, mutatsiooni ja valiku. Bremermanni uurimistöö sisaldas ka kaasaegsete geneetiliste algoritmide elemente. Teiste märkimisväärsete varajaste pioneeride hulka kuuluvad Richard Friedberg, George Friedman ja Michael Conrad. Paljud varajased tööd on uuesti trükitud Fogelis (1998).

Kuigi Barricelli simuleeris oma 1963. aastal avaldatud töös lihtsa mängu mängimise võime evolutsiooni, sai kunstlik evolutsioon 1960. aastatel ja 1970. aastate alguses Ingo Rechenbergi ja Hans-Paul Schwefeli töö tulemusena laialdaselt tunnustatud optimeerimismeetodiks - Rechenbergi rühm suutis evolutsioonistrateegiate abil lahendada keerulisi inseneriprobleeme. Teine lähenemine oli Lawrence J. Fogeli evolutsioonilise programmeerimise tehnika, mis pakuti välja tehisintellekti genereerimiseks. Evolutsiooniline programmeerimine kasutas algselt piiratud olekuga masinaid keskkonna ennustamiseks ning kasutas varieerumist ja valikut ennustusloogika optimeerimiseks. Geneetilised algoritmid said eriti populaarseks John Hollandi tööde kaudu 1970ndate alguses, eriti tema raamatu "Adaptation in Natural and Artificial Systems" (1975) kaudu. Tema töö sai alguse rakuautomaatide uuringutest, mida Holland ja tema õpilased viisid läbi Michigani ülikoolis. Holland võttis kasutusele formaliseeritud raamistiku järgmise põlvkonna kvaliteedi prognoosimiseks, mida tuntakse Holland'i skeemiteoreemina. GA-de uurimine jäi suuresti teoreetiliseks kuni 1980. aastate keskpaigani, mil Pittsburghis, Pennsylvanias toimus esimene rahvusvaheline geneetiliste algoritmide konverents.