Opened 9 years ago

Closed 7 years ago

#852 closed feature request (done)

Implement Particle Swarm Optimization

Reported by: mkofler Owned by: swagner
Priority: high Milestone: HeuristicLab 3.3.4
Component: Algorithms.ParticleSwarmOptimization Version: 3.3.4
Keywords: Cc:

Description (last modified by 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)

Attachments (1)

Particle Swarm Optimization 3.2.hl (39.7 KB) - added by mkofler 9 years ago.
Simple PSO engine

Download all attachments as: .zip

Change History (60)

Changed 9 years ago by mkofler

Simple PSO engine

comment:1 Changed 9 years ago by mkofler

  • Description modified (diff)
  • Status changed from new to assigned

comment:2 Changed 9 years ago by mkofler

  • Component changed from ### Undefined ### to Algorithms.ParticleSwarmOptimization
  • Version changed from 3.2 to 3.3

comment:3 Changed 9 years ago by mkommend

corrected project dependencies and set svn:ignore r3352

comment:4 Changed 8 years ago by gkronber

Excluded missing file from project with r3684.

comment:5 Changed 8 years ago by abeham

r4397

  • Moved PSO into a feature-branch

comment:6 Changed 8 years ago by abeham

  • Version changed from 3.3 to branch

comment:7 Changed 8 years ago by swagner

  • Summary changed from Implement Algorithms: Particle Swarm Optimization to Implement Particle Swarm Optimization

comment:8 Changed 8 years ago by epitzer

  • Status changed from assigned to reviewing

Simple but complete PSO implementation (r5033)

comment:9 Changed 8 years ago by epitzer

Add missing StorableClass attributes (r5034)

comment:10 Changed 8 years ago by epitzer

  • Owner changed from mkofler to epitzer
  • Status changed from reviewing to assigned

comment:11 Changed 8 years ago by epitzer

  • Status changed from assigned to accepted

comment:12 Changed 8 years ago by epitzer

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

comment:13 Changed 8 years ago by epitzer

  • Owner changed from epitzer to mkofler
  • Status changed from accepted to assigned

comment:14 Changed 8 years ago by mkofler

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

comment:15 Changed 8 years ago by 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

comment:16 Changed 8 years ago by swagner

  • Milestone changed from HeuristicLab x.x.x to HeuristicLab 3.3.3

comment:17 Changed 8 years ago by mkofler

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

comment:18 Changed 8 years ago by 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).

comment:19 Changed 8 years ago by mkofler

  • Owner changed from mkofler to epitzer
  • Status changed from assigned to reviewing

comment:20 Changed 8 years ago by epitzer

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

comment:21 Changed 8 years ago by mkofler

  • Owner changed from epitzer to mkofler
  • Status changed from reviewing to assigned

Results from Developer Stammtisch:

  • Implement at least one additional TopologyUpdater (pref. Multi PSO --> random neighborhood reset every x iterations).
Last edited 8 years ago by mkofler (previous) (diff)

comment:22 Changed 8 years ago by 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.

comment:23 Changed 8 years ago by 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

Last edited 8 years ago by mkofler (previous) (diff)

comment:24 Changed 8 years ago by 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>).

comment:25 Changed 8 years ago by 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

comment:26 Changed 8 years ago by 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.

comment:27 Changed 8 years ago by mkofler

  • Owner changed from mkofler to epitzer
  • Status changed from assigned to reviewing

comment:28 Changed 8 years ago by epitzer

  • Owner changed from epitzer to swagner

Works great, thanks!

comment:29 Changed 8 years ago by epitzer

Merged PSO into trunk (r5426)

comment:30 Changed 8 years ago by epitzer

Correct cloning constructor of NeighborhoodParticleUpdater and TotallyConnectedParticleUpdater. (r5427)

comment:31 Changed 8 years ago by swagner

  • Owner changed from swagner to abeham
  • Version changed from branch to 3.3.2

comment:32 Changed 8 years ago by 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

comment:33 Changed 8 years ago by 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

comment:34 Changed 8 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.3 to HeuristicLab 3.3.4
  • Status changed from reviewing to assigned

comment:35 Changed 8 years ago by abeham

  • Owner changed from abeham to mkofler

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

comment:36 Changed 8 years ago by 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.

comment:37 Changed 8 years ago by mkofler

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

comment:38 Changed 8 years ago by mkofler

  • Owner changed from mkofler to epitzer

comment:39 Changed 8 years ago by epitzer

  • Owner changed from epitzer to mkofler

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)

comment:40 Changed 8 years ago by 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

comment:41 Changed 8 years ago by epitzer

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

comment:42 Changed 8 years ago by epitzer

  • Owner changed from mkofler to gkronber
  • Status changed from assigned to reviewing

comment:43 Changed 8 years ago by gkronber

A sample would be great.

comment:44 Changed 8 years ago by 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.

Last edited 8 years ago by gkronber (previous) (diff)

comment:45 Changed 8 years ago by gkronber

  • Owner changed from gkronber to mkofler
  • Status changed from reviewing to assigned

comment:46 Changed 8 years ago by gkronber

r5844: minor adaption of description string in PSO

comment:47 Changed 8 years ago by epitzer

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

comment:48 Changed 8 years ago by 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.

comment:49 Changed 8 years ago by epitzer

Prevent NullReferenceException when opening incompatible problem (r5868)

comment:50 Changed 8 years ago by 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.

Last edited 8 years ago by mkofler (previous) (diff)

comment:51 Changed 8 years ago by mkofler

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

comment:52 Changed 8 years ago by epitzer

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

comment:53 Changed 8 years ago by mkofler

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

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

Last edited 8 years ago by mkofler (previous) (diff)

comment:54 Changed 8 years ago by 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).

comment:55 Changed 8 years ago by abeham

  • Owner changed from abeham to mkofler
  • Version changed from 3.3.2 to 3.3.3

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.

comment:56 Changed 8 years ago by 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).

Last edited 8 years ago by mkofler (previous) (diff)

comment:57 Changed 8 years ago by mkofler

  • Owner changed from mkofler to swagner
  • Status changed from reviewing to readytorelease

comment:58 Changed 8 years ago by abeham

r5960

  • Removed the PSO branch

comment:59 Changed 7 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.3 to 3.3.4
Note: See TracTickets for help on using tickets.