Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • Turun yliopisto
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
  •   Etusivu
  • Turun yliopisto
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit)
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Simuloitu jäähdytys penetraatioasteen optimoinnissa

Laulumaa, Juulia (2020-08-30)

 
Tweet refworks
 
Katso/Avaa
Laulumaa_Juulia_Pro_gradu_-tutkielma.pdf (1.226Mb)
Lataukset: 

avoin
Laulumaa, Juulia
30.08.2020
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
http://urn.fi/URN:NBN:fi-fe2020092976170
Tiivistelmä
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.
Kokoelmat
  • Pro gradu -tutkielmat ja diplomityöt sekä syventävien opintojen opinnäytetyöt (kokotekstit) [4439]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Lähetä palautetta | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Lähetä palautetta | Tietosuoja | Saavutettavuusseloste