Overview of Darwinian Particle Swarm Optimization [1]

Nature points to a way that may help to circumvent local minima, natural selection. The type of PSO developed and analyzed in this report, a so-called Darwinian PSO, is a variant of PSO in which many swarms of test solutions may exist at any time. They individually perform just like an ordinary PSO algorithm with some rules that are designed to simulate natural selection. We will learn if allowing multiple swarms to represent possible evolutionary tracks of parallel implementations of PSO, whether or not selection, as analogous to natural selection, can help to circumvent local minima.

Extending the PSO algorithm to multiple swarms will expand the parameter set and complicate the task of parameter selection. Particle birth and death within a swarm and swarm birth and death within the collection of swarms must be characterized. Under what conditions should a new particle in a swarm be created? Should the swarm be fixed in size? When should a new swarm be created? When should nature kill an existing swarm? All of these questions introduce complexity into the possible number of implementations. There is one existing paper [2] that can be used to help us formulate a starting point for the investigations.

In [2], only is single swarm is considered. At the end of each swarm update, the current fitnesses of the particles are used to order the particles. The top half of the particles are then duplicated and replace the positions and velocities of the bottom half of the particles. The personal bests of the particles are not changed. The author is able to achieve better convergence on some test problems.

Natural Selection in PSO

1. The longer a swarm lives, the more chance it has of possessing offspring. This is achieved by giving each swarm a constant, small chance of spawning a new swarm.
2. A swarm will have its life time extended by finding a more fit state.
3. A swarm will be punished for failing to find a more fit state.

Additonal Parameters Introduced

• Number of initial swarms? We choose 5.
• Maximum number of swarms? We choose 20.
• Initial particle count per swarm? We choose 20.
• Max particle count per swarm? We choose 30.
• Max spawn count: How many times will we let a swarm spawn? We choose 2.
• When should a swarm spawn? We assign a constant small probability that a swarm wil spawn in each step of the algorithm.
• When should a swarm be terminated? A swarm is deleted from the collection when its particle population falls below a predefined minimum threshhold.
• When should a particle be added to a swarm?
• When should a particle be removed from a swarm? There will be a section dedicated to this topic because the process of deleting particles from a swarm is adaptive.
• Should there be swarm interaction? We allow swarm interaction when a new swarm is spawned. The parent swarm contributes half of its particle population to the new swarm. A random member of the collection of swarms is selected to contribute half of its particle population. Additional particles are randomly initialized and added to the new swarm until it possesses the maximum number of particles allowed.
• Can the characteristics of the fitness landscape be evaluated and used to adjust the Darwinian pso parameters during the optimization? (fitness characterization) This last topic will probably not be investigated in this study.

Possible mathematical analysis

[1] J. Kennedy and R. Eberhart, Swarm Intelligence, Morgan Kaufmann Publishers, 2001.

[2] Peter J. Angeline, Using Selection to Improve Particle Swarm Optimization, 1998 IEEE International Conference on Evolutionary Computation proceedings : IEEE World Congress on Computational Intelligence, May 4-May 9, 1998, Anchorage, Alaska, USA.

Darwinian PSO