Geneettinen algoritmi

Geneettinen algoritmi on tietojenkäsittelytieteessä ratkaisujen hakuun käytettävä optimointimenetelmä. Se on evoluutioalgoritmi, jossa käytetään evoluutiobiologiasta tuttuja periytymisen, mutaatioiden ja rekombinaation prosesseja ratkaisujen hakemiseen. Geneettinen algoritmi esittää ratkaisuehdotukset kromosomeina.
Geneettisissä algoritmeissa synnytetään alussa ratkaisuehdotusten joukko, populaatio. Monesti se on satunnainen joukko hyvin erilaisia ratkaisuja. Kromosomeihin kohdistetaan muutoksia, mutaatioita. Mutaatiot muuttavat ratkaisuja, joista tulee "hyviä" tai "huonoja". Ennalta määritellyillä ehdoilla karsitaan "huonot ratkaisut" pois. Yleensä geneettisen algoritmin ensimmäinen ajokerta ei tuota parasta mahdollista ratkaisua. Sen takia mutaatioita ja niiden karsintaa toistetaan, kunnes tyydyttävä ratkaisu on saavutettu tai tietty määrä ratkaisuyrityskierroksia tehty. Geneettiset algoritmit on kehitetty alkujaan Darwinin evoluutioteorian pohjalta ja niiden toimintaperiaate muistuttaa joissain suhteissa sitä. Silti geneettisissä algoritmeissa ei jäljitellä luonnon evoluutiota, vaan geneettiset algoritmit ovat luonnossa tapahtuvaa evoluutiota yksinkertaisempia.
Geneettisellä algoritmilla on sovelluksia muun muassa tietojenkäsittelytieteessä, insinööritieteissä, taloustieteissä, fysiikassa ja matematiikassa.

Geneettinen algoritmi

Optimointimenetelmänä geneettinen algoritmi luokitellaan heuristiseksi globaaliksi optimointimenetelmäksi. Geneettinen algoritmi on evoluutiolaskennan alaluokka, joka hyödyntää evoluutiobiologian tutkimuksessa löydettyjä periytymisen, mutaation, valinnan ja rekombinaation prosesseja. 
Geneettiset algoritmit toteutetaan tietokonesimulaationa, jossa optimointiongelman yksittäisten ratkaisujen - kromosomien - muodostama populaatio kehittyy kohti parempaa ratkaisua. Perinteisesti yksittäiset kromosomit esitetään nollista ja ykkösistä koostuvina merkkijonoina, mutta myös muut merkintätavat ovat mahdollisia. Evoluution alkuvaiheessa populaatio on usein alustettu satunnaisesti ja etenee sukupolvittain. Sukupolven jokaisen kromosomin sopivuus mitataan, ja parhaiden kromosomien joukosta muodostetaan jälleen uusi sukupolvi mutaatioiden ja rekombinaation kautta.

Alustus

Alustusvaiheessa useita yksittäisratkaisuja luodaan satunnaisesti alkupopulaation luomiseksi. Populaation koko riippuu suuresti käsiteltävästä tapauksesta, mutta tyypillisesti populaation koko on satojen tai tuhansien kromosomin kokoinen. Perinteisesti alkupopulaatio luodaan satunnaisesti ja tasaisesti koko hakuavaruuden alueelta. Joissakin tapauksissa alkupopulaation luomisessa voidaan painottaa niitä hakuavaruuden alueita, joilta optimaalisen ratkaisun oletetaan todennäköisesti löytyvän.

Valinta

Jokaiselle algoritmin etenemisaskeleella osa senhetkisestä populaatiosta valitaan tuottamaan jälkikasvunaan uusi sukupolvi. Yksittäiset ratkaisut valitaan sopivuuteen perustuen siten, että parhaimman sopivuusarvon saavilla ratkaisuilla on suurin todennäköisyys tulla valituksi uuden sukupolven tuottajaksi. Valintamenetelmiä on olemassa useita, joissa valittavien yksilöiden osuuden suurus ja valintamenetelmän satunnaisuus vaihtelevat.

Lisääntyminen

Seuraava askel on uuden sukupolven tuottaminen edellisestä sukupolvesta valittujen yksilöiden perusteella. Uusien yksittäisratkaisujen tuottamisessa käytetään geneettisiä siirtymän, rekombinaation ja mutaation operaatioita.
Jokaista uutta luotavaa ratkaisua varten valitaan kaksi "vanhempaa". Näiden "jälkeläinen" muodostetaan yhdistelemällä (usein satunnaisesti) molempien vanhempien ominaisuuksia. Tätä menettelyä jatketaan, kunnes uuden populaation koko on riittävän suuri.
Kuvattu lisääntymisprosessi tuottaa lopulta uuden populaation, joka poikkeaa alkuperäisestä populaatiosta. Yleensä toisen populaation keskimäärinen sopivuus on ensimmäistä parempi, koska ratkaisukandidaattien joukosta on valintaprosessin aikana karsiutunut pois sopivuudeltaan huonot ratkaisut.

Tehokkuus

Geneettisiä algoritmeja tarvitaan, koska monien matemaattisten ongelmien ratkaiseminen muuten olisi hyvin työlästä, ellei mahdotonta. 
Geneettisen algoritmit teho ongelmanratkaisuissa perustuu yleensä vakiokokoisessa populaatiossa tapahtuvaan toistoon, jossa risteytys ja mutaatiot luovat uusia kokonaisuuksia joista valinta seuloo optimaalisimmat. Lopullinen geneettisen algoritmin tehokkuus syntyy sen eri ohjausparametrien yhteisvaikutuksesta. Siihen vaikuttaa populaation koko, "geenien" lukumäärä, mutaatioiden määrä ja risteytyksen läpi käyvien kromosomien lukumäärä. Ohjausparametrien parhaiden arvojen saaminen on melko vaikea ongelma. Ohjausparametrit voidaan antaa valmiina algoritmiin -tai niidenkin parhaat arvot voidaan hakea sopeuttavalla systeemillä.