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ä...

Full description

Bibliographic Details
Main Author: Luoto, Antti
Other Authors: Matemaattis-luonnontieteellinen tiedekunta, Faculty of Sciences, Matematiikan ja tilastotieteen laitos, Department of Mathematics and Statistics, University of Jyväskylä, Jyväskylän yliopisto
Format: Master's thesis
Language:fin
Published: 2013
Subjects:
Online Access: https://jyx.jyu.fi/handle/123456789/42193
_version_ 1826225696889896960
author Luoto, Antti
author2 Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics University of Jyväskylä Jyväskylän yliopisto
author_facet Luoto, Antti Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics University of Jyväskylä Jyväskylän yliopisto Luoto, Antti Matemaattis-luonnontieteellinen tiedekunta Faculty of Sciences Matematiikan ja tilastotieteen laitos Department of Mathematics and Statistics University of Jyväskylä Jyväskylän yliopisto
author_sort Luoto, Antti
datasource_str_mv jyx
description 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.
first_indexed 2024-09-11T08:52:07Z
format Pro gradu
free_online_boolean 1
fullrecord [{"key": "dc.contributor.author", "value": "Luoto, Antti", "language": null, "element": "contributor", "qualifier": "author", "schema": "dc"}, {"key": "dc.date.accessioned", "value": "2013-09-20T09:11:37Z", "language": null, "element": "date", "qualifier": "accessioned", "schema": "dc"}, {"key": "dc.date.available", "value": "2013-09-20T09:11:37Z", "language": null, "element": "date", "qualifier": "available", "schema": "dc"}, {"key": "dc.date.issued", "value": "2013", "language": null, "element": "date", "qualifier": "issued", "schema": "dc"}, {"key": "dc.identifier.other", "value": "oai:jykdok.linneanet.fi:1280453", "language": null, "element": "identifier", "qualifier": "other", "schema": "dc"}, {"key": "dc.identifier.uri", "value": "https://jyx.jyu.fi/handle/123456789/42193", "language": null, "element": "identifier", "qualifier": "uri", "schema": "dc"}, {"key": "dc.description.abstract", "value": "T\u00e4m\u00e4 pro gradu -tutkielma k\u00e4sittelee simuloitu j\u00e4\u00e4hdytys -nimisen kombinatorisen\noptimointimenetelm\u00e4n teoriaa ja k\u00e4yt\u00e4nt\u00f6\u00e4. Esimerkiksi kuvank\u00e4sittelyss\u00e4 sovelletun\nalgoritmin ideana on l\u00f6yt\u00e4\u00e4 annetulla joukolla m\u00e4\u00e4ritellyn reaaliarvoisen energiafunktion\nglobaali minimikohta sallimalla - ei pelk\u00e4st\u00e4\u00e4n energiaa v\u00e4hent\u00e4vi\u00e4 -\nvaan my\u00f6s energiaa kasvattavia siirtymi\u00e4 l\u00e4ht\u00f6joukon alkioiden v\u00e4lill\u00e4. Tilastolliseen\nfysiikkaan analogian omaavan, Gibbsin jakauman ominaisuuksiin pohjautuvan menetelm\n\u00e4n matemaattisena perustana toimivat ep\u00e4homogeeniset Markovin ketjut, joiden\nsuppenemista tarkastellaan Dobrushinin kontraktiokerroinmenetelm\u00e4n avulla.\n\nSimuloidun j\u00e4\u00e4hdytyksen suppenemislause, joka takaa ep\u00e4homogeenisen Markov\nChain Monte Carlo -ketjun suppenemisen minimienergiatilojen joukkoon, todistetaan\naluksi Gibbs-otannan tapauksessa sek\u00e4 deterministisille ett\u00e4 satunnaisille p\u00e4ivitysjonoille.\nT\u00e4t\u00e4 varten tehd\u00e4\u00e4n katsaus satunnaiskenttien, naapurustoj\u00e4rjestelmien, klikkien\nja potentiaalien teoriaan.\n\nSuppenemislause todistetaan my\u00f6s yleisempiin tilanteisiin soveltuvan Metropolis-otannan\ntapauksessa. Metropolis-algoritmilla ajettavaa simuloitua j\u00e4\u00e4hdytyst\u00e4 sovelletaan\nlopuksi konkreettiseen ongelmaan, jossa pyrit\u00e4\u00e4n muodostamaan suorakulmion\nmuotoiselle tenttisalille vilpin est\u00e4miseksi optimaalinen istumaj\u00e4rjestys. Simulointikokeiden\nyhteydess\u00e4 pohditaan menetelm\u00e4n k\u00e4yt\u00e4nn\u00f6n soveltamiseen liittyv\u00e4\u00e4 problematiikkaa\nja pohditaan lopuksi sit\u00e4, kuinka hyvin j\u00e4\u00e4hdytys soveltuu tenttisaliongelman\nratkaisemiseen.", "language": "fi", "element": "description", "qualifier": "abstract", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted using Plone Publishing form by Antti Luoto (ankaluot) on 2013-09-20 09:11:37.058375. Form: Pro gradu -lomake (1 tekij\u00e4) (https://kirjasto.jyu.fi/julkaisut/julkaisulomakkeet/pro-gradu-lomake-1-tekijae). JyX data:", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Submitted by jyx lomake-julkaisija (jyx-julkaisija@noreply.fi) on 2013-09-20T09:11:37Z\nNo. of bitstreams: 2\nURN:NBN:fi:jyu-201309202331.pdf: 854682 bytes, checksum: 7c5eaeab16e46df3a2f39b7fc48824c9 (MD5)\nlicense.html: 107 bytes, checksum: a7d86e598caa500b1b433bbb9dc8ef1c (MD5)", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.description.provenance", "value": "Made available in DSpace on 2013-09-20T09:11:37Z (GMT). No. of bitstreams: 2\nURN:NBN:fi:jyu-201309202331.pdf: 854682 bytes, checksum: 7c5eaeab16e46df3a2f39b7fc48824c9 (MD5)\nlicense.html: 107 bytes, checksum: a7d86e598caa500b1b433bbb9dc8ef1c (MD5)\n Previous issue date: 2013", "language": "en", "element": "description", "qualifier": "provenance", "schema": "dc"}, {"key": "dc.format.extent", "value": "1 verkkoaineisto.", "language": null, "element": "format", "qualifier": "extent", "schema": "dc"}, {"key": "dc.language.iso", "value": "fin", "language": null, "element": "language", "qualifier": "iso", "schema": "dc"}, {"key": "dc.rights", "value": "In Copyright", "language": "en", "element": "rights", "qualifier": null, "schema": "dc"}, {"key": "dc.subject.other", "value": "Gibbs-otanta", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "ep\u00e4homogeeninen Markovin ketju", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "Metropolis-algoritmi", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "satunnaiskentt\u00e4", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.subject.other", "value": "simuloitu j\u00e4\u00e4hdytys", "language": "", "element": "subject", "qualifier": "other", "schema": "dc"}, {"key": "dc.title", "value": "Simuloidun j\u00e4\u00e4hdytyksen suppenemislause", "language": null, "element": "title", "qualifier": null, "schema": "dc"}, {"key": "dc.type", "value": "master thesis", "language": null, "element": "type", "qualifier": null, "schema": "dc"}, {"key": "dc.identifier.urn", "value": "URN:NBN:fi:jyu-201309202331", "language": null, "element": "identifier", "qualifier": "urn", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Pro gradu", "language": "fi", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.type.ontasot", "value": "Master's thesis", "language": "en", "element": "type", "qualifier": "ontasot", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Matemaattis-luonnontieteellinen tiedekunta", "language": "fi", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.faculty", "value": "Faculty of Sciences", "language": "en", "element": "contributor", "qualifier": "faculty", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Matematiikan ja tilastotieteen laitos", "language": "fi", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.department", "value": "Department of Mathematics and Statistics", "language": "en", "element": "contributor", "qualifier": "department", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "University of Jyv\u00e4skyl\u00e4", "language": "en", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.contributor.organization", "value": "Jyv\u00e4skyl\u00e4n yliopisto", "language": "fi", "element": "contributor", "qualifier": "organization", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Matematiikka", "language": "fi", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.subject.discipline", "value": "Mathematics", "language": "en", "element": "subject", "qualifier": "discipline", "schema": "dc"}, {"key": "dc.date.updated", "value": "2013-09-20T09:11:37Z", "language": null, "element": "date", "qualifier": "updated", "schema": "dc"}, {"key": "dc.type.coar", "value": "http://purl.org/coar/resource_type/c_bdcc", "language": null, "element": "type", "qualifier": "coar", "schema": "dc"}, {"key": "dc.rights.accesslevel", "value": "openAccess", "language": "fi", "element": "rights", "qualifier": "accesslevel", "schema": "dc"}, {"key": "dc.type.publication", "value": "masterThesis", "language": null, "element": "type", "qualifier": "publication", "schema": "dc"}, {"key": "dc.subject.oppiainekoodi", "value": "4041", "language": null, "element": "subject", "qualifier": "oppiainekoodi", "schema": "dc"}, {"key": "dc.subject.yso", "value": "optimointi", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.subject.yso", "value": "algoritmit", "language": null, "element": "subject", "qualifier": "yso", "schema": "dc"}, {"key": "dc.rights.url", "value": "https://rightsstatements.org/page/InC/1.0/", "language": null, "element": "rights", "qualifier": "url", "schema": "dc"}]
id jyx.123456789_42193
language fin
last_indexed 2025-02-18T10:56:45Z
main_date 2013-01-01T00:00:00Z
main_date_str 2013
online_boolean 1
online_urls_str_mv {"url":"https:\/\/jyx.jyu.fi\/bitstreams\/39c2ccb7-2bbb-4c17-8f41-f8e1357fc177\/download","text":"URN:NBN:fi:jyu-201309202331.pdf","source":"jyx","mediaType":"application\/pdf"}
publishDate 2013
record_format qdc
source_str_mv jyx
spellingShingle Luoto, Antti Simuloidun jäähdytyksen suppenemislause Gibbs-otanta epähomogeeninen Markovin ketju Metropolis-algoritmi satunnaiskenttä simuloitu jäähdytys Matematiikka Mathematics 4041 optimointi algoritmit
title Simuloidun jäähdytyksen suppenemislause
title_full Simuloidun jäähdytyksen suppenemislause
title_fullStr Simuloidun jäähdytyksen suppenemislause Simuloidun jäähdytyksen suppenemislause
title_full_unstemmed Simuloidun jäähdytyksen suppenemislause Simuloidun jäähdytyksen suppenemislause
title_short Simuloidun jäähdytyksen suppenemislause
title_sort simuloidun jäähdytyksen suppenemislause
title_txtP Simuloidun jäähdytyksen suppenemislause
topic Gibbs-otanta epähomogeeninen Markovin ketju Metropolis-algoritmi satunnaiskenttä simuloitu jäähdytys Matematiikka Mathematics 4041 optimointi algoritmit
topic_facet 4041 Gibbs-otanta Matematiikka Mathematics Metropolis-algoritmi algoritmit epähomogeeninen Markovin ketju optimointi satunnaiskenttä simuloitu jäähdytys
url https://jyx.jyu.fi/handle/123456789/42193 http://www.urn.fi/URN:NBN:fi:jyu-201309202331
work_keys_str_mv AT luotoantti simuloidunjäähdytyksensuppenemislause