Thesis (MScEng)--Stellenbosch University, 2013. / 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.
| Identifer | oai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:sun/oai:scholar.sun.ac.za:10019.1/80172 |
| Date | 03 1900 |
| Creators | Ras, Marthinus Nicolaas |
| Contributors | Groenwold, A. A., Stellenbosch University. Faculty of Engineering. Dept. of Mechanical and Mechatronic Engineering. |
| Publisher | Stellenbosch : Stellenbosch University |
| Source Sets | South African National ETD Portal |
| Language | en_ZA |
| Detected Language | English |
| Type | Thesis |
| Format | 70 p. : ill. |
| Rights | Stellenbosch University |
Page generated in 0.0033 seconds