The development of some rotationally invariant population based optimization methods
Marthinus N. Ras · SUNScholar (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.