PSO
Overview
From Wikipedia:
In computer science, particle swarm optimization (PSO) is a computational method
that optimizes a problem by iteratively trying to improve a candidate solution
with regard to a given measure of quality. PSO optimizes a problem by having a
population of candidate solutions, here dubbed particles, and moving these
particles around in the search-space according to simple mathematical formulae
over the particle's position and velocity. Each particle's movement is influenced
by its local best known position but, is also guided toward the best known
positions in the search-space, which are updated as better positions are found
by other particles. This is expected to move the swarm toward the best solutions.
Parameters
The following is some guidance for the ranges of the parameters.
Number of Particles
A typical range is 20-40. For many problems, as few as 10 particles may be enough. For larger or more difficult problems, 100, 200, or more particles might be more appropriate.
Inertia
Generally the range is 0-1, typically very close to 1.
Cognition, Social, and Local parameters
Usually they are nearly equal and typically around 2, but they can range from 0-4. If the local parameter is set to 0, then the neighbors take no part in the optimization.
World Width and World Height
The range in the x and y directions, respectively. A good range is -50 to 50 in both directions. In that case, both the world width and height would be 100.
Maximum Velocity
Limits how much a particle can move for a given iteration. Typical values to try are 1, 2, and 10. Some implementations define maximum velocity as the world width or height.
Usage
swarm.py [-v] [test] numParticles inertia cognition socialRate localRate worldWidth worldHeight maxVelocity maxEpochs k fname
- -v invokes the verbose option, which will print the error as the algorithm runs in the format [error_x, error_y]
- whether or not the verbose option is used, information about each particle
state at the final epoch is printed. The data printed first is the globally
most fit particle in the format [Q value, x position, y position]. Immediately
below is the index of that particle in the array. Next, info about each
particle is printed in blocks as follows:
- i: index in particle array
- x: x position
- y: y position
- v_x: x velocity
- v_y: y velocity
- b: personal best Q value
- using the test argument will automatically provide the below parameters, -v works
- Number of Particles = 20
- Inertia = 0.95
- Cognition = 2
- Social Rate = 2
- Local Rate = 2
- World Width = 100
- World Height = 100
- Max Velocity = 2
- k = 0 (no neighbors taken into account)
- Max Epochs = 10,000
- no CSV file will be generated, which is normally specified by fname
Note: do not include an extension for fname, .csv is appended automatically
Additional Info
The problems solved in this particular program are as show:
These are hard coded in, and only Problem 1 remains uncommented, however anyone could write their own problem and make it into a Q function.
To give a better idea of what these particles are doing, here are two gifs of the particles coverging at the global max (20, 7) and the local max (-20, -7) over time, respectively.
Further, here is a line plot of the average error of the particles over time. This run was using the test parameters for problem 1:
It is observed that the particles quickly near the solution, but "bounce around" until they have achieved an error of less that 0.01 each. Riveting.