Particle Swarm Optimizer - The Social Structure

Today I want to write about the gravity like relationship between particles inside of a particle swarm.

This article is part of a series:

• An Introduction
• The Social Structure
• The Hive Mind
• ...

The Model

Going back to last article, we defined a model that looked something like the following:

type Particle = {
  Position  : ParameterSet
  Velocity  : float array
  LocalBest : Solution
}

type Swarm = {
  GlobalBest : Solution;
  Particles  : Particle list
}

// The remaining parts of the optimization problem will be discused later
type OptimizationProblem = {
  ...
  Func : TargetFunction
  ...
  
}

On the one hand there is the single particle with its knowledge about his own known best state. One the other hand there is the, to this point in the execution, best known state of the whole swarm. In a simple implementations the particles don't really talk to each other but just share there one global best state.

The Movement

The most simple logic for moving a particle in context of a swarm is:

1. Update the velocity of the particle using global and local best known solution as well as a random component
2. Update the position of the particle using the updated velocity
3. Update the local best known solution when appropriate
4. Update the global best known solution when appropriate

Looking at the model above this results in this function:

// below is the function signature aligned with parameter list 

//            OptimizationProblem -> Solution ->          Particle  -> Particle
let itterate  (problem,              (globalBestPos, _),  particle) =

  let weightLocal = randomBetweenZeroAndOne()
  let weightGlobal = randomBetweenZeroAndOne()
  
  let (localBestPos, localBestValue) = particle.LocalBest
  let currentPosition = particle.Position

  let updatedVelocity = particle.Velocity 
                        ++ (weightGlobal .* (globalBestPos -- currentPosition ))
                        ++ (weightLocal  .* (localBestPos  -- currentPosition ))

  let updatedPosition = currentPosition  
                        ++ updatedVelocity

  let newCurrentValue = problem.Func updatedPosition
  let updatedLocalBest =
    if  newCurrentValue < localBestValue then
      (updatedPosition, newCurrentValue)
    else
      particle.LocalBest
      
  {
    Position  = updatedPosition;
    LocalBest = updatedLocalBest;
    Velocity  = updatedVelocity
  }

OK, it's not quite so simple. First things first, there are three infix operators used in this code. Namely ++,-- and .*. These are used to have simple array operations on the positions and velocities of particles. The code follows:

let (--) v1 v2 = Array.map2 (-) v1 v2
let (++) v1 v2 = Array.map2 (+) v1 v2
let (.*) scalar v = v |> Array.map (fun vCoordinate -> scalar * vCoordinate)

These operators make it possible to use a shorter syntax for updating velocity and position.
In this simple implementation the weight put onto the local and the global gravity factor is equal. Depending on the problem at hand it might be smart to use different weight distributions. This will be discussed later in this article series.
Using these random aspects of the algorithm we update the velocity of the particle and using that the position. Finally we evaluate the Fitnesse of the new position and update the particles best known state. Finally we aggregate all this to form a new particle.

We now covered three of the four steps I was talking about in the listing above. The fourth step Updating the globally best known solution is not part of the logic concerning a single particle of the swarm and thusly will be discussed in the next article.

Up next - The Hive Mind

In the next article we will discuss how this global best known state is managed. At the end of that article we will have the first working implementation of the algorithm.

As always feel free to ask me about specifics and please point me to logic gaps or badly explained parts of my writing. Till next time.