The development of some rotationally invariant population based optimization methods

[摘要] ENGLISH ABSTRACT: In this study we consider the lack of rotational invariance of three different population based optimizationmethods, namely the particle swarm optimization (PSO) algorithm, the differential evolution(DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then proposerotationally 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 lackof diversity, which renders the linear PSO inferior to the classical PSO.The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm thataims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochasticsense only. What is more, the formulation depends on the introduction of a random rotationmatrix S, but invariance is only guaranteed for 'small' rotations in S. Herein, we propose a formulationwhich is diverse and strictly invariant under rotation, if still in a stochastic sense only. Todo so, we depart with the linear PSO, and then we add a self-scaling random vector with a standardnormal 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 constantmutation and standard crossover, is rotationally variant. We then study a previously proposedrotationally invariant DE formulation in which the crossover operation takes place in an orthogonalbase constructed using Gramm-Schmidt orthogonalization.We propose two new formulations by firstly considering a very simple rotationally invariant formulationusing constant mutation and whole arithmetic crossover. This rudimentary formulationperforms badly, due to lack of diversity. We then introduce diversity into the formulation using twodistinctly different strategies. The first adjusts the crossover step by perturbing the direction of thelinear combination between the target vector and the mutant vector. This formulation is invariantin a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmeticcrossover 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 optimizationmethods, namely the particle swarm optimization (PSO) algorithm, the differential evolution(DE) algorithm and the continuous-parameter genetic algorithm (CPGA). We then proposerotationally 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 lackof diversity, which renders the linear PSO inferior to the classical PSO.The previously proposed so-called diverse rotationally invariant (DRI) PSO is an algorithm thataims to combine both diversity and invariance. This algorithm is rotationally invariant in a stochasticsense only. What is more, the formulation depends on the introduction of a random rotationmatrix S, but invariance is only guaranteed for 'small' rotations in S. Herein, we propose a formulationwhich is diverse and strictly invariant under rotation, if still in a stochastic sense only. Todo so, we depart with the linear PSO, and then we add a self-scaling random vector with a standardnormal 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 constantmutation and standard crossover, is rotationally variant. We then study a previously proposedrotationally invariant DE formulation in which the crossover operation takes place in an orthogonalbase constructed using Gramm-Schmidt orthogonalization.We propose two new formulations by firstly considering a very simple rotationally invariant formulationusing constant mutation and whole arithmetic crossover. This rudimentary formulationperforms badly, due to lack of diversity. We then introduce diversity into the formulation using twodistinctly different strategies. The first adjusts the crossover step by perturbing the direction of thelinear combination between the target vector and the mutant vector. This formulation is invariantin a stochastic sense only. We add a self-scaling random vector to the unaltered whole arithmeticcrossover 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 rotationallyvariant. To construct a rotationally invariant CPGA it is possible to modify the crossoveroperation to be rotationally invariant. This however, again results in loss of diversity. We introducediversity in two ways: firstly using a modified mutation scheme, and secondly, following the sameapproach 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 thehope that this will stimulate additional future contributions, since rotational invariance in generalis a desirable, salient feature for an optimization algorithm.

[发布机构] Stellenbosch University