Particle Swarm Optimization

Particle Swarm Optimization preview image

2 collaborators

Uri_dolphin3 Uri Wilensky (Author)

Tags

computer science 

Tagged by Reuven M. Lerner over 10 years ago

Model group CCL | Visible to everyone | Changeable by group members (CCL)
Model was written in NetLogo 5.0.4 • Viewed 680 times • Downloaded 92 times • Run 1 time
Download the 'Particle Swarm Optimization' modelDownload this modelEmbed this model

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:

COPYRIGHT AND LICENSE

Copyright 2008 Uri Wilensky.

CC BY-NC-SA 3.0

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.

Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

patches-own
[
  val  ; each patch has a "fitness" value associated with it
       ; the goal of the particle swarm is to find the patch with the best fitness value
]

turtles-own
[
  vx                  ; velocity in the x direction
  vy                  ; velocity in the y direction

  personal-best-val   ; best value I've run across so far
  personal-best-x     ; x coordinate of that best value
  personal-best-y     ; x coordinate of that best value
]

globals
[
  global-best-x    ; x coordinate of best value found by the swarm
  global-best-y    ; y coordinate of best value found by the swarm
  global-best-val  ; highest value found by the swarm
  true-best-patch  ; patch with the best value
]

to setup-search-landscape
  ;; make a landscape with hills and valleys
  ask patches [ set val random-float 1.0 ]
  ;; slightly smooth out the landscape
  repeat landscape-smoothness [ diffuse val 1 ]
  let min-val min [val] of patches
  let max-val max [val] of patches
  ; normalize the values to be between 0 and 1
  ask patches [ set val 0.99999 * (val - min-val) / (max-val - min-val)  ]

  ; make it so that there is only one global optimum, and its value is 1.0
  ask max-one-of patches [val]
  [
    set val 1.0
    set true-best-patch self
  ]

  ask patches [ set pcolor scale-color gray val 0.0 1.0]
end 

to setup
  clear-all
  setup-search-landscape

  ; create particles and place them randomly in the world
  create-turtles population-size
  [
    setxy random-xcor random-ycor
    ; give the particles normally distributed random initial velocities for both x and y directions
    set vx random-normal 0 1
    set vy random-normal 0 1
    ; the starting spot is the particle's current best location.
    set personal-best-val val
    set personal-best-x xcor
    set personal-best-y ycor

    ; choose a random basic NetLogo color, but not gray
    set color one-of (remove-item 0 base-colors)
    ; make the particles a little more visible
    set size 4
  ]
  update-highlight
  reset-ticks
end 

to go
  ask turtles [
    ; should the particles draw trails, or not?
    ifelse trails-mode = "None" [ pen-up ] [ pen-down ]

    ; update the "personal best" location for each particle,
    ; if they've found a new value better than their previous "personal best"
    if val > personal-best-val
    [
      set personal-best-val val
      set personal-best-x xcor
      set personal-best-y ycor
    ]
  ]

  ; update the "global best" location for the swarm, if necessary.
  ask max-one-of turtles [personal-best-val]
  [
    if global-best-val < personal-best-val
    [
      set global-best-val personal-best-val
      set global-best-x personal-best-x
      set global-best-y personal-best-y
    ]
  ]
  if global-best-val = [val] of true-best-patch
    [ stop ]

  if (trails-mode != "Traces")
    [ clear-drawing ]

  ask turtles
  [
    set vx particle-inertia * vx
    set vy particle-inertia * vy

    ; Technical note:
    ;   In the canonical PSO, the "(1 - particle-inertia)" term isn't present in the
    ;   mathematical expressions below.  It was added because it allows the
    ;   "particle-inertia" slider to vary particles motion on the the full spectrum
    ;   from moving in a straight line (1.0) to always moving towards the "best" spots
    ;   and ignoring its previous velocity (0.0).

    ; change my velocity by being attracted to the "personal best" value I've found so far
    facexy personal-best-x personal-best-y
    let dist distancexy personal-best-x personal-best-y
    set vx vx + (1 - particle-inertia) * attraction-to-personal-best * (random-float 1.0) * dist * dx
    set vy vy + (1 - particle-inertia) * attraction-to-personal-best * (random-float 1.0) * dist * dy

    ; change my velocity by being attracted to the "global best" value anyone has found so far
    facexy global-best-x global-best-y
    set dist distancexy global-best-x global-best-y
    set vx vx + (1 - particle-inertia) * attraction-to-global-best * (random-float 1.0) * dist * dx
    set vy vy + (1 - particle-inertia) * attraction-to-global-best * (random-float 1.0) * dist * dy

    ; speed limits are particularly necessary because we are dealing with a toroidal (wrapping) world,
    ; which means that particles can start warping around the world at ridiculous speeds
    if (vx > particle-speed-limit) [ set vx particle-speed-limit ]
    if (vx < 0 - particle-speed-limit) [ set vx 0 - particle-speed-limit ]
    if (vy > particle-speed-limit) [ set vy particle-speed-limit ]
    if (vy < 0 - particle-speed-limit) [ set vy 0 - particle-speed-limit ]

    ; face in the direction of my velocity
    facexy (xcor + vx) (ycor + vy)
    ; and move forward by the magnitude of my velocity
    forward sqrt (vx * vx + vy * vy)

  ]
  update-highlight
  tick
end 

to update-highlight
  ifelse highlight-mode = "Best found"
  [ watch patch global-best-x global-best-y ]
  [
    ifelse highlight-mode = "True best"
    [  watch true-best-patch ]
    [  reset-perspective ]
  ]
end 


; Copyright 2008 Uri Wilensky.
; See Info tab for full copyright and license.

There are 10 versions of this model.

Uploaded by When Description Download
Uri Wilensky almost 11 years ago Updated to NetLogo 5.0.4 Download this version
Uri Wilensky over 11 years ago Updated version tag Download this version
Uri Wilensky over 11 years ago Updated to version from NetLogo 5.0.3 distribution Download this version
Uri Wilensky about 12 years ago Updated to NetLogo 5.0 Download this version
Uri Wilensky almost 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky almost 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky almost 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky almost 14 years ago Updated from NetLogo 4.1 Download this version
Uri Wilensky almost 14 years ago Model from NetLogo distribution Download this version
Uri Wilensky almost 14 years ago Particle Swarm Optimization Download this version

Attached files

File Type Description Last updated
Particle Swarm Optimization.png preview Preview for 'Particle Swarm Optimization' almost 11 years ago, by Uri Wilensky Download

This model does not have any ancestors.

This model does not have any descendants.