Populaation monimuotoisuuden mittaaminen liukulukukoodatuissa evoluutioalgoritmeissa

Abstract

Diplomityössä esitetään menetelmä populaation monimuotoisuuden mittaamiseen liukulukukoodatuissa evoluutioalgoritmeissa, ja tarkastellaan kokeellisesti sen toimintaa. Evoluutioalgoritmit ovat populaatiopohjaisia menetelmiä, joilla pyritään ratkaisemaan optimointiongelmia. Evoluutioalgoritmeissa populaation monimuotoisuuden hallinta on välttämätöntä, jotta suoritettu haku olisi riittävän luotettavaa ja toisaalta riittävän nopeaa. Monimuotoisuuden mittaaminen on erityisen tarpeellista tutkittaessa evoluutioalgoritmien dynaamista käyttäytymistä.

Työssä tarkastellaan haku- ja tavoitefunktioavaruuden monimuotoisuuden mittaamista. Toistaiseksi ei ole ollut olemassa täysin tyydyttäviä monimuotoisuuden mittareita, ja työn tavoitteena on kehittää yleiskäyttöinen menetelmä liukulukukoodattujen evoluutioalgoritmien suhteellisen ja absoluuttisen monimuotoisuuden mittaamiseen hakuavaruudessa. Kehitettyjen mittareiden toimintaa ja käyttökelpoisuutta tarkastellaan kokeellisesti ratkaisemalla optimointiongelmia differentiaalievoluutioalgoritmilla.

Toteutettujen mittareiden toiminta perustuu keskihajontojen laskemiseen populaatiosta. Keskihajonnoille suoritetaan skaalaus, joko alkupopulaation tai nykyisen populaation suhteen, riippuen lasketaanko absoluuttista vai suhteellista monimuotoisuutta. Kokeellisessa tarkastelussa havaittiin kehitetyt mittarit toimiviksi ja käyttökelpoisiksi. Tavoitefunktion venyttäminen koordinaattiakseleiden suunnassa ei vaikuta mittarin toimintaan. Myöskään tavoitefunktion kiertäminen koordinaatistossa ei vaikuta mittareiden tuloksiin. Esitetyn menetelmän aikakompleksisuus riippuu lineaarisesti populaation koosta, ja mittarin toiminta on siten nopeaa suuriakin populaatioita käytettäessä. Suhteellinen monimuotoisuus antaa vertailukelpoisia tuloksia riippumatta parametrien lukumäärästä tai populaation koosta.

In this thesis a new method for population diversity measurement for floating point encoded evolutionary algorithms is developed and tested experimentally. Evolutionary algorithms are population-based methods, which are used for solving optimization problems. In evolutionary algorithms it is necessary to control population diversity, to assure that search is reliable and on the other hand fast enough. Population diversity measurement is especially necessary when the dynamical behavior of an evolutionary algorithm is studied.

Population diversity measurement was considered in search and objective function spaces. So far there has not been fully satisfactory indicator for population diversity. The goal in this thesis is to develop a general method for population diversity measurement in floating point encoded evolutionary algorithms. Functionality and usability of developed indicators are considered experimentally by solving optimization problems with a differential evolution algorithm.

The developed indicators operate by calculating the standard deviations of the population. The standard deviations are then scaled regarding initial or current population, depending whether absolute or relative diversity is calculated. By experimental consideration the developed indicators were found functional and useful. Stretching of objective function in the direction of coordinate axes does not affect the operation of the indicator. Rotating of the objective function does not affect the results of the indicator. Time complexity of the developed method depends linearly on the population size, thus the operation of the indicator is fast even with large populations. Relative diversity gives comparable results regardless of number of dimensions or population size.