Show simple item record

dc.contributor.advisorNeri, Ferrante
dc.contributor.advisorKoskinen, Pekka
dc.contributor.authorPeltonen, Teemu
dc.date.accessioned2015-06-08T12:12:20Z
dc.date.available2015-06-08T12:12:20Z
dc.date.issued2015
dc.identifier.otheroai:jykdok.linneanet.fi:1475431
dc.identifier.urihttps://jyx.jyu.fi/handle/123456789/46236
dc.description.abstractVaikka globaalit optimointiongelmat ovat hyvin yleisiä laskennallisen nanotieteen alalla, ne ovat myös laskennallisesti erittäin vaativia ongelmia, joille tehokkaita ja yleisiä ratkaisualgoritmeja ei ole saatavilla. Tässä työssä teen yleiskatsauksen algoritmeihin, joiden tavoitteena on olla juuri tällaisia yleisiä menetelmiä, joita voi soveltaa tehokkaasti mihin ongelmaan tahansa. Rajoittuessani niin kutsuttuihin populaatiopohjaisiin metaheuristiikkoihin, erityisesti luonnosta ideansa saaneisiin evolutiivisiin algoritmeihin ja parviälyyn, tutkin niiden kyvykkyyttä ratkaista eräs vaikea todellisen maailman ongelma, Lennard-Jones-atomiryppään rakenneongelma. Käytän lisäksi yhtä algoritmeista, CCPSO2:ta, Lennard-Jones ongelman separoituvuusanalyysiin eli siihen, kuinka hyvin kyseisen ongelman voi ratkaista jakamalla se pienempiin osaongelmiin. Lennard-Jones-ongelman tutkiminen 200 atomiin asti osoittaa, että kyseiset menetelmät voivat olla hämmästyttävän tehokkaita optimoijia jopa korkeadimensioisissa todellisen maailman ongelmissa. Erityisesti yksi menetelmistä, CCPSO2, kykenee arvioimaan Lennard-Jones-atomiryppäiden globaaleja minimejä 10–20 % virheellä dimensiosta riippumatta, ja vieläpä todella vähällä määrällä raskaita energiafunktiokutsuja. Näytän lisäksi, että nämä menetelmät ovat ylivoimaisia verrattuna kahteen simuloidun jäähdytyksen versioon. Simuloitu jäähdytys on fyysikoiden keskuudessa suosittu luokka globaalin optimoinnin ratkaisualgoritmeja. Käyttämällä CCPSO2:ta jakamaan Lennard-Jones-ongelma pienempiin, dimensioiltaan erikokoisiin osaongelmiin, näytän että tehokkain tapa ratkaista kyseinen ongelma on jakaa se erittäin pieniin 4–12 dimension osaongelmiin riippumatta ongelman dimensiosta. Tämä on merkittävä tulos, sillä jako näin pieniin ongelmiin helpottaa vaikean Lennard-Jones-ongelman ratkaisua merkittävästi, ja se toimii suuntaviivana kyseiselle ongelmalle vieläkin tehokkaampia algoritmeja kehittäville tutkijoille.fi
dc.description.abstractWhile global optimization problems are very common when working in computational nanoscience, they also constitute a set of computationally very demanding problems that lack efficient all-round optimizers. In this thesis I do a small survey on algorithms that try to be exactly like this; general methods that can be applied to any problem off the shelf. Constraining myself to so-called population-based metaheuristics, especially Nature-inspired evolutionary algorithms and swarm intelligence, I study their capabilities of solving a difficult real-world optimization problem, the Lennard-Jones cluster structure problem. I also use one of the algorithms, CCPSO2, to study the Lennard-Jones problem's separability, that is, how well it can be solved by dividing the problem into smaller subproblems. An analysis on the Lennard-Jones problem of up to 200 atoms shows that these methods can be surprisingly efficient optimizers even in high-dimensional real-world problems. Especially one algorithm, namely CCPSO2, provides quite good and robust approximations for the global minima of the Lennard-Jones clusters with an error of around 10–20 %, and all that with a very small number of heavy energy function evaluations. I also show that they are superior to two versions of simulated annealing algorithms, a popular class of global optimization methods among physicists. By using CCPSO2 to divide the Lennard-Jones problem into smaller pieces of different dimensionalities, I show that the most efficient way to solve it is to divide the problem into subproblems of only 4–12 dimensions, regardless of the problem dimension. This is a remarkable result since this division dramatically decreases the difficulty of the Lennard-Jones problem and it serves as a guide for people trying to develop even more efficient algorithms for this problem.en
dc.format.extent1 verkkoaineisto (68s.)
dc.format.mimetypeapplication/pdf
dc.language.isoeng
dc.rightsJulkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.fi
dc.rightsThis publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.en
dc.subject.othermetaheuristiikka
dc.titleComparative study of population-based metaheuristic methods in global optimization
dc.identifier.urnURN:NBN:fi:jyu-201506082229
dc.type.ontasotPro gradu -tutkielmafi
dc.type.ontasotMaster’s thesisen
dc.contributor.tiedekuntaMatemaattis-luonnontieteellinen tiedekuntafi
dc.contributor.tiedekuntaFaculty of Sciencesen
dc.contributor.laitosFysiikan laitosfi
dc.contributor.laitosDepartment of Physicsen
dc.contributor.yliopistoUniversity of Jyväskyläen
dc.contributor.yliopistoJyväskylän yliopistofi
dc.contributor.oppiaineTeoreettinen fysiikkafi
dc.contributor.oppiaineTheoretical Physicsen
dc.date.updated2015-06-08T12:12:21Z
dc.rights.accesslevelopenAccessfi
dc.type.publicationmasterThesis
dc.contributor.oppiainekoodi4024
dc.subject.ysooptimointi
dc.subject.ysoalgoritmit
dc.format.contentfulltext
dc.type.okmG2


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record