Particle Swarm Optimization

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)

WHAT IS IT?

Particle swarm optimization (PSO) is a search/optimization technique in the field of machine learning. Although PSO is usually employed on search spaces with many dimensions, this model demonstrates its use in a two dimensional space, for purposes of easier visualization.

Formally speaking, there is some unknown function f(x,y), and we are trying to find values for x and y, such that f(x,y) is maximized. f(x,y) is sometimes called a fitness function, since it determines how good the current position in space is for each particle. The fitness function is also sometimes called a "fitness landscape", since it may be comprised of many valleys and hills.

One approach (random search) would be to keep randomly choosing values for x and y, and record the largest result found. For many search spaces this is not efficient, so other more "intelligent" search techniques are used. Particle swarm optimization is one such technique. Particles are placed in the search space, and move through the space according to rules that take into account each particle's personal knowledge and the global "swarm's" knowledge. Through their movement, particles discover particularly high values for f(x,y).

This model is closely based on the algorithm described by Kennedy and Eberhart's original paper (see reference below). However, this model is meant to demonstrate the principle, rather than be an exact replica. Some alterations were necessary to account for using a toroidal (wrapping) world, and to enhance the visualization of the swarm motion. Also, the function being optimized is discrete (based on a grid of values), rather than continuous.

HOW IT WORKS

Each particle has a position (xcor, ycor) in the search space and a velocity (vx, vy) at which it is moving through that space. Particles have a certain amount of inertia, which keeps them moving in the same direction they were moving previously.
They also have acceleration (change in velocity), which depends on two main things.

1) Each particle is attracted toward the best location that it has personally found (personal best) previously in its history.

2) Each particle is attracted toward the best location that any particle has ever found (global best) in the search space.

The strength with which the particles are pulled in each of these directions is dependent on the parameters ATTRACTION-TO-PERSONAL-BEST and ATTRACTION-TO-GLOBAL-BEST. As particles move farther away from these "best" locations, the force of attraction grows stronger. There is also a random factor about how much the particle is pulled toward each of these locations.

In this model, the particle swarm is trying to optimize a function that is determined by the values in the discrete grid of cells shown in the view. The landscape is created by randomly assigning values to each grid cell, then performing diffusion to smooth out the values, resulting in numerous local minima (valleys) and maxima (hills). This function was chosen merely for illustrative purposes. As a more plausible example of a real application of PSO, the variables (x,y,z,...) might correspond to parameters of a stock market prediction model, and the function f(x,y,z,...) could evaluate the model's performance on historical data.

The model runs until some particle in the swarm has found the "true" optimum value (which is 1.00).

HOW TO USE IT

Press SETUP to initialize the fitness landscape and place the particles randomly in the space. Each time you press SETUP, a different random landscape is created.

Press STEP (for one step) or GO to run the particle swarm optimization algorithm.

The LANDSCAPE-SMOOTHNESS slider determines how smooth of a landscape will be created when the SETUP button is pushed.

The POPULATION-SIZE slider controls the number of particles used.

The ATTRACTION-TO-PERSONAL-BEST slider determines the strength of attraction of each particle toward the location where it had previously found the highest value (in it's own history).

The ATTRACTION-TO-GLOBAL-BEST slider determines the strength of attraction of each particle toward the best location ever discovered by any member of the swarm.

The PARTICLE-INERTIA slider controls the amount to which particles keep moving in the same direction they have been (as opposed to being pulled by the forces of attraction).

The PARTICLE-SPEED-LIMIT slider controls the maximum rate of movement (in either the x or y directions) for each particle. Although this feature is not always part of

The TRAILS-MODE chooser allows you to choose what kind of visualization you would like for the particles' paths (trails). "Traces" means that particles will leave their paths indefinitely on the view. "Tails" means that only the last step they took will be displayed. "None" means that no particle paths will be shown. Note that the display will not update until GO (or STEP) is run again.

The HIGHLIGHT-MODE chooser lets you see the best location anywhere in the search space ("True best") or the best location that the swarm has found ("Best found"). Note that the display will not update until GO (or STEP) is run again.

The BEST-VALUE-FOUND monitor displays the "global best" value of the swarm so far. That is, what is the best value that has been found by any particle. The maximum value it could reach is 1.0, at which point the simulation will stop.

THINGS TO NOTICE

You will often see particles travelling in paths that are roughly elliptical. Why do you think this is? (Think about the major factors that influence the velocity of each particle.)

Sometimes the swarm quickly finds the "perfect" (value = 1.0) solution, and other times it becomes "stuck" in the wrong area of the search space, and looks like it may never find the perfect solution. This notion of getting trapped near a "local maximum", when there is a better "global maximum" somewhere in the search space is a common problem that can arise in many optimization techniques (hill climbers, genetic algorithms, simulated annealing). One variation of the PSO algorithm uses a repulsive force between particles to help keep them spread out in the space, and less likely to all gravitate to a suboptimal value.

THINGS TO TRY

Turn HIGHLIGHT-MODE to "Best found", and run the simulation several times. How often does the "Best found" location change? Does is change more frequently at the beginning, or near the end of the simulation?

Try varying the PARTICLE-INERTIA slider. When it's 0.0, the particles move solely based on the location of their "personal best" and the "global best", and not their movement history. When it's 1.0, the particles velocities never change, resulting in straight-line movement. Can you find an optimal value for the PARTICLE-INERTIA somewhere between these extremes? Do you think the optimal value depends on other factors, such as the population size, the smoothness of the landscape, or the parameters of attraction?

EXTENDING THE MODEL

Add a repulsive force between particles, to try to help prevent them all from prematurely converging on a small area of the search space.

The search space being explored in this model is meaningless --- just a random landscape of values that has been smoothed. Change it to something more meaningful.

What happens if the function that is being optimized is changing over time? That is, modify the model so that the particle swarm is trying to find the best solution in a dynamic environment, where the values of the grid cells are changing. If the change isn't happening too quickly, can the swarm follow the maximum around as it moves through the space?

There are many other variations on PSO. Try searching the web to learn more about some of them, or invent your own.

NETLOGO FEATURES

Using combinations of built-in NetLogo primitives can avoid tricky "edge cases" in toroidal worlds. When deciding how the velocity of each particle should change, we need some way to get a vector from each particle's location to another location in the world (the personal best or the global best). In an unbounded 2D space, one could compute this vector by subtracting (x-goal - xcor) and (y-goal - ycor). However, that doesn't work in our wrapping (toroidal) world. (Why not?). So, instead we use facexy to point the turtle in the correct direction, then dx and dy together give us a unit vector pointed towards the target, and we can multiply those by the distancexy to that location, to get a vector of the correct length.

RELATED MODELS

Simple Genetic Algorithm, Artificial Neural Net, Perceptron, Hill Climbing Example (Code Example).

CREDITS AND REFERENCES

Based on the algorithm presented in the following paper: Kennedy, J. & Eberhart, R. (1995), 'Particle swarm optimization', Neural Networks, 1995. Proceedings., IEEE International Conference on 4.

HOW TO CITE

If you mention this model in a publication, we ask that you include these citations for the model itself and for the NetLogo software:

• Stonedahl, F. and Wilensky, U. (2008). NetLogo Particle Swarm Optimization model. http://ccl.northwestern.edu/netlogo/models/ParticleSwarmOptimization. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.
• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern Institute on Complex Systems, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

Copyright 2008 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

There are 10 versions of this model.

Attached files

This model does not have any ancestors.

This model does not have any descendants.