Opened 3 months ago

Closed 2 months ago

#2797 closed defect (done)

Improve PSO implementation

Reported by: abeham Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.15
Component: Algorithms.ParticleSwarmOptimization Version: 3.3.14
Keywords: Cc:

Description (last modified by abeham)

There are a number of issues in the current PSO implementation:

  • Initial velocity vector is 0
  • Velocity vectors are truncated at "velocity bounds" meaning direction is lost, most often particles move in diagonals
  • Neighborhood particle updater doesn't really use neighbor best (it's the same as the totally connected particle updater)
  • Randomization during velocity update is rather low and only changes the length of the update vector, no perturbation on its direction is performed
  • The problem specific solution creator is ignored
  • Bound reflection is awkward
  • Particle behavior is difficult to predict
  • The neighbor best and global bests are calculated from the current population and not from the personal bests

Especially, the truncation of the velocity vector is a problem as the direction towards neighborhood best and personal best is not retained.

On the other hand, Standard PSO mentions neither velocity bounds nor a max velocity. I agree however that a "speed limit" may be useful in practice.

Change History (19)

comment:1 Changed 3 months ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.15
  • Owner set to abeham
  • Status changed from new to accepted

I'm going to implement these changes, since PSO is going to change behavior from 3.3.14 to 3.3.15 anyway.

comment:2 Changed 3 months ago by abeham

r15091:

  • Updated PSO to make it more compatible with SPSO 2011
  • Removed truncation of velocity vector and instead rescaled it given the maximum velocity
  • Added non-zero initial velocity according to SPSO 2011
  • Removed complicated bouncing code due to box constraints and instead implemented as described in SPSO 2011
  • Calculating neighbor best has been changed to use personal best
  • Avoiding local and global particle update and instead relying on neighborbest
  • More randomization during velocity update by using a separate random numbers per dimension
  • Reusing problem specific solution creator in RealVectorParticleCreator instead of always using UniformRandomRealVectorCreator

comment:3 Changed 3 months ago by abeham

r15092: fixed unit test

comment:4 Changed 3 months ago by abeham

r15093: updated sample

comment:5 Changed 3 months ago by abeham

  • Description modified (diff)
  • Summary changed from PSO should use max velocity instead of truncation at "velocity bounds" to Improve PSO implementation

r15096:

  • Added SPSO 2007 and SPSO 2011 particle updaters
  • Unhide particle updater parameter
  • Changed default parameters of sample
  • Changed max velocity to very high value by default (no speed limit)
  • Adapted unit test

comment:6 Changed 3 months ago by abeham

  • Owner changed from abeham to pfleck
  • Status changed from accepted to reviewing

r15102:

  • Recreated backwards compatibility by readding old operators and renaming new operators to SPSO*
    • If a previously configured algorithm is run again, the same results should be obtained
  • Set all old operators to internal, NonDiscoverableType, and Obsolete (they are also not fixed, e.g. PersonalBest update remains flawed)
  • Added SPSO 2007 velocity initializer and let users choose in SPSOParticleCreator
  • Changed description of PSO
  • Updated sample

comment:7 Changed 3 months ago by abeham

Changes r15071 and r15076 were already reviewed as part of #2748, but they should be released with this ticket instead.

comment:8 Changed 3 months ago by abeham

r15114:

  • Removed Add and Subtract methods from RealVector... our persistence thinks it can use "Add" to add elements to the vector

comment:9 Changed 2 months ago by pfleck

  • Owner changed from pfleck to abeham
  • Status changed from reviewing to assigned

Reviewed the new SPSO2011/2017 Operators:

  • Initial swarm size is suggested as
    • SPSO2011: 10 + 2 * sqrt(problem dim)
    • SPSO2017: 40
    • I think we should use 40 as default swarmsize (instead of the current 20)
  • (Initial)Inertia in the paper is 0.721. Should we use this instead of our default (0.8)?
  • In the TopologyInitializers, the neighborhood does not contain the current particle i (as stated in e.g. 3.2.1. of the SPSP paper above). Behavior-wise, this is not a bug because UpdateNeighborBest in the SPSOSwarmUpdater explicitly includes current particle i. However, i would like it better if the neighborhood list would contain the particle itself. If we keep the current behavior, I would like a comment in the TopoligyInitializers stating that the a particle i is implicitly included in its own neighborhood.
  • The SPSO paper mention an optional normalization for the velocity initialization. We could include this as well.
  • SPSO2011ParticleUpdater: Why is the radius multiplied with a random number 0-1 (line 54)? Doesn't the Vector direct already contains the 0-1 scale for each dimension for the hypersphere? In this current version, the hypersphere is shrunk, thus the center of the hypersphere is sampled more densly. Is this intended?
  • SPSOSwarmUpdater.UpdateNeighborBest: i would suggest to rename pairs to neighborhood.

The rest looks good.

comment:10 Changed 2 months ago by abeham

  • Owner changed from abeham to pfleck
  • Status changed from assigned to reviewing

In addition to the review above a bias was discovered in the SPSO2011ParticleUpdater with respect to sampling the random direction vector. The vector should ideally be sampled to be uniformly random on the surface of the unit hyper sphere. According to mathwold.wolfram.com this can be achieved by sampling each dimension from a unit normal distribution and scaling the resulting vector to unit size.

In a discussion with pfleck it was also agreed upon to adapt the topology initializers as these were still not equivalent to the description of standard PSO. The old topology initializers have been kept and adapted. A new topology initializer has been introduced and a topology updater was implemented that is based on the Adaptive Topology Updating scheme described in the paper by Clerc.

r15181:

  • Added IStochasticOperator interface to MultiPSOTopologyUpdater
  • Changed parameter defaults to those described in the paper (swarm size 40, inertia 0.721)
  • Added analyzer placeholder for the last iteration (has not been previously analyzed)
  • Changed random topology initializer that particles include themselves (to be able to use it with the new SPSOSwarmUpdater -> this should not affect the old RealVectorSwarmUpdater)
  • Changed ring topology initializer that particles include themselves (same as above)
  • Changed von neumann topology initializer that particles include themselves (same as above)
  • Added SPSO compatible random topology initializer (as described in the paper by Clerc)
  • Changed sampling of the random direction vector to be uniformly random on the surface of a hypersphere to avoid a slight bias in diagonal direction
  • Updating SwarmBestQuality and BestRealVector parameters in SPSOSwarmUpdater (an oversight)
  • Added a faster method to create a copy of a RealVector (based on Array.Copy)
  • Updated the sample
  • Updated the sample's test results (due to changed sampling in SPSO2011ParticleUpdater)

All review comments have been implemented except for the optional normalization. If we change PSO to optimize a scaled solution space this would incur a lot more changes. The scaling and descaling could also be accomplished by the problem.

comment:11 Changed 2 months ago by abeham

r15201: simplified faster cloning of RealVector

comment:12 Changed 2 months ago by pfleck

  • Owner changed from pfleck to abeham
  • Status changed from reviewing to assigned

Reviewed r15181, r15201:

  • SPSOAdaptiveRandomTopologyUpdater is randomizing the topology if the iteration was successful, not unsuccessful as stated in the paper and the itemdescription.
  • SPSORandomTopologyInitializer.Apply works, but it is quite hard to read in my opinion. Can't this be done in a simpler way?
  • Other changes look good.

comment:13 Changed 2 months ago by abeham

  • Owner changed from abeham to pfleck
  • Status changed from assigned to reviewing

r15214:

  • Fixed adaptive random topology updater
  • Adapted default values of the best attraction parameters
  • Changed code of the new topology initializer
  • Fixed the parameters of the SPSO particle updaters (c parameter is actually (personal|neighbor)bestattraction), reordered the method signature and provided defaults
  • Removed the max beyond parameter again
  • Updated the sample and updated the unit test
    • In the sample no inertia updating is used, but the topology initializers / updaters of SPSO are used

comment:14 Changed 2 months ago by pfleck

  • Owner changed from pfleck to abeham
  • Status changed from reviewing to readytorelease

Reviewed r15214: everything ok.

comment:15 Changed 2 months ago by abeham

r15223: Updated sample to change from Schwefel to Rastrigin (in the hope that it's numerically more stable)

comment:16 Changed 2 months ago by abeham

r15224: updated project file

comment:17 Changed 2 months ago by abeham

r15228: reduced precision in unit test to 1e-08 and renamed test class

comment:18 Changed 2 months ago by gkronber

I believe r15071 and r15076 (from #2748) should also be merged together with these changes.

comment:19 Changed 2 months ago by abeham

  • Resolution set to done
  • Status changed from readytorelease to closed

r15277: merged revisions 15071, 15076, 15091, 15092, 15093, 15096, 15102, 15114, 15181, 15201, 15214, 15223, 15224, 15228 to stable

Note: See TracTickets for help on using tickets.