Optimointi - mallintamista, matematiikkaa, geneettisiä algoritmeja

Virkaanastujaisesitelmä 16.11.1999, TKK

Harri Ehtamo

Historiaa

Princetonin yliopisto on tarunhohteinen paikka, ja erityisesti 40- ja 50-lukujen Princeton. J. Robert Oppenheimer toi mukanaan joukon nuoria fyysikoita Los Alamosista ja John von Neumann keräsi ympärilleen nuoria matemaatikkoja ja taloustieteilijöitä, jotka olivat sodan aikana palvelleet Yhdysvaltain ilmavoimissa ja laivastossa. Yhdessä he työskentelivät ajankohtaisten ongelmien kimpussa. Dick Feynman yleisti klassisen mekaniikan Hamiltonin periaatteen koskemaan myös kvanttimekaanisia prosesseja: Suurin vaikutus alkeishiukkasten välisessä vuorovaikutuksessa tulee klassisen minimin ympäristöstä.

Vuosisadan loistavat voitot teoreettisessa fysiikassa olivat kuitenkin johtaneet mahdollisen tulevaisuuden ydinsodan dilemmaan. Kuin ratkaisuksi tähän pulmaan oltiin alettu kehittää myös rationaalisten olentojen välisten vuorovaikutusten teoriaa. Von Neumann kuvasi tämän vuorovaikutuksen alkeistapauksia graafeilla samoin kuin Feynman kuvasi alkeishiukkasten välistä vuorovaikutusta. Syntyi peliteoria. Siinä, kun hiukkaset maksimoivat omaa, potentiaalienergian ja kineettisen energian välistä erotusta, rationaaliset pelaajat maksimoivat omaa, von Neumannin ja Morgensternin hyötyfunktiotaan, joka voidaan johtaa tekemällä muutamia uskottavia oletuksia pelaajien rationaalisesta käyttäytymisestä. Oscar Morgenstern oli John von Neumannin oppilas ja työtoveri. Yhdessä he kirjoittivat kirjan "Theory of Games and Economic Behavior", joka ilmestyi -44.

Samoihin aikoihin von Neumannin oppilas George B. Danzig loi lineaarisen optimointitehtävän, eli lineaarisen ohjelmoinnin tehtävän perusmallin. Tällaisia tehtäviä hän oli formuloinut jo Pentagonissa käsitellessään suuria tehtävien ajoitus-, resurssinjako- ja joukkojensiirto-ongelmia. Hän kirjoittaa: "Teimme pääasiallisen kehitystyön vuoden -46 lopussa ennen kuin tiesimme, että tietokone tulee toimimaan. Kun tietokone sitten toimi, siitä tuli jatkosuunnittelun, kehitystyön ja varsinaisen implementoinnin keskeinen suorittaja". Danzig oli kehittänyt tehtävän ratkaisemiseksi tietokonelaskentaan erityisen hyvin sopivan simplex-menetelmän, joka perustuu lineaarisen yhtälöryhmän eliminointimenettelyyn. Danzigin ryhmä menestyi niin hyvin, että se alkoi rahallisesti tukea tietokoneen kehitystä. 50-luvun alussa H.W. Kuhn ja A.W. Tucker kehittivät epälineaarisen optimoinnin peruskäsitteet tutkiessaan mikrotaloustieteen tasapainoteoriaa. Syntyi tieteen haara, jota kutsutaan operaatiotutkimukseksi, Operations Research.

Kuin ihmeen kaupalla tuohon tieteen pyhäkköön, Princetonin yliopistoon, saapasteli eräänä päivänä muuan mies "kaukaa maasta havumetsien". Suomen Pankin taloustieteellisessä tutkimuslaitoksessa pitkään toiminut talousmatemaatikko Henri Vartiainen opiskeli lukuvuoden 58-59 Asla-stipendiaattina Princetonissa kuunnellen Oscar Morgensternin ja George B. Danzigin luentoja. Kotiin tultuaan hän kirjoitti kolleegoilleen kaksi artikkelia: "Kruunaa ja klaavaa tieteellisesti eli katsaus peliteoriaan" ja "Lineaarisesta ohjelmoinnista ja simplex-menetelmästä".

1960-luvun alussa sovelletun matematiikan professori Olli Lokki aloitti operaatiotutkimuksen, erityisesti tilastotieteen, lineaarisen ohjelmoinnin ja peliteorian opetuksen Teknillisessä korkeakoulussa. Suomessa ensimmäisen väitöskirjan peliteoriasta teki Lokin ohjauksella hänen seuraajansa Raimo P. Hämäläinen 1976 aiheesta "Optimal Controller Design by Nonlinear and Game Theoretic Methods", joka oikeastaan edusti jo laskennallista optimointia ja peliteoriaa. Lineaarinen ohjelmointi puolestaan tunnetaan suomalaisessa teollisuudessa sangen hyvin professori Sampo Ruuthin pitkäaikaisen työn ansiosta.

Optimointimallin laatiminen

Minkälaisia ovat optimointimallit, kun puhutaan operaatiotutkimuksesta? Samalla valotan vähän operaatiotutkijan työnkuvaa. Tyypillinen esimerkki on tehtävä, jossa joukko resursseja on jaettava usealle eri aktiviteetille tai toimijalle. Resurssien käytöstä aiheutuva toiminta tuottaa tuloksen, jota halutaan maksimoida. Tämä on klassinen Danzigin ja kumppaneiden tutkima tehtävä, joka usein johtaa lineaariseen optimointimalliin.

Oletetaan, että kunkin aktiviteetin tuotto per sijoitettu resurssiyksikkö on satunnaismuuttuja. Tällöin maksimoimme tuloksen odotusarvoa. Voimme myös yrittää suojautua taloudelliselta riskiltä ja sijoittaa resurssit minimoimalla aktiviteettien tuoton heilahteluja. Tällöin saamme kvadraattisen mallin, jossa minimoitavana kohdefunktiona on tuoton varianssi. Usein kuitenkin vastaavassa tilanteessa emme halua pelkästään maksimoida voittoa tai minimoida riskiä vaan haluaisimme tehdä molempia. Miten tämä tehdään? Se tehdään maksimoimalla tuoton odotusarvon ja tuoton negatiivisen varianssin painotettua summaa. Erilaiset painokertoimet tuottavat erilaisia tehokkaita eli ns. Pareto optimaalisia ratkaisuja.

Olen kuvannut Markowitzin klassisen portfolion optimointitehtävän. Tämän tehtävän ratkaisu tietyllä painokertoimella antaa meille minimivarianssikorin. Olettakaamme, että itse hallitsemme resurssia, vaikkapa omaa kukkaroa, ja haluamme sijoittaa tietyn rahamäärän tiettyihin aktiviteetteihin, jotka muodostuvat esimerkiksi kasasta erilaisia arvopapereita.

Minimivarianssikorista tulee mieleen marjakori, jonka ostamme torilta. Siinä olevat marjat ovat makeita tai happamia. Sen saamme maistamalla selville. Sen sijaan marjojen haitta-ainemäärästä emme paljon tiedä; marjat ovat siis apulanta- tai luomuviljeltyjä tai siltä väliltä. Sijoittaessamme marjoihin tietyn määrän rahaa saamme tietyn elämänilon, mutta otamme myös tietyn riskin haitta-aineiden muodossa.

Arvopapereiden tapauksessa operaatiotutkija on etukäteen laskenut meille eri painokertoimisten korien odotetun tuoton ja riskin. Minkä korin siis valitsemme? Operaatiotutkijamme auttaa meitä myös tässä tehtävässä. Hän auttaa meitä tunnistamaan meidän ikioman von Neumannin ja Morgensternin hyötyfunktiomme. Esittämillään yksinkertaisilla kysymyksillä hän saa siitä sen oleellisen tiedon, jolla hän pystyy neuvomaan, mikä tehokas kori miellyttäisi nimenomaan meitä. Hän saattaisi kysyä esimerkiksi seuraavan tyyppisiä kysymyksiä. Oletetaan, että sinulla on kaksi vaihtoehtoa. Vaihtoehto A, saat osallistua ilmaiseksi arvontaan, jossa voitat fifty-fifty todennäköisyydellä 100 mk, tai vaihtoehto B, saat ilmaiseksi 50 mk. Kumman vaihtoehdon valitset? Useimmat meistä valitsisivat vaihtoehdon B, joka kertoisi tutkijallemme, että olemme riskin karttajia, ja että hyötyfunktiomme tällä kohtaa on kupera. Kysymällä lisää tämänkaltaisia kysymyksiä tutkijamme saa selville hyötyfunktiomme kuperuuden riskin suhteen. Tekemällä muutamia järkeviä oletuksia, esimerkiksi satunnaismuuttujien luonteesta, voidaan osoittaa, että hyötyfunktion kuperuusparametrilla ja portfoliotehtävän painokertoimella on yksi-yhteen vastaavuus. Näin ollen operaatiotutkijamme suosittelee meille sellaista koria, jota vastaava painokerroin vastaa meidän riskiasennettamme, ja jota vastaava sisältö maksimoi meidän hyötymme.

Kuten tiedämme sellaisiakin henkilöitä on, jotka ovat käytännössä hyvin sisäistäneet tähän tehtävään sopivan hyötyfunktionsa. Kun tällainen henkilö näkee yksinkertaisen kuvaajan tehokkaista portfolioista, eli siis tehokkaista tuoton odotusarvo-varianssi -pareista, hän pystyy välittömästi sanomaan, minkä korin hän valitsee. Meille muille operaatiotutkijan täytyy laatia riittävän selkeä esitys hyötyfunktiosta ja muista asiaan liittyvistä seikoista. Eikä tässä vielä kaikki. Tietenkin hän konsulttina on ensin miettinyt, mitä arvopapereita hän koriin pistää ja kuinka paljon. Kymmenen vai kymmenentuhatta. Tietenkin hän on valinnut sellaisia arvopapereita, joiden käyttäytymisestä hänellä on riittävästi historiatietoa ja joihin hän voi soveltaa Black-Scholes kaavaansa tai jotain sopivaa aikasarjaa laskeakseen niiden odotusarvot ja varianssit.

Tietoverkossa optimoiva konsultti

Entä mikä muu kuin raha voisi olla meidän resurssimme? Jos toimimme esimerkiksi sähkömarkkinoilla resurssimme on sähköä, joka tuotetaan vesivoimalla jossain Euroopan kolkassa ja jostain Euroopan kolkasta tulevalla maakaasulla ja hiilellä. Osa tuotannosta voi olla tuulivoimasta peräisin. Ja koska korissa on pitkän aikavälin sähköoptioita, operaatiotutkijan on laadittava meille resurssimalli, josta käy selville käytettävissämme olevan resurssin määrä ko. suunnittelujaksolla. Lisäksi mallin parametreja tulee päivittää, että se olisi sopivasti ajan tasalla.

Jokainen optimointitehtävä voidaan tulkita resurssinjakotehtävänä. Kääntäen, jokaista oikeaa resurssinjakotehtävää voidaan yleensä luontevasti analysoida optimointimallilla, vaikkei sellaisen rakentaminen sinänsä helppoa ole puhumattakaan sen ratkaisemisesta. Malleissa saattaa olla useita tuhansia muuttujia ja saman verran yhtälö- ja epäyhtälörajoituksia, jotka määrittelevät ns. käyvät allokaatiot tai vaihtoehdot. Tällaisia, jo klassisia resurssinjakotehtäviä ovat erityyppiset verkko- ja logistiikkatehtävät. Näissä resurssina voi olla ylläpidettävä verkko tai reitistö, verkkoa käyttävät asiakkaat, jne.

Erityisen mielenkiinnon kohteena tällä hetkellä ovat optimointimallit, jotka kuvaavat tietoliikenneverkkojen optimaalista käyttöä. Mannertenvälisen ATM-moniliikenneverkon tekninen toteutus johtaa jo sinänsä hierakkiseen- eli monitasoiseen optimointitehtävään, jonka eräs keskeinen ratkaisukäsite on peliteoreettinen Stackelbergin tasapaino. Moniliikenneverkon optimointimallit ovat siten laskennallista peliteoriaa. Lähitulevaisuudessa optimointiteoreetikon täytyy myös pystyä kopioimaan itsensä virtuaalitodellisuuteen, tietoverkossa toimivaksi optimointikonsultiksi. Optimoivia agentteja ja kaupankäynnin mediaattoreita käytetään kohta sähköisessä kaupankäynnissä webissä. Tällaisia asioita tutkitaan tällä hetkellä muun muassa TKK:n Systeemianalyysin laboratoriossa.

Edellä kuvaamiani tehtäviä voidaan mallintaa optimoinnilla, olettaen että tehtävät osataan ratkaista. Jos tehtävä on lineaarinen optimointitehtävä, jossa on noin muutama sata, ehkä muutama tuhat muuttujaa, voimme melko turvallisin mielin kääntyä simplex-menetelmän puoleen. Ratkaisu tulee luotettavasti ja nopeasti. Mutta entäs jos tehtävässä onkin epälineaarisia osia ja muuttujia onkin kymmeniä tuhansia? Ennen kuin ryntäämme sokeasti geneettisten optimointimenetelmien kimppuun kerron pienen tarinan, joka osoittaa, että matemaattisia malleja sovellettaessa on aina hyvä muistaa myös inhimillisen tekijän mukanaolo.

Suuressa toimistotalossa asiakkaat valittivat liian hitaita hissipalveluita. Rinnakkain toimivia hissejä oli useita, mutta odotushuoneet olivat aina täynnä. Niinpä operaatiotutkija suunnitteli uuden, optimointiin perustuvan hissien ajoitusjärjestelmän. Asiakkaitten valitukset vain pahenivat. Heitä hermostutti ja sekaannusta aiheutti sinne tänne liian nopeasti sinkoilevat hissit. Tämän jälkeen palattiin hitaaseen liikennöintiin, mutta talon vahtimestarin aloitteesta odotushuoneisiin asennettiin kokovartalopeilit. Ongelma poistui. Asiakkaat olivat tyytyväisiä ihaillessaan itseään peileistä ja vertaillessaan itseään toisiin asiakkaisiin.

Laskennan kompleksisuus

Mitä voimme sanoa optimointimallin ratkaisemisesta? Mitä voimme sanoa laskennan kompleksisuudesta? Laskentahan on, aina kompleksista. Näin hiljattain artikkelin, jossa hissien optimaalinen ajoitus tapahtui huippunopeasti reaaliajassa geneettisillä algoritmeilla. Tehtävässä oli kymmeniätuhansia muuttujia. Ennen kuin otamme kantaa näihin kysymyksiin luokaamme jälleen katsaus historiaan.

Hollantilainen optimointiteoreetikko G. Zoutendijk ihmettelee väitöskirjassaan 1960 suurten ja nopeiden tietokoneiden laskentatehoa: "Ne näyttävät selviytyvän helposti epälineaarisesta optimointitehtävästä, jossa on parikymmentäkin muuttujaa". Samaan aikaan eräs toinen matemaatikko, M. Powell, kuvailee optimointikokousta ja ihailee uusia laskenta-algoritmeja: "W. Davidonin keksintö muuttuvan metriikan menetelmä on täysin mullistanut optimoinnin. Ennen sitä kymmenen muuttujan funktion optimointi oli työlästä. Nykyään 100:n muuttujan funktio voidaan minimoida muutamassa sekunnissa". Tästä Davidonin keksinnöstä käytetään nykyään nimitystä sekanttimenetelmä tai kvasi-Newtonin menetelmä. Se on miltei kaikkien analyyttisten algoritmien perusosa.

Vuonna -84 professori Luenberger Stanfordista jakoi optimointitehtävät silloisen laskentakyvyn mukaan. Pienessä tehtävässä muuttujia ja rajoituksia on 1-5, keskisuuressa niitä on noin 5-100, ja suuressa 100-1000, jopa muutamia tuhansia. Tänä päivänä nuo luvut voidaan kertoa sadalla. Tietokoneiden teho on sellaista luokkaa, että 1960-luvulla kehitetyt loistavat analyyttiset menetelmät pääsevät täysin oikeuksiinsa.

Näitä epälineaariseen optimointiin tarkoitettuja menetelmiä ovat erilaiset sakko- ja estefunktiomenetelmät, eli ns. ulko- ja sisäpistemenetelmät sekä erilaiset käypien suuntien menetelmät. Kaikissa näissä menetelmissä varsinainen iterointi tapahtuu jollain sekanttimenetelmällä. Nykyään jopa lineaarinen tehtävä muutetaan ensin epälineaariseksi, jolloin rajoitukset otetaan huomioon sopivalla estefunktiolla, ja tehtävä ratkotaan sitten sekanttimenetelmällä. Laskennan kompleksisuusanalyysi kertoo nyt, että hyvin suurilla tehtävillä sisäpistemenetelmä toimii nopeammin kuin simplex-menetelmä. Käytäntö on vahvistanut tämän havainnon.

Entä, kun laskentateho vielä kasvaa? Löytyykö menetelmiä, löytyykö tehtäviä? Suuren lentoyhtiön lentokoneiden reititysongelmassa voi olla miljoonia muuttujia. Tilastollisesti tämän tyyppisillä, monesti epälineaarisilla jättitehtävillä on paljon "kyllin hyviä" paikallisia optimeja. Ratkaisuksi riittää, että löydämme niistä yhden. Samaan tehtäväluokkaan kuuluvat myös erityyppiset suuret, epälineaariset pienimmän neliösumman tehtävät, kuten neuroverkkojen opettamiseen liittyvät tehtävät. Näitä on suhteellisen helppo ratkoa ns. heuristisilla optimointimenetelmillä. Esimerkiksi luonnon evoluutiota matkiva geneettinen algoritmi tai tilastollisen fysiikan menetelmiä matkiva simuloitu jäähdytys sopivat erityisen hyvin. Jos aikaa on, esimerkiksi geneettinen algoritmi tuottaa siihen rakennetun mutaation ansiosta pikku hiljaa aina vähän parempia optimeja.

Tehtävien koon ja laskentamenetelmien suhteen loppua ei siis näy niin kauan kuin tietokoneet kehittyvät. Optimointimenetelmiä on helppo muokata rinnakkaislaskentaan sopiviksi, mutta pullonkaulaksi voi muodostua viestinvälitys eri laskentatehtävien välillä. Rajoja tulee vastaan myös hyvin yllättäviltä suunnilta. Uusin tutkimus on kiinnittänyt erityisesti huomiota ns. keskisuuriin tehtäviin. Näitä on kaikissa tehtäväluokissa ja niitä on erityisen vaikea ratkoa millään tietyllä menetelmällä. Usein näillä tehtävillä on paljon likimäärin yhtä hyviä paikallisia optimeja, mutta vain yksi selvästi toisia parempi globaali optimi. Sen löytäminen on hyvin työlästä; tarvitaan uutta analyyttistä ajattelua. Tilanne on samantapainen kuin laskennallisessa fysiikassa. Muutaman kappaleen kvanttimekaniikka samoin kuin suurten systeemien tilastollinen fysiikka on laskennallisesti helppoa. Sen sijaan keskisuuret systeemit ovat haastavimpia - mutta myös sovellutusten kannalta hedelmällisimpiä.

Optimoinnin opettaminen

Miten sitten vihkiä opiskelijat optimoinnin saloihin? Yllättävää kyllä, tämä voidaan tehdä parin kuvan avulla. Optimointiopin kurssilla pidän huolen siitä, että nämä kuvat painuvat opiskelijoiden sydämiin.

Optimointiopin perustehtävä on määrätä pisteen etäisyys annetusta joukosta, ja karakterisoida tämä etäisyys näiden välistä kulkevan suoran avulla; ks. kuva 1.

Kuva 1.

Ratkaisu: Siirretään suora joukon tangentiksi sellaiseen kohtaan, jossa pisteestä piirretty jana on kohtisuorassa tangenttia vastaan. Optimoinnissa tästä havainnosta seuraa mm. koko Lagrangen kertoimien teoria.

Duaalisuus optimoinnissa tarkoittaa seuraavaa: Tämä tehtävä voidaan ratkaista myös laskemalla kohtisuora etäisyys kaikkiin välistä kulkeviin suoriin ja ottamalla näistä maksimi. Laskennan kannalta kyseessä on ulkopistemenetelmä. Sisäpistemenetelmässä ratkaisu haetaan joukon sisältä käsin esimerkiksi sekanttimenetelmää käyttäen; ks. kuva 2.

Kuva 2.

Entä geneettinen algoritmi? Oletetaan, että optimoitavana on jokin funktio, jolla on paljon paikallisia maksimeja. Kromosomipopulaatio on kerääntynyt erään maksimin ympärille. Äkkiä eräs kromosomi hyppää mutaation ansiosta rikki menneestä kananmunasta etsiskelemään parempaa maksimia.

Näin on asianlaita opetuksessa ja tutkimuksessakin. Vaikka ryhmätyö tuottaakin tulosta, jonkun ennakkoluulottoman yksilön täytyy aina välillä hypätä aidan yli nuuhkimaan uusia ideoita ja parempia viheriöitä.