| Summary: | 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.
|
|---|