Changes between Version 2 and Version 3 of Documentation/Reference/Particle Swarm Optimization


Ignore:
Timestamp:
03/30/11 16:57:25 (11 years ago)
Author:
mkofler
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/Particle Swarm Optimization

    v2 v3  
    11= Particle Swarm Optimization =
     2Particle swarm optimization (PSO) is a stochastic population-based optimization algorithm that was first introduced by Kennedy and Eberhart. Members of the population are called particles. Each particle moves in search space, taking advantage of the particle’s own experience and the experience of the particle’s neighbours or the experience of the whole swarm.
     3
     4Our particle swarm optimization algorithm has been designed to work with arbitrary solution encodings. However, so far a concrete implementation is only available for real vector encoded problems, i.e. [[Single Objective Test Function]].
    25
    36'''Algorithm Parameters:'''
     
    69|| Inertia             || Inertia weight on a particle's movement (omega). Default: -0.2 ||
    710|| !InertiaUpdater      || Updates the omega parameter. ||
    8 || !MaxIterations || The maximum number of iterations which should be processed. ||
     11|| !MaxIterations || The maximum number of iterations which should be processed. Default: 1000 ||
    912|| !MutationProbability || The probability that the mutation operator is applied on a solution. ||
    1013|| Mutator             || The operator used to mutate solutions. ||
     
    1417|| !PersonalBestAttraction || Weight for particle's pull towards its personal best soution (phi_p). Default: -0.01 ||
    1518|| Population Size     || The size of the population of solutions. ||
    16 || Seed                || The random seed used to initialize the new pseudo random number generator. ||
    17 || Selector            || The operator used to select solutions for reproduction. ||
    18 || !SetSeedRandomly    || True if the random seed should be set to a random value, otherwise false. ||
     19|| Seed                || The random seed used to initialize the new pseudo random number generator. Default: 0 ||
     20|| !SetSeedRandomly    || True if the random seed should be set to a random value, otherwise false. Default: true ||
    1921|| !SwarmSize           || Size of the particle swarm. Default: 10 ||
    20 || !SwarmUpdater        || Encoding-specific parameter which is provided by the problem. ||
     22|| !SwarmUpdater        || Encoding-specific parameter which is provided by the problem. May provide additional encoding-specific parameters, such as velocity bounds for real valued problems. ||
    2123|| !TopologyInitializer || Creates neighborhood description vectors. ||
    2224|| !TopologyUpdater     || Updates the neighborhood description vectors. ||
    2325
    24 '''Is there a sample/tutorial?'''
     26=== Local vs. Global PSO ===
     27Topology initializers group the particles into neighborhoods according to a certain strategy. 
    2528
    26 '''References:'''
     29So far, the following topologies have been implemented:
     30* `RandomTopologyInitializer`: Randomly connectes every particle with `NroOfParticles` other particles. Neighborhood connections are not symmetric, meaning if particle A is a neighbor of particle B, particle B does not necessarily have to be a neighbor of particle A. The default `NroOfParticles` is 3.
     31* `RingTopologyInitializer`: Every particle is connected with its preceeding and its following particle.
     32* `VonNeumannTopologyInitializer`: Every particle is connected with the two following and the two previous particles, wrapping around at the beginning and the end of the population.
     33
     34If you want to implement your own topology, you must inherit from `ITopologyInitializer` or derive from the base class `TopologyInitializer`.
     35 
     36In general local PSOs (with topologies) converge slower than global PSOs but are less likely to be captured in local minima due to greater population diversity. (Kennedy and Mendes, 2002) investigated the impact of different topologies on algorithm performance. The found that:
     37* Global PSO: quick to converge, worst results
     38* Circular Topology: moderate results
     39* Wheel Topology: moderate results
     40* Von Neumann Topology: best results
     41
     42=== Parameter Adjustment ===
     43
     44Like many other metheuristics, the PSO algorithm frequently faces the problems of being trapped in local optima. Balancing the global exploration and local exploitation abilities of PSO is therefore very important.
     45
     46'''Parameter Tuning  '''
     47
     48A recent paper by (Pedersen 2010) provides a most helpful table of PSO parameters that have been tuned for different optimization scenarios. We recommend them as a first starting point when optimizing new problems. Some of the settings (like using a negative inertia weight) may seem quirky, but we also got some very good results with those settings.
     49
     50'''Velocity Bounds'''
     51Another is to adjust the minimum/maximum velocity bounds vector. Particle velocities on each dimension are clamped to a certain velocity range. The parameter `VelocityBounds` controls the maximum global exploration ability of PSO.
     52* large velocity --> global exploration
     53* small velocity --> local exploitation
     54
     55'''Inertia Weight'''
     56The inertia weight parameter was introduced in 1998 by Shi and Eberhart. The idea was to use a maximum velocity ad set the velocity bounds to One common strategy is to adjust the inertia weight dynamically during the optimization run (via fuzzy optimization, by linear decreasing or increasing or randomizing the parameter).
     57
     58It is possible to let the algorithm adjust some parameters dynamically during runtime.
     59* Inertia Weight: Configure the `InertiaUpdater` to adjust the inertia weight. You can select any operator that implements `IDiscreteDoubleValueModifier`. The standard Simulated Annealing annealing operators (exponential, square root, linear, quadratic increase/decrease) can be used.
     60* Velocity Vector: In the `SwarmUpdater` the velocity vector can be likewise adjusted. Please note that do so far only use one `IDiscreteDoubleValueModifier` for all vector dimensions, therefore the value (but not the sign) of all dimensions will be equal.
     61
     62'''Topology Updaters'''
     63* `MultiPSOTopologyUpdater`: The whole population is divided into `NrOfSwarms` non-overlapping sub-swarms. Neighborhood topology is dynamic and randomly assigned. Swarms are re-grouped every regroupingPeriod iteration. The operator is implemented as described in (Liang and Suganthan 2005).
     64
     65=== Is there a sample/tutorial? ===
     66
     67We are currently preparing one. Please stay tuned.
     68
     69=== References: ===
    2770* Kennedy, J. and  Eberhart, R.C., 2001. Swarm Intelligence. Morgan Kaufmann. ISBN 1-55860-595-9.
     71* Kennedy, J. and Mendes, 2002. R. Population structure and particle swarm performance. Congress on Evolutionary Computation, pp. 1671-1676.
     72* Liang, J.J. and Suganthan, P.N., 2005. Dynamic multi-swarm particle swarm optimizer. IEEE Swarm Intelligence Symposium, pp. 124-129.
    2873* Pedersen, M.E.H., 2010. [http://www.hvass-labs.org/people/magnus/publications/pedersen10good-pso.pdf | Good parameters for particle swarm optimization]. Technical Report HL1001 (Hvass Laboratories)