Opened 5 years ago

Closed 4 years ago

#1961 closed feature request (done)

CMAES algorithm implementation

Reported by: gkronber Owned by: abeham
Priority: medium Milestone: HeuristicLab 3.3.9
Component: Algorithms.CMAEvolutionStrategy Version: 3.3.9
Keywords: Cc:

Description


Change History (36)

comment:1 Changed 5 years ago by abeham

  • Owner changed from swagner to abeham
  • Status changed from new to accepted

comment:2 Changed 5 years ago by abeham

  • Version changed from 3.3.7 to branch

r9115: Added CMA-ES branch

comment:3 Changed 5 years ago by abeham

r9118: Updated CMA-ES (working version), but no wiring

comment:4 Changed 5 years ago by abeham

r9121: Added wiring code, removed obsolete parameters, simplified mainloop slightly, changed sigmabounds to a matrix

comment:5 Changed 5 years ago by abeham

r9122:

  • Added an analyzer for the behavior of CMA-ES
  • Fixed counting of evaluated solutions
  • Fixed ItemNames

comment:6 Changed 5 years ago by abeham

r9129:

  • Changed CMA-ES to reference RealVector directly and work with that encoding only (separation of algorithm and encoding was not trivial to achieve)
  • Simplified operator graph (also improves performance)
  • Simplified strategy parameters (those used only during update are initialized in update)
  • Added many termination criteria (same as in Hansen's Java version)
  • Added different ways to calculate the mean (different weightings)

comment:7 Changed 5 years ago by abeham

r9132:

  • Removed optimization plugin as no changes are necessary there
  • Changed analyzer to plot mean solution instead of best offspring
  • Added a realvector creator that can inject a predefined point

comment:8 Changed 5 years ago by abeham

r9140: Added creator to project, fixed wiring in CMA-ES algorithm, fixed visualization of random landscape, removed useless function in test functions

comment:9 Changed 5 years ago by abeham

r9148:

  • Added Logarithmic flag also to AxisRatio
  • Fixed some bugs regarding initial iterations
  • Removed the PredefinedRealVectorCreator and instead added a NormalDistributedRealVectorCreator
    • When sigma is 0 this is the same as the PredefinedRealVectorCreator

comment:10 Changed 5 years ago by abeham

r9155: commit of project files

comment:11 Changed 5 years ago by abeham

r9158: improved wiring slightly, added check in OnStarted and fixed name of placeholder

comment:12 Changed 5 years ago by mkommend

Remark: The CMA-ES cannot be saved if the algorithm is paused or an exception occurred during the execution. This is due to the use of a Queue in the CMA-ES parameters (line 255) which cannot be handled be the persistence.

comment:13 Changed 5 years ago by abeham

r9199:

  • Switched to ALGLIB's high quality normal distributed random number generator
  • Added automatic restriction to bounds after mutation in case MaxTries > 1 and no valid solution could be obtained

comment:14 Changed 5 years ago by abeham

r9200: Fixed serialization of paused algorithm

comment:15 Changed 5 years ago by ascheibe

r9243 removed readonly properties from cmaes as this lead to an exception in Hive

comment:16 Changed 5 years ago by mkommend

r9244: Corrected bounds update in CMAMutator.

comment:17 Changed 5 years ago by mkommend

r9245: Corrected another bug regarding the bounds check in the CMAMutator.

comment:18 Changed 5 years ago by mkommend

r9260: Adapted CMA-ES solution to contain only the algorithm projects as all the other changes have already been integrated in the trunk in r9258.

comment:19 Changed 5 years ago by abeham

r9264: removed all other plugins from the branch

comment:20 Changed 5 years ago by abeham

r9291: Removed dependency to ALGLIB in CMA-ES implementation (code is commented)

comment:21 Changed 5 years ago by abeham

r9297:

  • Improved performance of CMA-ES without ALGLIB
    • All CMA-ES parameter are standard .NET types instead of HL types

comment:22 Changed 5 years ago by abeham

r9298: fixed bug introduced in last commit regarding initialization of cCov

comment:23 Changed 5 years ago by abeham

r9299: removed comment

comment:24 Changed 5 years ago by abeham

r9302: updated analyzer to match the output of Hansen more closely

comment:25 Changed 5 years ago by abeham

r9303: Improved performance slightly (thx to mkommend)

comment:26 Changed 4 years ago by mkommend

When will this feature be included in the trunk and released? I've used the implementation to optimize several problems and it works like a charm. Hence, I am wondering why this is still in a branch.

comment:27 Changed 4 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.9
  • Owner changed from abeham to mkommend
  • Status changed from accepted to reviewing

Yes it should be integrated. Would you want to do a review on the branch version before we can integrate it into the trunk?

I'm particularly interested in your opinion on treating the box constraints. Currently, points that are outside the bounds are resampled (I think only the specific dimension). This can take quite some time. The points are truncated at the boundaries if after a certain number of tries no sample was completely within the bounds.

comment:28 Changed 4 years ago by mkommend

r9685: Corrected plugin dependencies of CMAES.

comment:29 Changed 4 years ago by mkommend

Review Comments

General comments

  • Cloning unit test does not pass
  • ParameterVisibility unit test does not pass
  • References are not set to CopyLocal = false
  • AssemblyVersion should be 3.3.8.WCREV
  • PluginVersion should be 3.3.8.WCREV
  • LicenseInformation is inconsistent (copyright year 2012 vs 2013).
  • What is the use of the property CMAType in the various Operators? It always returns typeof(CMAParameters) as far as I have spotted.

CMAParameters

  • Some properties (e.g., Weights, PC, ... ) are compared by == although they contain reference types like double[] or double[,]. Therefore, a change event is fired even if the values are the same.
  • StorableQualityHistory calls ToArray which is unnecessary and wastes memory.

The defined interfaces look fine and reasonable. CMAInitializer looks find, but I haven't checked every mathematical transformation and error checks of the strategy parameters.

CMAMutator

  • Line 129: Is it intentional that the real vector gets only corrected if MaxTries > 1? And why exactly was 1 chosen as comparison value?
    • IMHO the behavior that out of bounds dimension are resampled is OK and also the truncation is reasonable. Maybe the number of maximum tries could be reduced to 100 to save some execution time.

CMARecombinators

  • CMALinearweightedRecombinator: It states in the descriptions that it used linear increasing weights, although IMHO the weights are decreasing.
  • The previous statements also holds for the CMALogweightedRecombinator.

CMAEvolutionStrategy

  • FixedValueParameters would be more suitable for some parameters which use types from HeuristicLab.Data (e.g. Seed, SetSeedRandomly, ...).

The CMAAnalyzer looks fine for me. I have no comments regarding the Terminator class.

Last edited 4 years ago by mkommend (previous) (diff)

comment:30 Changed 4 years ago by mkommend

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

comment:31 Changed 4 years ago by abeham

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

r9709: implemented reviewer comments

  • Cloning unit test does not pass
  • ParameterVisibility unit test does not pass
  • References are not set to CopyLocal = false
  • AssemblyVersion should be 3.3.8.WCREV
  • PluginVersion should be 3.3.8.WCREV
  • LicenseInformation is inconsistent (copyright year 2012 vs 2013).
  • What is the use of the property CMAType in the various Operators? It always returns typeof(CMAParameters) as far as I have spotted. - It is meant as a possibility to develop CMA-ES for more specific applications with more knowledge of the underlying problem and/or specific constraints. You'd need to implement your own Initializer, Manipulator, Recombinator and Updater.
  • Some properties (e.g., Weights, PC, ... ) are compared by == although they contain reference types like double[] or double[,]. Therefore, a change event is fired even if the values are the same. - I removed change notification altogether.
  • StorableQualityHistory calls ToArray which is unnecessary and wastes memory.
  • Line 129: Is it intentional that the real vector gets only corrected if MaxTries > 1? And why exactly was 1 chosen as comparison value? - I added an extra parameter that controls if you want to always truncate the point at the bounds or if you allow sampled points outside the bounds. The second way is preferred if your evaluation function can handle such points through penalties.
    • IMHO the behavior that out of bounds dimension are resampled is OK and also the truncation is reasonable. Maybe the number of maximum tries could be reduced to 100 to save some execution time.
  • CMALinearweightedRecombinator: It states in the descriptions that it used linear increasing weights, although IMHO the weights are decreasing.
  • FixedValueParameters would be more suitable for some parameters which use types from HeuristicLab.Data (e.g. Seed, SetSeedRandomly, ...).
Last edited 4 years ago by abeham (previous) (diff)

comment:32 Changed 4 years ago by mkommend

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

Reviewed the source changes in r9709 and everything looks fine, but I must admit i haven't tested the new code extensively.

comment:33 Changed 4 years ago by abeham

r9718: Integrated branch into trunk

comment:34 Changed 4 years ago by abeham

r9719: Removed plugin dependency

comment:35 Changed 4 years ago by ascheibe

r9720 fixed output path of project

comment:36 Changed 4 years ago by abeham

  • Component changed from Algorithms to Algorithms.CMAEvolutionStrategy
  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from branch to 3.3.9

r9736: Merged CMA-ES into stable branch

Note: See TracTickets for help on using tickets.