Implement Particle Swarm Optimization

[mkofler]

The attached engine describes a simple PSO in HL3.2 and was configured for test functions. Required functionality that goes beyond the currently available operators was realized via Programmable Operators. In particular, two additional operaters were identified that could be beneficial for other algorithms as well:

• Scalar multiplication: Multiplying a vector with a scalar (used in UpdateVelocities)
• Vector addition: Adding two vectors (used in ApplyMove)

[mkofler]

Simple PSO engine

[mkommend]

corrected project dependencies and set svn:ignore r3352

[gkronber]

Excluded missing file from project with r3684.

[abeham]

r4397

• Moved PSO into a feature-branch

[epitzer]

Simple but complete PSO implementation (r5033)

[epitzer]

Add missing StorableClass attributes (r5034)

[epitzer]

Configurable ParticleUpdater, and topologies, different topology initializers and support for dynamic topology changes (r5209)

[mkofler]

Added two parameter updaters (for omega and the velocity bounds) in r5225.

[epitzer]

As discussed:

• Always assume velocity centered around zero and symmetric
• Add Interface for VelocityBoundsModifier (e.g. IDiscreteDoubleMatrixModifier) similar to IDiscreteDoubleValueModifier from Simulated Annealing
• VelocityBoundsModifier should have child operator IDiscreteDoubleValueModifier
• Change ValueModifier for Omega directly to IDiscreteDoubleValue

[mkofler]

[5311] Implemented changes to parameter updaters as dicussed in comment 15 above.

[mkofler]

[5312] Overrode Prepare() method to set velocity vector and omega to start values of updaters (if they have been specified, otherwise leave as is).

[epitzer]

added item descriptions, implemented IStorableContent interface, added missing StorableClass attributes, and fixed value updater reset (r5316)

[mkofler]

Results from Developer Stammtisch:

• Implement at least one additional TopologyUpdater (pref. Multi PSO --> random neighborhood reset every x iterations).

[mkofler]

[5339]: Added Multi PSO Initializer/Updater as described in (Liang and Suganthan, 2005). The operator randomly partitions a given swarm into non-overlapping sub swarms. Re-grouping takes place every N iterations.

[mkofler]

[5342]: Worked on parameter wiring to ensure that users may only select correct parameter combinations (e.g. NeighborhoodParticleUpdater + some topology but not EmptyTopology). WIP

[abeham]

I looked over the changes of r5342:

• IParticleUpdater was changed to derive from IItem to INamedItem, but I assume it will always be an operator and therefor should derive from IOperator (in a similar fashion other interfaces should be adapted).
• The StorableConstructor should always be empty, the Initialize method should be called in an AfterDeserializationHook. Hint: There's a ​code snippet for generating the hook.
• It would be better to repopulate the ValidValues instead of selecting the right one and leaving the wrong options present.

Some further general comments on the source (whoever is responsible):

• Is the EmptyTopologyInitializer needed? OptionalConstrainedValueParameters allow to select nothing and the Placeholder in the algorithm will also do nothing when its operator parameter returns null as its ActualValue.
• Same question regarding the IdentityTopologyUpdater.
• It is dangerous to make public properties in ParticleUpdater that forward the call to *Paramter.ActualValue.Value. Such properties can only be used when the operator is executed in a context (when it is executed by the engine) and thus calling these properties from the point of a public visibility will fail in almost any case. The general rule of thumb in HeuristicLab is to only make "value-properties" in operators when the parameter is of type IValueParameter. Also the properties depend on ActualValue-caching for a performant implementation (calling get twice would traverse the scope tree twice if no caching was present). While this kind of caching exists currently, I think it is better not to make this transparent in such a way. The rule of thumb is to call the parameter properties at the beginning of Apply and caching the result in local variables.
• It would be better if interfaces would contain parameter definitions using the interface types (instead of ValueParameter<T> use IValueParameter<T>).

[mkofler]

Code cleanup in r5410. Thanks to Andreas Beham for the detailed review and feedback how to improve the code.

Pending changes for upcoming release:

• Realize parallelization of evalutor
• Prepare PSO sample

[mkofler]

r5418: Adapted PSO to perform move evaluation in parallel (using the parallel engine). See also changes made by Andreas to other standard algorithm as documented in #1333.

[epitzer]

Works great, thanks!

[epitzer]

Merged PSO into trunk (r5426)

[epitzer]

Correct cloning constructor of NeighborhoodParticleUpdater and TotallyConnectedParticleUpdater. (r5427)

[abeham]

r5435

• Made public properties that redirect to ActualValue.Value private or protected
• Sealed all of the specific operators
• Removed files that are present in the repository, but are not included in the project
• Removed .sln file (is this still needed?)
• Added license headers to some files
• Unified the pattern for writing the constructors similar to other files in the trunk
• Corrected assembly and plugin version from 3.3.0.x to 3.3.2.x
• Fixed the wiring in the VelocityBoundsModifier

[abeham]

r5440

• Fixed wiring of VelocityBoundsModifier again (on second thought a "real" wiring is not really necessary)
• Added PSO as dependency to the main project

After looking through the code and the operator graph I would recommend to target the 3.3.4 release instead of the imminent 3.3.3. A number of bigger issues need to be considered in my opinion:

1. I am missing a separation between algorithm, encoding and problem. All interfaces for required operators reside inside the ParticleSwarmOptimization plugin. These should rather be located in a place that acts as a connector between algorithm, encoding and problem, such as e.g. HeuristicLab.Optimization.
   • Those parts of the interface that target encoding specific information (e.g. Parameters with the generic type RealVector) would need to be cut out, introduced as additional interfaces in the encoding plugin, and wired by the problem.
   • The other algorithm specific parts would need to be wired by the algorithm
2. Instead of providing the necessary abstractions for problems to be solved by PSO, the PSO algorithm is tailored especially to solve test function problems. Some of the parameter names reflect this in that they're called "Point" instead of the more general "RealVector". From my understanding of the code the PSO needs a ParticleCreator, a ParticleUpdater, a SwarmUpdater, and a NeighborUpdater which _can_ be RealVector rather than _must_ be RealVector. These operators should be moved to HeuristicLab.Encodings.RealVector. The topology operators, as well as the Omega updater are algorithm specific and do not require problem specific knowledge as far as I can see.
   • The BestPointInitializer is also encoding/problem-specific
3. It's questionable whether an IntegerVector is needed to hold the neighborhood information, or if an IntArray would suffice. The reason is simply that dependencies to encoding plugins should be made only when features of that encoding are used (Mutation, Crossover, etc.) which is not the case here.
4. The algorithm should collect basic result values such as Iterations or EvaluatedSolutions
5. We should model our algorithms by using combined operators that encapsulate most of the "core functionality" of that algorithm (also called MainLoop). This makes it easier to reuse PSO e.g. in hybrid algorithms
6. The algorithm should die more gracefully in case the problem does not provide the necessary operators

[abeham]

After discussing the necessary changes in a short meeting, I'll hand the ticket back to mkofler.

[mkofler]

Code refactoring in progress. Thanks to abeham for the detailed review and great discussion.

[5560]: Indroduced necessary interfaces to realize a clean separation between algorithm, encoding and problem. In detail:

• HeuristicLab.Optimization: Added ITopologyInitializer, ITopologyUpdater, IParticleCreator, IParticleUpdater, ILocalParticleUpdater, IGlobalParticleUpdater, IDiscreteDoubleMatrixModifier and ISwarmUpdater
• HeuristicLab.Encodings.RealVectorEncoding: Added new folder ParticleOperators with encoding specific interfaces (IRealVectorParticleCreator, IRealVectorParticlepdater, IRealVectorSwarmUpdater) and opertors (RealVectorParticleCreator, RealVectorParticleUpdater, RealVectorTotallyConnectedParticleUpdater, RealVectorNeughborhoodParticleUpdater, RealVectorSwarmUpdater).
• Created main loop for PSO and worked on wiring of algorithm. Execution with wrong problem is now more difficult. You would have to load a compatible problem first and then replace it by an incompatible problem to be able to press start.
• Replaced IntegerVector parameters by IntArray as suggested.

[5561]: Worked on new SwarmUpdater operator, mostly.

• Merged BestPointInitializer, NeighborUpdater and VelocityBoundsUpdater into a single operator (much copy&paste of epitzer's code).
• Added wiring in SingleObjectiveTestFunctionProblem for IRealVectorParticleCreator, IRealVectorParticleUpdater and IRealVectorSwarmUpdater.
• Added results collection.

[5566]: Worked on main loop operator graph and RealVectorSwarmUpdater.

[5568]: Pair-programming with epitzer

• Removed work-a-round CombinedOperator for ISwarmUpdater (which has to be set by the Problem). Introduced new algorithm parameter instead.
• Moved ResultsCollector and initial call of ISwarmUpdater into main loop.
• Worked on RealVectorNeighborhoodParticleUpdater and RealVectorTotallyConnectedParticleUpdater.
• RealVectorSwarmUpdater: Pruned code and added VelcityBoundsUpdater functionality.
• Worked on operator graph in main loop
• IDiscreteDoubleMatrixModifier is an IOperator now.

Work in progress.

[mkofler]

[5581] Algorithm up an running now. Fixed main loop (Analyzer was not included in loop) and minor fix in RealVectorSwarmUpdater.

[epitzer]

Additional improvements to PSO (r5592)

• simplify and clean up RealVectorSwarmUpdater
• make the RealVectorParticleCreator an AlgorithmOperator
• standardize naming of local variables in ParticleUpdaters
• remove default parameter values from main loop
• new implementation of MultiPSOTopologyUpdater (using shuffling)

[mkofler]

Code cleanup in [5643]:

• Added CurrentInertia variable to scope and results. Reasoning: Algorithm parameters should not be changed during execution as theInertiaUpdater did before.
• Adjusted Prepare() method to correctly wire/instantiate CurrentInertia (value comes either from Inertia Algorithm parameter or from InertiaUpdater).
• Removed NeighborUpdater (functionality has been merged into SwarmUpdater).
• Removed references to HeuristicLab.Encodings.RealVectorEncoding in main project.
• Evaluated solutions are now also counted and stored in results collection
• Renamed remaining Point parameters to more generic RealVector parameters

[epitzer]

Set CurrentInertia inside operator graph and make sure all operators use it. Set default end value to epsilon instead of zero (r5645)

[gkronber]

A sample would be great.

[gkronber]

Review comments:

• as has been remarked already by swagner it is inconvenient that an exception is thrown immediately after a new problem is created (in all cases but real-valued test functions). This is caused by the fact that the SwarmUpdater parameter in the PSO algorithm is a constrained-value parameter and thus does not allow null values. As a side remark the exception also occurs when a incompatible problem (which does not define a SwarmUpdater operator) is dragged on the algorithm however in this case the exception is silently caught somewhere and the drag-and-drop operation shows no effect (this issue is probably not specific to PSO). It would be nice if the algorithm can handle such situations more gracefully similar to TS. In TS the situation is similar as it needs a MoveGenerator operator defined in the problem. TS does not throw an exception when a problem without MoveGenerators is created or opened.

• PSO has a number of OptionalConstrainedValueParameters and ConstrainedValueParameters for operators. The values of the parameters depend on each other and thus the selected value and valid values of dependent parameters are updated when the selected value of a parameter is changed by the user. However, the list of valid values in ConstrainedValueParameters can be edited freely by the user via the GUI. It seems this case is ignored as the necessary parameter wiring is not present in the PSO class. This means it is possible for the user to set a combination of incompatible TopologyUpdaters, TopologyInitializers and this leads to an exception when the algorithm is executed. Either changing the valid values should be prevented by setting the parameter to readonly state or the wiring of ConstrainedValueParameters should be improved.

• In class PSO a PlaceHolder operator for a velocity bounds updater is created but it seems this operator is never used.

• The class VelocityBoundsUpdater (or modifier, the terminology is inconsitent here) seems ill-placed. As already suggested by abeham after an earlier review the functionality of the should be merged into a the SwarmUpdater. Thus I would prefer to move the VelocityBoundsUpdater class into the Encodings.RealVector plugin to the particle operators. I tried to set the VelocityBoundsUpdater parameter in the RealVectorSwarmUpdaterParameter, but I was unable to set a configuration that can be executed. It seems this is impossible anyway, as the statement in line 203 in class RealVectorSwarmUpdater tries to create a new operation for its successor, but this will not succeed as the successor of RealVectorSwarmUpdater is null. It seems the velocity bounds updater is not really necessary for the PSO algorithm and maybe we should think about excluding this functionality from the next release.

• the removal of the concept of a global best solution and instead handling this a special case of a global neighborhood seems to be a good idea. This should also be reflected in the PSO parameters. This means that it is probably a good idea to use a topology initializer and set it to 'Fully connected topology' as a default (I assume the terms neighborhood and topology are used interchangeably in the PSO implementation). I think this is already implemented as suggested.

• The separation between algorithm, problem, and encoding has been greatly improved, thanks!

Concluding remarks: I think the PSO implementation is almost ready for release. The most important issues that should be addressed before the release are the fact that an exception is thrown when creating or opening any problem except for the 'real valued test functions problem' and the problem of the missing wiring of the ConstrainedValueParameters.

[gkronber]

r5844: minor adaption of description string in PSO

[epitzer]

• Remove superfluous placeholders
• Hide ParticleUpdater
• Add CurrentVelocityBounds parameter analogous to CurrentInertia
• Add (Current)VelocityBounds to results
• Merge VelocityBoundsModifier directly into SwarmUpdater (r5866)

[epitzer]

Wiring of MaxIterations in the RealVectorSwarmUpdater would mandate inclusion into the ISwarmUpdater interface. One option would be to include all algorithm parameters into this interface to allow the swarm updater arbitrary parameter access and correct wiring.

[epitzer]

Prevent NullReferenceException when opening incompatible problem (r5868)

[mkofler]

Regarding the issue with incompatible problems:

Parts of the old OperatorGraph seem to remain active if I create a valid problem (SingleObjectiveTestFunction) and then replace it with an invalid problem. For instance, the AckleyEvaluator throws an exception on execution after(!) the problem has been replaced by a user-defined problem. Same thing happens for TabuSearch but does not throw an error. Reason: ParticleCreator is empty for user defined problem.

--> Won't change since it is an issue with the engine.

[epitzer]

Make particles reflect from the bounds to prevent them from becoming stuck. (r5892)

[mkofler]

Hid start/end index parameters for inertia weight updater (r5893).

Wired SwarmUpdater to update VelocityBounds when VelocityBoundsStartValue is adjusted (r5905).

[mkofler]

Small code fixes as discussed with Andreas. Renamed SwarmUpdater to RealVectorSwarmUpdater. Moved update code for velocity bounds wiring in RealVectorSwarmUpdater to new method (r5911).

[abeham]

My concluding remarks

• The results collector in the MainLoop collects a variable Iterations, however it is injected as CurrentIteration. Since it is called Iterations / Generations in all other algorithms, I renamed all occurrences of CurrentIteration to Iterations in r5935.
• The InertiaUpdater is configured to go from 1 to double.Epsilon, even though the inertia set by default is -0.2. Shouldn't the default values of the InertiaUpdater be something like StartValue = -0.2 and EndValue ~ -1e-12?

Other than that, I think this is ready for release. I'll forward it to mkofler once again, to look into the question regarding the InertiaUpdater. I understand that it's just a minor issue, so please set it to release afterwards.

[mkofler]

Thank you for the fix. The proposed default value change for the InertiaUpdater is problematic because StartValue and EndValue for the ExponentialDiscreteDoubleValueModifier must be greater than 0. Hard-wiring the StartValue of InertiaUpdater to Inertia is therefore probably not the best idea. I changed the default Inertia setting to 1 instead - that way the values are initially consistent (r5941).

[abeham]

r5960

• Removed the PSO branch