Parametrien tunnistus ja datajoukon sovittaminen optimoinnin avulla Potku-ohjelmassa

(1)

Heta Rekilä

Parametrien tunnistus ja datajoukon sovittaminen optimoinnin avulla Potku-ohjelmassa

Tietotekniikan pro gradu -tutkielma 25. kesäkuuta 2019

Jyväskylän yliopisto

(2)

Tekijä:Heta Rekilä

Yhteystiedot:heta.l.rekila@student.jyu.fi

Ohjaajat:Tero Tuovinen (informaatioteknologian tiedekunta) ja Mikko Laitinen (matemaattis- luonnontieteellinen tiedekunta, fysiikan laitos)

Työn nimi: Parametrien tunnistus ja datajoukon sovittaminen optimoinnin avulla Potku- ohjelmassa

Title in English:Parameter identification and fitting a data set using optimization methods in Potku

Työ:Pro gradu -tutkielma

Suuntautumisvaihtoehto:Ohjelmistotekniikka Sivumäärä:90+0

Tiivistelmä: Tutkielmassa perehdytään erityyppisiin optimointialgoritmeihin, joita mode- FRONTIER-optimointiympäristö tarjoaa. Ympäristöä voi käyttää tehokkaaseen optimointialgoritmien vertailuun. Algoritmien suoriutumisen arviointia varten määriteltiin vertailu- menetelmä, jossa hyödynnettiin ZDT-funktioita. Vertailun tulosten perusteella valittiin kaksi algoritmia, NSGA-II ja MOGA-II, joita käytettiin simuloidun datajoukon sovittamiseen kokeellista datajoukkoa vastaavaksi. Datajoukot olivat Jyväskylän yliopiston fysiikan laitoksen Potku-ohjelmalla tuotettuja energiaspektrejä. Havaittiin, että sovittamiseen soveltui parhaiten NSGA-II. Algoritmi toteutettiin osaksi Potku-ohjelmaa.

Avainsanat:optimointi, Potku, monitavoitteinen optimointi, modeFRONTIER, MOGA-II, NSGA-II, ERDA, datajoukon sovittaminen, Pareto-optimaalisuus, zdt-funktiot, sukupolvien etäisyys -mittari, välistys-mittari, virheen suhdeluku -mittari, fluenssi, rekyylijakauma, energiaspektri, vertailu

Abstract:This thesis focuses on different types of optimization algorithms that are inclu- ded in modeFRONTIER. modeFRONTIER is an application that can be used to efficiently compare optimization algorithms. A comparison method that uses ZDT functions was deve-

(3)

loped to aid when the performance of these different algorithms was evaluated. The results indicated that two algorithms, NSGA-II and MOGA-II, would be the best candidates to use in fitting a data set to match another data set. These two data sets were energy spectra from an application called Potku (a simulation and analysis software from the Department of Phy- sics in the University of Jyväskylä), and the simulated energy spectrum was matched to the experimental energy spectrum. It was observed that the best performance was by NSGA-II.

NSGA-II was implemented as a part of Potku.

Keywords:optimization, Potku, multiobjective optimization, modeFRONTIER, MOGA-II, NSGA-II, ERDA, data set fitting, Pareto optimality, ZDT functions, generational distance, spacing, error ratio, fluence, recoil atom distribution, energy spectrum, comparison

(4)

Termiluettelo

ARGA (eng.Adaptive Range Genetic Algorithm). Yksitavoitteinen optimointialgoritmi, joka käyttää muuttujien määrittelyvälin automaattista mukauttamista. Toimii jatkuvien muuttujien lisäksi kokonaislukumuuttujilla ja diskreeteillä arvoilla.

ARRangeGA (eng. Adaptive Real Range Genetic Algorithm). Yksitavoittei- nen optimointialgoritmi, joka käyttää muuttujien määrittelyvä- lin automaattista mukauttamista. Toimii vain jatkuvilla muut- tujilla.

ARMOGA (eng.Adaptive Range Multi-Objective Genetic Algorithm). Mo- nitavoitteinen optimointialgoritmi, jossa käytetään muuttujien määrittelyvälin automaattista mukauttamista. Toimii jatkuvien muuttujien lisäksi kokonaislukumuuttujilla ja diskreeteillä arvoilla.

Dominointi Ratkaisu A dominoi ratkaisua B, kun sen tavoitefunktioiden arvot ovat vähintään yhtä hyviä kuin ratkaisun B, ja lisäksi vä- hintään yhden tavoitefunktion arvon pitää olla parempi kuin ratkaisulla B.

Energiaspektri Alkuaineelle laskettava atomien määrä näytteen eri syvyyksis- sä.

ER Virheen suhdeluku (eng.Error Ratio): mittari, joka kertoo, kuinka moni löydetyn Pareto-rintaman ratkaisuista kuuluu todelli- seen Pareto-rintamaan.

ERDA Elastinen rekyylianalyysi (eng. Elastic Recoil Detection Ana- lysis).

FAST RSM- eli vastauspintamalleja käyttävä nopeasti konvergoituva monistrateginen optimointialgoritmi.

Fluenssi Ionisuihkun määrä, hiukkasta/cm².

Get_espe Ohjelma, joka tulkitsee MCERD-ohjelman tulokset energia-

(5)

GD Sukupolvien etäisyys (eng. Generational Distance): mittari, joka kertoo, kuinka lähellä löydetty Pareto-rintama on ongelman todellista Pareto-rintamaa.

HYBRID Monistrateginen optimointialgoritmi, joka käyttää geneettisiä algoritmeja ja SQP-gradienttimenetelmiä.

Ionisuihku Ioneja kiihdytetään tiettyyn nopeuteen ja ohjataan suihkuna kohti näytettä.

JarrutusvoimadE/dx Voima, jolla hiukkaset hidastuvat liikkuessaan näytteessä tai muussa materiaalissa.

Konvergenssi Algoritmin suppeneminen, eli kuinka nopeasti algoritmi pää- tyy kohti jotain tiettyä ratkaisualuetta.

MCERD Monte Carlo -simulaatiota käyttävä elastista rekyylianalyysia laskeva ohjelma.

MEGO (eng Multi-Objective Efficient Global Optimization). Monita- voitteinen, Gaussin prosesseihin perustuva monistrateginen optimointialgoritmi.

modeFRONTIER Optimointiympäristö, johon on toteutettu eri yksi- ja monitavoitteisia optimointialgoritmeja.

MOGA (eng. Multi-Objective Genetic Algorithm). Monitavoitteinen, elitismiä käyttävä geneettinen optimointialgoritmi.

MOGT (eng. Multi-Objective Game Theory). Monitavoitteinen peli- teoriaan perustuva optimointialgoritmi.

Monte Carlo -menetelmä Satunnaisen mallintamisen menetelmä, joka MCERD-ohjelman tapauksessa ottaa huomioon atomin moninkertaisen sironnan.

MOPSO (eng. Multi-Objective Particle Swarm Optimization). Monita- voitteinen partikkeliparvioptimointialgoritmi.

MOSA (eng.Multi-Objective Simulated Annealing). Monitavoitteinen, hehkutusta simuloiva optimointialgoritmi.

NSGA (eng. Nondominated Sorting Genetic Algorithm). Nopeaa ei- dominoinnin perusteella tehtävää lajittelua käyttävä monitavoitteinen optimointialgoritmi.

(6)

Pareto-rintama Tavoitefunktioiden arvojen perusteella järjestetty ratkaisujoukko, jossa mikään ratkaisu ei dominoi toista.

pilOPT Numeerisia tutkimusstrategioita ja RSM-pohjaisia ratkaisuja hyödyntävä monistrateginen optimointialgoritmi.

PSO (eng. Particle Swarm Optimization). Parviälykkyyteen perustuva partikkeliparvioptimointialgoritmi.

Python-skripti Python-ohjelmointikielellä tehty lyhyt suoritettava ohjelma.

RBS (eng.Rutherford Backscattering Spectrometry). Tekniikka, jossa näytemateriaalia kohti ammutaan näytemateriaalin atomeja kevyempiä ioneja, jolloin suihkun ioni siroaa kohti ilmaisinta.

Rekyylijakauma Alkuaineen pitoisuuksien jakautuminen näytteen eri syvyyk- sissä. Käytetään syötetietona MCERD-ohjelmalle.

RSM Vastauspintamalli (eng.Response Surface Model).

SAnGeA (eng.Screen Analysis Genetic Algorithm). Monistrateginen optimointialgoritmi, joka käyttää seulontamenetelmää ja geneettisten algoritmien globaalia etsintää.

SBX (eng. Simulated Binary Crossover). Binääristä risteytystä simuloiva reaaliluvuille käytetty risteytys.

SP Välistys (eng. Spacing): mittari, joka kertoo, kuinka tasaisesti ratkaisut ovat jakautuneet löydetyllä Pareto-rintamalla.

SQP Peräkkäinen neliöllinen ohjelmointi (eng. Sequential Quadra- tic Programming).

Substraatti Näytteen alin kerros, joka on ionisuihkun kannalta hyvin pak- su, jopa ääretön.

Tavoitefunktio Funktio, jonka arvo on tarkoitus minimoida tai maksimoida optimoinnin avulla.

ZDT-funktiot Monitavoitteisen optimointialgoritmin testaukseen suunnitel- tuja monitavoitteisia optimointiongelmia.

(7)

Kuvat

Kuva 1. Kaavio lentoaika-ERDA-mittauslaitteistosta. . . 3

Kuva 2. Esimerkki lentoaika-energiahistogrammista (eng.ToF-E histogram). . . 4

Kuva 3. Esimerkki rekyylijakauman muuttumisesta. . . 6

Kuva 4. Optimointiongelman ratkaisut ja dominointi. . . 9

Kuva 5. Esimerkki neljästä pisteestä muodostuvasta rekyylijakaumasta. . . 29

Kuva 6. Työnkulkukaavio tavoitefunktioiden arvojen selvittämiseksi. . . 31

Kuva 7. Pisteen A ja B välinen etäisyys. . . 34

Kuva 8. Pareto-rintamat funktioille ZDT1, ZDT2 ja ZDT3. . . 39

Kuva 9. NSGA-II-algoritmilla löydetty ZDT2-funktion Pareto-rintama. . . 46

Kuva 10. ZDT3-funktion Pareto-rintamat: todellinen, evoluutiostrategian löytämä ja NSGA-II-algoritmin löytämä. . . 47

Kuva 11. Piin energiaspektri fluenssilla 1·10¹⁴. . . 52

Kuva 12. Piin energiaspektri fluenssilla 9·10⁵. . . 53

Kuva 13. NSGA-II, MOGA-II ja Pareto-rintamat: alkupopulaatio 1.. . . 58

Kuva 14. NSGA-II, MOGA-II ja Pareto-rintamien ensimmäiset ratkaisut: rekyylijakaumat alkupopulaatiolle 1. . . 59

Kuva 15. NSGA-II, MOGA-II ja Pareto-rintamien ensimmäiset ratkaisut: energiaspektrit alkupopulaatiolle 1. . . 60

Kuva 16. NSGA-II, MOGA-II ja Pareto-rintamien viimeiset ratkaisut: rekyylijakaumat alkupopulaatiolle 1. . . 61

Kuva 17. NSGA-II, MOGA-II ja Pareto-rintamien viimeiset ratkaisut: energiaspektrit alkupopulaatiolle 1. . . 62

Kuva 18. NSGA-II, MOGA-II ja Pareto-rintamat: alkupopulaatio 2.. . . 63

Kuva 19. NSGA-II, MOGA-II ja Pareto-rintamien ensimmäiset ratkaisut: rekyylijakaumat alkupopulaatiolle 2. . . 64

Kuva 20. NSGA-II, MOGA-II ja Pareto-rintamien ensimmäiset ratkaisut: energiaspektrit alkupopulaatiolle 2. . . 65

Kuva 21. NSGA-II, MOGA-II ja Pareto-rintamien viimeiset ratkaisut: rekyylijakaumat alkupopulaatiolle 2. . . 66

Kuva 22. NSGA-II, MOGA-II ja Pareto-rintamien viimeiset ratkaisut: energiaspektrit alkupopulaatiolle 2. . . 67

Kuva 23. MOPSO ja Pareto-rintama: alkupopulaatio 1. . . 68

Kuva 24. MOPSO ja Pareto-rintaman ratkaisut: rekyylijakaumat alkupopulaatiolle 1. . . 68

Kuva 25. MOPSO ja Pareto-rintaman ratkaisut: energiaspektrit alkupopulaatiolle 1. . . 69

Taulukot

Taulukko 1. ZDT1 ja GD-arvot. . . 42

Taulukko 2. ZDT1 ja SP-arvot. . . 42

Taulukko 3. ZDT1, ZDT2, ZDT3 ja ER-arvot. . . 42

(8)

Taulukko 8. ZDT1, ZDT2, ZDT3 ja suoritusajat. . . 45

Taulukko 9. Fluenssi NSGA-II-algoritmilla: alkupopulaatio 100. . . 49

Taulukko 13. Fluenssi MOGA-II-algoritmilla: alkupopulaatio 100. . . 51

Taulukko 17. Fluenssi MOPSO-algoritmilla: alkupopulaatio 100.. . . 54

Taulukko 18. Fluenssi MOPSO-algoritmilla: alkupopulaatio 50. . . 54

Taulukko 21. NSGA-II, MOGA-II, MOPSO ja energiaspektrien sovituksen kesto. . . 57

Taulukko 22. Tutkimuslaitteiston ja nopeammin optimoinnin suorittaneen laitteiston laitemääritykset.. . . 74

(9)

Sisältö

1 JOHDANTO . . . 1

2 ELASTINEN REKYYLIANALYYSI JA MONTE CARLO -SIMULOINTI . . . 3

3 OPTIMOINTITEORIA . . . 8

3.1 Evolutionaariset algoritmit . . . 10

3.1.1 MOGA-II. . . 11

3.1.2 NSGA-II . . . 12

3.1.3 ARMOGA . . . 14

3.1.4 Evoluutiostrategia. . . 16

3.2 Heuristiset menetelmät . . . 18

3.2.1 MOSA . . . 18

3.2.2 MOGT . . . 21

3.2.3 MOPSO . . . 23

3.3 Monistrategiset algoritmit. . . 25

4 MODEFRONTIER-OPTIMOINTIYMPÄRISTÖ. . . 27

4.1 Työnkulkukaaviot . . . 28

4.2 Tavoitefunktiot . . . 32

4.2.1 Pinta-alojen erotus . . . 32

4.2.2 Pisteiden välinen etäisyys . . . 33

5 ALGORITMIEN VERTAILU JA TULOKSET . . . 35

5.1 Vertailumenetelmä . . . 35

5.1.1 ZDT-funktiot . . . 37

5.1.2 Algoritmin suoriutumisen mittarit . . . 38

5.2 ZDT-funktiot: vertailun tulokset . . . 41

5.3 NSGA-II, MOGA-II ja energiaspektrien sovittaminen . . . 48

5.3.1 Fluenssin etsiminen . . . 49

5.3.2 Rekyylijakauman muodon rajojen etsiminen . . . 55

6 JOHTOPÄÄTÖKSET . . . 70

6.1 Potku-ohjelman toteutuksen pääpiirteet . . . 72

7 YHTEENVETO. . . 75

LÄHTEET . . . 77

(10)

1 Johdanto

Optimointi on hyödyllinen väline ongelmien ratkaisuun. Se on työkalu, jota voidaan käyttää vastauksen etsimiseen ongelmiin, joissa tarkoituksena on etsiä paras mahdollinen ratkaisu (Mosavi 2010). On myös olemassa ongelmia, jotka määritetään useammalla kuin yhdellä ta- voitteella. Kun tavoitteet ovat ristiriidassa keskenään, optimaalisia ratkaisuja on useampia (Chase ym. 2009). Monitavoitteiset optimointiongelmat ovat myös ratkaistavissa optimoinnin avulla, ja menetelmää kutsutaan monitavoitteiseksi optimoinniksi. (Salmi 2008)

Optimointiongelmaa ratkaistaessa voi käyttää erilaisia ja erityyppisiä algoritmeja, kuten esimerkiksi biologisesta evoluutiosta vaikutteita ottaneita evolutionaarisia algoritmeja (Simon 2013). Eräs mahdollisuus on myös käyttää heuristisia algoritmeja, joissa tarkoituksena ei ole välttämättä etsiä parhainta ratkaisua, kunhan päästään sopivan lähelle sitä (Kokash 2014).

Eri luokkiin kuuluvat algoritmit kuuluvat siten eri algoritmiperheisiin.

Tutkielmassa perehdytään eri perheisiin kuuluviin optimointialgoritmeihin ja vertaillaan nii- tä keskenään. Vertailun perusteella niistä valitaan sopiva automatisoimaan prosessia, joka liittyy Jyväskylän yliopiston fysiikan laitoksen analyysi- ja simulaatiosovellus Potkuun (Ars- tila ym. 2014). Lisäksi algoritmien vertailuprosessin luotettavuutta selvitetään ja pyritään varmistamaan.

Potku-ohjelmaa käytetään näytemateriaalin alkuainekoostumuksen ja -jakauman analysoi- miseen. Koostumuksen selvitystä käytetään hyödyksi mm. ohutkalvojen ja puolijohteiden tutkimuksessa. Epäpuhtauksien selvittäminen on myös tyypillistä. (University of Jyväskylä 2019; Arstila ym. 2014)

Potku-ohjelmassa voidaan tuottaa simuloimalla dataa, joka on samantyyppistä kuin näytema- teriaalista kokeellisesti mitattu. Simuloitua datajoukkoa tarkennetaan säätämällä simulaation lähtöarvoja, jolloin simuloitu datajoukko saadaan vastaamaan kokeellista dataa. Lopputu- loksena simulaation avulla voidaan saada tarkempaa tietoa näytemateriaalista kuin mitä pel- källä kokeellisen datan analyysilla saa selville. (University of Jyväskylä 2018) Simulaation lähtöarvojen eli parametrien tunnistaminen ja muokkaminen optimoinnin avulla on tarkoitus

(11)

käytetyt resurssit vapautuvat näin muuhun käyttöön, mikä helpottaa ohjelman käyttöä.

Optimointialgoritmeja testataan Esteco SpA -yrityksen kehittämällä modeFRONTIER-op- timointiympäristöllä, johon on toteutettu algoritmeja eri optimointiperheistä (Esteco SpA 2019b). modeFRONTIER tarjoaa tehokkaan tavan testata eri optimointialgoritmeja ilman, että niistä tarvitsee tehdä erillisiä toteutuksia, joten tutkimus rajataan koskemaan vain tarjottuja algoritmeja.

Kun sopiva optimointialgoritmi on löydetty, se toteutetaan kiinteäksi osaksi Potku-ohjelmaa.

Optimointiprosessista tulee kätevämpi tehdä verrattuna siihen, että optimointi tapahtuisi eril- lisenä modeFRONTIER-optimointiympäristön kanssa. Optimoinnin tekemiseen ei tarvitse useaa ohjelmaa, joten aikaa ei kulu ympäristöjen yhteensovittamiseen. Lisäksi modeFRON- TIER ei mahdollista yhtä sulavaa simulaatioparametrien tai kokeellisen datan muokkaamista kuin Potku.

Tutkielman luvussa 2 esitellään tarkemmin Potku-ohjelman ominaisuuksia ja niiden fysi- kaalista taustaa, mm. elastista rekyylianalyysia ja Monte Carlo -simulointia. Luku 3 pohjus- taa optimointia ja vertailussa käytettyjen algoritmien periaatteita ja tekniikoita. Luvussa 4 kuvataan modeFRONTIER-optimointiympäristö ja siinä käytetyt työnkulkukaaviot. Lisäk- si luvussa esitetään optimoinnin tavoitefunktiot, jotka mittaavat kokeelllisen ja simuloidun datajoukkojen vastaavuutta toisiinsa.

Luku 5 kuvaa kaksivaiheisen vertailumenetelmän ja sen tulokset. Myös vertailumenetelmäs- sä tarvittavat funktiot ja mittarit esitellään. Johtopäätökset ja valitun algoritmin toteutuksen pääpiirteet kuvataan luvussa 6. Luvussa 6 arvioidaan myös tulosten luotettavuutta ja pohdi- taan epävarmuuksia. Viimeisessä luvussa 7 on yhteenveto.

(12)

2 Elastinen rekyylianalyysi ja Monte Carlo -simulointi

Elastinen rekyylianalyysi (ERDA, eng. Elastic Recoil Detection Analysis) perustuu siihen, että ionisuihku ammutaan kohti näytemateriaalia. Suihkun ionit törmäävät näytemateriaalin atomeihin, jonka seurauksena näytemateriaalista rekyloituu (eli kimpoaa) hiukkasia kohti ilmaisinta. Rekyloituneille hiukkasille määritetään sekä lentoaika että energia lentoaikaport- tien ja energiailmaisimen avulla. (Arstila, Sajavaara ja Keinonen 2001; Arstila ym. 2014) Rekyloituneiden näyteatomien lisäksi myös sironnutta suihkua voi käyttää näytteen analy- sointiin.

Kuvassa 1 on esimerkki lentoaikojen ja energioiden mittamiseen tarvittavasta mittauslaitteis- ton asettelusta (Laitinen 2013). Lentoaikojen ja energioiden perusteella voidaan määrittää rekyyliatomin massa, joka puolestaan kertoo atomin alkuaineen ja isotoopin (Arstila, Sajavaara ja Keinonen 2001). Tuloksena saadaan jokaiselle alkuaineelle lentoaika-energiahistogrammi (kuva 2).

Lentoaika-energiahistogrammissa esitetystä datasta voidaan muodostaa erilaisia havainnol- listavia kuvia, mm. energiaspektrejä. Energiaspektrit saadaan muodostettua alkuainekoh- taisesti (Arstila ym. 2014), toisin kuin perinteisemmällä RBS-tekniikalla (eng. Rutherford Backscattering Spectrometry), joka pohjautuu näytemateriaalin atomeja kevyempien suih- kuionien näytteestä siroamiseen (Ernst 2005). Potku-ohjelman energiaspektrit kuvaavat näyt- teestä sironneiden havaittujen atomien energiaa ja määrää (Arstila ym. 2014). Energiaspekt-

Kuva 1. Kaavio lentoaika-ERDA-mittauslaitteistosta. (Laitinen 2013)

(13)

Kuva 2. Esimerkki lentoaika-energiahistogrammista (eng.ToF-E histogram).

rien muodostamista varten on kehitetty analyysi- ja simulaatiosovellus Potku, joka pohjautuu edellä kuvattuun lentoaikojen ja energioiden mittaamiseen (Arstila ym. 2014).

Potku-ohjelmalla voi lisäksi havainnollistaa näytemateriaalissa tapahtuneita ionisuihkun ai- heuttamia muutoksia (koostumuksen muutokset) sekä näytemateriaalin eri syvyyksissä olevia alkuaineiden pitoisuuksia (syvyysprofiilit) (Arstila ym. 2014). Havainnollistusten avulla saadaan kuva siitä, mistä alkuaineista näyte koostuu, ja kuinka paljon niitä on milläkin sy- vyydellä.

Potku-ohjelman kehittäminen aloitetiin Jyväskylän yliopiston informaatioteknologian tiede- kunnan kanssa yhdessä toteutetussa opiskelijaprojektissa vuonna 2013 (University of Jyväs- kylä 2019). Ohjelmaa on jatkokehitetty tämän jälkeen, ja yhtenä isoimmista muutoksista siihen lisättiin simulaatiopuoli vuonna 2018. Simulaatiopuolta käytetään simuloimaan ioni- suihkumittausta, ja siihen tarvittava laskenta tapahtuu erillisellä MCERD-ohjelmalla (Arsti- la, Sajavaara ja Keinonen 2001). MCERD sulautettiin osaksi Potku-ohjelmaa.

MCERD-ohjelma ottaa huomioon moninkertaisen sironnan ilmiön Monte Carlo -menetel- män avulla (University of Jyväskylä 2019). Monte Carlo -menetelmällä mallinnetaan satun- naisuutta: satunnaisesti jakautuneet näytemateriaalin pistemäiset atomit aiheuttavat sisääntu-

(14)

levan ionisuihkun ja näytteestä ulos suuntautuneiden hiukkasten sirontaa. (Arstila, Sajavaara ja Keinonen 2001) Lisäksi sirontojen välillä tapahtuu pääosin elektronisesta jarrutusvoimas- ta dE/dx(eng. stopping force) johtuvaa, kitkamaista hidastumista (Laitinen 2013; Arstila, Sajavaara ja Keinonen 2001).

MCERD-simulaatiota ohjataan erilaisilla parametreilla. Parametrit kattavat mm. ilmaisimen määrittämisen (ilmaisimeen kuuluvat kalvot, lentoaikaportit ja energiailmaisin), suihkun ionin määrittelyn, näytemateriaalin kerrosten koostumuksen sekä muita laskennan laajuutta rajoittavia parametreja. (Arstila 1999) Monet näistä parametreista ovat yhteisiä kokeellisen puolen kanssa, joten niitä ei ole välttämättä tarkoitus muuttaa, jos halutaan vaikuttaa vain simulaatioon.

Oleellisin parametri simulaation muokkaamiseen on rekyylijakauma (vastaa kokeellisen puolen syvyysprofiilia). Se kertoo tietyn alkuaineen pitoisuuksien jakautumisen näytteen eri sy- vyyksissä. Rekyylijakauman muoto on tyypillisimmin suorakulmainen. Sen pisteitä muuttamalla (ks. kuva 3) käyttäjä muuttaa siis alkuainepitoisuuksia näytteessä ja sen seurauksena MCERD-ohjelman tuottamaa dataa. (Arstila 1999)

MCERD-ohjelman tuottama data kertoo alkuperäisen ionin syvyyden, rekyyliatomin tilastol- lisen painon (suhteellisen osuuden), ionin lentoajan ja sen energian ilmaisimessa. Jotta datasta voidaan muodostaa energiaspektri, tarvitaan toinen ohjelma, sillä MCERD-ohjelmaa ei voi käyttää energiaspektrien muodostamiseen. Muodostamista varten käytössä on get_espe-ni- minen ohjelma. (Arstila, Sajavaara ja Keinonen 2001)

Get_espe laskee MCERD-ohjelman tuloksista näytteestä sironneiden atomien määrän ja energian eli energiaspektrin. Get_espe-ohjelmassa on lisäksi piirre, jota hyödynnetään myöhem- min tutkimuksessa: Jos rekyylijakaumaa ei muuteta syvyysakselin suhteen niin, että nollassa olevat välit muuttuvat (esimerkiksi kuvassa 3 vihreällä näkyvä muutos), voi uuden energiaspektrin laskea pelkällä get_espe-ohjelmalla (Arstila, Sajavaara ja Keinonen 2001). Tällöin vältytään hitaan MCERD-ohjelman ajolta, joka muuten olisi tarpeen. Jos taas syvyydessä, jossa ei rekyylijakauman mukaan aiemman MCERD-ajon aikana ollut alkuainetta, kasvate- taan alkuaineen määrää, get_espe-ohjelman ajo ilman MCERD-ohjelman uudelleenajoa ei ole mahdollista. Tällaisen muutoksen esimerkki on kuvattu kuvassa 3 punaisella.

(15)

Kuva 3. Esimerkki rekyylijakauman muuttumisesta. Vihreällä merkitty liikkuminen ei tarvitse MCERD-ohjelman ajoa uudelleen, koska syvyysakselilla väli [125, 230] ei muutu, jossa suhteellinen pitoisuus on 0. Punaisella merkitty muutos puolestaan vaatii MCERd-ohjelman uudelleen ajon muuttuneella rekyylillä, koska väli on pienentynyt.

Get_espe-ohjelmaa ohjataan samoilla parametreilla kuin MCERD-ohjelmaa, mutta lisäksi tarvitaan myös fluenssia (annos eli ionisuihkun määrä, hiukkasta/cm²). Fluenssin suuruu- den avulla voidaan määrittää syntyneen energiaspektrin intensiteetti, eli voidaan vaikuttaa näytteestä irroneiden atomien määrään (energiaspektrin korkeus). Fluenssi täsmäytetään ko- keelliseen dataan seuraavasti: näytemateriaalin pohjakerroksen eli substraatin energiaspektri sovitetaan vastaamaan kokeellisen substraatin energiaspektriä niin, että rekyylijakauma on staattinen. Kun fluenssi on kiinnitetty, voidaan näytteen pinnan alkuaineiden rekyylijakau- mia muuttamalla sovittaa niiden energiaspektrit kokeellisia spektrejä vastaaviksi.

Simuloidun ja kokeellisen datan sovittamiseen tarvitaan energiaspektrien vertaamista. Ver- tailu tapahtuu seuraavasti: Kokeellinen ja simuloitu energiaspektri piirretään samaan ku- vaajaan, josta nähdään visuaalisesti, kuinka erilaiset ne ovat. Kuvaajasta voi laskea tietylle syvyysakselin (eli vaaka-akselin) välille, mikä suhde näiden kahden energiaspektrin pinta- aloilla on. Mitä lähempänä suhde on lukua yksi, sitä enemmän ne vastaavat toisiaan. Suh- delukua voi käyttää rekyylijakauman pisteiden suhteellisen pitoisuuden (pystyakseli) koor- dinaattien kertomiseen. Kun seuraavalla kerralla muodostetaan energiaspektrit, simuloitu

(16)

spektri vastaa enemmän kokeellista spektriä. (University of Jyväskylä 2018)

Kun simuloitu ja kokeellinen energiaspektri vastaavat mahdollisimman hyvin toisiaan, antaa simulaation avulla määritetty rekyylijakauma yleensä tarkemman kuvan näytemateriaalis- ta kuin mitä suoraviivaisella kokeellisen datan analyysilla selviää (University of Jyväskylä 2018). Ennen tutkimustyön alkua syksyllä 2018 sovittamisprosessi tehtiin käsin: Ensin et- sittiin sopiva fluenssi muuttamalla sen arvoja vertailukertojen välillä. Fluenssin sopivan arvon löydyttyä vertailukertojen välillä muutettiin rekyylijakaumaa, ja lopputuloksena olivat toisiaan vastaavat energiaspektrit ja näytteen koostumuksesta kertova rekyylijakauma. Tut- kimuksen jälkeen energiaspektrien sovitus tehdään automaattisesti optimoinnin avulla.

(17)

3 Optimointiteoria

Optimointi on työkalu, jonka avulla voidaan ratkaista ongelmia, kun käytössä on rajattu mää- rä tietoa. Ongelma kuvataan yleensä tavoitefunktiona, joita voi olla yksi tai useampi. Nämä funktiot saavat minimi- tai maksimiarvonsa, kun tulos on paras mahdollinen, eli optimaali.

(Mosavi 2010) Tällaista optimointiongelman ratkaisemista, jossa tavoitefunktioita on useampi, kutsutaan monitavoittteiseksi optimoinniksi (Salmi 2008).

Monitavoitteisessa optimoinnissa tuloksena ei synny vain yhtä optimaalista ratkaisua, jos tavoitefunktiot ovat ristiriidassa. Nämä ratkaisut kertovat tavoitefunktioiden väliset kompro- missit (eng.tradeoff), eli miten yhden tavoitefunktion tuloksen parantaminen tekee muiden tavoitefunktioiden tuloksista huonompia kuin niiden optimaalinen tulos yksin tarkasteltuna olisi (Chase ym. 2009). Löytyneen ratkaisujoukon paremmuus selvitetään dominoinnin mukaan (Deb 2011):

Määritelmä 1.Ratkaisu x¹dominoi ratkaisua x², jos seuraavat väitteet pitävät paikkansa:

1. Ratkaisu x¹ei ole huonompi kuin ratkaisu x²minkään tavoitteen kohdalla.

2. Ratkaisu x¹on selvästi parempi kuin ratkaisu x²vähintään yhden tavoitteen kannalta.

Ratkaisuxⁱon siis vektori, joka koostuu tavoitefunktioille annettavista lähtöarvoista. Ratkai- sut muodostavat ratkaisuavaruuden, joka sisältää kaikki mahdolliset ratkaisut. (Deb 2011) Pareto-optimaalinen rintama sisältää kaikki ne ratkaisut ja niiden tavoitefunktioiden arvot, joita mikään muu ratkaisu ei dominoi (Chase ym. 2009). Kuvasta 4 (Deb 2011) nähdään eräät ratkaisut kuvattuna tavoitefunktioiden arvojen muodostamassa avaruudessa (a) ja niistä löytynyt Pareto-rintama (b).

Monitavoitteisten optimointiongelmien luonteesta johtuen pelkkä Pareto-rintaman etsiminen ei riitä hyvän ratkaisujoukon saamiseksi. Monitavoitteiselle optimoinnille onkin määritetty kaksi tavoitetta (Deb 2011; Goldenthal ja Bercovier 2004):

1. Etsi mahdollisimman monta ratkaisua, jotka kuuluvat Pareto-rintamaan, ja

2. Etsi ratkaisujoukko, joka on tarpeeksi monimuotoinen, jotta se voi edustaa Pareto- rintaman koko laajuutta (eng.range).

(18)

Kuva 4. Kuva (a): Ratkaisut on kuvattu tavoitefunktioiden (f_1 ja f_2) arvojen muodostamassa avaruudessa. Kuva (b): Ratkaisut 3, 5 ja 6 ovat sellaisia, joita mikään muu ratkaisu ei dominoi. Tällöin ei löydy toista ratkaisua, jolla vähintään yksi tavoitefunktion arvo on parempi, eikä toisen tavoitefunktion arvo ole huonompi.

Esimerkiksi evolutionaariset optimointialgoritmit sopivat monitavoitteisten optimointiongelmien ratkaisemiseen (Goldenthal ja Bercovier 2004; Deb 2011; Salmi 2008; Simon 2013).

Monitavoitteisia optimointiongelmia voidaan ratkaista myös muuntyylisillä menetelmillä.

Näitä ovat esimerkiksi heuristiset menetelmät ja monistrategiset menetelmät, joista jälkim- mäisessä yhdistetään useampia menetelmiä ja strategioita yhden sijasta (Esteco SpA 2019a).

modeFRONTIER-optimointiympäristöstä, jota käytetään tutkimuksen myöhemmässä vaiheessa, löytyy optimointialgoritmeja kaikista kolmesta kategoriasta. Lisäksi se tarjoaa gra- dienttiperustaisia ja adaptoituvia algoritmeja sekä mahdollisuuden määritellä ulkoisen optimointialgoritmin Matlab-, Scilab- tai GNU Octave -skriptin avulla (Esteco SpA 2019b).

Ne kuitenkin jätetään tarkastelun ulkopuolelle niiden huonon soveltuvuuden takia energiaspektrien sovittamisen ongelmaan. Seuraavaksi käsitellään tarjottuja optimointimenetelmiä tarkemmin. Algoritmien jaottelu perustuu modeFRONTIER-optimointiympäristössä olevaan jaotteluun.

(19)

3.1 Evolutionaariset algoritmit

Evolutionaariset optimointialgoritmit ovat ottaneet vaikutteita toimintaperiaatteisiinsa biologisesta evoluutiosta. Ne hyödyntävät ideoita lisääntymisestä, mutaatiosta ja rekombinaatios- ta. (Kokash 2014)

Näissä algoritmeissa pidetään tallessa ratkaisujoukkoa eli populaatiota eikä vain yhtä ratkaisua (Goldenthal ja Bercovier 2004). Tällöin useampi ratkaisu osallistuu uuden populaation muodostamiseen. Populaatioajattelu tekee prosessista rinnakkaisen, ja siten nopeuttaa lokaa- leista optimeista ja mahdottomista ratkaisuavaruuden alueista selviytymistä. (Deb 2011) Monet evolutionaariset algoritmit hyödyntävät ratkaisujoukon muodostamisessa aiemmin määriteltyä dominointia (Goldenthal ja Bercovier 2004; Deb 2011). Jos pääperiaatteena on käyttää ei-dominoituja ratkaisuja apuna muodostamaan uutta populaatiota (Deb 2011; Gol- denthal ja Bercovier 2004; Deb ym. 2002; Poles ym. 2007), viimeisessä sukupolvessa kaikki ratkaisut ovat ei-dominoituja (Goldenthal ja Bercovier 2004). Viimeisen sukupolven ratkaisut muodostavat lopullisen Pareto-rintaman.

Evolutionaarisia optimointialgoritmeja voidaan käyttää hyvinkin erilaisten optimointiongelmien ratkaisemiseen. Niitä on esimerkiksi käytetty avaruusaluksen lentoradan laskemiseen (Deb 2011), robottien optimointiin, neuroverkkojen opettamiseen sekä lääketieteelliseen diag- nosointiin (Simon 2013). Näiden käyttöä kannattaa siis harkita, kun kyseessä on monimut- kaisempi, useista muuttujista koostuva ongelma, jota ei välttämättä pysty ratkaisemaan perinteisin keinoin derivoimalla.

Tyypillisesti evolutionaarinen algoritmi koostuu seuraavista vaiheista: ensin luodaan alkupopulaatio ratkaisuehdokkaita esimerkiksi satunnaisesti, ja tämän jälkeen populaatiota päivite- tään iteroimalla. Päivittämiseen käytetään yleensä yhtä tai useampaa operaatiota: valintaa, risteytystä, mutaatiota ja/tai eliittien säilytystä. (Deb 2011) Valinnassa uuteen populaatioon otetaan mukaan paremmat ratkaisut, ja risteytyksessä uusia jälkeläisiä luodaan valitsemal- la kaksi ratkaisua ja vaihtamalla näiden kahden välillä tietoa. Mutaatio puolestaan muokkaa olemassa olevaa ratkaisua vain hieman, jotta uusi ratkaisu pysyy edellisen lähettyvillä, ja eliittien säilytyksessä valitaan parhaimmat ratkaisut edellisestä ja muokatusta populaatiosta uuteen populaatioon. (Deb 2011)

(20)

modeFRONTIER-optimointiympäristö tarjoaa neljä eri evolutionaarista optimointialgorit- mia hyödynnettäväksi. Nämä ovat MOGA-II, NSGA-II, ARMOGA ja evoluutiostrategia (ES, eng.Evolution Strategy) (Esteco SpA 2019b). Kolme ensimmäistä kuuluvat geneettisiin algoritmeihin, jotka ovat alaluokka evolutionaaristen algoritmien sisällä. Evolutionaa- risten ja geneettisten algoritmien luokittelussa löytyy pieniä eroja (Beyer ja Schwefel 2002) (kuten ratkaisunxⁱmuuttujien kuvaaminen reaaliluvuilla versus binäärijonoina (Arakawa ja Hagiwara 1998)), joihin tutkielmassa ei keskitytä tarkemmin. Evoluutiostrategia on toinen alaluokka evolutionaaristen algoritmien sisällä. On olemassa myös kolmas alaluokka, evolutionaarinen ohjelmointi (Beyer ja Schwefel 2002), mutta se on rajattu tutkielman ulkopuolelle.

3.1.1 MOGA-II

MOGA-II on paranneltu versio MOGA-algoritmista (eng. Multi-Objective Genetic Algo- rithm) (Poles ym. 2007; Poloni ja Pediroda 1998). Jokainen muuttuja kuvataan binäärijo- nona, jonka pituus riippuu muuttujan määrittelyvälistä. Erona MOGA-algoritmiin, MOGA- II-algoritmissa on myös mukana elitismi, joka suosii Pareto-rintaman lähellä olevia parhaim- min hajautuvia ratkaisuja. (Poles ym. 2007)

MOGA-II käyttää operaatioinaan klassista eli yhden kohdan risteytystä, suunnallista ristey- tystä, mutaatiota sekä valintaa. Näitä operaatioita käytetään uusien populaatioiden luomiseen. Jokaiseen senhetkisen populaation ratkaisuun sovelletaan jotakin operaatioista, ja näin saadaan uusia jälkeläisiä. (Poles ym. 2007)

Yhden kohdan risteytyksessä nykyinen ratkaisu on ensimmäinen vanhempi, ja toinen vanhempi valitaan monitavoitteisella turnausvalinnalla, joka palauttaa satunnaisesta populaation alijoukosta ensimmäisen ei-dominoidun ratkaisun. Näille kahdelle valitaan satunnaisesti jokin kohta, josta ne katkaistaan. Häntäosat vaihdetaan keskenään, ja toinen luoduista yksilöis- tä valitaan satunnaisesti uudeksi yksilöksi. (Poles ym. 2007)

Suunnallinen risteytys puolestaan olettaa, että vertaamalla kahden yksilön sopivuutta on mahdollista selvittää suunta, jossa ratkaisu paranee. MOGA-II-algoritmissa otetaan nykyinen yksilöija kaksi satunnaisesti valittua muuta, samaan populaatioon kuuluvaa yksilöä (j,

(21)

k), ja näitä käytetään luomaan uusi yksilö liikkumalla nykyisestä yksilöstä satunnaisesti pai- notettuun suuntaan. Painotetun suunnan tulee olla nykyisen yksilön ja kahden muun kanssa muodostetun suuntien välillä. (Poles ym. 2007) Tämä on variaatio evolutionaarisesta suun- nallisesta risteytyksestä, joka tuottaa parempia jälkeläisiä kuin klassinen risteytys (Yamamo- to ja Inoue 1995). Yksilöiden jja k valinnassa MOGA-algoritmin kohdalla on käytetty lo- kaalia turnausta ja satunnaisia askelia renkaanmallisessa (toroidisessa) verkossa: Nykyinen yksilö on aloituskohta, josta otetaan tietty määrä satunnaisia askelia. Saavutetuista yksilöis- tä muodostetaan ehdokasjoukko, josta parhaiten sopiva valitaan ykilöksi j. Sama prosessi toistetaan yksilönkluomiseksi. (Poles ym. 2007)

MOGA-II-algoritmin mutaatiossa määritellään muuttuja nimeltään DNA-merkkijonon mutaation suhde (eng.DNA String Mutation Ratio). Tämän avulla voidaan kontrolloida, kuinka suuri prosenttiosuus binäärijonosta muutetaan. Viimeisenä oleva valintaoperaatio yksinker- taisesti valitsee nykyisen yksilön uudeksi yksilöksi, joka lisätään uuteen populaatioon. (Poles ym. 2007)

3.1.2 NSGA-II

Kuten MOGA-II, NSGA-II (eng. Nondominated Sorting Genetic Algoritm) on paranneltu versio aikaisemmasta algoritmista. NSGA itsessään pyrkii jo pitämään yllä mahdollisimman monimuotoista ratkaisujoukkoa sekä konvergoitumaan eli suppenemaan kohti todelli- sen Pareto-rintaman aluetta (Srinivas ja Deb 1995; Deb ym. 2002).

NSGA-algoritmissa on kuitenkin puutteita: esimerkiksi ei-dominoitu lajittelu on laskennallisesti kompleksista ja siten kallista, geneettisen algoritmin nopeuttamiseen soveltuvaa elitis- miä ei ole, ja lisäksi käyttäjän on määriteltävä monimuotoisuuden ylläpitämiseen tarvittava erillinen jakoparametri, joka ei anna tilaa dynaamisuudelle (Deb ym. 2002). Näihin puuttei- siin vastataan NSGA-II-algoritmilla.

NSGA-II toimii siis elitistisellä periaatteella, siinä on tarkasti määritelty monimuotoisuuden säilyttämisjärjestelmä ja se painottaa ei-dominoituja ratkaisuja (Deb 2011). Kuten evo- lutionaarisissa ja geneettisissä algoritmeissa yleensä, NSGA-II alkaa satunnaisen kokoa N olevan alkupopulaation luonnilla, jota päivitetään iteroimalla. Päivitystä varten populaatio

(22)

lajitellaan ei-dominoinnin suhteen. Lajittelu auttaa säilyttämään sopivimmat ratkaisut. (Deb ym. 2002) Samankokoisen jälkeläisistä koostuvan populaation luomisessa käytetään geneet- tisiä operaatioita, jotk ovat esimerkiksi binäärinen turnausvalinta, rekombinaatio eli risteytys ja mutaatio. Seuraavaksi nykyinen populaatio ja jälkeläispopulaatio yhdistetään, jolloin saadaan uusi populaatio kokoa2N. (Deb 2011; Deb ym. 2002) Populaatioiden yhdistäminen tuo elitismin mukaan prosessiin.

Seuraavaksi yhdistetty populaatio lajitellaan ei-dominoinnin suhteen. Kun ollaan lajiteltu niin monta rintamaa, että niiden koko vastaa uuden populaation kokoa N, lajittelu voidaan lopettaa. Näin toimimalla säästytään koko yhdistetyn populaation lajittelulta, lajittelu nopeu- tuu ja siten myös laskennan kompleksisuus pienenee. (Deb ym. 2002)

NSGA-II käyttää nopeaa ei-dominoitua lajittelua, joka on selvä parannus tavalliseen versioon. Tavallisessa ei-dominoidussa lajittelussa yhden ratkaisun dominoinnin selvittämisek- si sitä pitää verrata jokaisen muun ratkaisun kanssa. Vertailua jatketaan muiden ratkaisujen kanssa, kunnes kaikki kyseisen rintaman ei-dominoidut ratkaisut on löydetty. Löydetyt ratkaisut laitetaan sivuun, ja jäljelle jäävistä ratkaisuista etsitään seuraava rintama. Pahimmas- sa tapauksessa rintamien muodostaminen voi olla kompleksisuudeltaanO(MN³), eli se voi vaatia näin monta laskua.Mon tavoitteiden määrä. (Deb ym. 2002)

Nopea ei-dominoitu lajittelu laskee jokaiselle ratkaisulle pdominointiluvun (kuinka monta ratkaisua dominoi ratkaisuap), ja ratkaisujoukonS_p, joka sisältää ne ratkaisut, joita ratkaisup dominoi. Ensimmäisen ei-dominoidun rintaman ratkaisujen dominointiluku on 0, ja jokaista ratkaisua kohti käydään läpi joukkoS_p, jonka jokaisen alkion dominointilukua pienennetään yhdellä. Ne alkiot, joiden dominointiluku menee nollaan, muodostavat toisen ei-dominoidun rintaman. Lajittelua jatketaan, kunnes kaikki rintamat on löydetty. Kompleksisuuden puoles- ta nopean lajittelun tulos onO(MN²). (Deb ym. 2002) Tämä on selvä parannus aiempaan tavalliseen lajitteluun.

Uuteen populaatioon halutaan yhdistetyn populaation parhaimmat ratkaisut, joten ei-dominoinnin suhteen lajittelun jälkeen yhdistetty populaatio on paremmuusjärjestyksessä. Uuteen populaatioon voidaan siis lisätä kaikki ei-dominoidut rintamat (eli niiden sisältämät ratkaisut), jotka mahtuvat kokonaisuudessaan uuteen populaatioon (Deb 2011; Deb ym. 2002).

(23)

Kaikkia ei-dominoituja rintamia ei voi kuitenkaan mahduttaa uuteen populaatioon, joten vii- meinen rintama, joka mahtuu osittain mukaan, pitää järjestää (Deb 2011).

Järjestämiseen, ja samalla populaation monimuotoisuuden takaamiseen NSGA-II käyttää ahtauden vertaamista. Sen määrittämiseen ei tarvita mitään käyttäjän erikseen määrittelemää muuttujaa (toisin kuin aiemmin mainittu jakoparametri NSGA-algoritmissa). Ahtauden ver- taamisoperaatiossa verrataan ensin ratkaisuja dominoinnin suhteen: suosittu ratkaisu on se, joka kuuluu parempaan eli järjestysluvultaan pienempään dominoinnin rintamaan. Jos molemmat ratkaisut kuuluvat samaan rintamaan, paremmuuden selvittämisessä käytetään ah- tausetäisyyttä (eng.crowding distance). Tällä arvioidaan ratkaisun etäisyyttä sen molemmil- la puolilla oleviin ratkaisuihin. Populaatio järjestetään vuorollaan jokaisen tavoitefunktion arvojen mukaan kasvassa järjestyksessä. Päiden ratkaisut saavat äärettömät etäisyyden arvot, ja muut ratkaisut niiden väliltä saavat etäisyysarvon niiden vierekkäisten ratkaisujen tavoitefunktioiden arvojen pohjalta.

Ratkaisun ahtausetäisyys on siis kaikille tavoitefunktioille laskettujen etäisyyksien summa.

(Deb ym. 2002) Suurempi ahtausetäisyys tarkoittaa, että ratkaisu on vähemmän ahtaassa paikassa, jolloin ratkaisu on parempi vaihtoehto kuin sellainen, jonka ahtausetäisyys on pienempi. (Deb 2011; Deb ym. 2002) Uuteen populaatioon valitaan parhaimmat ratkaisut täyttämään jäljellä olevat paikat, jolloin uudessa populaatiossa on tasan N ratkaisua (Deb ym. 2002).

Kun aloitetaan seuraavaa kierrosta uuden populaation luomiseksi, käytetään samoja geneetti- siä operaatioita kuten aiemmin. Binäärisessä turnausvalinnassa on kuitenkin muutos ensim- mäiseen sukupolveen nähden: valintakriteerinä on pelkän ei-dominoinnin sijasta ahtauden vertaamisoperaatio. (Deb ym. 2002)

3.1.3 ARMOGA

ARMOGA, kuten edellä käsitellyt MOGA-II ja NSGA-II, on myös paranneltu versio aiemmin kehitetystä algoritmista, tässä tapauksessa ARGA-algoritmista (eng. Adaptive Ran- ge Multi-Objective Genetic Algorithm) (Obayashi, Sasaki ja Oyama 2005; Sasaki ym. 2001;

Obayashi ja Sasaki 2004). ARGA-algoritmin pohjalla on algoritmi ARRangeGA (eng.Adap-

(24)

tive Real Range Genetic Algorithm) (Arakawa ja Hagiwara 1997). ARMOGA-, ARGA- ja ARRangeGA-algoritmeissa muuttujat ovat geneettisille algoritmeille tyypillisesti binääri- muodossa. (Arakawa ja Hagiwara 1998, 1997)

Kaikkien kolmen algoritmin periaatteena on se, että perinteisessä geneettisessä algoritmissa ratkaisun muodostavien muuttujien määrittelyväli pitää jakaa moneen diskreettiin arvoon, ja tämä on laskennallisesti raskasta. Seurauksena ratkaisujen laskemisen määrää pitää pie- nentää, johon ARGA on tehokas ratkaisu. (Arakawa ja Hagiwara 1998; Sasaki ym. 2001;

Obayashi ja Sasaki 2004) Algoritmissa käytetään muuttujien määrittelyvälin mukauttamista.

Väli mukautuu automaattisesti edelliselle populaatiolle laskettuihin keskiarvoon ja keskiha- jontaan perustuen. (Arakawa ja Hagiwara 1997, 1998) Joka M:s populaatio alustetaan uudelleen tätä käyttäen, jolloin uusi populaatio on lähempänä lupaavimpia ratkaisuavaruuden alueita (Obayashi, Sasaki ja Oyama 2005; Sasaki ym. 2001).

Populaation muuttujille lasketaan keskiarvo ja keskihajonta, jotka summattuna muodostavat koko populaation keskiarvon ja hajonnan. Näiden perusteella voidaan määrittää normitettu jakauma, joka näyttää määrittelyvälin tilanteen ja siten parhaiten sopivan välin kyseiselle populaatiolle. Seuraavan populaation muuttujien määrittelyväli riippuu edellisen populaation keskiarvosta. (Arakawa ja Hagiwara 1997, 1998)

ARGA-algoritmiin on lisätty ARRangeGA-algoritmin tarjoaman jatkuvien muuttujien kä- sittelyn lisäksi kokonaislukumuuttujien ja diskreettien muuttujien käsittely. Näissä tapauk- sissa määrittelyväli lasketaan myös edellisen populaation keskiarvon avulla, jota sitten hyö- dynnetään laskettaessa uusia rajoja. Rajojen laskemisen kaavoja käytetään binäärimuotoisen muuttujan muuttamiseen tarvittavaan muotoon eli kokonaisluvuksi tai diskreetiksi arvoksi.

(Arakawa ja Hagiwara 1997)

ARMOGA-algoritmissa mukaan tulee monitavoitteisuus, joten siinä pitää ottaa huomioon ratkaisujen monimuotoisuuden säilyttäminen. Ominaisuus on toteutettu muokkaamalla muuttujien määrittelyvälin mukautumisessa tarvittavaa jakaumaa (Obayashi, Sasaki ja Oyama 2005). Jakaumaa muutetaan seuraavasti: se jaetaan kolmeen osaan, joista reunaosien laskennassa käytetään tilanteeseen sopivaa ARGA-algoritmista perittyä käsittelymenetelmää, mutta keskimmäinen osa käsitellään perinteisellä binääriluvun muutoksella reaaliluvuksi.

(25)

(Sasaki ym. 2001)

ARMOGA-algoritmin hyviä puolia on se, että keskitetystä etsinnästä johtuen Pareto-optimaalisia ratkaisuja löydetään tehokkaasti. Lisäksi algoritmi estää konvergoitumisen saman- laisiin ratkaisuihin. Huonona puolena voidaan taas nähdä se, että lokaaleja minimejä voi olla vaikea välttää tietyissä tilanteissa. Toinen huono puoli on se, että populaation alustaminen uudelleen hidastaa prosessia. (Obayashi, Sasaki ja Oyama 2005)

3.1.4 Evoluutiostrategia

Evoluutiostrategia (ES) on osa evolutionaarisia algoritmeja. Siinä on samoja piirteitä geneettisten algoritmien kanssa, mutta se ei kuitenkaan ole geneettinen algoritmi: siitä puuttuu kromosomi- ja geeniajattelu (Arakawa ja Hagiwara 1998) sekä vanhempien valintaprosessi on erilainen verrattuna geneettisiin algoritmeihin (Beyer ja Schwefel 2002). Eroja ei käsitellä tutkielmassa tarkemmin. Evolutionaarisena algoritmina evoluutiostrategia kuitenkin sisältää geneettisiä operaatioita, tässä tapauksessa valinnan, rekombinaation ja mutaation (Beyer ja Schwefel 2002).

Yksinkertaisin evoluutiostrategian muoto on (1+1)-ES. Siinä populaatiosta valitaan vain yksi vanhempi, jota käytetään luomaan yksi jälkeläinen. Populaatioon otetaan mukaan jäljelle jäänyt vanha populaatio, ja valinta tehdään vanhemman ja jälkeläisen välillä siitä, kumpi lisä- tään uuteen populaatioon, ja kumpi hylätään. (Beyer ja Schwefel 2002) Evoluutiostrategias- ta on myös olemassa versio (µ + 1)-ES, jossaµ kuvaa potentiaalisten vanhempien määrää, joista valitaan kaksi: näiden avulla tuotetaan yksi jälkeläinen, ja uuteen populaatioon pääsee kahdesta vanhemmasta ja jälkeläisestä kaksi parhainta (Beyer ja Schwefel 2002).

Kun jälkeläisten määrä vapautetaan, saadaan kahta edellistä strategiaa yleisempi strategia:

(µ +λ)-ES. Tämä evoluutiostrategia käyttääµ-kokoista vanhempiehdokasjoukkoa, jota käy- tetään muodostamaan λ jälkeläistä, kun λ ≥ 1. Jotta populaation koko pysyisi samana, λ huonointa ratkaisuaµ +λ joukosta hylätään pois uudesta populaatiosta. (Beyer ja Schwefel 2002)

Toisenlainen variaatio evoluutiostrategiasta on (µ, λ)-ES. Strategiassa luodaan jälkeläiset samoin kuin edellä kuvatussa strategiassa, mutta valintaprosessissa on merkittävä ero: van-

(26)

hempiehdokasjoukko hylätään jo alkuvaiheessa, ja populaatio täydennetään vain lapsiyksi- löillä riippumatta siitä, kuinka hyviä tai huonoja vanhemmat ovat (Beyer ja Schwefel 2002).

(µ,λ)-ES luottaa siihen, että jälkeläisiä luodaan enemmän kuin vanhempiratkaisuja on, jotta populaation koko ei muuttuisi. Tämä on tiukan darwinistisen luonnollisen valinnan mukais- ta. (Beyer ja Schwefel 2002)

Evolutionaarisilla strategioilla populaation ratkaisuun liittyy ratkaisuvektorin xⁱ ja tavoite- funktioilla saavutettujen arvojen lisäksi endogeenisiä eli kehittyviä strategiaparametreja. Nä- mä parametrit vaikuttavat evoluutiostrategiassa käytettävien geneettisten operaatioiden eri- näisiin tilastollisiin ominaisuuksiin, erityisesti mutaatioon. Parametrit voivat siis kehittyä prosessin aikana. (Beyer ja Schwefel 2002)

Evoluutiostrategioissa on myös eksogeenisiä parametreja, jotka pysyvät staattisina prosessin aikana: näitä ovat jo aiemmin mainitut vanhempiehdokasjoukon kokoµ, jälkeläisten määrä λ ja sekoitusnumeroρ. Sekoitusnumero kertoo, kuinka monta vanhempaa käytetään yhden jälkeläisen luonnissa. (Beyer ja Schwefel 2002) Kunρ= 1, niin vanhempana on vain yksi ratkaisu, jolloin rekombinaatiota ei tapahdu, vaan jälkeläien on tämän vaiheen jälkeen vanhem- pansa kopio. modeFRONTIER-optimointiympäristön tarjoama versio evoluutiostrategiasta on tällainen versio (Esteco SpA 2019b).

Seuraavaksi esitellään yleinen algoritmi, jonka mukaan evolutionaariset strategiat toimivat.

Alussa luodaan satunnainen alku- eli vanhempipopulaatio, joka on kokoaµ. Vanhempipopu- laatiosta luodaan uusi, kokoaλ oleva populaatio ratkaisu kerrallaan: yhden ratkaisun luomiseksi ensin valitaan kokoaρ oleva vanhempiehdokasjoukko, jonka on täysin sattumanvarai- nen. Seuraavaksi tehdään endogeenisten strategiaparametrien rekombinaatio, jonka jälkeen mutatoidaan ensin endogeeniset strategiaparametrit ja sen jälkeen ratkaisuvektori. Ratkai- suvektorin avulla lasketaan tavoitefunktioiden arvot uudelleen. Kun jälkeläisä on luotu λ kappaletta, voidaan suorittaa valinta sopivuuden perusteella. (Beyer ja Schwefel 2002) Evoluutiostrategian algoritmi vastaa siis pääpiirteissään geneettisen algritmin muotoa. Erona ovat evoluutiostrategialle tyypilliset strategiaparametrit. (Beyer ja Schwefel 2002)

(27)

3.2 Heuristiset menetelmät

Heuristiset menetelmät pohjaavat heuristisiin algoritmeihin. Nämä ovat algoritmeja, jotka antavat ratkaisun ongelmaan, mutta ratkaisu ei välttämättä ole paras mahdollinen. Ratkaisu voi myös sopia vain osaan ongelman ilmentymiin, eli koko ongelmaa ei välttämättä ratkaista (Kokash 2014). modeFRONTIER-optimointiympäristö tarjoaa seuraavat tähän kategoriaan kuuluvat algoritmit: MOSA, MOGT ja MOPSO (Esteco SpA 2019b).

3.2.1 MOSA

MOSA-algoritmi (eng.Multi-Objective Simulated Annealing) on monitavoitteiset optimoi- tiongelmat huomioon ottava versio SA-algoritmista (Ulungu ym. 1999), jonka idea pohjautuu kemiallisten aineiden tai metallien jäähtymiseen hehkutuksen (eng. annealing) avulla (Ulungu ym. 1999; Simon 2013). Simuloitu hehkutus on geneerinen lokaalin etsinnän algoritmi, jossa ratkaisua etsittäessä sallitaan liikkeet myös sellaisiin ratkaisuihin, jotka eivät pa- ranna ratkaisua (Ulungu ym. 1999; Kokash 2014). Strategia valitaan sen takia, että algoritmi ei jumittuisi lokaaliin minimiin tai maksimiin, vaan pääsisi etsimään koko ratkaisuavaruuden alueelta parhainta tulosta (Ulungu ym. 1999).

Ratkaisun liikehdintää sallitaan vain algoritmin alussa, jolloin oikean elämän hehkutuksessa lämpötila on korkea, ja atomien liikkuvuus suurta. Kun lämpötilaa lasketaan, liike pienenee.

Vastaavasti simuloidussa hehkutuksessa lämpötilaan verrattavissa oleva parametri pienenee, jolloin ratkaisun hyväksymisestä tulee entistä valikoidumpaa. Lopussa hyväksytään vain pa- ranevat ratkaisut. (Ulungu ym. 1999; Simon 2013)

Simuloitu hehkutus eroaa evolutionaarisista algoritmeista siinä, että se ei hyödynnä populaa- tioajattelua, vaan käsittelee yhtä ratkaisua kerrallaan. Prosessi aloitetaan luomalla jokin ratkaisu, joka on ensimmäinen vertailukohta. (Simon 2013) Tässä vaiheessa määritellään myös simuloidulle hehkutukselle tyypilliset parametrit: alkuarvo lämpötilalle T (tai vaihtoehtoisesti ratkaisun hyväksymistodennäköisyydellep, johon palaan myöhemmin), lopettamiskri- teereinä olevat loppulämpötila ja ilman ratkaisun paranemista tehtävien iteraatioiden määrä.

(Ulungu ym. 1999) Lisäksi määritellään jäähtymiskerroinα (α < 1) ja lämpötila-askeleen pituus N_step jäähtymisaikataulussa (Ulungu ym. 1999), tai vaihtoehtoisesti koko jäähtymi-

(28)

saikataulun funktioα(T)(Simon 2013).

Iteraatiovaiheessa valitaan satunnaisesti uusi ratkaisuehdokas ja lasketaan sille tavoitefunktion arvo. Jos tavoitefunktion arvo on pienempi kuin edellisen ratkaisun, se päivitetään uudeksi ratkaisuksi. (Simon 2013) Ratkaisujen eroa voidaan mitata myös tavoitefunktioiden arvojen erotuksena: jos erotus on negatiivista, uusi ratkaisu hyväksytään. Jos erotus taas on positiivista, niin uudelle ratkaisuehdokkaalle määritellään todennäköisyys p, joka kertoo, millä todennäköisyydellä ratkaisuehdokas hyväksyttään uudeksi ratkaisuksi. Todennä- köisyyden laskennassa käytetään hyodyksi Boltzmannin jakaumaa ja senhetkistä lämpötilan arvoa. (Ulungu ym. 1999) Lämpötilaa muutetaan funktion tai kertoimen ja askeleen muutoksen mukaan joka iteraatiolla, kunnes lopetuskriteerit täyttyvät (Ulungu ym. 1999; Simon 2013).

Simuloidun hehkutuksen suoriutumiseen ja tulokseen kolme algoritmin osaa vaikuttavat mer- kittävästi: alkulämpötila, jäähtymisaikataulu ja uuden ratkaisuehdokkaan luomiseen käytet- ty menetelmä. Jos alkulämpötila on liian alhainen, ratkaisuavaruutta ei käydä tarpeeksi läpi, kun taas liian korkea alkulämpötila hidastaa algoritmin konvergenssia. (Simon 2013)

Jäähtymisaikataululla on samankaltainen rooli kuin alkulämpötilalla, eli sekin vaikuttaa kon- vergenssiin. On olemassa erilaisia funktioita, joita voidaan käyttää jäähdyttämiseen: Näistä yleisimmät ovat lineaarinen, eksponentiaalinen, käänteinen, logaritminen ja käänteinen lineaarinen jäähtyminen. (Simon 2013) Lineaarisen jäähtymisen kaava on seuraavanlainen:

α(T) =T₀−uk, (3.1)

jossa T₀ on alkulämpötila, u on vakio, ja k kertoo iteraation numeron. Eksponentiaalinen jäähtyminen, jota käyttävät myös Ulungu ym. (1999), määritellään seuraavasti:

α(T) =αT, (3.2)

jossaα on vakio (eli aiemmin mainittu jäähtymiskerroin) jaT senhetkinen lämpötila. Kään- teisen jäähtymisen kaava on seuraava:

α(T) = T

l+βT, (3.3)

jossaβ on vakio suuruusluokkaa 1·10⁻⁴. Logaritminen jäähtyminen kuvataan funktiolla α(T) = c

, (3.4)

(29)

jossacon vakio. Käänteinen lineaarinen jäähtyminen puolestaan määritellään seuraavasti:

α(T) =T₀

k . (3.5)

Ratkaisuehdokas voidaan valita täysin satunnaisesti, mutta se ei ole kovin tehokasta. Tehok- kuuden parantamiseksi suositaan nykyisen ratkaisun lähellä olevia ratkaisuja. Tätä varten etsitään joukko ratkaisuja, jotka ovat senhetkisen ratkaisun ympärillä, ja kyseisestä joukosta valitaan uusi ratkaisuehdokas (Ulungu ym. 1999).

Monitavoitteisessa simuloidussa hehkutuksessa toimitaan melkein samalla tavalla kuten yhden tavoitteen simuloidussa hehkutuksessa. Erona on, että uuden ratkaisun hyväksyminen muuttuu, sillä uuden ehdokkaan paremmuutta ei voi verrata vain yhden tavoitefunktion avulla. Lisäksi optimoinnin tuloksena ei tule ainoastaan yhtä mahdollisesti optimaalista ratkaisua, vaan joukko Pareto-optimaalisia ratkaisuja. (Ulungu ym. 1999)

Kun uuden ehdokkaan kaikkien tavoitefunktioiden arvot ovat parempia kuin edellisen (a), tai kun kaikki tavoitteet huononevat (b), voidaan käyttää samoja menettelytapoja kuten ennen- kin. Tilanteelle, jossa osa arvoista huononee ja osa taas paranee, pitää kehittää omanlaisensa lähestymistapa. Ulungu ym. (1999) käyttävät lähestymistapaa, jossa tilanne käsitellään joko tapauksen (a) tai (b) mukaan riippuen siitä, kuinka suuri ratkaisujen etäisyys on. Tätä kutsutaan kriteerien skaalaus -menetelmäksi.

Menetelmässä projisoidaan moniulotteiset tavoitefunktioiden arvojen etäisyydet yhdeksi yk- siulotteiseksi suoraksi, jonka jälkeen voidaan käyttää yksitavoitteisen version todennäköi- syyden laskemista. Projisoinnissa käytetään skaalausfunktiota, joka käyttää apunaan pai- nokerrointa λ. (Ulungu ym. 1999) On olemassa erilaisia skaalausfunktioita, joista Ulungu ym. (1999) käyttävät painotettua summaa. Sen voi määritellä seuraavasti:

s(Z,λ) =

K k=1

∑

λ_kz_k (3.6)

K

∑

k=1

λ_k=1,λ_k>0,∀k,

jossa K on tavoitefunktioiden arvojen määrä yhtä ratkaisua kohti ja Z on tavoitefunktioiden arvot yhtä ratkaisua kohti. Projisointiin käytetyllä menetelmällä ei ole kuitenkaan suurta vaikutusta lopputulokseen koko prosessin satunnaisuuden takia. (Ulungu ym. 1999)

(30)

3.2.2 MOGT

MOGT-algoritmi (eng. Multi-Objective Game Theory) perustuu peliteorian (Nash 1951) ja simplex-algoritmin (Nelder ja Mead 1965) yhdistelmään. Peliteoriat perustuvat siihen, että pelaajien tekemät valinnat pelin aikana vaikuttavat toisten pelaajien käyttäytymiseen ja ta- voitteisiin, kun jokainen pelaaja tavoittelee itselle suotuisinta lopputulosta (Greiner ym. 2017).

Peliteorioita on kahdenlaisia: yhteistyöllä toimivia ja kilpailupelejä. MOGT-algoritmin vuok- si keskitytään kilpailupeleihin, ja erityisesti versioon, jossa oleellisena osana on Nash-tasapaino (Clarich, Rigoni ja Poloni 2003; Greiner ym. 2017).

Tavoitefunktiot ja ratkaisuavaruus jaetaan pelaajien kesken (yksi tavoitefunktio per pelaaja), ja kukin pelaaja optimoi, tässä tapauksessa minimoi, omaa funktiotaan. Peliteorian mukaan toisten pelaajien tuottamat tulokset vaikuttavat muiden pelaajien tuloksiin. Pelaajat pelaavat yhtä aikaa, kunnes saavutetaan tasapaino: molemmat pelaajat ovat minimoineet funktionsa niin, että yksi arvo tulee omasta ratkaisuavaruuden osasta, ja loput muilta pelaajilta. Tasa- paino, nimeltään Nash-tasapaino, voidaan määrittää seuraavasti kahden pelaajan (A ja B) tapauksessa:

Määritelmä 2.(x^∗,y^∗)∈AxB on Nash-tasapainossa jos, ja vain jos:







f_A(x^∗,y^∗) =in f f_A(x,y^∗) x∈A f_B(x^∗,y^∗) =in f f_B(x^∗,y) x∈B.

(3.7)

Tasapainoon päädytään siis silloin, kun pelaajat eivät enää pysty parantamaan omaa tulos- taan. Nash-tasapainoon perustuviin peliteorioihin kuuluu myös se, että pelaajat eivät tee yh- teisiä, ryhmälle suotuisia päätöksiä, eivätkä pelaajat myöskään keskustele keskenään ennen pelin alkua. (Greiner ym. 2017)

Funktiot f_A ja f_B voivat olla myös sellaisia, joita ei pystytä minimoimaan perinteisin keinoin (derivoimalla), jolloin tarvitaan jokin muu keino. MOGT-algoritmi ottaakin tätä varten mukaan simplex-algoritmin (Clarich, Rigoni ja Poloni 2003).

Simplex-algoritmi (Nelder ja Mead 1965) on yksitavoitteinen optimointialgoritmi, joka toi-

(31)

tujien määrän. Algoritmin jokaisessa iteraatiossa huonoin ratkaisu xⁿ⁺¹ korvataan uudella ratkaisullaxⁿ⁺¹_N . Uusi ratkaisu saadaan projisoimallaxⁿ⁺¹ tasolleπ, joka muodostuu jäljelle jääneistä ratkaisuista (kokoan). Tasonπ yhtälö on seuraava:

π =a₁x₁+a₂x₂+...+a_nx_n+b=0. (3.8) Projisoitu piste voidaan määrittää vektorin x₀= (a₁,a₂, . . . ,a_n) avulla, joka kulkee tasoon π nähden kohtisuorassa. Tästä saadaan suora(x−xⁿ⁺¹) =λ₀x₀, joka kulkee ratkaisunxⁿ⁺¹ kautta ja on kohtisuorassa tasoon π nähden. Kun kerroin λ₀ kerrotaan kahdella, saadaan ratkaisu suoralta, joka kuuluu myös tasolleπ. Tällöin projisoitu piste on seuraava:

xⁿ⁺¹_N =xⁿ⁺¹+2λ₀x₀. (3.9)

Korvauksen jälkeen voidaan joko kasvattaa tai pienentää kerrointaλ₀ riippuen siitä, kuinka hyvä ratkaisusta tuli. Prosessia jatketaan niin kauan, kunnes saavutetaan haluttu määrä ite- raatioita tai algoritmi on konvergoitunut. Konvergoituminen tarkoittaa tässä tapauksessa sitä, että tietyn ratkaisujen välinen etäisyys on pienempää kuin jokin määritetty alaraja. (Clarich, Rigoni ja Poloni 2003)

MOGT-algoritmi alkaa siten, että määritetään kaksi tai enemmän pelaajaa, jotka jakavat tavoitefunktiot ja ratkaisuavaruuden keskenään. Pelaaja 1 minimoi funktiota f₁ ja pelaaja 2 funktiota f₂: pelaajalla 1 muuttuja x muuttuu, ja muuttujaa y kohdellaan vakiona, jolla on arvoy₀. Vastaavasti pelaajan 2 kohdalla muuttujaymuuttuu, ja muuttujaxon vakiox₀. Mo- lemmat pelaajat käyttävät simplex-algoritmia oman funktionsa optimoimiseen, jonka jälkeen kummallakin on senhetkinen paras ratkaisu omalle muuttujalleen. Tämän jälkeen pelaajat päivittävät toistensa vakioarvoja juuri löytämillään x:n ja y:n arvoilla, jonka jälkeen aloitetaan uusi simplex-ajo, jossa tarvittavat n+1 ratkaisua ovat edellisellä kierroksella löydetyt parhaimmat ratkaisut.(Clarich, Rigoni ja Poloni 2003)

Tulokseen vaikuttaa paljon se, kuinka ratkaisuavaruus on jaettu pelaajien kesken. MOGT-algoritmiin on lisätty vielä tilastollista analyysia Studentin t-testin muodossa, jonka pohjalta jakoa voidaan muuttaa dynaamisesti algoritmin ajon aikana riippuen siitä, kuinka tilastolli- sesti merkittäviä muuttujat ovat. (Clarich, Rigoni ja Poloni 2003)

(32)

Ennen uuden kierroksen alkua, jokaiselle muuttujalle lasketaan Studentin t-arvo (Vecchio 1997): Jokaista muuttujaa kohti jo lasketut ratkaisut jaetaan joukkoihin + ja -. Muuttujan eri arvot normitetaan välille [0, 1], ja alkupuolikkaan arvot kuuluvat joukkoon - ja loppupuo- likkaan joukkoon +. Kummallekin joukolle lasketaan keskiarvot tavoitefunktioiden arvoista, jolloin näiden erotus jaettuna keskiarvojen keskihajonnalla tuottaa etsityn t-arvon.

Jos t-arvo on korkea, todennäköisyys sille, että joukot + j - ovat erillisiä, on suuri. Muuttujan arvon muutos esimerkiksi matalasta arvosta suureen arvoon tuottaa merkittävän muutoksen tavoitefunktion arvoon. Kaikki pienen t-arvon saaneet muuttujat voidaan siten siirtää toiselle pelaajalle, koska niillä ei ole suurta vaikutusta tavoitefunktioon. (Clarich, Rigoni ja Poloni 2003)

3.2.3 MOPSO

MOPSO (eng.Multi-Objective Particel Swarm Optimization) on algoritmi, joka perustuu yk- sitavoitteiseen partikkeliparvialgoritmiin (PSO) (Eberhart, Shi ja Kennedy 2001; Coello ja Lechuga 2002; Coello, Pulido ja Lechuga 2004). PSO-algoritmi puolestaan perustuu parviä- lykkyyteen (Kokash 2014), ja sen pohjana on lintuparvien liikkeet (Coello ja Lechuga 2002;

Coello, Pulido ja Lechuga 2004).

PSO-algoritmissa käytetään populaatioita, joita parannetaan iteroimalla. Erotuksena evolutionaarisista algoritmeista, PSO-algoritmissa yksilöllä eli partikkelilla on muuttujien ja tavoitefunktion arvojen lisäksi nopeus, jolla se liikkuu ratkaisuavaruudessa. Partikkelilla on näiden lisäksi vielä hitaus eli inertia, jolloin ne pyrkivät pitämään senhetkisen nopeutensa.

(Simon 2013)

Prosessin aikana pyritään parantamaan yhteisen suorituksen lisäksi myös yksilösuorituksia.

Yksilösuoritusten parantamiseksi prosessissa pidetään yllä jokaisen partikkelin kohdalla sen parasta paikkaa, jossa se on aiemmin ollut: jokainen partikkeli siis muistaa, millä arvoilla sen tavoitefunktion tulos on ollut paras. (Simon 2013) Näin sallitaan partikkelin aikaisempien kokemusten hyödyntäminen populaatiossa olevan tiedon lisäksi (Coello, Pulido ja Lechuga 2004). Partikkelilla on tämän lisäksi tieto siitä, mitkä ovat olleet sen lähistöllä olevien muiden partikkelien parhaat paikat ratkaisuavaruudessa. Partikkelin oma paras paikka ja muiden

(33)

paikat vaikuttavat inertiasta huolimatta satunnaisesti partikkelin nopeuteen: partikkeli pyrkii takaisin parhaalle mahdolliselle paikalle. (Simon 2013)

Coello ja Lechuga (2002) kehittivät monitavoitteisen version PSO-algoritmista, jossa tuo- daan mukaan monitavoitteisuuden käsittely. Tähän käytetään MOPSO-algoritmissa ei-domi- nointiin perustuvaa partikkelien järjestämistä, jolloin ei-dominoidut populaation ratkaisut tallennetaan ulkoiseen muistiin, säiliöön, jota päivitetään iteroimalla. Säiliön lisäksi käy- tetään geografiaan perustuvaa hyperkuutiolähestymistapaa, jolla pyritään säilyttämään ratkaisujen monimuotoisuus. Hyperkuutiot muodostetaan jakamalla tavoitefunktioiden arvojen avaruus osiin, ja pitämällä yllä tietoa, mihin kuutioon säiliössä olevat partikkelit osuvat.

(Coello ja Lechuga 2002)

Hyperkuutioiden perusteella voidaan tietää, millä alueilla on enemmän partikkeleita kuin toisilla, eli kuinka tiheä alue on (Coello, Pulido ja Lechuga 2004). Päivityksen yhteydes- sä suositaan siis ei-dominoituja ratkaisuja ja vähemmän tiheällä alueella olevia ratkaisuja.

(Coello ja Lechuga 2002)

MOPSO-algoritmista on myös kehitetty paranneltu versio. Aikaisempaan versioon on lisätty rajoitteiden käsittely ja mutaatio-ominaisuus, joka huomattavasti parantaa ratkaisujen etsi- misen laajuutta. (Coello, Pulido ja Lechuga 2004)

Rajoitteet käsitellään seuraavasti: Kun on aika valita, mikä partikkeli säilytetään säiliös- sä, rajoitteet tarkistetaan. Jos molemmat partikkelit ovat mahdollisia, valinta tehdään ei- dominoinnin mukaan. Jos vain toinen partikkeli on mahdollinen, se hyväksytään. Kun molemmat partikkelit ovat mahdottomia, mukaan otetaan se, jonka rajoitteiden rikkomus on pienempi. (Coello, Pulido ja Lechuga 2004)

Mutaatio yrittää etsiä ratkaisuja kaikkien partikkelien kanssa etsinnän alussa. Tällöin etsintä- laajuus on suurempi kuin ennen, jolloin nopea konvergoituminen saattoi johtaa valheelliseen Pareto-rintamaan. Mutaation vaikutusta kuitekin pienennetään nopeasti alun jälkeen, jolloin mutatoituneiden partikkelien määrä putoaa. Operaatiolla vaikutetaan niin partikkeleihin kuin partikkelien muuttujien määrittelyväleihin, jolloin etsinnän laajuus on taattu. (Coello, Pulido ja Lechuga 2004)

(34)

MOPSO-algoritmin peruskulku pysyy samana parannuksista huolimatta. Seuraavaksi se käy- dään läpi. Ensin luodaan alkupopulaatio ja asetetaan partikkeleille alkunopeudet, jonka jäl- keen partikkelien tuottamat tavoitefunktioiden arvot lasketaan. Kaikki ei-dominoidut partikkelit tallennetaan säiliöön, ja luodaan hyperkuutiot, joihin säiliön partikkelit paikannetaan.

Jokainen partikkeli pitää yllä myös tietoa parhaimmasta paikastaan, joka alussa on tietysti alkuarvo. (Coello ja Lechuga 2002; Coello, Pulido ja Lechuga 2004)

Populaatiota päivitetään iteroimalla: Jokaiselle partikkelille lasketaan uusi nopeus, jonka perusteella partikkeli saa uuden paikan. Jos partikkeli menee yli sille määritettyjen rajojen jon- kin muuttujan suhteen, voidaan joko laittaa uudeksi arvoksi tämä raja, tai muuttaa muuttujan suuntaa kertomalla se luvulla -1. Seuraavaksi partikkelien tavoitteet lasketaan uudelleen, ja säiliön ja hyperkuutioiden tilanne päivitetään päivityksen perusteella. Kaikki ei-dominoidut partikkelit pääsevät säiliöön, ja kaikki dominoidut partikkelit otetaan ulos. Jos säiliö tulee täyteen ei-dominoituja partikkeleita, hyperkuutioiden avulla voidaan suosia vähemmän ti- heillä alueilla olevia partikkeleita. Lopuksi päivitetään partikkelin paras paikka, jos se on tarpeen, ja voidaan siirtyä seuraavaan iteraatioon. (Coello ja Lechuga 2002; Coello, Pulido ja Lechuga 2004)

Partikkelin nopeus lasketaan seuraavalla kaavalla:

V EL[i] =W·V EL[i] +R₁·(PBEST S[i]−POP[i]) +R₂·(REP[h]−POP[i]), (3.10) jossa W on hitauspaino (0,4), R₁ ja R₂ ovat satunnaisia lukuja väliltä [0,1].PBESTS[i] on partikkeliniparas paikka, jaPOP[i]on partikkelinisenhetkinen arvo.REP[h]on arvo, joka tulee säiliöstä, ja indeksih, joka vastaa jotakin hyperkuutiota, lasketaan seuraavasti: Kaikki hyperkuutiot, joissa on enemmän kuin yksi partikkeli, saavat sopivuusarvon, joka on sitä pienempi, mitä enemmän partikkeleita kuutio sisältää. Seuraavaksi valitaan kuutio, jolla on suuri sopivuusarvo ja sen sisältä satunnaisesti yksi partikkeli, joka antaa arvon muuttujalle REP[i]. (Coello ja Lechuga 2002; Coello, Pulido ja Lechuga 2004)

3.3 Monistrategiset algoritmit

modeFRONTIER-optimointiympäristön tarjoamat monistrategiset algoritmit yhdistävät use-

(35)

netelmät ovat seuraavat: MEGO, FAST, HYBRID, SAnGeA ja pilOPT (Esteco SpA 2019b).

MEGO (eng. Multi-Objective Efficient Global Optimization) soveltuu hyvin optimointion- gelmiin, joissa on paljon lokaaleja minimejä, sillä se etsii globaalia minimiä käyttäen hyö- dykseen automaattista kompromissia ratkaisuavaruuden tutkimisen ja konvergoitumisen vä- lillä (Esteco SpA 2019a). MEGO on surrogaattiavusteinen menetelmä, joka perustuu Gaus- sin prosesseihin. Se on vakaatilainen algoritmi, ja se saturoi kaikki saatavissa olevat säikeet.

Globaalin minimin etsintä perustuu täyttymiskriteerin täyttymiseen. (Esteco SpA 2019b) FAST-algoritmi puolestaan on suunniteltu konvergoitumaan nopeasti, jota varten se käyttää RSM-malleja eli vastauspintamalleja. (Esteco SpA 2019a, 2019b) FAST käyttää hyödykseen toista, sille sopivaa algoritmia, esimerkiksi MOGA-II- tai NSGA-II-algoritmia sekä valitsee automaattisesti parhaimman RSM-algoritmin (Esteco SpA 2019b). Tällä tavoin FAST-algoritmi voi keskittyä kaikista mielenkiintoisimman ratkaisuavaruuden osan tutkimiseen (Esteco SpA 2019a).

HYBRID on algoritmi, joka yhdistää geneettisten algoritmien robustisuuden ja gradienttimenetelmien tarkkuuden, jolloin saadaan mukaan myös geneettisten algoritmien globaalin etsinnän ja SQP-gradienttimenetelmien lokaalin etsinnän edut (Esteco SpA 2019a, 2019b).

HYBRID-algoritmissa käytetty SQP-ratkaisija on AFilterSQP, joka ratkaisee skaalattua ver- siota alkuperäisestä ongelmasta. Skaalattu versio on saatu parannetulla epsilon-rajoitetulla tekniikalla (Esteco SpA 2019b).

SAnGeA-algoritmi (eng. Screen Analysis Genetic Algorithm) yhdistää geneettisten algoritmien globaalia etsintää ja seulontamenetelmää, jolla saadaan selvitettyä tärkeimmät muuttujat (Esteco SpA 2019a, 2019b). Algoritmi sopii useamman tavoitteen optimointiongelmille, jotka ovat rajoittamattomia (Esteco SpA 2019a).

pilOPT käyttää hyväkseen useaa eri numeerista tutkimistrategiaa (Esteco SpA 2019a) ja yh- distää lokaalin ja globaalin etsinnän. Tämän jälkeen se muokkaa oikeita ja RSM-pohjaisia ratkaisuja niiden suoriutumisen perusteella (Esteco SpA 2019b). Näin se ottaa huomioon ajan ja laskennallisen tehon käyttämällä sisäistä muokkautuvaa algoritmistrategiaa (Esteco SpA 2019a).

(36)

4 modeFRONTIER-optimointiympäristö

modeFRONTIER on Esteco SpA -yrityksen tarjoama optimointiympäristö (Esteco SpA 2019a).

Sen toimintaperiaate perustuu käyttäjän rakentamiin työnkulkukaavioihin (eng. workflow), joita optimoidaan tarjotuilla, sisäänrakennetuilla optimointialgoritmeilla (Esteco SpA 2019b).

Tällöin testattavia algoritmeja ei tarvitse erikseen toteuttaa, vaan algoritmin vaihto onnistuu helposti modeFRONTIER-optimointiympäristön sisällä. Optimointiympäristön tarjoamien monitavoitteisten optimointialgoritmien teoria on esitelty luvussa 3.

modeFRONTIER luo ajon aikana tuloskansioon jokaista läpikäytyä 1 000 ratkaisuehdokasta kohden oman kansionsa: lisäksi näiden kansioiden alla on oma kansio jokaiselle ratkaisuehdokkaalle, ja jokaiselle yhden ratkaisun laskemista varten käytetylle skriptille. Kansioraken- ne mahdollistaa esimerkiksi eri ratkaisuihin liittyvien tulostiedostojen tarkastetelun. (Esteco SpA 2019b)

Kansiorakenne tarkoittaa myös sitä, että hakemisto, jossa skriptien suorittaminen tapahtuu, muuttuu jokaisen skriptin ja ratkaisun kohdalla (Esteco SpA 2019b). Tällä on merkittävä vai- kutus MCERD- ja get_espe-ohjelmien suorittamiseen, ja se on otettu huomioon Potku-ohjelman energiaspektrin vertaamista mallintavaa työnkulkukaaviota suunnitellessa. Potku ja siten myös MCERD- ja get_espe-ohjelmat olettavat, että siitä hakemistosta, jossa niitä suoritetaan, on tietynlainen kansiorakenne ympärillä mm. datatiedostoihin pääsyn osalta (Uni- versity of Jyväskylä 2018; Arstila 1999). Datatiedostot ja muut tarvittavat tiedostot pitää kopioida oikeille paikoilleen, jotta MCERD- ja get_espe-ohjelmien suoritus onnistuu.

modeFRONTIER-optimointiympäristön kansiorakenteen luomista ja tiedostojen kopiointia ei tarvitse huomioida Potku-ohjelman versiossa, sillä siellä ei tarvitse säilyttää jokaisen ratkaisuehdokkaan tietoja samalla tavalla. MCERD- ja get_espe-ohjelmien tarvitsemat kansio- rakenteet luodaan vain kerran Potku-ohjelman alustuksen yhteydessä, ja hakemisto, jossa ohjelmia suoritetaan, on sama. (University of Jyväskylä 2018)

Spektrien sovittamisessa tutkittavana tapauksena on fysiikan laitokselta käyttöön saatua tietoa näytteestä, jossa on piistä koostuva pohjakerros eli substraatti. Sen päälle on kasvatet-