Opened 4 weeks ago
Closed 3 days 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 4 weeks 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
comment:2 Changed 4 weeks ago by abeham
- 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 4 weeks ago by abeham
r15092: fixed unit test
comment:4 Changed 4 weeks ago by abeham
r15093: updated sample
comment:5 Changed 4 weeks ago by abeham
- Description modified (diff)
- Summary changed from PSO should use max velocity instead of truncation at "velocity bounds" to Improve PSO implementation
- 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 weeks ago by abeham
- Owner changed from abeham to pfleck
- Status changed from accepted to reviewing
- 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 weeks ago by abeham
comment:8 Changed 3 weeks ago by abeham
- Removed Add and Subtract methods from RealVector... our persistence thinks it can use "Add" to add elements to the vector
comment:9 Changed 2 weeks 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 weeks 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.
- 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 13 days ago by abeham
r15201: simplified faster cloning of RealVector
comment:12 Changed 12 days ago by pfleck
- Owner changed from pfleck to abeham
- Status changed from reviewing to assigned
- 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 12 days ago by abeham
- Owner changed from abeham to pfleck
- Status changed from assigned to reviewing
- 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 11 days ago by pfleck
- Owner changed from pfleck to abeham
- Status changed from reviewing to readytorelease
Reviewed r15214: everything ok.
comment:15 Changed 11 days ago by abeham
r15223: Updated sample to change from Schwefel to Rastrigin (in the hope that it's numerically more stable)
comment:16 Changed 11 days ago by abeham
r15224: updated project file
comment:17 Changed 11 days ago by abeham
r15228: reduced precision in unit test to 1e-08 and renamed test class
comment:18 Changed 8 days ago by gkronber
comment:19 Changed 3 days 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
I'm going to implement these changes, since PSO is going to change behavior from 3.3.14 to 3.3.15 anyway.