Simuloidun jäähdytyksen suppenemislause
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.
...
Keywords
Metadata
Show full item recordCollections
- Pro gradu -tutkielmat [29684]
License
Related items
Showing items with similar title or keywords.
-
Markovin ketju Monte Carlo -simulointi ja Peskunin järjestys
Parkkinen, Santeri (2019)Tämän tutkielman tavoitteena on esitellä Markovin ketju Monte Carlo -simulointi äärellisessä tila-avaruudessa ja käsitellä simulointialgoritmien vertailuun liittyvää ongelmaa. Markovin ketju Monte Carlo -simuloinnissa ... -
Importance sampling type estimators based on approximate marginal Markov chain Monte Carlo
Vihola, Matti; Helske, Jouni; Franks, Jordan (Wiley-Blackwell, 2020)We consider importance sampling (IS) type weighted estimators based on Markov chain Monte Carlo (MCMC) targeting an approximate marginal of the target distribution. In the context of Bayesian latent variable models, the ... -
On resampling schemes for particle filters with weakly informative observations
Chopin, Nicolas; Singh, Sumeetpal S.; Soto, Tomás; Vihola, Matti (Institute of Mathematical Statistics, 2022)We consider particle filters with weakly informative observations (or ‘potentials’) relative to the latent state dynamics. The particular focus of this work is on particle filters to approximate time-discretisations of ... -
Reitinhakualgoritmien käyttö videopeleissä
Keränen, Emil (2018)Reitinhaku on sekä videopeleissä että tekoälyn ja robotiikan puolella hyvin tuttu ongelma. Sen tutkimiseen on käytetty viime vuosina paljon resursseja lisääntyneen tekoälykiinnostuksen vuoksi. Tässä tutkielmassa keskitytään ... -
Post-kvanttisalausten standardoinnin nykytilanne
Seppänen, Edvard (2024)Nykyisten salausmenetelmien turvallisuus on asetettu kyseenalaiseksi kvanttitietokoneiden kehityksen myötä. Vuonna 1994 Peter Shor kehitti algoritmin, joka kykenee murtamaan nykyiset salausmenetelmät riittävän tehokkaan ...