Simuloitu jäähdytys penetraatioasteen optimoinnissa

Abstract

Selkäreppuongelma on yksi diskreeteistä kombinatorisista optimointiongelmista, joissa aika ei riitä tehtävän laajuudesta riippuen täydelliseen luettelointiin. Tällaisten tehtävien ratkaisemiseksi on kehitelty heuristisia ratkaisualgoritmeja. Tässä tutkielmassa perehdytään yhden selkäreppuongelman erikoistapaukseen penetraatioasteen laskemiseksi, sekä sen ratkaisuun kahdella approksimointimenetelmällä: parantavalla haulla sekä simuloidulla jäähdytyksellä. Lisäksi tutustutaan simuloitu jäähdytys -algoritmin konvergenssiin homogeenisessa ja epähomogeenisessa tapauksessa Markov-ketjujen avulla.

Simuloidussa jäähdytyksessä käytettävän jäähdytysohjelman optimaalista valintaa tarkastellaan kahdella eri aineistolla osin puhtaasti kokeilemalla ja osin teoriaan perustuen. Samalla tutkitaan simuloitu jäähdytys -algoritmin erilaisten rakenteiden, kuten pisteen naapuruston, aloituspisteen sekä Markov-ketjujen siirtymätavan valinnan vaikutuksia penetraatioasteeseen.

Simuloitu jäähdytys konvergoi teoriassa kohti globaalia optimiarvoa tietyin ehdoin, mutta käytännössä tätä konvergenssia voidaan vain approksimoida, jolloin algoritmin päätymistä globaaliin optimiarvoon ei voida taata, mutta sopivalla toteutuksella voidaan saada hyviä tuloksia. Algoritmin hyvä toteutus voi riippua käytettävästä aineistosta paljonkin. Tutkielmassa käytettyjen aineistojen valossa voidaan todeta algoritmissa käytetyn aloituspisteen tyypin vallitsevan tuloksia. Näkyvä vaikutus, mutta selvästi pienempi, oli myös jäähdytysohjelman valinnalla varsinkin suoritusaikoihin sekä naapuruston että Markov-ketjujen siirtymien valinnalla.