Comparative study of population-based metaheuristic methods in global optimization

Abstract

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.

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