Simuloidun jäähdytyksen suppenemislause

Abstract

Tämä pro gradu -tutkielma käsittelee simuloitu jäähdytys -nimisen kombinatorisen optimointimenetelmän teoriaa ja käytäntöä. Esimerkiksi kuvankäsittelyssä sovelletun algoritmin ideana on löytää annetulla joukolla määritellyn reaaliarvoisen energiafunktion globaali minimikohta sallimalla - ei pelkästään energiaa vähentäviä - vaan myös energiaa kasvattavia siirtymiä lähtöjoukon alkioiden välillä. Tilastolliseen fysiikkaan analogian omaavan, Gibbsin jakauman ominaisuuksiin pohjautuvan menetelm än matemaattisena perustana toimivat epähomogeeniset Markovin ketjut, joiden suppenemista tarkastellaan Dobrushinin kontraktiokerroinmenetelmän avulla.

Simuloidun jäähdytyksen suppenemislause, joka takaa epähomogeenisen Markov Chain Monte Carlo -ketjun suppenemisen minimienergiatilojen joukkoon, todistetaan aluksi Gibbs-otannan tapauksessa sekä deterministisille että satunnaisille päivitysjonoille. Tätä varten tehdään katsaus satunnaiskenttien, naapurustojärjestelmien, klikkien ja potentiaalien teoriaan.

Suppenemislause todistetaan myös yleisempiin tilanteisiin soveltuvan Metropolis-otannan tapauksessa. Metropolis-algoritmilla ajettavaa simuloitua jäähdytystä sovelletaan lopuksi konkreettiseen ongelmaan, jossa pyritään muodostamaan suorakulmion muotoiselle tenttisalille vilpin estämiseksi optimaalinen istumajärjestys. Simulointikokeiden yhteydessä pohditaan menetelmän käytännön soveltamiseen liittyvää problematiikkaa ja pohditaan lopuksi sitä, kuinka hyvin jäähdytys soveltuu tenttisaliongelman ratkaisemiseen.