Comparative study of population-based metaheuristic methods in global optimization
T Peltonen · Jyväskylä University Digital Archive (University of Jyväskylä) · 2015
Vaikka 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.