Global Best PSO (GBestPSO)

The GBestPSO is the canonical version of the PSO. It is popular, not only, because it is the original version of the algorithm (which is cited often within literature), but is also a simple algorithm to implement.

As with all algorithms modelled as a function, the type of the GBestPSO is simply defined as:

List[Particle[S,A]] => RVar[List[Particle[S,A]]]

where a collection of entities are transformed from a given set of entities to a new collection of entities, with randomness applied. This process is then repeatedly reapplied, until a stopping condition is reached.

We’re going to exclude the import statements simply for brevity, but the reader is encouraged to examine the example algorithm definition in the examples sub-module of the project source.

Getting things ready

In order to define an experiment, there are a couple of things we need to get ready first. The most obvious should be that there needs to be some kind of problem, upon which we will be executing the GBestPSO.

As the very first step, we need to get the needed imports in scope:

import cilib._
import cilib.pso._
import cilib.exec._

import eu.timepit.refined.auto._

import scalaz.effect._
import scalaz.effect.IO.putStrLn
import spire.implicits._
import spire.math.Interval

import cilib.syntax.algorithm._

import scalaz._
import Scalaz._

Next, we define the GBestPSO itself. The GBestPSO is defined to use a velocity update equation that uses the personal best of the current particle and then the collection’s current best particle to determine the new velocity vector for the current particle within the algorithm.

Let’s define the two “particle attractors” which we need in the velocity update equation. Because these two values will attract or guide the particle in the search space, we refer to them as Guide instances:

scala> val cognitive = Guide.pbest[Mem[Double],Double]
cognitive: cilib.pso.Guide[cilib.Mem[Double],Double] = cilib.pso.Guide$$$Lambda$16278/214426163@49470504

scala> val social    = Guide.gbest[Mem[Double]]
social: cilib.pso.Guide[cilib.Mem[Double],Double] = cilib.pso.Guide$$$Lambda$16280/690650021@5f3236cf

Again, we need to provide some type parameters to keep the compiler happy, but in this case we need to provide a type called Mem[Double], which is needed to track the memory of a particle and at the same time, fulfills the function constraints of the PSO algorithm itself: that the algorithm participants must cater for a HasMemory instance which exists for the Mem[Double] type.

Now we can define the algorithm itself, providing some constants that are known to provide convergent behaviour within the PSO:

scala> val gbestPSO = pso.Defaults.gbest(0.729844, 1.496180, 1.496180, cognitive, social)
gbestPSO: scalaz.NonEmptyList[cilib.pso.Particle[cilib.Mem[Double],Double]] => (cilib.pso.Particle[cilib.Mem[Double],Double] => cilib.Step[Double,cilib.pso.Particle[cilib.Mem[Double],Double]]) = cilib.pso.Defaults$$$Lambda$16292/1626559323@17550792

scala> val iter = Iteration.sync(gbestPSO)
iter: scalaz.Kleisli[[β$0$]cilib.Step[Double,β$0$],scalaz.NonEmptyList[cilib.pso.Particle[cilib.Mem[Double],Double]],scalaz.NonEmptyList[cilib.pso.Particle[cilib.Mem[Double],Double]]] = Kleisli(cilib.Iteration$$$Lambda$16297/103374689@29c75b1c)

Now that the algorithm is defined, we need to define an “environment” within which this algorithm will execute. The environment is simply a collection of vaues that defines the comparison and evaluator for the algorithm, such as minimizing a benchmark problem.

Let’s define such an environment using a simple problem, borrowing the problem definition from the benchmarks sister project. We will also be minimizing this problem and defining the bounds of the problem space.

scala> val env =
     |   Environment(
     |     cmp = Comparison.dominance(Min),
     |     eval = Eval.unconstrained(cilib.benchmarks.Benchmarks.spherical[NonEmptyList, Double]).eval)
env: cilib.Environment[Double] = Environment(cilib.Comparison$$anon$3@6e1d77ac,cilib.RVar$$anon$3@161b9fd6)

scala> val bounds = Interval(-5.12,5.12)^30
bounds: scalaz.NonEmptyList[spire.math.Interval[Double]] = NonEmpty[[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12]]

Here we define a the evaluator, which is an unconstrained Eval instance, which uses the spherical function definiton from the benchmarks project. We explicitly provide the needed type parameters to keep the compiler happy, that being that the Position is a NonEmtpyList[Double]. Additionally, the cmp value defines how the optimization will be driven, which is to minimize the evaluator in this example.

Let’s now define the entity collection that we need to given the algorithm instance. The collection requires the problem bounds and also defines how the entity instances will be initialized, once random positions are generated for the given problem space

scala> val swarm = Position.createCollection(PSO.createParticle(x => Entity(Mem(x, x.zeroed), x)))(bounds, 20)
swarm: cilib.RVar[scalaz.NonEmptyList[cilib.pso.Particle[cilib.Mem[Double],Double]]] = cilib.RVar$$anon$2@26e887b3

The last requirement is to provide the RNG instance that will use used within the algorithm. We define this value and then repeatedly run the algorithm on the entity collection, stopping after 1000 iterations of the algorithm have been performed

scala> val rng = RNG.fromTime // Seed the RNG with the current time of the computer
rng: cilib.RNG = cilib.CMWC@7508e63f

scala> val result = Runner.repeat(1000, iter, swarm).run(env).run(rng)
result: (cilib.RNG, Exception \/ scalaz.NonEmptyList[cilib.pso.Particle[cilib.Mem[Double],Double]]) = (cilib.CMWC@56c2d7b8,\/-(NonEmpty[Entity(Mem(Solution(NonEmpty[4.693939635971973E-8,1.4378320445104335E-8,-6.219167771951458E-8,-4.377636040982557E-8,3.856619942358585E-8,1.2109389689822477E-7,8.548722337856861E-8,3.4165885175352995E-8,-9.990001130189553E-8,3.9008463275886585E-7,6.494033805164026E-8,-1.9496305769448302E-8,6.656349803084795E-8,-7.288218425921954E-8,8.337777018459546E-8,5.756395719001939E-8,-1.2967116548182113E-7,-7.311812871903937E-8,5.245493818920895E-8,-9.555315425834384E-8,1.7280050036615185E-8,2.625803187024974E-8,-5.845523779717283E-8,2.1661023677846343E-8,9.267400264898403E-8,3.2274713535957166E-8,-6.641199234891886E-8,1.3127380541532574E-7,-3.530170377784559E-8,-8...

scala> result._2 match {
     |   case -\/(error) =>
     |     // Not much to do. The process failed with an error
     |     throw error
     | 
     |   case \/-(value) =>
     |     value.map(x => Lenses._position.get(x))
     | }
res0: scalaz.NonEmptyList[cilib.Position[Double]] = NonEmpty[Solution(NonEmpty[2.1857964304419953E-8,1.4651108740241468E-8,-7.075409199472031E-8,1.0352865866760279E-8,2.3659649431829002E-8,1.2137806452498576E-7,8.782864416618846E-8,-5.2138125623830055E-8,-1.1409070299562794E-7,3.8990846922613983E-7,9.614028925087552E-8,-2.0987391792364988E-8,6.654980535087722E-8,-2.4956471240206077E-7,8.729232652189358E-8,6.285177045891795E-8,-1.3284304550520904E-7,-7.009529509182523E-8,4.7168824353024506E-8,-8.440257404908426E-8,-7.952511957124087E-9,2.6840685389745142E-8,3.9011945458191585E-8,3.2934791164198634E-8,8.803888015305202E-8,3.690354688102076E-8,2.0382434186094978E-7,9.118239998299364E-8,-3.2313062689646436E-8,-9.583882396971035E-8],NonEmpty[[-5.12, 5.12],[-5.12, 5.12],[-5.12, 5.12],[-5.12, ...