Geneettinen algoritmi - Ajoneuvoreititysongelman analysointi ja ratkaiseminen geneettisellä alg

GA on metaheuristinen ja evolutionäärinen optimointialgoritmi, jonka ideana on mallintaa luonnon evoluutiota soveltamalla geneettistä perintää Darwinin teorian mukaisesti. Se ra-kentaa ja ylläpitää kokeellisista ratkaisuista koostuvaa populaatiota useiden sukupolvien ajan. John Holland on esittänyt GA:n ensimmäistä kertaa 1960-luvulla. [1, katso 32]

Populaatiossa olevat ratkaisut esitetään binäärikoodatuilla merkkijonoilla, joita kutsutaan kromosomeiksi. Nämä koostuvat alleeleista, jotka ovat binääriarvoja 0 tai 1. Tämän vuok-si GA:n suunnitteluavaruus tehdään diskreetikvuok-si vuok-siten, että arvot, joita muuttujat voivat saada, ovat luvun 2 potensseja, eli 2ⁿ, jossa n ∈ N. Ratkaisuun liittyvät muuttujat voi-daan tällä tavalla esittää binäärimuodossa toisiinsa liitettyinä. Kokonaislukuina muuttujia ovat esimerkiksi 00 = 0,01 = 1,10 = 2 ja 11 = 4. Binääriarvoja voidaan esittää re-aalilukuina, joista esitellään esimerkkejä Taulukossa 2.3. Eräs ratkaisu eräälle ongelmal-le on esimerkiksi101000110110101, joka koostuu neljästä muuttujasta, jotka ovat liitetty toisiinsa sekventiaalisesti:1010,0011,011ja0101. Genetiikassa nämä tunnetaan geno-tyyppeinä ja näiden ilmentymät (eli ratkaisujen muuttujat, jotka ovat Taulukon 2.3 mukaan vastaavasti0.667,0.200,0.429ja0.333) ovat fenotyyppejä. [6, s. 121]

Klassisessa GA:ssa ratkaisut esitetään tietyn mittaisina binäärisinä merkkijonoina. Monis-sa ongelmisMonis-sa tällainen esitysmuoto tuottaa usein sellaisia arvoja, jotka ovat kiinnostavan kohdealueen ulkopuolella. Tästä seuraavien karkeiden epätarkkuuksien vuoksi suositel-laan todellisten koodauksien soveltamista. [33]

GA etenee yleisesti seuraavin askelin, joita esitellään Algoritmissa 2.1 ohjelmallisessa muodossa [6, s. 121–122]:

1. (Alustusvaihe) Luodaan muuttujann_p ∈ N suuruinen populaatio, joka koostuu yk-silöistäx⁽¹⁾₁ , ...,x⁽¹⁾np diskretisoidussa suunnitteluavaruudessa.

2. (Arviointivaihe) Lasketaan jokaiselle yksilölle objektiivinen kuntoarvo (fitness-arvo), joka kertoo yksilön sopivuudesta ratkaisuna optimointiongelmaan. Erilaisilla opti-mointiongelmilla on erilaiset fitness-funktiot, jotka yleensä liittyvät kustannuksiin.

3. Toistetaan sukupolvessag ∈ Naskeleita 4–6 niin kauan, kunnes koko populaatio on generoitu (siis yksilötx^(g+1)₁ , ...,x^(g+1)np ). Näillä askelilla luodaan kaksi jälkeläistä.

4. (Valintavaihe) Kaksi yksilöä valitaan toimimaan vanhempina.

5. (Risteytysvaihe) Valituilla yksilöillä suoritetaan risteytysoperaatio todennäköisyydel-läp_c, josta syntyy kaksi jälkeläistä. Jos risteytystä ei tapahdu, jälkeläiset ovat ident-tisiä kopioita vanhemmistaan. Risteytyksen todennäköisyys on yleensä hyvin suuri, esimerkiksip_c≈0.90.

6. (Mutaatiovaihe) Risteytyksestä syntyneille jälkeläisille suoritetaan mutaatio toden-näköisyydellä p_m. Tämä on yleensä alhainen, esimerkiksip_m ≈ 0.01, koska mu-taatio suoritetaan jälkeläisten kromosomien jokaiselle alleelille.

7. Uudesti luotu populaatio korvaa edellisen populaation ja arviointivaihe tehdään uu-delleen. Josnp on pariton, yksi valitaan satunnaisesti poistettavaksi.

8. (Lopetusvaihe) Askelia 2–7 toistetaan, kunnes algoritmia varten ennalta asetetut lopetuskriteerit täyttyvät.

Metaheuristisilla algoritmeilla on 3 tyypillistä ongelmaa, jotka täytyy ratkaista ennen kuin niitä voidaan tehokkaasti soveltaa optimointiongelmissa. Ne

1. jumittuvat lokaaliin optimiin, 2. rajoittuvat tiettyyn sykliin ja

3. eivät pysty pakenemaan tietystä hakualueesta. [2]

Ongelman 1 GA ratkaisee mutaatiovaiheellaan. Kun populaatio pysyy monipuolisena mu-taatioiden myötä, ratkaisuhaku voi paeta lokaaleista optimeista. [34] Ongelmat 2 ja 3 on ratkaistu GA:n kanssa automaattisesti, koska tämä on luonteeltaan stokastinen: syklit muuttuvat jatkuvasti, koska risteytys- ja mutaatiovaiheiden operaattorit perustuvat satun-naisuuteen – ja GA:lla ei ole minkäänlaisia sääntöjä, joka ohjaisi sen hakusuuntaa. Vain satunnaisuus ohjaa GA:ta. [2]

1 def g e n e t i c _ a l g o r i t h m ( ) :

GA:n vaiheita voidaan täydentää ja muokata monilla eri tavoilla sen parantamista varten.

Se etsii ratkaisuja globaalisti (tutkimalla koko populaatiota), kun taas toinen algoritmi – (meta)heuristinen tai ei – etsii lokaalisti (tutkimalla populaatiossa olevia kromosomeja yksitellen) [2]. Seuraavaksi käsitellään jokainen GA:n vaihe yksityiskohtaisemmin, jotta saadaan parempi kuva GA:n toiminnasta. Luvuissa 2.2.4 ja 2.2.5 on hyvä pitää mielessä, että reaalikoodattujen kromosomien tapauksissa oletetaan, että risteytys- ja mutaatio-operaattorit kohdistuvat TSP-tyyppisille optimointiongelmille.

2.2.1 Alustus

Alustusvaiheessa luodaan populaatio, joka koostuu yksilöistä. Nämä esittävät ratkaisuja optimointiongelmalle. Populaatio alustetaan yleensä satunnaisesti. [34] Populaation kook-si on suokook-siteltu olevan välillä[30,200][1]. Menetelmä, jolla populaatio alustetaan, on kui-tenkin muokattavissa. Soveltamalla erikoistuneita algoritmeja populaation alustuksessa on mahdollista, että hyviä ratkaisuja löydetään aikaisemmin [35]. Tässä luvussa

esitel-lään muutamia menetelmiä, joilla populaatio voidaan alustaa.

Yleisesti käytetyt menetelmät populaation alustukselle (satunnaisen alustuksen lisäksi) ovat sellaiset algoritmit, jotka toimivat lokaalihakumenetelminä tai rakenteellisina hakual-goritmeina. Lokaalihakumenetelmissä etsitään parempia ratkaisuja tutkimalla aloitetun ratkaisun välittömiä naapureita [34]. Ratkaisun välitön naapuri nähdään ratkaisuna, joka on muokattu alkuperäisestä ratkaisusta yhdellä mutaatiolla, esimerkiksi kahden alleelin välisellä vaihdolla. Lokaalihakualgoritmeja ovat esimerkiksi Luvussa 2 mainitut SA ja TS.

Rakenteellisissa hakualgoritmeissa tutkitaan ongelman rakennetta ja pyritään tästä poimi-maan hyödyllisiä osia lopullista ratkaisua varten. Tällaisia algoritmeja ovat muun muas-sa NN, pyyhkäisyalgoritmi (Sweep Algorithm), lähin lisäysmenetelmä (Nearest Addition Method) ja säästöalgoritmi (Saving Algorithm) [2][31]. NN ja SA valitaan tarkasteltaviksi niiden yksinkertaisuuden vuoksi. NN-algoritmia tutkitaan enemmän Luvussa 3.2.1.

SA:ssa lämpötila T⁽ⁿ^sa⁾ määrää, kuinka todennäköisesti johonkin huonompaan ratkai-suun siirrytään. Kun T⁽ⁿ^sa⁾ on suuri, siirtyminen huonompaan ratkaisuun on todennä-köisempää, ja pienillä lämpötiloilla epätodennäköisempää. Lämpötilan voi määrittää eri tavoin, esimerkiksi yhtälöllä

jossa p_sa ≥ 1 on hehkutuskerroin, T⁽¹⁾ aloituslämpötila, n_sa nykyinen iteraatio ja n_max iteraatioiden maksimilukumäärä. [6, s. 107]

Kun lämpötila on laskettu, seuraavaksi on selvitettävä, kumpi käsiteltävistä ratkaisuista (iteraation nykyinen ratkaisu ja ehdokasratkaisu) on parempi. Tämä selvitetään laskemal-la niiden objektiiviset arvot ja vertailemallaskemal-la niitä. Jos seuraavan ratkaisun objektiivinen arvo on parempi kuin nykyisen, siihen siirrytään välittömästi. Muussa tapauksessa määri-tetään todennäköisyys sille, että ehdokasratkaisuun siirrytään. Tällainen käyttäytyminen saavutetaan esimerkiksi yhtälöllä

jossax⁽ⁿ^sa⁾on iteraationn_sanykyinen ratkaisu,x⁽ⁿ^sa⁺¹⁾on iteraationn_sa ehdokasratkai-su,f(x⁽ⁿ^sa⁾)on funktio, joka määrittää ratkaisunx⁽ⁿ^sa⁾objektiivisen arvon, jaP⁽ⁿ^sa⁾ mer-kitsee todennäköisyyttä sille, että iteraation n_sa nykyisestä ratkaisusta siirrytään uuteen.

[6, s. 108] Algoritmi 2.2 esittää SA:n kulkua populaation luomisen kannalta. Jos popu-laatio ei ole valmis SA:n päätyttyä, loput ratkaisut luodaan satunnaisesti. Jos popupopu-laation koko ylittää sen rajan np, parhaat np ratkaisua valitaan populaatioon. Tästä voi suurilla iteraatiolukumäärillän_max seurata ongelmia, joita käsitellään Luvussa 3.2.1.

1 def i n i t i a l i z e _ p o p u l a t i o n ( p o p u l a t i o n _ s i z e ) :

Populaatiosta on pääteltävä, mitkä yksilöistä ovat parempia kuin muut. Kun tämä tiede-tään, kyseiset yksilöt valitaan ehdokkaiksi risteytysvaihetta varten. Tieto hyvistä yksilöistä saadaan määrittelemällä objektiivinen funktio, joka kertoo yksilön arvosta skalaarisesti.

Objektiivista funktiota sovelletaan jokaiselle populaation yksilölle, jotta näitä voidaan ver-rata toisiinsa yksinkertaisesti. Nämä tunnetaan yksilöiden fitness-arvoina.

Objektiivinen funktio on yleensä identtinen minimoitavan tai maksimoitavan kustannus-funktion kanssa. Täten se on optimointiongelmasta riippuvainen. Maksimointiongelman voi helposti muuttaa minimointiongelmaksi sekä päinvastoin. Kun f(x) on optimointon-gelman objektiivinen funktio, käännös suoritetaan yhtälöllä

maxf(x) = −min−f(x). (2.45)

Fitness-arvon laskemiseen voidaan myös huomioida rajoitteita siltä varalta, jos niiden rik-komista halutaan välttää. Tällaiset lisäykset tunnetaan sakkofunktioina. [36] Nämä ovat helposti toteutettavissa. Esimerkkejä näistä ovat vakiosakko ja lineaarinen sakkofunktio.

Vakiosakkoa sovelletaan, jos jokin yhtäsuuruusrajoite rikotaan, ja lineaarista sakkofunk-tiota käytetään epäyhtälörajoitteiden rikkomuksisssa; sakon suuruus nousee lineaarisesti rikkomuksen suuruuden perusteella.

Yksinkertaisille sakkofunktioille on kuitenkin määriteltävä erillisiä parametreja, joiden sää-täminen voi olla hyvin haastavaa ja aikaavievää. GA:n sakkofunktioiden parametrien ar-vot on aina määritettävä oikein, jotta optimaalisin ratkaisu saavutetaan. Lisäksi sakko-funktiot häiritsevät objektiivista sakko-funktiota. Pienillä sakkokertoimilla häirintä on pieni, mutta on mahdollista, että optimi ei ole lähellä todellista, rajoitettua optimia. Suurilla sakkoker-toimilla optimi on lähellä todellista, rajoitettua optimia, mutta häirintä voi olla niin vakavaa, että objektiivisella funktiolla voi ilmetä keinotekoisia lokaaleja optimeja. Tällainen häirintä ei välttämättä johdu GA:sta, sillä tämä on luonteeltaan stokastinen. [36]

Jos rajoitteen rikkominen on täysin kiellettyä, objektiivisessa funktiossa rikkomuksesta voidaan antaa niin suuri sakko, että yksilö ei ole enää kelvollinen. Vaihtoehtoisesti kelvot-tomat yksilöt voidaan poistaa populaatiosta kokonaan, jolloin tätä ylläpidetään lisäämällä uusia kelvollisia yksilöitä.

Arviointivaiheen aikana on mahdollista tarkistaa populaation monipuolisuus. Jos populaa-tiosta löytyy yksilöitä, joilla on yhtäsuuret fitness-arvot, yksilöt voidaan olettaa identtisiksi ja poistaa, kunnes vain yksi sellainen on jäljellä. Poistetut yksilöt korvataan satunnaisesti tuotetuilla yksilöillä. Sitten populaatio arvioidaan uudelleen. Tätä toistetaan, kunnes po-pulaatio täyttää monipuolisuusvaatimukset. [31]

2.2.3 Valinta

Kun populaation kaikki yksilöt on arvioitu, seuraavana tehtävänä on luoda uusi populaa-tio, joka sisältää parempia yksilöitä. Tämä saavutetaan risteytys- ja mutaatio-operaatioilla.

Ensin täytyy päättää, miten yksilöitä valitaan näitä operaatioita varten. Valintavaiheessa valitaan kaksi yksilöä, jotka toimivat vanhempina. Valitut yksilöt sitten tuottavat kaksi jäl-keläistä risteytysvaiheessa, jota tarkastellaan tarkemmin Luvussa 2.2.4.

Pääperiaate ehdokasyksilöiden valinnoissa on arviointivaiheessa lasketut fitness-arvot.

Perusoletus siinä on se, että hyvillä yksilöillä on hyvät geenit, joita optimaalisimmalla yksi-löillä saattaa olla, kun taas huonot geenit poistetaan populaatiosta poistamalla se yksilöt, joilla on huonot fitness-arvot [7, katso 8]. Ehdokasyksilöiden valintamenetelmä on hen-kilökohtaisesti päätettävissä, mutta käytännössä valintamenetelmän tulisi noudattaa yllä mainittua periaatetta. Tässä luvussa esitellään kaksi suosittua funktiota, joilla vanhemmat valitaan: rulettipyörä- ja turnausvalinta.

Kuva 2.7. Rulettipyörävalinnassa yksilön todennäköisyys tulla valituksi on suoraan ver-rannollinen sen fitness-arvoon. Rulettipyörässä yksi tasku vastaa yhtä yksilöä ja sen suu-ruus yksilön todennäköisyyttä tulla valituksi.

Rulettipyörävalinnassa (Roulette Wheel Selection) yksilöiden valintatodennäköisyys on suoraan verrannollinen niiden fitness-arvojen kanssa. Olkoon f(x)yksilöiden objektiivi-nen funktio,gsukupolvi, jonka populaatiossa valinta tehdään,n_ppopulaation koko jax_i^(g) sukupolven g populaatiossa oleva yksilö. Todennäköisyys sille, että yksilö x_i^(g) valitaan vanhemmaksi rulettipyörämenetelmällä on

p_ri = f(xi(g))

∑︁np

j=1f(x_j^(g)). (2.46)

Rulettipyörävalintaa voidaan ajatella tulevan varsinaisesta rulettipyörästä. Tämä sisältää taskuja, joihin ruletissa käytetty pallo voi laskeutua. Erään taskun koko esittää tietyn yksi-lön fitness-arvoa. [6, s. 122] Tätä havainnollistetaan Kuvassa 2.7.

Turnausvalinnassa (Tournament Selection) muutaman yksilön ryhmä muodostetaan valit-semalla populaatiosta yksilöt satunnaisesti huomioimatta näiden fitness-arvoja. Ryhmän voittaja valitaan vanhemmaksi. Turnauksessa olevat yksilöt järjestetään niiden fitness-arvojen mukaan. Voittajat valitaan todennäköisyyksillä

w_t=

⎧

⎨

⎩

p_t·(1−p_t)ⁿ^t⁻¹, 1≤n_t< q_t 1−∑︁qt−1

i=1 pt·(1−pt)ⁱ⁻¹, nt=qt

, (2.47)

jossap_ton itse määritetty todennäköisyys sille, että fitness-arvoltaan paras yksilö voittaa turnauksen,n_t merkitsee yksilön sijoitusta turnauksessa jaq_ton osallistuvien yksilöiden lukumäärä. [6, s. 122–123] Kuva 2.8 esittää turnausvalinnan toimintaa.

p_t yleensä valitaan väliltä [0.50,1.00]. Suurilla q_t turnausvalinta valitsee hyviä

fitness-Kuva 2.8.Turnausvalintamenetelmässä valitaanq_tehdokasyksilöä umpimähkäisesti. Sit-ten nämä järjestetään siSit-ten, että parhaimman fitness-arvon omaava yksilö on ensimmäi-nen, ja huonoimman fitness-arvon omaava yksilö on viimeinen. Mitä tummempi piste on, sitä parempi fitness-arvo yksilöllä on. Turnauksen kooksi on valittu 10 yksilöä. Ensimmäi-seksi sijoittunut yksilö valitaan vanhemmaksi yhtälön(2.47)mukaisesti.

Taulukko 2.4.Turnausvalinnassa valittujen ehdokkaiden voittotodennäköisyyksiäw_t, jot-ka on laskettu yhtälöstä (2.47) ja pyöristetty viiden desimaalin tarkkuuteen. Tässä tur-nauksen koko on1< q_t≤5.

p_t= 0.90 p_t= 0.75 p_t= 0.65 p_t= 0.50 n_t n_t< q_t n_t =q_t n_t< q_t n_t =q_t n_t< q_t n_t =q_t n_t< q_t n_t =q_t

1 0.90000 – 0.75000 – 0.65000 – 0.50000 –

2 0.09000 0.10000 0.18750 0.25000 0.22750 0.35000 0.25000 0.50000 3 0.00900 0.01000 0.04688 0.06250 0.07963 0.12250 0.12500 0.25000 4 0.00090 0.00100 0.01172 0.01563 0.02787 0.04286 0.06250 0.12500

5 – 0.00010 – 0.00391 – 0.01501 – 0.06250

arvon omaavia yksilöitä todennäköisemmin [31]. Toisaalta pienelläq_ttaip_tvoidaan ylläpi-tää populaation monipuolisuutta, mikä ehkäisee optimiratkaisun ennenaikaista suppene-mista lokaaleihin optimiratkaisuihin [6, s. 123][37]. Josq_ttaip_tasetetaan liian alhaisiksi, on mahdollista, että populaatio ei enää suppene optimia kohti, vaan hajaantuu jatkuvasti, sillä häviäjiä valitaan useammin kuin voittajia. Taulukko 2.4 havainnollistaa populaatiosta valittujen ehdokkaiden voittotodennäköisyyksiä muuttujanp_teri arvoilla.

Turnausvalinnasta on muotoiltu binäärinen turnausvalinta, jossa valitaan 2 osallistujaa.

Suuremmalle fitness-arvon omaavalle yksilölle annetaan esimerkiksi 75% todennäköi-syys ja pienemmälle 25%. [1] Kahdella osallistujalla pystytään myös kätevästi päättä-mään, kumpi osallistujista on kelvollisempi, jos optimointiongelmaan liittyy rajoitteita: jos osallistujaArikkoo rajoitteita ja osallistujaB ei, niin turnauksen voittaja onB. [36]

2.2.4 Risteytys

Kun kaksi yksilöä on valittu vanhemmiksi, risteytysvaihe aloitetaan. Ristetyksen tavoittee-na on luoda kaksi uutta yksilöä, jotka perivät vanhempiensa geenit. Risteytyksen myötä laadukkaat vanhemmat lähestyvät tiettyä ratkaisua, kun taas heikommat vanhemmat voi-vat yllättäen löytää paljon paremman ratkaisun. Toistamalla risteytystä hyvillä yksilöillä fitness-arvojen suhteen hyvät geenit ilmenevät yhä useammin, jolloin hyvistä geeneistä koostuva ratkaisu lopullisesti suppenee [34].

Ennen risteytystä päätetään, tehdääkö se ylipäänsä. Jokaista paria kohti tämä päätetään todennäköisyydellä p_c. Jos risteytystä ei tehdä, jälkeläiset ovat identtisiä vanhempien-sa kansvanhempien-sa. Risteytyksen todennäköisyysparametri pc voidaan nähdä tehottomana siinä mielessä, että parametria tulee muokata kokeellisesti, jotta GA:lla saadaan lähellä opti-mia oleva ratkaisu. Tällaista ongelmaa on tutkittu vastepinnan menetelmällä (Response Surface Methodology), jolla todennäköisyysmuuttuja optimoidaan systemaattisilla kokeil-la ennen GA:n alustusta [2].

Sovellettava risteytysoperaattori on vapaasti päätettävissä. Klassisia risteytysoperaatto-reita ovat yhden pisteen, kahden pisteen ja homogeeninen risteytys [6, s. 123]. Näiden toimintaperiaatetta esitellään Kuvassa 2.9.

• Yhden pisteen risteytyksessä yksi piste kromosomissa valitaan umpimähkäisesti, josta eteenpäin geneettinen tieto vaihdetaan vanhempien kanssa. Kromosomit, jot-ka syntyvät vaihdon myötä, annetaan vanhempien jälkeläisille.

• Kahden pisteen risteytyksessä valitaan kaksi pistettä kromosomissa umpimähkäi-sesti. Geneettinen tieto kahden valitun pisteen välillä vaihdetaan vanhempien kans-sa. Syntyneet kromosomit annetaan vanhempien jälkeläisille.

• Homogeenisessa risteytyksessä jokaisella kromosomin alleelilla on tietty todennä-köisyys, jossa geneettinen tieto kyseisessä alleelissa vaihdetaan. Tässä luodaan homogeeninen maski, jonka perusteella geneettinen tieto vaihdetaan: jos maskin eräs alleeli on 0, tietoa ei vaihdeta, kun taas tapauksessa1 tieto vaihdetaan. To-dennäköisyys alleelin vaihdolle on yleensä välillä[0.50,0.80].

Yleensä yksinkertaisten risteytysoperaattoreiden soveltaminen optimointiongelmissa on tehotonta [1]. Näiden ratkaisujen esittäminen binäärisenä merkkijonona voi olla hankalaa – etenkin, jos ratkaisuun liittyy rajoitteita. Otetaan esimerkiksi TSP, jossa tämän eräs

rat-Kuva 2.9.Yksinkertaisia risteytysoperaattoreita binäärikoodatulle tietorakenteelle. a) Yh-den pisteen risteytys. b) KahYh-den pisteen risteytys. c) Homogeeninen risteytys. Vaihtose-kvenssi määrää, missä alleeleissa vaihto tehdään.

Taulukko 2.5. Binäärisen tietorakenteen risteytys TSP:ssä. Kaupunkeja on yhteensä 8.

a) Genotyyppi ennen risteytystä. b) Genotyyppi risteytyksen jälkeen. c) Fenotyyppi ennen risteytystä. d) Fenotyyppi risteytyksen jälkeen.

a) 101 111 110 010 000 001 100 100 101 b) 101 110 010 010 000 001 111 100 001

c) 5 7 6 2 0 1 3 4 5

d) 5 6 2 2 0 1 7 4 1

kaisu ennen risteytystä esitetään binäärisenä merkkijonona. Taulukosta 2.5 nähdään, et-tä kromosomin esitet-täminen binäärimuodossa ei ole suotuisaa, koska ratkaisua joudutaan joko korjaamaan tai poistamaan.

Monissa tutkimuksissa on ehdotettu, että reaalikoodaus toimii binäärikoodausta parem-min, sillä reaalikoodauksella ratkaisut jakautuvat kohdistetulle hakualueelle paremparem-min, jol-loin on mahdollista löytää parempia ratkaisuja [1][33][36]. Lisäksi reaalikoodatun kromo-somin tulkitseminen ja käsittely on helpompaa, koska tarvetta muuntaa ratkaisua edes-takaisin eri muotoihin ei ole. Monet tutkimukset tosiaan soveltavat ehdottamiaan ristey-tysoperaattoreita reaalikoodatuille tietorakenteille, muun muassa järjestetty risteytys (OX, Order Crossover) ja simuloitu binääriristeytys (Simulated Binary Crossover) [26][36].

Sovelletaan risteytysoperaattoria OX. Tässä molemmille vanhemmille valitaan

alleelise-Kuva 2.10.Yksinkertaisia risteytysoperaattoreita reaalikoodatulle tietorakenteelle. a) OX.

b) Yhden pisteen risteytys. c) Kahden pisteen risteytys. Huomaa kohdissa b) ja c) van-hemman B muutokset alleelijärjestyksessä, jotta vanvan-hemman A alleelijärjestys säilyy.

kvenssi satunnaisesti. Sitten jälkeläiset perivät vanhemmille valitut alleelisekvenssit alku-peräisillä sijainneilla. [38, s. 174] Menetelmät, joilla loput alleelit sijoitetaan paikoilleen, vaihtelevat tapauksittain. Tässä tapauksessa ne siirretään oikealle siten, että valittujen alleelisekvenssien sijainnit eivät muutu. Kuva 2.10 havainnollistaa OX-operaattoria.

Muita yksinkertaisia risteytysoperaattoreita voidaan mallintaa alkuperäisistä risteytysope-raattoreista, jotka soveltuvat binäärikoodatuille kromosomeille. Binääriarvojen muuttami-sen sijaan alleeleja vaihdetaan vanhempien kesken siten, että yhden vanhemman allee-lisekvenssit säilyttävät järjestyksen, kun taas toisen vanhemman alleelisekvenssien jär-jestykset muutetaan. Uudessa järjestyksessä huomioidaan myös se, että jälkeläisten A ja B välisillä alleelisekvensseistä löytyvät samat alleelit. Vastaavat risteytysoperaattorit kuvitetaan Kuvassa 2.10.

2.2.5 Mutaatio

Kun jälkeläiset on luotu risteytysvaiheessa, GA siirtyy mutaatiovaiheeseen. Tämän tarkoi-tuksena on monipuolistaa jälkeläispopulaatio, sillä risteytyksen myötä yksilöt suppenevat jotakin ratkaisua kohti. Monipuolisuuden avulla on mahdollista paeta lokaaleista optimi-ratkaisuista sekä löytää jokin parempi ratkaisu. Klassisessa GA:ssa mutaatio-operaatio suoritetaan yksinkertaisesti siten, että binäärikoodatun kromosomin jokaisella alleelilla on todennäköisyysp_mmuuttua nollasta ykköseksi tai ykkösestä nollaksi [6, s. 123–124].

Kuva 2.11. Yksinkertaisia mutaatio-operaattoreita reaalikoodatulle tietorakenteelle. a) Vaihto kahden alleelin välillä. b) Alleelisekvenssin inversio. c) Alleelisekvenssin sekoitus.

d) Alleelisekvenssin siirto.

Sovelletaan reaalikoodausta Luvussa 2.2.4 esitetyin perustein. Kuva 2.11 esittää esi-merkkejä mutaatio-operaattoreista kyseiselle tietorakenteelle. Koska mutaatiovaiheen tar-koituksena on monipuolistaa jälkeläisistä koostuva populaatio, on riittävää tehdä harvoja muutoksia satunnaisesti.

Binäärikoodauksessa mutaatio voidaan kohdistaa yhteen alleeliin, kun taas reaalikoo-dauksessa – olettaen, että käsitellään TSP:tä – se on kohdistettava useampaan kuin yh-teen alleeliin, sillä jos vain yhtä alleelia muokataan, TSP:lle olennainen ehto rikkoutuu.

Kun yhtä tai useampaa alleelia muokataan, muitakin alleeleja on muokattava siten, että kyseinen ehto yhä pätee.

Perinteiset mutaatio-operaattorit, joita on kuvailtu tässä luvussa, eivät huomioi yksilöi-den fitness-arvoja ollenkaan. Tämä voi vaikeuttaa globaalin optimin saavuttamista, sillä suurin osa mahdollisista mutaatioista lähellä globaalia optimia heikentävät nykyistä rat-kaisua. Tätä ongelmakohtaa on pyritty ratkaisemaan käyttämällä perinteisten mutaatio-operaattoreiden sijaan lokaalihakumenetelmiä [31][33].

2.2.6 Lopetus

GA:ta suoritetaan niin kauan, kunnes ennalta asetetut lopetuskriteerit täyttyvät. Tässä luvussa esitetään GA:n yleisimmät lopetuskriteerit.

Ensimmäisenä on hyvä taata, että GA:n suoritus edes päättyy. Tämä saavutetaan yk-sinkertaisella lopetuskriteerillä, jossa rajoitetaan käsiteltävien sukupolvien lukumäärää.

Taataan siis se, että GA käsittelee enintääng_maxsukupolvea.

GA:n suorituksen aikana pidetään kirjaa optimaalisimmasta yksilöstä. Kun GA löytää yk-silön, joka on kirjattua yksilöä parempi, kirjanpitoa päivitetään siten, että uusi yksilö kor-vaa vanhan. On mahdollista, että seuraavan optimiyksilön löytäminen on aikaavievää (tai ongelman optimiratkaisu on jo löydetty). Tällöin GA etsii ratkaisuja jatkuvasti, muttei

löy-dä mitään parempaa. Tällainen ilmiö ratkaistaan lopetuskriteerillä, jossa GA lopetetaan, josg_min sukupolven jälkeen optimiyksilö ei muutu. Kun uusi parempi ratkaisu löydetään, sukupolvikirjanpito lopetuskriteerin suhteen nollataan. Vaihtoehtoisesti jos uusi ratkaisu parantaa edellistä ratkaisua erittäin vähän – esimerkiksi vähemmän kuin0.0001– se kir-jataan ylös, mutta se ei nollaa sukupolvikirjanpitoa [2].

Jos optimointiongelman alaraja z_min (tai yläraja z_max) tunnetaan tai on määritettävissä, sitä voidaan soveltaa opastavana fitness-arvona. Sen rinnalle voidaan lisäksi asettaa eril-linen kynnysarvoz_t, joka työntää GA:n löytämän optimiratkaisun fitness-arvoa asetettua rajaa kohti. Josz−zt≤zmin taiz+zt ≥zmax, niin GA:n suoritus lopetetaan.

Jos optimointiongelma on laajuudeltaan suuri, sukupolvien käsittelyssä voi kulua hyvin pitkä aika. Käsiteltävien sukupolvien lukumäärän muuttaminen tämän suhteen on epä-tarkkaa ja saattaa vaikuttaa GA:n suoriutumiseen negatiivisesti. Täten tarvitaan lopetus-kriteeri, joka riipuu kuluneesta ajasta. Koska tietokoneet suorittavat GA:ta optimointion-gelman ratkaisemisessa, eräänä lopetuskriteerinä voidaan soveltaa CPU-aikaa (Central Processing Unit, suoritin), joka on kätevästi mitattavissa.

2.2.7 Sovellutukset

GA ja tavanomaiset heuristiikat ovat toisiaan täydentäviä. Hybridisoimalla nämä toisten-sa kanstoisten-sa toisten-saadaan algoritmeja, jotka suoriutuvat paremmin kuin GA ja heuristiikat yk-sin. [2] Hybridisaatiota voidaan myös soveltaa optimointiongelmien rajoittamisessa. GA:n fitness-funktioon voidaan lisätä sakkofunktioita, jotka ovat peräisin optimointiongelman ra-joitteista. Tällöin optimointiongelman ratkaisuja rohkaistaan käyttäytymään tietyllä tavalla populaatiossa. [36]

GA soveltuu hyvin optimointiongelmiin, joissa ”kombinatoriset räjähdykset” ovat yleisiä.

Morriset al.esittävät tutkimuksessa [33] Lamarckin genetiikkaan perustuva GA, jolla myö-tävaikutetaan lääkkeiden suunnittelussa. Lamarckinen genetiikka perustuu ideaan, jossa yksilön ominaisuudet, jotka voivat ilmestyä ja kadota luontoon sopeutuessa, voivat pe-riytyä jälkeläisille. Tässä tutkitaan molekulaarista telakointia, joka on haastava optimoin-tiongelma. Se vaatii tehokasta näytteiden ottoja koko alueessa, jossa on positionaalista, orientaationaalisia ja konformaatiomaisia mahdollisuuksia. Sekä kanoniset GA:t että EA:t on todettu menestyksellisiksi algoritmeiksi lääkkeiden suunnittelussa ja molekulaarisessa telakoinnissa.

Langattomiin verkkoihin liittyy kompleksisia optimointiongelmia. Tavoitteena on ratkaista reititysongelmia, jotta langattomien verkkojen elinikää voidaan pidentää (jos verkko käyt-tää pattereita) tai maksimoida työmäärää siten, että verkko pystyy toimimaan itsenäises-ti energiakeräysmenetelmin. [39] Muitakin tavoitteita on, kuten langattoman videolähe-tysten laadun parantaminen. Tällaisiin ongelmiin liittyy yksi tai useampi pääasema sekä

monia verkkosolmuja. Nämä johtavat kombinatorisiin räjähdyksiin. Koska GA on popu-laatioon perustuva algoritmi, se sopii erityisen hyvin langattomien verkkojen reititysongel-mien ratkaisemista varten. [7]

GA voidaan kätevästi hyödyntää keinotekoisten neuroverkkojen (ANN, Artificial Neural Network) kehittämisessä. GA:n kromosomi esitetään ANN:n painoarvoina. Alustusvai-heessa tuotetaan satunnaisesti populaatio ANN:n painoarvoista. Sitten jokaisen sukupol-ven aikana painoarvojen fitness-arvo lasketaan ANN:n toimesta. Tällä menettelyllä GA soveltuu hyvin ANN:n painoarvojen käsittelyä varten BP-algoritmin (Back-Propagation) kanssa. [40]. Potvinet al.ovat soveltaneet tutkimuksessa [41] GA:n ja ANN:n hybridisaa-tiota, joka on osoittautunut kilpailukykyiseksi algoritmiksi VRPTW:n ratkaisemisessa.

Optimointiongelmia ratkaistaessa tavoitteet ovat usein ristiriidassa toistensa kanssa; ta-voitteiden samanaikainen optimointi on käytännössä mahdotonta. Monet todelliset in-sinööritason ongelmat sisältävät useita tavoitteita, esimerkiksi kustannusten minimointi, suorituskyvyn maksimointi ja luotettavuuden maksimointi. Yleisiä menetelmiä useamman tavoitteen optimointiin ovat muun muassa tavoitefunktion muuntaminen yhdistelmäfunk-tioksi sopivien painoarvojen avulla ja tavoitteiden muuntaminen rajoitteiksi (yhtä tavoitetta lukuun ottamatta). Molemmat menetelmät ovat luonteiltaan umpimähkäisiä ja palauttavat vain yhden arvon. [34]

Toinen yleinen menetelmä on Pareto-optimaaliratkaisu, joka on joukko ratkaisuja, jot-ka ovat toistensa suhteen epädominoivia: kun siirrytään yhdestä Pareto-ratjot-kaisusta toi-seen, löytyy aina tietty uhraus eräässä tavoitteessa, jolla saavutetaan tietty hyöty muissa.

Pareto-optimaalisista ratkaisujoukoista yleensä pidetään enemmän kuin yksittäisistä rat-kaisuista, koska ne ovat käytännöllisiä, kun pidetään mielessä käytännöllisiä ongelmia, koska päätöksentekijän lopullinen ratkaisu on aina jonkinlainen vaihtokauppa. [34]

GA soveltuu tällaisiin ongelmiin hyvin, koska se perustuu populaation käsittelyyn: GA et-sii samanaikaisesti ratkaisuavaruuden eri alueilta ratkaisuja, jolloin vaikealle ongelmalle löytyy monipuolisia ratkaisuja. Perinteinen GA kuitenkin optimoi vain yhtä tavoitetta, jo-ten sitä muokataan sijo-ten, että se soveltuu monitavoitteellisiin ongelmiin. Tässä käytetään erikoistuneita fitness-funktioita ja muita menetelmiä, joilla korostetaan ratkaisun monipuo-lisuutta. Yhdistämällä GA Pareto-optimaaliratkaisujen kanssa saadaan monitavoitteinen

In document Ajoneuvoreititysongelman analysointi ja ratkaiseminen geneettisellä algoritmilla (sivua 31-45)