Cover of Swarm Intelligence Book
Andries P Engelbrecht Fundamentals of Computational Swarm Intelligence

Particle Swarm Optimisation Algorithms

The following classes are available (all discussions assume CIlib version 0.5, and therefor assumes the same directory structure as used in CIlib):

  • gbest PSO [ Hide ]

    Find below the XML specification for a standard Global Best PSO implementation (section 12.1.1).

    <simulator>
      <algorithms>
        <algorithmid="gbest-pso"class="pso.PSO">
          <iterationStrategyclass="pso.iterationstrategies.ASynchronousIterationStrategy"/>
          <initialisationStrategyclass="algorithm.initialisation.ClonedPopulationInitialisationStrategy">
            <prototypeEntityclass="pso.particle.StandardParticle">
              <positionUpdateStrategyclass="pso.positionupdatestrategies.StandardPositionUpdateStrategy"/>
              <velocityUpdateStrategyclass="pso.velocityupdatestrategies.StandardVelocityUpdate">
                <inertiaWeightclass="controlparameter.ConstantControlParameter"parameter="0.729844"/>
                <cognitiveAccelerationclass="controlparameter.RandomizingControlParameter"parameter="1.496180"/>
                <socialAccelerationclass="controlparameter.RandomizingControlParameter"parameter="1.496180"/>
                <vMaxclass="controlparameter.ConstantControlParameter"parameter="2.0"/>
              </velocityUpdateStrategy>
              <velocityInitialisationStrategyclass="pso.particle.initialisation.RandomInitialVelocityStrategy"/>
            </prototypeEntity>
            <entityNumbervalue="30"/>
          </initialisationStrategy>
        </algorithm>
      </algorithms>
      <problems>
        <problemid="griewank"class="problem.FunctionMinimisationProblem">
          <functionclass="functions.continuous.Griewank"domain="R(-600, 600)^30"/>
        </problem>
      </problems>
      <measurementsid="measurements"class="simulator.MeasurementSuite"resolution="1"samples="30">
        <addMeasurementclass="measurement.single.Fitness"/>
        <addMeasurementclass="measurement.single.Diversity"/>
        <addMeasurementclass="measurement.single.FitnessEvaluations"/>
      </measurements>
      <simulations>
        <simulation>
          <algorithmidref="gbest-pso">
            <addStoppingConditionclass="stoppingcondition.MaximumIterations"maximumIterations=" 1000 "/>
          </algorithm>
          <problemidref="griewank"/>
          <measurementsidref="measurements"file="data/griewank.gbest.p_30.w_0_72.c1_1_49.c2_1_49.vmax_2.txt"/>
        </simulation>
      </simulations>
    </simulator>

    Click here to download this file.

    The XML file above provides a specification for a simulation which executes a standard global best (gbest) PSO (Algorithm 12.1 on page 95) on the spherical (page 25) and bohchevsky functions. Using the simulator provided with CIlib, running the command ./simulator.sh xml/gbestPSO.xml for Linux users or simulator.bat xml/gbestPSO.xml for Windows users, the simulation as specified in the above XML will be executed, and the results of the simulations are written to the data/spherical.gbest.p20w1.0c1_2c2_2Vmax1.0.txt and data/bohachevksy1.gbest.p20w1.0c1_2c2_2Vmax1.0.txt files respectively.

    How is a simulation defined? A simulation is specified using the simulator tag.

    What are the main things that need to be specified for a simulation? For each simulation, you need to specify the algorithms that are used in the simulation, the problems on which these algorithms will be applied, the measurements used to extract information from a simulation, and then lastly, the specific simulations need to be specified (this is which algorithms are applied to which problems). More than one algorithm can be specified. The same for the problems, measurements and simulations.

    How is the gbest PSO specified? An algorithm is specified using the algorithm tag. The main CIlib class from which all PSO algorithms inherit is the PSO class in the pso package. The algorithm is therefore specified as pso.PSO (package.class). The next step is to specify the topology used, which is the GBestTopology to be found in the entity.topologies package. Alternatives are the LBestTopology and the VonNeumannTopology classes.

    How do you specify the update mode? Two update modes have been defined for PSO, namely synchronous and asynchronous updates (section 12.3.4, page 117), and are implemented in the pso.iterationstrategies package. The default update mode for the PSO class in CIlib is synchronous, but can be changed via the iterationStrategy tag. This simulation specifies the asynchronous mode.

    The number of particles? Using the particles tag, you can specify any number of particles. For this simulation, 20 particles are used.

    How are stopping conditions specified? This is done using the addStoppingCondition tag. All stopping conditions are implemented under the StoppingConditions package. For this simulation, the gbest PSO will be stopped when 100000 function evaluations (page 103) have been exceeded.

    How do we specify the behaviour and parameters of gbest PSO? We make use of Initialisation Strategies to tell CIlib how to initialise the particles of a swarm (more generically, the entities of a population). The tags (with regard to algorithm initialisation) used in this XML file are now explained:

    • Initialization Strategy: We make use of the algorithm.initialisation.ClonedEntityInitialisationStrategy class which creates a prototype entity as specified by the other tags inside the initialisationStrategy tag. This prototype entity is then used to clone the rest of the entities in the population.
    • Entity type: A standard particle, implemented in pso.particle.StandardParticle, is specified. Standard particles have fixed length, and floating-point elements.
    • How is the gbest particle determined? This XML file specifies that the gbest is updated using the iteration neighborhood best update (equation 12.5) strategy implemented in the pso.positionupdatestrategies.IterationNeighbourhoodBestUpdateStrategy class. This strategy chooses the global best from the current particles. The alternative (and default for CIlib) is to select the global best from the personal best positions, using the memory neighborhood best update (equation 12.4) strategy implemented in the pso.positionupdatestrategies.MemoryNeighborhoodBestUpdateStrategy class.
    • How are particle positions updated? The standard position update (equation 12.1) strategy (CIlib default) is specified using the pso.positionupdatestrategies.StandardPositionUpdateStrategy class. Alternative position update strategies include:
      • pso.positionupdatestrategies.BareBonesPositionUpdateStrategy
      • pso.positionupdatestrategies.BinaryPositionUpdateStrategy
      • pso.positionupdatestrategies.DEPositionUpdateStrategy
      • pso.positionupdatestrategies.GaussianPositionUpdateStrategy
      • pso.positionupdatestrategies.LinearPositionUpdateStrategy
      • pso.positionupdatestrategies.MutationPositionUpdateStrategy
    • How are particle velocities updated? The standard gbest PSO velocity update (equation 12.2) strategy (CIlib default) is specified using the pso.velocityupdatestrategies.StandardVelocityUpdate class. Alternative velocity update strategies include:
      • pso.velocityupdatestrategies.BareBonesDEVelocityUpdate
      • pso.velocityupdatestrategies.BareBonesExploitVelocityUpdate
      • pso.velocityupdatestrategies.BareBonesVelocityUpdateStrategy
      • pso.velocityupdatestrategies.CoherenceVelocityUpdate
      • pso.velocityupdatestrategies.FIPSVelocityUpdate
      • pso.velocityupdatestrategies.GCVelocityUpdate
      • pso.velocityupdatestrategies.LFVelocityUpdate
      • pso.velocityupdatestrategies.LinearVelocityUpdate
      • pso.velocityupdatestrategies.VEPSOVelocityUpdate

      Other settings that can also be specified, via subtags, for the velocity update strategy are:
      • Inertia weight: Using the inertiaWeight tag, you can specify a value for the inertia weight, and the behaviour of the parameter. A weight value of 0.729844 is specified, and the behaviour is that the value remains static (it does not change), as effected via the controlparameterupdatestrategies.ConstantUpdateStrategy class.
      • Acceleration coefficients: The cognitive and social acceleration coefficients are specified using the cognitiveAcceleration and socialAcceleration tags, respectively. Here, both have a static behaviour with initial values of 1.496180.
      • Velocity clamping: By default, there is no velocity clamping. To enforce clamping, the vMax tag is used. For the above, a clamping of 1.0 is used, and the value remains static.

    • You do not have to specify all of the above. What is given above are implemented as defaults. Should you want to change the default values for any aspect, only then do you need to specify these as illustrated in the XML example.

    How are problems specified? All problems are implemented in the problem package. This package currently allows for a number of different problem types, including FunctionMinimisationProblems and FunctionMaximisationProblems. The former is specified for this simulation, using the problem tag. Function types to be optimised are implemented in the functions package. In this case, continuous functions are used. The actual functions are implemented in the functions.continuous package, where you will find the Spherical class, which is one of the prolems that we will be optimising here. The domain of each function can be defined using the domain attribute. The specified domain is the default for this function, and is given as a 30-dimensional problem, with floating-point parameters (specified by the "R"), each within the range [-5.12,5.12].

    How is information extracted from a simulation? To do this, you need to use a Measurement, implemented in the measurement package. For this simulation, 3 measurements are used, namely the Fitness of the best particle, the number of FitnessEvaluations, and the Diversity (equation 12.41) of the swarm. Measurements are written to a file at frequency specified by the resolution attribute. In this case, information is written to a file each 5th iteration. Through the samples attribute, you can specify how many times the algorithm has to be executed on the problem (start from different random initial conditions). In this case, gbest PSO will be executed 30 times for each of the problems specified (Spherical and Bohachevsky). Results for each simulation will be written to the file specified in a tab-delimited format. First, the fitness of the best particle will be given for each simulation, then the swarm diversity for each simulation, then the number of fitness evaluations for each simulation. Each line contains this information for the specific iteration.

    How is the output file specified? Using the measurements tag, the measurements to use is specified via the "fitness" idref attribute, and the output file is specified using the file attribute.

    The actual simulation is effected via the simulations tag, where more that one different simulation can be specified. For each simulation the algorithm, the problem, and the measurements need to be specified.

    Exercise: Download CIlib, and install it (remember you need JDK 1.5). Then, using the provided simulator, execute the above XML file, and see what happens. Then, try to change some of the parameters and behaviours, before you look at the rest of the algorithms and explanations on this site. Browse through the packages and see what options are available.

  • lbest PSO [ Show ]
  • Swarm Initialization [ Show ]
  • Stopping Conditions [ Show ]
  • Neighborhood Topologies [ Show ]