Luonnon innoittamat metaheuristiikat
Rantala, Daniel (2023-06-09)
Luonnon innoittamat metaheuristiikat
(09.06.2023)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2023061454939
https://urn.fi/URN:NBN:fi-fe2023061454939
Tiivistelmä
Metaheuristiset menetelmät näyttäytyvät lupaavilta ratkaisumalleilta, joiden avulla voidaan nopeuttaa optimointia ja säästää resursseja. Luonto on monimuotoisuutensa ansiosta täynnä tehokkaita menetelmiä, jotka tarjoavat kattavan kirjon mahdollisuuksia optimointimenetelmien kehittämiseksi.
Tämän tutkielman tarkoitus on perehdyttää lukija kolmeen tunnettuun luonnon innoittamaan metaheuristiseen menetelmään: kiiltomatoalgoritmi, simuloitu jäähdytys ja geneettinen algoritmi. Kiiltomatoalgoritmi ja geneettinen algoritmi edustavat populaatiopohjaisia metaheuristiikoita ja simuloitu jäähdytys puolestaan on kehityskaaripohjainen metaheuristinen menetelmä. Menetelmien matemaattinen toimintaperiaate on vielä varsin keskeneräinen ja tämän tutkimuksen tavoitteena onkin luoda suomenkielinen pohja metaheuristiikoiden matemaattiseksi ymmärtämiseksi. Lisäksi tarkastellaan metaheuristiikoiden soveltuvuutta diskreettien optimointitehtävien ratkaisemiseen.
Metaheuristiikoiden nopea konvergoituminen kohti optimia näyttäytyy mahdollisuutena toimia ongelmaitsenäisenä ratkaisumenetelmänä, minkä takia metaheurististen menetelmien ja niiden sovellutusten tutkimus on ollut kiivasta. Lupaavista ominaisuuksistaan huolimatta metaheuristiikat eivät kuitenkaan toimi ongelmasta riippumatta parhaalla mahdollisella tavalla, vaikka ne siihen pyrkivätkin.
Tämän tutkielman tarkoitus on perehdyttää lukija kolmeen tunnettuun luonnon innoittamaan metaheuristiseen menetelmään: kiiltomatoalgoritmi, simuloitu jäähdytys ja geneettinen algoritmi. Kiiltomatoalgoritmi ja geneettinen algoritmi edustavat populaatiopohjaisia metaheuristiikoita ja simuloitu jäähdytys puolestaan on kehityskaaripohjainen metaheuristinen menetelmä. Menetelmien matemaattinen toimintaperiaate on vielä varsin keskeneräinen ja tämän tutkimuksen tavoitteena onkin luoda suomenkielinen pohja metaheuristiikoiden matemaattiseksi ymmärtämiseksi. Lisäksi tarkastellaan metaheuristiikoiden soveltuvuutta diskreettien optimointitehtävien ratkaisemiseen.
Metaheuristiikoiden nopea konvergoituminen kohti optimia näyttäytyy mahdollisuutena toimia ongelmaitsenäisenä ratkaisumenetelmänä, minkä takia metaheurististen menetelmien ja niiden sovellutusten tutkimus on ollut kiivasta. Lupaavista ominaisuuksistaan huolimatta metaheuristiikat eivät kuitenkaan toimi ongelmasta riippumatta parhaalla mahdollisella tavalla, vaikka ne siihen pyrkivätkin.