CMAES algorithm implementation

[abeham]

r9115: Added CMA-ES branch

[abeham]

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

[abeham]

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

[abeham]

r9122:

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

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

[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

[abeham]

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

[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

[abeham]

r9155: commit of project files

[abeham]

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

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

[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

[abeham]

r9200: Fixed serialization of paused algorithm

[ascheibe]

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

[mkommend]

r9244: Corrected bounds update in CMAMutator.

[mkommend]

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

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

[abeham]

r9264: removed all other plugins from the branch

[abeham]

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

[abeham]

r9297:

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

[abeham]

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

[abeham]

r9299: removed comment

[abeham]

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

[abeham]

r9303: Improved performance slightly (thx to mkommend)

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

[abeham]

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.

[mkommend]

r9685: Corrected plugin dependencies of CMAES.

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

[abeham]

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, ...).

[mkommend]

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

[abeham]

r9718: Integrated branch into trunk

[abeham]

r9719: Removed plugin dependency

[ascheibe]

r9720 fixed output path of project

[abeham]

r9736: Merged CMA-ES into stable branch