Geneettinen algoritmi
Wikipedia
Geneettinen algoritmi on tietojenkäsittelyssä hakuun käytettävä optimointimenetelmä. Geneettisellä algoritmilla on sovelluksia mm. tietojenkäsittelytieteessä, insinööritieteissä, taloustieteissä, fysiikassa ja matematiikassa. Optimointimenetelmänä geneettinen algoritmi luokitellaan heuristiseksi globaaliksi optimointimenetelmäksi. Geneettinen algoritmi on evolutionäärisen laskennan alaluokka, joka hyödyntää evoluutiobiologian tutkimuksessa löydettyjä perinnän, mutaation, valinnan ja rekombinaation menetelmiä.
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.
Sisällysluettelo |
[muokkaa] Periaate
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 yleensa satunnaisesti. Tämän jälkeen ratkaisupopulaatiota parannetaan mutaation, rekombinaation ja valinnan menetelmin.
[muokkaa] 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.
[muokkaa] 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.
[muokkaa] 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 "lapsi" muodostetaan yhdistelemällä (usein satunnaisesti) molempien vanhempien ominaisuuksia. Tätä menettelyä jatketaan, kunnes uuden populaation koko on riittävän suuri.
Kuvattu lisääntymisprosessti 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.
[muokkaa] Lopputulos
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 jatkamieen 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
[muokkaa] Pseudokoodiesitys
Luo alkupopulaatio Mittaa yksittäiset sopivuudet tietylle osalle populaation ratkaisukandidaateista Toista Valitse sopivimmat yksilöt lisääntymistä varten Luo uusi sukupolvi yhdistelemällä valittuja yksilöitä geneettisiä operaatioita käyttäen Mittaa lapsipopulaation yksilöiden sopivuudet Uudelleensijoita sopivimmat yksilöt Kunnes lopetusehto toteutuu