Geneettinen algoritmi

Geneettinen algoritmin toteutusta varten tulee tyypillisesti määritellä kaksi asiaa:

• koodaustapa, jolla käsiteltävän ongelman ratkaisut voidaan esittää kromosomeina,
• sopivuusfunktio, jolla yksittäisten ratkaisujen paremmuutta voidaan verrata toisiinsa.

Standardimenetelmä ongelman ratkaisujen esittämiseen on käyttää nollista ja ykkösistä koostuva bittitaulukko, jossa jokainen rivi vastaan yhtä yksittäistä ratkaisuvaihtoehtoa. Taulukkoesityksen etuna on bittijonojen keskinäisen vertailun ja muokkaamisen helppous. Geneettisen ohjelmoinnin ala tuntee myös puumaisia ja vapaamuotoisia esityksiä ratkaisujoukosta. Ratkaisujen laatua mittaava sopivuusfunktio on määritelty kaikille yksittäisratkaisuille ja sen määrittely riippuu aina käsillä olevasta ongelmasta.

Kun ratkaisujen geneettinen esitystapa ja sopivuusfunktio on määritelty, geneettinen algoritmin ensimmäinen vaihe on alkupopulaation alustus, joka tehdään yleensä satunnaisesti. Tämän jälkeen ratkaisupopulaatiota parannetaan mutaation, rekombinaation ja valinnan menetelmin.

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 parhaan ratkaisun oletetaan todennäköisesti löytyvän.

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.

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ääräinen sopivuus on ensimmäistä parempi, koska ratkaisukandidaattien joukosta on valintaprosessin aikana karsiutunut pois sopivuudeltaan huonot ratkaisut.

Edellä kuvattua menettelyä jatketaan kunnes jokin lopetuskriteeri tulee toteutettua. Tyypillisä lopetuskriteerejä ovat mm.

• Riittävän hyvän ratkaisun löytyminen
• Sukupolvien määrälle asetettu yläraja tulee täyteen
• Algoritmin jatkamiseen käytettävät resurssit (usein käytössä oleva laskentakapasiteetti) on käytetty loppuun
• Algoritmin jalostaman parhaimman ratkaisun taso ei enää parane merkittävästi

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 parhaat. 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ä.

• Monissa ongelmissa geneettisillä algoritmeilla on taipumus päätyä "hyvyysfunktiomaisemien" (engl. fitness landscape) lokaaleihin optimeihin. Ongelma voidaan kiertää muuttamalla hyvyysfunktiota, lisäämällä erilaisia mutaatiomenetelmiä (esimerkiksi pistemutaation lisäksi "geenin nurin perin kääntymisiä") ja lisäämällä mutaatiopainetta. Ratkaisuna voi olla myös "niche penalty", jossa yksilön selviytymismahdollisuus pienenee jos sen lähellä on samanlaisia eliöitä. Tämä lisää populaatioon painetta, joka lisää variaatiota, joka taas johtaa pois lokaalista optimista.
• Operoitaessa dynaamista dataa geneettiset algoritmit ovat joskus vaikeuksissa, koska genomit ovat sopeutuneet alussa olleisiin arvoihin, jotka algoritmin pyöriessä muuttuvat merkityksettömiksi. Mutaatioiden määrien lisääminen poistaa yleensä tämän ongelman.
• Geneettiset algoritmit ratkaisevat tiukan spesifisiä tehtäviä heikosti. Jos jonkin ominaisuuden ainut hyvyysarvo on "oikein/väärin", ei geneettinen algoritmi ratkaise ongelmaa satunnaista arvontaa paremmin.
• Valinta on ehdottomasti tärkeä osa geneettisen algoritmin toimintaa, mutta moni pitää populaatioiden sekoittamista tärkeämpänä.
• Geneettiset algoritmit ovat taipuvaisia löytämään erittäin nopeasti hyvän ratkaisun, vaikka hakuavaruus olisi erittäin vaikea.
• Spesifissä optimointiongelmassa yksinkertaisempi algoritmi löytää yleensä ratkaisun geneettistä algoritmia paremmin.
• Geneettisen algoritmin teholle keskeistä on sen alkuparametrien huolellinen valinta tai niiden ohjelman aikainen sovittaminen. Yleensä liian matala mutaatiotahti johtaa lokaaleihin optimeihin ja liian korkea johtaa jo löydettyjen hyvien ratkaisujen rikkoutumiseen.
• Hybridimenetelmää, esimerkiksi geneettisen algoritmin ja gradienttimenetelmän yhdistelmää, voidaan käyttää nopeuttamaan optimointia tapauksissa joissa paikallinen optimi on helposti saatavissa gradienttimenetelmällä. Tällöin siis geneettisen algoritmin tuottamat ratkaisut toimivat lähtöpisteinä gradienttihauille ja yksilöiden hyvyys arvioidaan gradienttimenetelmän antaman tuloksen perusteella.