Particle swarm optimization

A particle swarm searches for a global minimum of a function

As a particle swarm optimization (PSO) a is natural analog optimization method referred to, which according to the model of the biological swarm behavior seeks a solution to an optimization problem.

Analogous to the natural phenomenon, a population of solution candidates is moved through the search space in order to obtain a good solution to the problem. For this purpose, the position of each individual is recalculated in each calculation step. The PSO is a metaheuristic , it was proposed in 1995 by James Kennedy and Russell Eberhart.

Analogy to natural swarms

A flock of starlings

The behavior of natural flocks of animals is subject to certain laws. The individuals within a swarm try to stay with the group at all times, to follow the group movement and to maintain a certain minimum distance from other individuals. Craig Reynolds used these principles to simulate swarms of animals in films and computer games. He called the individual individuals in a swarm boids . Frank Heppner and Ulf Grenander expanded Reynolds 'model to include the Boids' need to find a resting place. The need to rest increases as you approach a rest area. Thus the swarm behavior is also influenced by the properties of the room. The search for an optimal resting place for a flock of birds can thus be viewed as a kind of particle swarm optimization.

algorithm

The starting positions of the particles are distributed over the space to be examined. The statistical test planning offers possibilities to find a favorable distribution. In addition to the starting position, each particle is also assigned an initial velocity vector that can be chosen at random. In addition, each particle has: ${\displaystyle {\vec {p}}_{0}}$ ${\displaystyle {\vec {v}}_{0}}$

• an inertia of movement ${\displaystyle \omega }$
• a memory for the coordinates with the best value that he has achieved (individual best value) ${\displaystyle {\vec {p}}_{best}}$
• the knowledge of the coordinates of the global best value of all particles or those of the best value of the particles in its environment ${\displaystyle {\vec {g}}_{best}}$
• a cognitive weighting factor ${\displaystyle c_{k}}$
• a social weighting factor ${\displaystyle c_{s}}$

The particles move through the search space using this information. The best values ​​are continuously updated by comparing them with the current value of the particle. For each step in the movement, a new speed vector is calculated for each particle from the inertia, the individual best value and the global best value. These individual terms are also weighted with random factors for each step . ${\displaystyle n}$ ${\displaystyle {\vec {v}}_{n+1}}$ ${\displaystyle r_{i}}$

${\displaystyle {\vec {v}}_{n+1}=\omega \cdot {\vec {v}}_{n}+c_{k}\cdot r_{1}\cdot ({\vec {p}}_{best}-{\vec {p}}_{n})+c_{s}\cdot r_{2}\cdot ({\vec {g}}_{best}-{\vec {p}}_{n})}$

A termination condition must be defined to terminate the algorithm . For example, the algorithm can be terminated if the global best value does not change significantly after a certain number of steps.

The algorithm can be executed iteratively with different parameters (starting positions, particle properties) in order to check the statistical significance of the extreme value found.

Web links

Commons : Particle swarm optimization  - collection of images, videos and audio files

• Particle Swarm Optimization - a homepage on the subject by Xiaohui Hu, Ph.D. (engl.)

Individual evidence

1. ↑ Eberhart, Russell C .; Shi, Yuhui: Computational Intelligence: Concepts to Implementations , page 87.
2. ^ Russell Eberhart, James Kennedy: A New Optimizer Using Particle Swarm Theory. (PDF) 1995, accessed on January 12, 2016 (English). 
3. ↑ ^{a b} Marcel Röber: Multi-criteria optimization methods for computationally intensive technical tasks. (PDF) March 31, 2010, accessed January 11, 2017 .