The development of some rotationally invariant population based optimization methods
Date
2013-03
Authors
Ras, Marthinus Nicolaas
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: In this study we consider the lack of rotational invariance of three different population based optimization
methods, namely the particle swarm optimization (PSO) algorithm, the differential evolution
(DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then propose
rotationally invariant versions of these algorithms.
We start with the PSO. The so-called classical PSO algorithmis known to be variant under rotation,
whereas the linear PSO is rotationally invariant. This invariance however, comes at the cost of lack
of diversity, which renders the linear PSO inferior to the classical PSO.
The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm that
aims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochastic
sense only. What is more, the formulation depends on the introduction of a random rotation
matrix S, but invariance is only guaranteed for ‘small’ rotations in S. Herein, we propose a formulation
which is diverse and strictly invariant under rotation, if still in a stochastic sense only. To
do so, we depart with the linear PSO, and then we add a self-scaling random vector with a standard
normal distribution, sampled uniformly from the surface of a n-dimensional unit sphere.
For the DE algorithm, we show that the classic DE/rand/1/bin algorithm, which uses constant
mutation and standard crossover, is rotationally variant. We then study a previously proposed
rotationally invariant DE formulation in which the crossover operation takes place in an orthogonal
base constructed using Gramm-Schmidt orthogonalization.
We propose two new formulations by firstly considering a very simple rotationally invariant formulation
using constant mutation and whole arithmetic crossover. This rudimentary formulation
performs badly, due to lack of diversity. We then introduce diversity into the formulation using two
distinctly different strategies. The first adjusts the crossover step by perturbing the direction of the
linear combination between the target vector and the mutant vector. This formulation is invariant
in a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmetic
crossover vector. This formulation is strictly invariant, if still in a stochastic sense only. In this study we consider the lack of rotational invariance of three different population based optimization
methods, namely the particle swarm optimization (PSO) algorithm, the differential evolution
(DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then propose
rotationally invariant versions of these algorithms.
We start with the PSO. The so-called classical PSO algorithmis known to be variant under rotation,
whereas the linear PSO is rotationally invariant. This invariance however, comes at the cost of lack
of diversity, which renders the linear PSO inferior to the classical PSO.
The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm that
aims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochastic
sense only. What is more, the formulation depends on the introduction of a random rotation
matrix S, but invariance is only guaranteed for ‘small’ rotations in S. Herein, we propose a formulation
which is diverse and strictly invariant under rotation, if still in a stochastic sense only. To
do so, we depart with the linear PSO, and then we add a self-scaling random vector with a standard
normal distribution, sampled uniformly from the surface of a n-dimensional unit sphere.
For the DE algorithm, we show that the classic DE/rand/1/bin algorithm, which uses constant
mutation and standard crossover, is rotationally variant. We then study a previously proposed
rotationally invariant DE formulation in which the crossover operation takes place in an orthogonal
base constructed using Gramm-Schmidt orthogonalization.
We propose two new formulations by firstly considering a very simple rotationally invariant formulation
using constant mutation and whole arithmetic crossover. This rudimentary formulation
performs badly, due to lack of diversity. We then introduce diversity into the formulation using two
distinctly different strategies. The first adjusts the crossover step by perturbing the direction of the
linear combination between the target vector and the mutant vector. This formulation is invariant
in a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmetic
crossover vector. This formulation is strictly invariant, if still in a stochastic sense only. For the CPGA we show that a standard CPGA using blend crossover and standard mutation, is rotationally
variant. To construct a rotationally invariant CPGA it is possible to modify the crossover
operation to be rotationally invariant. This however, again results in loss of diversity. We introduce
diversity in two ways: firstly using a modified mutation scheme, and secondly, following the same
approach as in the PSO and the DE, by adding a self-scaling random vector to the offspring vector.
This formulation is strictly invariant, albeit still in a stochastic sense only.
Numerical results are presented for the variant and invariant versions of the respective algorithms.
The intention of this study is not the contribution of yet another competitive and/or superior population based algorithm, but rather to present formulations that are both diverse and invariant, in the
hope that this will stimulate additional future contributions, since rotational invariance in general
is a desirable, salient feature for an optimization algorithm.
AFRIKAANSE OPSOMMING: In hierdie studie bestudeer ons die gebrek aan rotasionele invariansie van drie verskillende populasiegebaseerde optimeringsmetodes, met name die partikel-swerm optimerings (PSO) algoritme, die differensi¨ele evolusie (DE) algoritme en die kontinue-parameter genetiese algoritme (KPGA). Ons stel dan rotasionele invariante weergawes van hierdie algoritmes voor. Ons beginmet die PSO. Die sogenaamde klassieke PSO algoritme is bekend dat dit variant is onder rotasie, terwyl die lineˆere PSO rotasioneel invariant is. Hierdie invariansie lei tot ’n gebrek aan diversiteit in die algoritme, wat beteken dat die lineˆere PSO minder goed presteer as die klassieke PSO. Die voorheen voorgestelde sogenaamde diverse rotasionele invariante (DRI) PSO is ’n algoritme wat beoog om beide diversiteit en invariansie te kombineer. Hierdie algoritme is slegs rotasioneel invariant in ’n stogastiese sin. Boonop is die formulering afhanklik van ’n willekeurige rotasie matriks S, maar invariansie is net gewaarborg vir ’klein’ rotasies in S. In hierdie studie stel ons ’n formulering voor wat divers is en streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. In hierdie formulering, vertrek ons met die lineˆere PSO, en voeg dan ’n self-skalerende ewekansige vektor met ’n standaard normaalverdeling by, wat eenvormig van die oppervlakte van ’n n-dimensionele eenheid sfeer geneem word. Vir die DE algoritme toon ons aan dat die klassieke DE/rand/1/bin algoritme, wat gebruik maak van konstante mutasie en standaard kruising rotasioneel variant is. Ons bestudeer dan ’n voorheen voorgestelde rotasionele invarianteDE formulering waarin die kruisingsoperasie plaasvind in ’n ortogonale basis wat gekonstrueer wordmet behulp van die Gramm-Schmidt ortogonalieseringsproses. Verder stel ons dan twee nuwe formulerings voor deur eerstens ’n baie eenvoudige rotasionele invariante formulering te oorweeg, wat konstante mutasie en volledige rekenkundige kruising gebruik. Hierdie elementˆere formulering onderpresteer as gevolg van die afwesigheid van diversiteit. Ons voeg dan diversiteit by die formulering toe, deur gebruik te maak van twee afsonderlike strategie ¨e. Die eerste verander die kruisings stap deur die rigting van die lineˆere kombinasie tussen die teiken vektor en die mutasie vektor te perturbeer. Hierdie formulering is slegs invariant in ’n stogastiese sin. In die ander formulering, soos met die nuwe rotasionele invariante PSO, voeg ons bloot ’n self-skalerende ewekansige vektor by die onveranderde volledige rekenkundige kruisingsvektor. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Vir die KPGA wys ons dat die standaard KPGA wat gemengde kruising en standaard mutasies gebruik, rotasioneel variant is. Om ’n rotasionele invariante KPGA te konstrueer is dit moontlik om die kruisingsoperasie aan te pas. Dit veroorsaak weereens ’n verlies aan diversiteit. Ons maak die algoritmes divers op twee verskillende maniere: eerstens deur gebruik te maak van ’n gewysigde mutasie skema, en tweedens deur die selfde aanslag te gebruik as in die PSO en die DE, deur ’n self-skalerende ewekansige vektor by die nageslag vektor te voeg. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Numeriese resultate word vir die variante en invariante weergawe van die onderskeie algoritmes verskaf. Die doel van hierdie studie is nie die bydrae van bloot nog ’n kompeterend en/of beter populasiegebaseerde optimeringsmetode nie, maar eerder om formulerings voor te lê wat beide divers en invariant is, met die hoop dat dit in die toekoms bykomende bydraes sal stimuleer, omdat rotasionele invariansie in die algemeen ’n aantreklike, belangrike kenmerk is vir ’n optimerings algoritme.
AFRIKAANSE OPSOMMING: In hierdie studie bestudeer ons die gebrek aan rotasionele invariansie van drie verskillende populasiegebaseerde optimeringsmetodes, met name die partikel-swerm optimerings (PSO) algoritme, die differensi¨ele evolusie (DE) algoritme en die kontinue-parameter genetiese algoritme (KPGA). Ons stel dan rotasionele invariante weergawes van hierdie algoritmes voor. Ons beginmet die PSO. Die sogenaamde klassieke PSO algoritme is bekend dat dit variant is onder rotasie, terwyl die lineˆere PSO rotasioneel invariant is. Hierdie invariansie lei tot ’n gebrek aan diversiteit in die algoritme, wat beteken dat die lineˆere PSO minder goed presteer as die klassieke PSO. Die voorheen voorgestelde sogenaamde diverse rotasionele invariante (DRI) PSO is ’n algoritme wat beoog om beide diversiteit en invariansie te kombineer. Hierdie algoritme is slegs rotasioneel invariant in ’n stogastiese sin. Boonop is die formulering afhanklik van ’n willekeurige rotasie matriks S, maar invariansie is net gewaarborg vir ’klein’ rotasies in S. In hierdie studie stel ons ’n formulering voor wat divers is en streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. In hierdie formulering, vertrek ons met die lineˆere PSO, en voeg dan ’n self-skalerende ewekansige vektor met ’n standaard normaalverdeling by, wat eenvormig van die oppervlakte van ’n n-dimensionele eenheid sfeer geneem word. Vir die DE algoritme toon ons aan dat die klassieke DE/rand/1/bin algoritme, wat gebruik maak van konstante mutasie en standaard kruising rotasioneel variant is. Ons bestudeer dan ’n voorheen voorgestelde rotasionele invarianteDE formulering waarin die kruisingsoperasie plaasvind in ’n ortogonale basis wat gekonstrueer wordmet behulp van die Gramm-Schmidt ortogonalieseringsproses. Verder stel ons dan twee nuwe formulerings voor deur eerstens ’n baie eenvoudige rotasionele invariante formulering te oorweeg, wat konstante mutasie en volledige rekenkundige kruising gebruik. Hierdie elementˆere formulering onderpresteer as gevolg van die afwesigheid van diversiteit. Ons voeg dan diversiteit by die formulering toe, deur gebruik te maak van twee afsonderlike strategie ¨e. Die eerste verander die kruisings stap deur die rigting van die lineˆere kombinasie tussen die teiken vektor en die mutasie vektor te perturbeer. Hierdie formulering is slegs invariant in ’n stogastiese sin. In die ander formulering, soos met die nuwe rotasionele invariante PSO, voeg ons bloot ’n self-skalerende ewekansige vektor by die onveranderde volledige rekenkundige kruisingsvektor. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Vir die KPGA wys ons dat die standaard KPGA wat gemengde kruising en standaard mutasies gebruik, rotasioneel variant is. Om ’n rotasionele invariante KPGA te konstrueer is dit moontlik om die kruisingsoperasie aan te pas. Dit veroorsaak weereens ’n verlies aan diversiteit. Ons maak die algoritmes divers op twee verskillende maniere: eerstens deur gebruik te maak van ’n gewysigde mutasie skema, en tweedens deur die selfde aanslag te gebruik as in die PSO en die DE, deur ’n self-skalerende ewekansige vektor by die nageslag vektor te voeg. Hierdie formulering is streng invariant onder rotasie, selfs al is dit steeds net in ’n stogastiese sin. Numeriese resultate word vir die variante en invariante weergawe van die onderskeie algoritmes verskaf. Die doel van hierdie studie is nie die bydrae van bloot nog ’n kompeterend en/of beter populasiegebaseerde optimeringsmetode nie, maar eerder om formulerings voor te lê wat beide divers en invariant is, met die hoop dat dit in die toekoms bykomende bydraes sal stimuleer, omdat rotasionele invariansie in die algemeen ’n aantreklike, belangrike kenmerk is vir ’n optimerings algoritme.
Description
Thesis (MScEng)--Stellenbosch University, 2013.
Keywords
Rotational invariance, Particle swarm optimization, Differential evolution, Continuous parameter genetic algorithms, Dissertations -- Mechanical engineering, Theses -- Mechanical engineering