Parviälykkyys lineaarisissa layout-ongelmissa
AUTIO, VILLE (2012)
2012
Tietojenkäsittelyoppi - Computer Science
Informaatiotieteiden yksikkö - School of Information Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2012-05-09
Julkaisun pysyvä osoite on
https://urn.fi/urn:nbn:fi:uta-1-22393
https://urn.fi/urn:nbn:fi:uta-1-22393
Tiivistelmä
Hiukkasparvioptimointi (particle swarm optimization, PSO) on suhteellisen tuore stokastinen, populaatiopohjainen optimointimenetelmä. Se on esittelynsä jälkeen kehittynyt nopeasti mielenkiintoiseksi menetelmäksi, jota on sovellettu useilla eri alueilla. Algoritmin ja sen piirteiden esittelyn jälkeen tässä työssä käytetään esimerkkitapauksena klassista kauppamatkustajan ongelmaa ja sen ratkaisemista PSO:lla yhdessä Lin-Kernighan-heuristiikan kanssa.
Varsinainen tutkimuskohde tässä työssä oli lineaarinen kahden sivun ris-teysluku -ongelma, joka kuuluu lineaaristen layout-ongelmien joukkoon. Nämä vaativuusluokkaan NP-kova kuuluvat ongelmat liittyvät graafiteoriaan ja niitä voidaan hyödyntää myös käytännön ongelmien ratkaisemisessa. Ongelmaan on kehitetty viime aikoina lukuisia eri ratkaisumenetelmiä, ja tässä työssä tutkitaan, miten PSO:n kaltaista yleistä optimointimenetelmää voidaan soveltaa kyseisen ongelman ratkaisemiseen. Tulokset eivät tuottaneet parannusta tunnettuihin menetelmiin verrattuna, mutta menetelmä osoittautui kuitenkin käyttökelpoiseksi. Permutaatioiden käsittelyyn soveltuvaa PSO-muunnelmaa myös paranneltiin kyseisen ongelman ratkaisuun paremmin soveltuvaksi.
Asiasanat:hiukkasparvioptimointi, kauppamatkustajan ongelma, paikallinen optimointi, lineaarinen kahden sivun risteysluku -ongelma, lineaarinen layout-ongelma
Varsinainen tutkimuskohde tässä työssä oli lineaarinen kahden sivun ris-teysluku -ongelma, joka kuuluu lineaaristen layout-ongelmien joukkoon. Nämä vaativuusluokkaan NP-kova kuuluvat ongelmat liittyvät graafiteoriaan ja niitä voidaan hyödyntää myös käytännön ongelmien ratkaisemisessa. Ongelmaan on kehitetty viime aikoina lukuisia eri ratkaisumenetelmiä, ja tässä työssä tutkitaan, miten PSO:n kaltaista yleistä optimointimenetelmää voidaan soveltaa kyseisen ongelman ratkaisemiseen. Tulokset eivät tuottaneet parannusta tunnettuihin menetelmiin verrattuna, mutta menetelmä osoittautui kuitenkin käyttökelpoiseksi. Permutaatioiden käsittelyyn soveltuvaa PSO-muunnelmaa myös paranneltiin kyseisen ongelman ratkaisuun paremmin soveltuvaksi.
Asiasanat:hiukkasparvioptimointi, kauppamatkustajan ongelma, paikallinen optimointi, lineaarinen kahden sivun risteysluku -ongelma, lineaarinen layout-ongelma