Geneettinen algoritmi

Mikä se on?

Luonnollinen evoluutio voidaan mallintaa pelinä, jossa hyvin elämää pelaavan organismin palkintona on sen perintöaineksen siirtyminen seuraajilleen ja sen jatkuva eloonjääminen.^[2] Luonnollisessa evoluutiossa se, miten hyvin yksilö menestyy, riippuu siitä, kenen kanssa se toimii ja kenen kanssa se kilpailee, sekä ympäristöstä. Geneettiset algoritmit simuloivat luonnonvalintaa optimointiongelman ratkaisuehdokkaiden (kromosomien, yksilöiden, olentojen tai fenotyyppien) populaatiossa.

Ehdokkaita arvioidaan ja risteytetään, jotta saadaan aikaan hyviä ratkaisuja. Tällaiset ratkaisut voivat viedä paljon aikaa, eivätkä ne ole ihmiselle itsestään selviä. Evoluutiovaihe aloitetaan satunnaisesti luotujen olioiden populaatiolla. Jokaisessa sukupolvessa jokaisen populaation yksilön kunto arvioidaan. Jotkut valitaan satunnaisesti nykyisestä populaatiosta (niiden kelpoisuuden perusteella) ja muutetaan (yhdistetään uudelleen ja mahdollisesti mutatoidaan satunnaisesti) uuden populaation muodostamiseksi. Sykli toistuu tämän uuden populaation kanssa. Algoritmi päättyy joko sen jälkeen, kun tietty määrä sukupolvia on kulunut tai kun populaation hyvä kuntotaso on saavutettu. Jos algoritmi on päättynyt sukupolvien enimmäismäärän saavuttamiseen, se ei välttämättä tarkoita, että hyvä kuntotaso on saavutettu.

Tämän ohjelmointi tietokoneella

Pseudokoodi on:

1. Alustaminen: Hyvin usein näillä on satunnaisia arvoja.
2. Arviointi: Pistemäärä on luku, joka kertoo, kuinka hyvin ratkaisu ratkaisee ongelman.
3. Seuraavat vaiheet suoritetaan, kunnes pysäytysvaatimus täyttyy:
1. Valinta: Valitse ratkaisut/yksilöt seuraavaa iteraatiota varten.
2. Rekombinaatio: Yhdistä poimitut ratkaisut
3. Mutaatio: Muuttaa satunnaisesti äskettäin luotuja ratkaisuja
4. Arviointi: Sovelletaan fitness-funktiota, katso vaihe 2.
5. Jos pysäytysvaatimus ei täyty, aloitetaan valintavaiheesta uudelleen.

Esimerkki

Edellä oleva kuvaus on abstrakti. Konkreettinen esimerkki auttaa.

Sovellukset

Yleisesti ottaen

Geneettiset algoritmit ovat hyviä ratkaisemaan ongelmia, joihin kuuluvat aikataulujen laatiminen ja aikataulutus. Niitä on sovellettu myös tekniikan alalla. Niitä käytetään usein globaalien optimointiongelmien ratkaisemiseen.

Yleisenä nyrkkisääntönä voidaan todeta, että geneettiset algoritmit voivat olla hyödyllisiä ongelma-alueilla, joilla on monimutkainen kuntomaisema, sillä sekoittaminen on suunniteltu siirtämään populaatio pois paikallisista optimaaleista, joihin perinteinen vuorikiipeilyalgoritmi saattaa juuttua. Yleisesti käytetyt crossover-operaattorit eivät voi muuttaa mitään yhtenäistä populaatiota. Pelkkä mutaatio voi varmistaa geneettisen algoritmin kokonaisprosessin ergodisuuden (Markovin ketjuna tarkasteltuna).

Esimerkkejä geneettisillä algoritmeilla ratkaistuista ongelmista ovat: peilit, jotka on suunniteltu ohjaamaan auringonvalo aurinkokeräimeen, antennit, jotka on suunniteltu vastaanottamaan radiosignaaleja avaruudessa, tietokoneen hahmojen kävelymenetelmät, aerodynaamisten kappaleiden optimaalinen suunnittelu monimutkaisissa virtauskentissä.

Algoritmien suunnittelun käsikirjassaan Skiena kehottaa välttämään geneettisiä algoritmeja kaikissa tehtävissä: "On melko luonnotonta mallintaa sovelluksia geneettisten operaattoreiden, kuten mutaation ja risteytyksen, avulla bittijonoihin. Pseudobiologia lisää toisen tason monimutkaisuutta sinun ja ongelmasi väliin. Toiseksi geneettiset algoritmit vievät hyvin kauan aikaa ei-triviaaleissa ongelmissa. [...] Vertaus evoluutioon - jossa merkittävä edistys vaatii miljoonia vuosia - voi olla varsin osuva. [...] En ole koskaan kohdannut mitään ongelmaa, johon geneettiset algoritmit olisivat mielestäni olleet oikea tapa puuttua. Lisäksi en ole koskaan nähnyt geneettisiä algoritmeja käyttäen raportoituja laskennallisia tuloksia, jotka olisivat tehneet minuun myönteisen vaikutuksen. Pysy simuloidussa hehkutuksessa heuristisen haun voodoo-tarpeisiisi.""

Lautapelit

Lautapelit ovat erittäin tärkeä osa geneettisten algoritmien soveltamista peliteoreettisiin ongelmiin. Suuri osa laskennallisen älykkyyden ja pelien varhaisesta työstä kohdistui klassisiin lautapeleihin, kuten tic-tac-toe-peleihin,^[3] shakki ja tammi.^[4] Tietokone voi nykyään useimmissa tapauksissa pelata lautapelejä korkeammalla tasolla kuin paras ihminen, jopa sokeilla tyhjentävillä hakutekniikoilla. Go on huomattava poikkeus tästä suuntauksesta, ja se on toistaiseksi vastustanut konehyökkäyksiä. Parhaat Go:n tietokonepelaajat pelaavat nykyään hyvän aloittelijan tasolla.^[5][6] Go-strategian sanotaan perustuvan pitkälti kuvioiden tunnistamiseen eikä pelkästään loogiseen analyysiin, kuten shakissa ja muissa enemmän nappuloista riippumattomissa peleissä. Laadukkaiden ratkaisujen löytämiseksi tarvittava valtava tehokas haarautumiskerroin rajoittaa voimakkaasti siirtosarjan etsinnässä käytettävää ennakointia.

Tietokonepelit

Geneettistä algoritmia voidaan käyttää tietokonepeleissä tekoälyn luomiseen (tietokone pelaa sinua vastaan). Tämä mahdollistaa realistisemman pelikokemuksen; jos ihmispelaaja pystyy löytämään askelsarjan, joka johtaa aina menestykseen, vaikka se toistettaisiin eri peleissä, ei haastetta voi enää olla. Jos taas oppimistekniikka, kuten geneettinen algoritmi strategiaa varten, pystyy välttämään aiempien virheiden toistamista, peli on pelattavampi.

Geneettiset algoritmit vaativat seuraavat osat:

• Menetelmä haasteen esittämiseksi ratkaisun kannalta (esim. sotilaiden reitittäminen hyökkäyksessä strategiapelissä).
• Kunto- tai arviointifunktio, jolla määritetään instanssin laatu (esim. vastustajalle tällaisessa hyökkäyksessä aiheutetun vahingon mittaaminen).

Kuntofunktio hyväksyy entiteetin mutatoidun instanssin ja mittaa sen laatua. Tämä funktio on räätälöity ongelma-alueen mukaan. Monissa tapauksissa, erityisesti koodin optimointiin liittyvissä tapauksissa, fitness-funktio voi olla yksinkertaisesti järjestelmän ajoitusfunktio. Kun geneettinen esitys ja kuntofunktio on määritelty, geneettinen algoritmi muodostaa alkuperäiset ehdokkaat edellä kuvatulla tavalla ja parantaa niitä soveltamalla toistuvasti mutaatio-, ristiinkytkentä-, inversio- ja valintaoperaattoreita (jotka on määritelty ongelma-alueen mukaan).

Rajoitukset

Geneettisen algoritmin käytössä on rajoituksia verrattuna vaihtoehtoisiin optimointialgoritmeihin:

• Monimutkaisten ongelmien toistuva soveltuvuusfunktion arviointi on usein keinotekoisten evoluutioalgoritmien rajoittavin osa-alue. Optimaalisen ratkaisun löytäminen monimutkaisiin ongelmiin vaatii usein hyvin kalliita kuntoarvioita. Todellisen maailman ongelmissa, kuten rakenteellisissa optimointiongelmissa, yhden funktion arviointi voi vaatia useita tunteja tai jopa useita päiviä täydellistä simulointia. Tyypilliset optimointimenetelmät eivät pysty käsittelemään tämäntyyppisiä ongelmia. Usein joudutaan käyttämään approksimaatiota, koska tarkan ratkaisun laskeminen vie liian kauan. Geneettiset algoritmit yhdistelevät joskus erilaisia approksimaatiomalleja monimutkaisten tosielämän ongelmien ratkaisemiseksi.
• Geneettiset algoritmit eivät skaalaudu hyvin. Jos mutaatiolle altistuvien elementtien määrä on suuri, hakuavaruuden koko kasvaa usein eksponentiaalisesti. Tämän vuoksi tekniikkaa on erittäin vaikea käyttää esimerkiksi moottorin, talon tai lentokoneen suunnitteluun. Jotta geneettisiä algoritmeja voitaisiin käyttää tällaisissa ongelmissa, ne on pilkottava mahdollisimman yksinkertaiseen esitystapaan. Tästä syystä näemme evoluutioalgoritmeja, jotka koodaavat tuulettimien siipiä moottoreiden sijasta, rakennusten muotoja yksityiskohtaisten rakennussuunnitelmien sijasta ja siipiprofiileja kokonaisten lentokonemallien sijasta. Toinen monimutkaisuuteen liittyvä ongelma on kysymys siitä, miten suojella osia, jotka ovat kehittyneet edustamaan hyviä ratkaisuja, uusilta tuhoavilta mutaatioilta, erityisesti silloin, kun niiden kelpoisuusarviointi edellyttää, että ne yhdistyvät hyvin muiden osien kanssa.
• "Parempi" ratkaisu on vain verrattuna muihin ratkaisuihin. Tämän vuoksi pysäytyskriteeri ei ole selvä kaikissa ongelmissa.
• Monissa ongelmissa geneettisillä algoritmeilla on taipumus konvergoitua kohti paikallisia optimeja tai jopa mielivaltaisia pisteitä ongelman globaalin optimin sijasta. Tämä tarkoittaa, että algoritmi ei "osaa" uhrata lyhyen aikavälin kuntoa pitkän aikavälin kunnon saavuttamiseksi. Tämän todennäköisyys riippuu kuntoarvofunktion muodosta: tietyissä ongelmissa globaalin optimin löytäminen on helppoa, toisissa taas funktion voi olla helpompi löytää paikallisia optimeja. Tätä ongelmaa voidaan vähentää käyttämällä erilaista fitness-funktiota, lisäämällä mutaationopeutta tai käyttämällä valintatekniikoita, jotka ylläpitävät monipuolista ratkaisupopulaatiota. Yleinen tekniikka monimuotoisuuden ylläpitämiseksi on käyttää "niche-sakkoa": mihin tahansa riittävän samankaltaisten yksilöiden ryhmään (niche-säde) lisätään rangaistus, joka vähentää kyseisen ryhmän edustusta seuraavissa sukupolvissa, jolloin muita (vähemmän samankaltaisia) yksilöitä voidaan pitää populaatiossa. Tämä temppu ei kuitenkaan välttämättä ole tehokas, riippuen ongelman maisemasta. Toinen mahdollinen tekniikka olisi yksinkertaisesti korvata osa populaatiosta satunnaisesti generoiduilla yksilöillä, kun suurin osa populaatiosta on liian samankaltainen keskenään. Monimuotoisuus on tärkeää geneettisissä algoritmeissa (ja geneettisessä ohjelmoinnissa), koska homogeenisen populaation ylittäminen ei tuota uusia ratkaisuja. Evoluutiostrategioissa ja evolutiivisessa ohjelmoinnissa monimuotoisuus ei ole olennaista, koska niissä luotetaan enemmän mutaatioon.
• Dynaamisilla aineistoilla toimiminen on vaikeaa, sillä genomit alkavat jo varhaisessa vaiheessa lähentyä ratkaisuja, jotka eivät ehkä enää kelpaa myöhemmille aineistoille. Tämän korjaamiseksi on ehdotettu useita menetelmiä, joilla lisätään geneettistä monimuotoisuutta ja estetään varhainen konvergenssi joko lisäämällä mutaation todennäköisyyttä ratkaisun laadun laskiessa (ns. käynnistetty hypermutaatio) tai lisäämällä ajoittain kokonaan uusia, satunnaisesti tuotettuja elementtejä geenipooliin (ns. satunnaiset maahanmuuttajat). Evoluutiostrategiat ja evoluutio-ohjelmointi voidaan taas toteuttaa niin sanotulla "pilkkustrategialla", jossa vanhempia ei ylläpidetä ja uudet vanhemmat valitaan vain jälkeläisistä. Tämä voi olla tehokkaampaa dynaamisissa ongelmissa.
• Geneettiset algoritmit eivät pysty tehokkaasti ratkaisemaan ongelmia, joissa ainoa soveltuvuusmitta on yksi oikea/väärän mitta (kuten päätösongelmat), koska ratkaisua ei voida konvergoida (ei ole mäkeä, jota kiivetä). Näissä tapauksissa satunnaishaku voi löytää ratkaisun yhtä nopeasti kuin GA. Jos tilanne kuitenkin sallii onnistumis-/epäonnistumiskokeilun toistamisen, jolloin saadaan (mahdollisesti) erilaisia tuloksia, onnistumisten ja epäonnistumisten suhde on sopiva kuntomittari.
• Tiettyjen optimointiongelmien ja ongelmatapausten osalta muut optimointialgoritmit voivat olla tehokkaampia kuin geneettiset algoritmit, kun otetaan huomioon konvergenssin nopeus. Vaihtoehtoisia ja täydentäviä algoritmeja ovat esimerkiksi evoluutiostrategiat, evolutiivinen ohjelmointi, simuloitu hehkutus, Gaussin sopeutuminen, mäen kiipeäminen ja parviäly (esim. muurahaispesäoptimointi, hiukkasparvioptimointi) sekä kokonaislukuiseen lineaariseen ohjelmointiin perustuvat menetelmät. Geneettisten algoritmien soveltuvuus riippuu ongelman tuntemuksen määrästä; hyvin tunnettuihin ongelmiin on usein olemassa parempia, erikoistuneempia lähestymistapoja.

Historia

Alan Turing ehdotti vuonna 1950 "oppivaa konetta", joka olisi evoluution periaatteiden mukainen. Evoluution simulointi tietokoneella alkoi jo vuonna 1954 Nils Aall Barricellin työstä, joka käytti tietokonetta Institute for Advanced Study -instituutissa Princetonissa, New Jerseyssä. Hänen vuonna 1954 julkaistua työtään ei huomattu laajalti. Australialainen kvantitatiivisen genetiikan tutkija Alex Fraser julkaisi vuodesta 1957 alkaen sarjan artikkeleita, joissa simuloitiin sellaisten organismien keinotekoista valintaa, joissa useat lokukset kontrolloivat mitattavaa ominaisuutta. Näistä lähtökohdista biologien suorittama evoluution tietokonesimulointi yleistyi 1960-luvun alussa, ja menetelmiä kuvattiin Fraserin ja Burnellin (1970) sekä Crosbyn (1973) kirjoissa. Fraserin simulaatiot sisälsivät kaikki nykyaikaisten geneettisten algoritmien olennaiset elementit. Lisäksi Hans-Joachim Bremermann julkaisi 1960-luvulla sarjan artikkeleita, joissa myös omaksuttiin optimointiongelmien ratkaisupopulaatio, jossa käytiin läpi rekombinaatio, mutaatio ja valinta. Bremermannin tutkimukseen sisältyi myös nykyaikaisten geneettisten algoritmien elementtejä. Muita merkittäviä varhaisia pioneereja ovat Richard Friedberg, George Friedman ja Michael Conrad. Monet varhaisista julkaisuista on julkaistu uudelleen Fogelissa (1998).

Vaikka Barricelli oli vuonna 1963 raportoimassaan työssä simuloinut yksinkertaisen pelin pelaamisen kyvyn kehittymistä, keinotekoisesta evoluutiosta tuli laajalti tunnustettu optimointimenetelmä Ingo Rechenbergin ja Hans-Paul Schwefelin 1960-luvulla ja 1970-luvun alussa tekemän työn tuloksena - Rechenbergin ryhmä pystyi ratkaisemaan monimutkaisia teknisiä ongelmia evoluutiostrategioiden avulla. Toinen lähestymistapa oli Lawrence J. Fogelin evoluutio-ohjelmointitekniikka, jota ehdotettiin tekoälyn tuottamiseen. Evoluutio-ohjelmoinnissa käytettiin alun perin äärellisiä tilakoneita ympäristön ennustamiseen, ja siinä käytettiin variaatiota ja valintaa ennustajalogiikoiden optimoimiseksi. Erityisesti geneettiset algoritmit tulivat suosituksi John Hollandin 1970-luvun alussa tekemän työn ja erityisesti hänen kirjansa Adaptation in Natural and Artificial Systems (1975) ansiosta. Hänen työnsä sai alkunsa soluautomaatteja koskevista tutkimuksista, joita Holland ja hänen oppilaansa tekivät Michiganin yliopistossa. Holland esitteli formalisoidun kehyksen seuraavan sukupolven laadun ennustamiseksi, joka tunnetaan nimellä Hollandin skeemateoreema. Geneettisten algoritmien tutkimus pysyi pitkälti teoreettisena 1980-luvun puoliväliin asti, jolloin Pittsburghissa, Pennsylvaniassa järjestettiin ensimmäinen kansainvälinen geneettisten algoritmien konferenssi.