Geneettinen algoritmi Geneettinen algoritmi on toistoon perustuva proseduuri, joka ylläpitää vakiokokoista ehdokasratkaisujen populaatiota P(t). Jokaisen toiston, sukupolven, aikana populaation sisältämät rakenteet arvioidaan ja arvion perusteella valitaan ne rakenteet, joista tuotetaan uusi ehdokassukupolvi. Geneettistä algoritmia on sovellettu mm. kriittisten proseduurien parametrien arvoalueiden optimointiin kuvaamalla parametrien ennakoitu arvoalue geneettisellä koodilla - risteytys ja luonnollinen valinta seulovat optimaaliset parametrijoukot. Usein on tarpeen korvata risteytys sovellukseen paremmin sopivilla lisääntymisrutiineilla.

kuva 5: Yksitasoinen mukautuva järjestelmä

Geneettinen algoritmi toteuttaa populaation tasolla kaksitasoisen takaisinkytkennän. Yksitasoinen takaisinkytkentä (kuva 5), edustaa tilannetta jossa yksilö säätää välittömästi käyttäytymistään ympäristön suhteen siitä saatavan syötevirran ohjaamana. Kaksitasoisessa takaisinkytkennässä palautteen avulla säädetään modulin käyttäytymistä ohjaavaa mukautumisstrategiaa muokkaamalla parametreja, jotka säätelevät yksitasoisen takaisinkytkennän laajuutta ja vaikutusta (kuva 6).

kuva 6: Kaksitasoinen mukautuva järjestelmä

Geneettistä algoritmia sovellettaessa ongelman ratkaiseva ohjelma sunnitellaan moduleiksi siten että modulit ovat valinnaisia. Moduleja edustava perimä toteutetaan useimmiten laskennallisen hallittavuuden vuoksi binääritaulukkona, jossa 1 edustaa ominaisuutta ja 0 sen puutetta. Laajoissa ohjelmistoissa perimä voidaan kuvata tuhansien, jopa kymmenien tuhansien alkioiden taulukolla. Taulukon sisältöä muokkaamalla saadaan ohjelman käyttäytyminen muuttumaan. Ohjelmasta toteutetaan useita kilpailevia versioita ja versioita edustavia taulukoita monistetaan, risteytetään ja mutatoidaan yksisoluisia jäljittelevällä tavalla. Ohjelmaversioista karsitaan niiden käyttäytymisen perusteella heikoimmat ja risteytetään kelpuutetut uudeksi sukupolveksi. Riittävä sukupolvien määrä tuottaa optimaalisen ratkaisun, mutaatioita tarvitaan vain riittävän versioinnin ylläpitämiseksi. Olen esityksessäni pitäytynyt yksikkömuodossa geneettinen algoritmi, tarkoittaen alla olevaa pseudokielistä yleistystä. Alan kirjoituksissa termillä tarkoitetaan toisinaan myös optimoinnin kohteena olevia yksittäisiä sovellus- ja jopa ratkaisuversioita tässä kuvattavan yleisen mallin lisäksi. muotoile ongelma kehitä karkea ratkaisurakenteiden populaatio versioi ja risteytä rakenteet evaluoi rakenteet karsi rakenteet jatka riviltä 3. ellei mikään ratkaisu tyydytä Ongelman muotoilu edellyttää ratkaisun erittelyä siltä edellytettävien ominaisuuksien mukaan, niin että ratkaisun tuottava rakenne voidaan kuvata perimällä. Alkupopulaatio voidaan tuottaa mutatoimalla ja monistamalla alkuratkaisua. Yleinen malli Yleisellä tasolla geneettisen algoritmin (GA) hakuavaruuden laajuutta voidaan tarkastella kutsussa GA(N,C,M,G,W,S) olevien kuuden parametrin avulla (Holland). Parametreista N edustaa populaation yksilöiden määrää eli kokoa. C ilmaisee risteytyksien suhteellista osuutta, kustakin sukupolvesta risteytetään C*N yksilöä. C kuten M ja G voi saada arvoja väliltä 0.0-1.0. M määrittää mutaatioiden esiintymistiheyden, joka saadaan tulosta M*N*L, missä L edustaa perimän sisältämien geenien määrää. Pieni mutaatioiden osuus varmistaa, ettei haku juutu paikallisiin optimeihin - suurella mutaatioiden määrällä voidaan hävittää jo löytynyt ratkaisu. G määrittää seuraavaan sukupolveen selviytyvien osuuden N*(1-G). W säätelee valintafunktion skaalausta, ts. sillä määritellään se valintafunktion arvo, joka määrää karsinnan nollapisteen: Jos esimerkiksi yksilöihin liitetyt painokertoimet voivat saada arvoja välillä 0 - 130, niin ensimmäisessä sukupolvessa ratkaisujen saamien painokertoimien hajonta on laajempi kuin satojen sukupolvien jälkeen - kuitenkin populaatioon sovellettavan karsinnan on tarkasteltava kutakin sukupolvea tasa-arvoisesti. S parametrillä säädellään sitä pyritäänkö kunkin sukupolven parhaiden ratkaisujen perimä kopioimaan vai voidaanko se jopa kadottaa risteyttämällä. Edellinen nopeuttaa optimaalisen ratkaisun löytymistä, jälkimmäinen estää juuttumisen paikallisiin optimeihin. Strategiasta riippuen algoritmin sovellukset voidaan jakaa kahteen pääluokkaan, sen mukaan mitä perimän avulla kuvataan. Pääsuuntauksia kutsutaan Pittin esim. (De Jong) ja Michiganin (Holland) versioiksi sen mukaan liitetäänkö yksittäiseen geeniin kokonaisia proseduureja vai ohjelmalauseita. Sovellusesimerkki Käytän esimerkkinä yksinkertaistettua optimointiongelmaa - hypermediadokumentin julkaisumuodon ja ilmiasun valintaa. Tehtävänä on suunnitella geneettistä algoritmia käsittelevä vuorovaikutteinen hypermediadokumentti. Ensiksi on päätettävä käytetäänkö dokumentissa 256 väriä vai mustavalkoisuutta, hinnoitellaanko/tuotetaanko nimike materiaaliltaan 150,- vai 250,- markan hintaiseksi ja julkaistaanko se CD-ROMina vai levykkeinä. On siis löydettävä tasapaino tuotteen hyväksyttävyyden/jaeltavuuden, tuotantoon panostettavien resurssien ja arvioitavan tuoton suhteen. Muotoilen aluksi ratkaisulle esitysmallin (representation scheme): iImaistaan kolmea vaihtoehtoista edellä kuvattua valintaa kaksiaakkosisella {0,1} merkkijonolla, edustakoon se suunnittelustrategian perimää. Aakkoston koko K on siis 2 ja perimän pituus (sen geenien lukumäärä) L on 3, ja näin strategiavaihtoehtoja on 8, K potenssiin L. Koska tarkoituksena on perustaa yrityksen toiminta vuorovaikutteisten tietokonedokumenttien tuotannolle ja yrityksen näkökulmasta on tärkeätä saavuttaa kokemusta eri versioiden toteutukseen liittyvistä ongelmista niin päätetään aluksi kokeilla tuotteitten myyntiä neljän vaihtoehtoisen version avulla ja tarkkailla niiden myyntiä. Tilannetta voidaan tarkastella esimerkiksi seuraavan mallin avulla.

Taulukko 1: Esimerkki ongelman ja ratkaisun periaatteen kuvaavasta mallista.

Vaihtoehtojen laadun arviointi on sovelluksen näkökulmasta tärkeää - esimerkkitapauksessa on eroa arvioidaanko perimän elinkelpoisuutta myyntilukujen vai saavutetun tuoton pohjalta, ennakoidaanko tuotteen elinkaari ja miten sisällytetään se arviointiin? Arviointia edustaa geneettisessä algoritmissa arviointifunktio f(X), jonka avulla tuotetaan geneettisen algoritmin tarvitsema suoritusaikainen informaatio. Esimerkin malleja (tuotestrategioita) on verrattu esimerkiksi viikkottaisten myyntilukujen perusteella, luvuiksi on esimerkkitapauksessa saatu 7, 4, 0 ja 5. Ensimmäistä myyntiviikkoa edustavan sukupolven koko M on 4, tämän kantasukupolven yksilöt voidaan valita moelivaltaisesti esimerkiksi ylläolevan taulukon tapaan. Algoritmia sovellettaessa arvioidaan ensin ehdokasratkaisuiden joukko, parhaat valitaan risteytettäviksi seuraavaksi sukupolveksi. Esimerkin tapauksessa arviointi skaalataan välille 0, 1 painolukujen arvoalueen suhteen. Allaolevaan taulukkoon on kuvattu ensimmäisen sukupolven arviointifunktion tulokset ja siitä poimittava risteytettävien yksilöiden joukko.

Taulukko 2: Ensimmäisestä sukupolvesta valittu risteytettävien joukko.

Risteytysoperaatiot Risteytys eli ratkaisuversioiden perimän vaihtaminen toteutetaan analogisesti biologisen risteytyksen kanssa, missä RNA-rihmat ensin asettuvat rinnakkain ja sitten kiertyvät toistensa ympäri ja katkeavat kierroskohdasta muodostaen uudet RNA rihmat.

Kuva 7: Risteytys (cross-over).

Esimerkkitapauksen kromosomit risteytetään toisen ja kolmannen alleelin välistä. Mahdollisia risteytyskohtia on geenin pituus L-1 kappaletta, esimerkkitapauksessa siis 2. Risteytyskohdan ja yleisemmin risteytysmenetelmän valinnalla voidaan seuloa ja painottaa erilaisia perimätekijöiden yhdistelmiä. Geneettisen algoritmin soveltuvuutta ja tehoa suhteessa ongelma-alueen määrittelemään hakuavaruuteen voidaan parantaa risteytysoperaatioita kehittämällä ja improvisoimalla. Maskattu risteytys on kuvattu Davisin Geneettisten algoritmien käsikirjassa nimellä 'uniform crossover' (Davis, s. 49). Maskatussa risteytyksessä kaksi vanhempaa tuottaa kaksi jälkeläistä, siten että kromosomin mittaisen binäärimaskin avulla valitaan alleelit jälkeläisiin: maskin ykkönen siirtää ensimmäisen vanhemman alleelin ensimmäiseen lapseen ja toisen vanhemman alleelin toiseen lapseen, nollat siirtävät toisen vanhemman alleelin ensimmäiseen lapseen ja ensimmäisen vanhemman alleelin toiseen lapseen. Maskia vaihtamalla voidaan toteuttaa eksoottisiakin risteytysoperaatioita aina tarpeen mukaan. Mallit (schemata) Hollandin väitöskirjan pääoivalluksena voidaan pitää malliteoriaa, edellä esitettyyn esimerkkiin sovellettuna seuraavasti. Hollandin mukaan 'hälläväliä' merkin # avulla voidaan erotella (tässä tapauksessa kaikkien tuotestrategioitten) hakuavaruudesta yksittäisiä ominaisuuksia ja niiden yhdistelmiä määritteleviä malleja, esimerkiksi värillisyys (1##), CD formaatti (#1#), kalleus (##1), mustavalkoisuus (0##), levykemuoto (#0#) ja halpuus (##0). Kutakin ominaisuutta esiintyy jo kantasukupolvessa 2 versiota, joten ominaisuuksia edustaville malleille voidaan laskea painoarvot esim. seuraavasti: värillisyys (1##) (7+4)/2 = 5,5, CD formaatti (#1#) (7+5)/2 = 6, jne. Painoarvojen merkitsevyys riippuu tietenkin siitä kuinka edustava versioiden valikoima keskiarvon perustana on - esimerkkitapauksissa kaksi kahdeksasta mahdollisesta. Kaikkien mallien mallin (###) painoarvo edustaa koko hakuavaruuden painoarvojen keskiarvoa. Sukupolvien myötä mallien painokertoimet tarkentuvat versioiden esiintymien ohessa.

Taulukko 3: Risteytys sukupolvesta 0 sukupolveksi 1.

Yleisesti sanotaan määrittelemättömien geenien edustavan niitä hakuavaruuden ulottuvuuksia, joihin hakua kohdistetaan. Painokertoimen lisäksi malliin liittyy kaksi sitä kuvaavaa suuretta: mallin kardinaalisuus (order) ja sen kiinnitetty pituus (defining length) - kardinaalisuudella tarkoitan kromosomin määriteltyjen geenien määrää ja kiinnitetyllä pituudella määriteltyjen geenien maksimietäisyyttä. Kardinaalisuus määrittelee mallin yleisyyden ja erityisyyden; kiinnitettyä pituutta käytetään arvioitaessa mallin kestävyyttä risteytyksessä - ts. esimerkkimme mallit 1#1, 1#0, 0#1 ja 0#0 rikkoutuvat aina. Michalewicz muotoilee malliteoreeman (Schema Theorem) ja siihen liittyvän rakennuspalikkaoletuksen (Building Block Hypothesis) seuraavasti: Malliteoreema Lyhyitä, kardinaalisuudeltaan vähäisiä, mutta painoarvoiltaan keskitasoa vahvempia malleja testataan eksponentiaalisesti lisääntyviä kertoja geneettisen algoritmin perättäisissä sukupolvissa. Teoreemaa voidaan myös tulkita seuraavasti: Mallit, esimerkissämme 27, muodostavat arviointifunktion antamien painokertoimien perusteella hakuavaruuteen hierarkian, puurakenteen, jonka juurena on mallien malli, ###. Teoreema väittää, että geneettinen algoritmi itsessään suosii hakupuun optimaalisia alueita. Ohjelmointiteknisesti tämä tarkoittaa sitä, ettei algoritmin toteutuksen tarvitse sisältää mitään edellä esitetyistä mallien painokertoimien laskennoista ja tilastoista, riittää kun huolehditaan kunkin sukupolven parhaiden yksilöiden risteyttämisestä. Rakennuspalikkaoletus Geneettinen algoritmi etsii optimaalista käyttäytymistä yhdistelemällä rakennuspalikoita, joilla tarkoitetaan teoreeman kuvaamia lyhyitä, kardinaalisuudeltaan vähäisiä ja painoarvoiltaan vahvimpia malleja. Ylläoleva on oletettu kuvaus geneettisen algoritmin toiminnasta eikä sitä ole mitenkään todistettu. Ohjelmoinnin näkökulmasta tehtävänä on kuvata mainittujen rakennuspalikoiden joukko ja haluttua käyttäytymistä arvottava funktio. Teoreemasta ja oletuksesta tarkemmin esim. (Michalewicz, s. 51). Geneettisen algoritmin rinnakkaisuus Geneettinen algoritmi sisältää paljon rinnakkaistettavia toimintoja niin sukupolven elinkelpoisuuden määrittämisen, ristetytyksen, kromosomien täsmäyttämisen kuin geenien edustaman käyttäytymisen arvioinnin tasolla. Rinnakkaisuudesta on eroteltavissa erilaisia tasoja rinnakkaisten elementtien karkeisuuden (ongelman hajautettavuuden) ja rinnakkaisten prosessien suorittumisnopeuden suhteen, jolloin algoritmin sopivasti modularisoitua toteutusta voidaan hajauttaa vaikka paikallisverkkoon. Rinnakkaisohjelmoinnin teoriasta esimerkkinä Unity paralleelinotaatio ja ohjelmointikieli (Chandy ja Misra). Kirja tarkastelee rinnakkaisohjelmointia formaaleista lähtökohdista esittäen kattavan valikoiman sovelluksia myös perinteisesti proseduraalisesti ratkaistuihin ongelmiin.

Kuva 8: Viestiperusteinen luokitusjärjestelmä.

Michiganin koulukunta pyrkii kohti hienojakoista rinnakkaisuutta erityisesti koneoppimiseen soveltuvalla geneettisen algoritmin toteutuksella. Ohjelma jalostaa kromosomimalliensa avulla optimaalisen sääntölauseiden joukon, joka toteuttaa ohjelman tehtävän. Toteutuksessa jokaisella alleellilla on omat vastineensa toiminto-osan ohjelmalauseissa (kuva 8). Kromosomien edustamaa käyttäytymistä arvioitaessa voidaan keskittyä ohjelmalauseiden arviointiin. Holland korostaakin alleeleja vastaavien ohjelmalauseiden itseellisyyttä ja sisällöllistä riippumattomuutta. Käytettävien resurssien mukaan voidaan toteutus hajauttaa sukupolvitasosta aina geenien sisältämien perusoperaatioiden tasolle. Tämä hienojakoinen paralleelisuus on toteutettu kuvassa esitetyn viestimekanismin avulla (kuva 8). Sama ohjelmalause voi esiintyä eri alleeleissa, joiden painokertoimet muodostuvat käytettyjen ohjelmalauseiden painokertoimien yhdistelmistä. Esimerkkitapauksessamme voisimme osittaa tuotteen hinnoittelun ja MV/väri sekä levyke/CD tuotannon kustannuslaskelmat 'tietorakenteiksi' ja varsinaisen tuotantoprojektin resurssien ja ajan hallinnan 'ohjelmalauseiksi'. Budjetoinnin onnistumisen eräs tavoite on paikantaa tarvittavat panokset ja niitä vastaavat tuotot - löytää molemmat taloudet optimaalisesti ja yhdenmukaisesti kuvaavat tietorakenteet; tuotantopäätöksen eräänä edellytyksenä voidaan pitää niiden tehtävien, toimintojen ja materiaalivirtojen erottelemista, mitkä ovat ratkaisusta riippumatta välttämättömiä, mitkä taas valinnan varaisia. Holland esittää artikkelissaan Escaping Brittleness (Buckles), ohjelmalauseiden painoarvojen laskemiseksi 'vesiketju' (Bucket Brigade) algoritmia, joka soveltuu erityisesti lauseperustaisten oppivien ympäristöjen ja hahmontunnistusjärjestelmien sääntöjen optimointiin. Algoritmi voidaan pelkistetyimmillään kuvata seuraavasti: Esimerkkimme tuotanto on jaettu työtehtäviin: tiedostomuunnoksiin, väripalettien ja kirjasinleikkausten harmonisointeihin, aineiston tallennustoimintoihin jne. Kuvitellaan, että ne muodostavat tuotestrategian toteuttavan toimintojen sarjan, jota voidaan verrata vaikkapa tulipalon sammutustalkoiden vesiketjuun. Idea on yksinkertaisesti, että aina 'siirrettyään ämpäriä' ohjelmalause saa palkkioksi lisää painoarvoa. Michiganin koulukunta on kehittänyt vesiketjualgoritmista joustavan ja muokkautuvan työkalun oppivien järjestelmien sääntölauseiden painoarvojen laskentaan perustuvaksi arviointifunktioksi. Geenejä edustavat aakkoset Geneettisen algoritmin sovelluksissa kromosomit yleensä toteutetaan binääriaakkosin risteytys- ja mutaatio-operaatioitten yksinkertaisuuden ja selkeyden vuoksi. Lisäksi binääriaakkosten talletustehokkuus on paras, ne tarjoavat eniten malleja per bitti ominaisuuksien koodaustavasta riippumatta (Goldberg 1). Ihmisen perimä on neliaakkoksinen: sen muodostavat geenit voivat olla neljää eri valkuaisainetta. Eräs lähestymistapa on käyttää binäärigeenien asemesta reaalilukuja. Menetelmää on sovellettu mm. optimoitaessa moniparametristen funktioiden parametrijoukkoja. Vertailtaessa binääri- ja reaalilukukromosomien käyttäytymistä voidaan havaita reaalilukuesityksen olevan yleensä nopeampi, yhdenmukaisempi ja tarkempi kuin binääriaakkoston (Michalewicz, s. 82). Suunnittelijalle on eduksi reaalilukuaakkosten parempi geeni/ohjelman muuttuja vastaavuus. Erilaisista geneettisistä aakkosista ja niiden soveltamisesta lisää esimerkiksi (Goldberg 2). Geneettinen ohjelmointi John Koza on kehittänyt geneettisenä ohjelmointina (Genetic programming) tunnetun menetelmän, joka perustuu ohjelman rakenteen kuvaavien semanttisten puiden risteyttämiseen ja manipulointiin (Koza 1) (Koza 2). Geneettisessä ohjelmoinnissa määritellään ongelman (ohjelmointitehtävän) ratkaisemiseksi tarvittavat terminaaliarvot ja muuttujat sekä niitä muokkaavat käsittelyt. Terminaaleista ja niihin sovellettavista operaatioista muodostetaan mielivaltainen ohjelmaversioiden joukko, alkupopulaatio. Populaation yksilöihin sovelletaan niiden suorituksen tehokkuutta ja/tai ratkaisun hyvyyttä punnitsevaa arviointifunktiota. Darwinilaisen mallin mukaista luonnollista valintaa mukaillen populaation parhaiksi arvioidut yksilöt valitaan risteytymään ja lisääntymään seuraavaan ohjelmaversioiden sukupolveen. Uusia versiosukupolvia tuotetaan joko ennalta kiinnitetty määrä tai kunnes hyväksyttävä ratkaisuversio löytyy. Geneettisessä ohjelmoinnissa risteytyksellä ja mutaatioilla muokataan suoraan ohjelmaa, kun geneettisen algoritmin sovelluksissa käsitellään rakenteita edustavia merkkijonoja, kromosomeja. Vaikka Kozan patentoima sovelluskehitysympäristö on toteutettu Common Lispillä, hän painottaa sovelluksensa riippumattomuutta mistään yksittäisestä ohjelmointikielestä tai -ympäristöstä (Koza 1). Geneettistä ohjelmointia onkin sovellettu mm. C-kieliseen, Assembler ja Mathematica ohjelmointiin.