Particle swarm optimization: Difference between revisions

Revision as of 22:34, 7 April 2005

Revision as of 19:08, 9 May 2005

Line 3:

Particle Swarm Optimization (PSO) is form of [[swarm intelligence]]. Imagine a swarm of insects or a school of fish. If one sees a desireable path to go (ie for food, protection, etc.) the rest of the swarm will be able to follow quickly even if they are on the opposite side of the swarm.

This is modeled by particles in multidimensional space that have a position and a velocity. These particles are flying through hyperspace butand remember the best position that they have seen. Members of a particle swarm can communicate good solutionspositions to each other and adjust their own position and velocity based on thatthese good positions. There are two main ways this communication is done:

* a swarm best that is known to all

* local bests are known in neighborhoods of particles

Updating the position and velocity is done through the following formulas at each iteration:

* p<math> x = px + v </math>

* <math> v = wv + c_1 r_1 (\hat{x}-x) + c_2 r_2 (\hat{x}_g-x) </math>

* v = w*v + c₁*(p_{particle best}-p) + c₂*(p_{global best}-p)

Choosing** good values for w, c<submath>1w</submath>, andis c₂ requiresthe muchinertial tweakingconstant. Good values are inusually theslightly rangeless 0-2than 1.

** <math>c_1</math> and <math>c_2</math> are constants that say how much the particle is directed towards good positions. Good values are usually right around 1.

** <math>r_1</math> and <math>r_2</math> are random values in the range <math>[0, 1]</math>.

Once a fairly good solution is found the optizimation is finished.

** <math>\hat{x}</math> is the best the particle has seen.

** <math>\hat{x}_g</math> is the global best seen by the swarm. This can be replaced by <math>\hat{x}_l</math>, the local best, if neighborhoods are being used.

== Algorithm ==

* Initialize the<math>x</math> "currentand position"<math>v</math> of each particle to a random value. The range of these values may be ___domain specific.

* Initialize the "current velocity" of each particle<math>\hat{x}</math> to athe randomcurrent valueposition.

* Initialize each "particle best"<math>\hat{x}_g</math> to the current position andthat calculatehas the best fitness in the swarm.

* Initialize the "global best" to the best fitness in the swarm.

* Loop while the "globalfitness best"of <math>\hat{x}_g</math> is below a threshold and the number of iterations is less than asome maxpredetermined number of iterationsmaximum.

** forFor each particle do the following:

*** Update <math>x</math> according to the above equation.

*** Re-calculateCalculate fitness for new position.

*** itIf it is better than the "globalfitness of best"<math>\hat{x}</math> replace it.

*** ifIt it is better than the "particlefitness best"of <math>\hat{x}_g</math> replace it.

*** Update <math>v</math> according to the above equation.

== See also ==

* Loop while the "global best" is below a threshold and the number of iterations is less than a max number of iterations.

* [[RPSO|Repulsive Particle Swarm Optimization]]

** for each particle do the following:

* [[swarm intelligence]]

*** Update position: p = p + v.

* [[Optimization (mathematics)]]

*** Re-calculate fitness for new position.

*** if it is better than the "particle best" replace it.

*** it it is better than the "global best" replace it.

*** Update velocity: v = w*v + c₁*(p_{particle best}-p) + c₂*(p_{global best}-p) (The first term is an inertia value. The second term moves the velocity toward the best the particle has seen. The last term moves the velocity towards the best the swarm has seen.)