Improve PSO implementation

[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.

[abeham]

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

[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

[abeham]

r15092: fixed unit test

[abeham]

r15093: updated sample

[abeham]

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

[abeham]

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

[abeham]

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

[abeham]

r15114:

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

[pfleck]

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.

[abeham]

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.

[abeham]

r15201: simplified faster cloning of RealVector

[pfleck]

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.

[abeham]

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

[pfleck]

Reviewed r15214: everything ok.

[abeham]

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

[abeham]

r15224: updated project file

[abeham]

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

[gkronber]

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

[abeham]

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