Geneettisellä algoritmilla optimiratkaisu

Kun optimointiongelma on vaikea, ratkaisuvaihtoehtoja ja vaikuttavia parametreja on valtavasti ja niiden välillä on monimutkaisia riippuvuuksia, perinteiset laskentamenetelmät jumiutuvat helposti paikalliseen optimiin. Sen sijaan että löytäisivät vuoren korkeimman huipun, ne saattavat jäädä laaksossa olevaan kummun päälle, kun kaikki polut osoittavat vain alaspäin. Tällaisessa tilanteessa geneettinen algoritmi (GA) tarjoaa tehokkaan tavan lähestyä ongelmaa. GA optimointiprosessi etenee seuraavien vaiheiden ja haasteiden kautta:

1. Laaditaan moniulotteinen kustannusfunktio, joka kertoo miten eri tekijät ja parametrit vaikuttavat lopputulokseen:
   • Optimoinnin ytimessä on siis kustannusfunktio (fitness function), jonka maksimi- tai minimiarvoa algoritmi pyrkii löytämään.
   • Kun parametreja on kymmeniä tai satoja, funktion muodostama "maasto" muuttuu moniulotteiseksi pinnaksi, jossa on lukuisia harjanteita, laaksoja ja paikallisia huippuja (local optima).
   • Perinteiset matemaattiset menetelmät (kuten gradienttimenetelmät) voivat eksyä tällaisessa sokkelossa ensimmäiseen vastaantulevaan paikalliseen huippuun, vaikka paras ratkaisu (global optima) odottaisi aivan muualla.
2. Selvitetään parametrien rajoitukset. Todellisen maailman ongelmissa parametreilla on lähes aina tiukat rajoitukset:
   • Fyysiset tai loogiset rajat määrittelevät parametreille sallitut minimi- ja maksimiarvot (esimerkiksi lämpötila, budjetti, materiaalin paksuus tai aikataulu).
   • Geneettisessä algoritmissa nämä rajoitukset huomioidaan joko koodauksessa (niin että virheellisiä ratkaisuja ei voi edes syntyä) tai rankaisemalla kustannusfunktiossa ratkaisuja, jotka rikkovat annettuja rajoja (penalty function).
3. Miten geneettinen algoritmi löytää optimin? Sen sijaan, että algoritmi yrittäisi laskea suoraan "oikotien" huipulle, se hyödyntää laajaa hakupintaa käyttäen rinnakkaisuutta:
   • GA ei etsi ratkaisua vain yhdestä pisteestä, vaan lähettää maastoon tutkimaan populaation "tutkijoita".
   • Evoluution voima: Vahvimpien populaation jäsenten valinnan, risteytyksen ja mutaation kautta populaatio hajautuu moniulotteiselle pinnalle ja etsii optimia laajalta alueelta. Kun vahvimmat yksilöt jatkavat pienten muutosten myötä matkaa ja mukaan lisätään vähän satunnaisuutta, algoritmi oppii vähitellen välttämään karikot, pysymään sallituilla rajoilla ja kiipeämään kohti parasta mahdollista lopputulostaan.

Vesivoimalan ohjaaminen geneettisellä algoritmilla.

Tässä esimerkissä yritämme maksimoida vesivoimalan tuotantoa, kun veden virtaama on annettu kullekin ajan hetkelle. Turbiinien läpi on siis ajettava tietty vesimäärä (m3/s) ja samalla sähkötuotanto generaattoreista olisi maksimoitava. Ongelma on, että kullakin turbiinilla on oma tyyppikäyränsä (kuva 1), joka määrittää millaisen sähkötehon siitä saa tietyllä virtauksella. Huomioitava on, että eri turbiineissa tuotanto nousee eri tavalla virtauksen mukana ja saavuttaa maksiminsa eri virtauksilla. Ja maksimin jälkeen virtauksen kasvattaminen vähentää sähkötuotantoa. Kokonaisvirtaus pitäisi siis jakaa turbiinien kesken niin, että sähkön kokonaistuotanto maksimoituu. Tämä voi tarkoittaa myös sitä, että turbiineja kannattaa sammuttaa ja ajaa vain osalla koneista. Toisaalta meillä on fyysisiä rajoituksia. Esimerkiksi virtauksia ei voi vaihtaa kovin aggressiivisesti eikä turbiineja käynnistellä määrättömästi. Erilaisia ajomalleja ja vaihtoehtoja on lukematon määrä eikä kaikkia vaihtoehtoja voida mitenkään käydä läpi ennen kuin virtauksen tavoite taas muuttuu ja pitää löytää uusi optimi. Geneettisellä algoritmilla haluttu tavoite ja rajoitukset voidaan kirjoittaa kustannusfunktioon, jota sitten optimoidaan populaation evoluution voimalla.

Tässä kuvitteellisessa voimalaesimerkissä toimii rinnakkain kolme kiinteäsiipistä Francis turbiinia ja yksi muuttuvasiipinen Kaplan turbiini. Optimia haettaessa turbiineja yritetään ajaa niin, että sähköntuotanto maksimoituu. Tämä tarkoittaa, että jossain tapauksessa jokin turbiini kannattaa kokonaan sammuttaa koska silloin päätään ominaiskäyrässä paremmalle alueelle. Oheisessa kuvassa nähdään optimoinnin tulos. Jokaiselle hetkelle on haettu optimi toiminta kullekin turbiinille niin että virtaustavoite täyttyy ja sähköntuotanto maksimoituu. Optimoinnin pitää siis ajaa koko ajan koska tavoitevirtaama muuttuu ajassa.

Kuvasta 2 nähdään, että optimointi on ajanut turbiineja niin, että veden haluttu kokonaisvirtaus toteutuu. Sähköntuotannolle ei ole referenssiä. Mutta kustannusfunktio pakottaa sen maksimoimiseen. GA algoritmin hyöty on siinä, että optimointia voidaan ajaa jokaiselle ajan hetkelle. Myös osa GA:n populaatiosta voidaan periyttää seuraavaan aikaikkunaan. Näin optimointia voidaan vähän keventää ja laskentakuorma voidaan pitää alhaisena. Pitäähän seuraavan hetken optimi olla saatavilla kun optimia tarvitaan. Tässä tapauksessa kerran minuutissa.