Implement ALPS

[pfleck]

Implement the Age-Layered Population Structure[1].

Abstract: To reduce the problem of premature convergence we define a new method for measuring an individual’s age and propose the Age-Layered Population Structure (ALPS). This new measure of age measures how long the genetic material has been evolving in the population: offspring start with an age of 1 plus the age of their oldest parent instead of starting with an age of 0 as with traditional measures of age. ALPS differs from a typical evolutionary algorithm (EA) by segregating individuals into different age-layers by their age and by regularly introducing new, randomly generated individuals in the youngest layer. The introduction of randomly generated individuals at regular intervals results in an EA that is never completely converged and is always exploring new parts of the fitness landscape. By using age to restrict competition and breeding, younger individuals are able to develop without being dominated by older ones. Analysis of the search behavior of ALPS finds that the offspring of individuals that are randomly generated mid-way through a run are able to move the population out of mediocre localoptima to better parts of the fitness landscape. In comparison against a traditional EA, a multi-start EA and two other EAs with diversity maintenance schemes we find that ALPS produces significantly better designs with a higher reliability than the other EAs.

[1] ​http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.153.1516

[pfleck]

r11507 Created ALPS branch

[pfleck]

r11508 Added first ALPS concepts as UserDefinedAlgorithm.

[pfleck]

r11509 Updated ALPS UserDefinedAlgorithm.

[pfleck]

r11521 Simplified emigration of elders.

[pfleck]

r11531 MatingPoolCreator now uses OpenLayers variable correctly.

[pfleck]

r11558

• Updated prototype APLS-OperatorGraph.
• Added Samples for VRP and SymReg.
• Temporarily added OptionalSubScopesProcessor for the ALPS prototype.

[pfleck]

r11566 Added ALPS-Plugin.

• Updated Build-Configuration for DataPreprocessingViews.

[pfleck]

r11567 Added AlpsGeneticAlgorithm and updated plugin description.

[pfleck]

r11568 Added Parameters for ALPS-GA.

[pfleck]

r11569

• Added a generic EnumValue for wrapping an enum.
• Added a generic EnumValueView which displays a drop down with the available enum values.
• Made AgingScheme an EnumValue instead of ValueTypeValue.

[pfleck]

r11578 Implemented wiring of ALPS-GA based on Island-GA wiring.

[pfleck]

r11580 Implemented AlpsGeneticAlgorithmMainLoop.

[pfleck]

r11583

• Implemented MatingPoolCreator.
• Added a modified GeneticAlgorithMainLoop as main operator in ALPS-GA-MainLoop.

[pfleck]

r11585 Implemented EldersEmigrator.

• Implemented EldersSelector and ShiftToRightMigrator.

[pfleck]

r11586 Implemented LayerUpdator.

• Added First/LastSubScopeProcessor.
• Added two Calculators because ExpressionCalculator does not support required features yet.
• Added some wiring.
• Small bugfixes and refactorings.

[pfleck]

r11590

• Finished implementing LayerUpdator.
• Proper implemented per-layer results.
• Some bugfixes and wiring.
• Added LastSubScopeCloner. Note that the First/LastSubScopeCloner/Processor might be dropped and Left/Right-Selectors are used instead. Thanks to jkarder for this suggestion.

[pfleck]

r11609

• Fixed Bugs with Per-Layer-Results.
• Fixed Bugs in EldersSelector.
• Added LayerCreator instead of LastSubScopeCloner for avoiding operators for some temporary hacks.

[pfleck]

r11617

• Fixed Bug in MatingPoolCreator.
• Added AgeDiversityAnalyzer.

[pfleck]

r11620

• Implemented automatic calculation of the age limits based on ALPS' parameter.
• Renamed AgeDiversityAnalyzer to AgeDistributionAnalyzer.

[pfleck]

r11676 Added LayerPopulationSize variable (for PopulationSizeAnalyzer)

[pfleck]

r11677 Merged trunk. Updated .net version of ALPS plugin.

[pfleck]

r11678

• Fixed bug when updating crossovers and mutators.
• Made DataReducers Reduction- and TargetOperationParameter to ValueLookupParameter. This enables ALPS to make the age determination configurable.

[pfleck]

r11975 merged trunk

[bburlacu]

r11997: Removed obsolete diversity analyzer and added the new bottom-up and phenotype diversity analyzers (and similarity calculators)

[pfleck]

r12018

• merged trunk after 3.3.11 release
• updated copyright and plugin version in ALPS plugin
• removed old ALPS samples based on an userdefined alg

[pfleck]

r12035

• Added LayerUniformSubScopesProcessor which introduces an intermediate ExecutionContext which translates array-based parameters to single-value parameters.
• Updated ALPS-OperatorGraph to make usage of the new LayerUniformSubScopesProcessor.
• Added a temporary operator for calculating number of selected sub scopes because presetting the value during operator parameterization does not work for the new intermediate context.

Note: the change of the PopulationSizeParameter still causes an error when creating a new layer. This will be fixed soon.

[pfleck]

r12036

• Used Left/RightSelector instead of First/LastSubScopesProcessor
• Used the LayerUniformSubScopesProcessor for reseeding and opening new layer to take usage of the per-layer parameterization.
• Added LayerSorter because layers are sorted wrong after MergingReducer.
• Removed obsolete LastSubScopeCloner.

[pfleck]

r12038 Merged r12037 from trunk into ALPS.

[pfleck]

r12039 Per-layer parameter can be used to define all multiple layers. If less values are specified in the array the last value is used for all subsequent layers. I.e. when the array has the length 1, all layers use that same one value. From a usability point of view, this behavior may has to be discussed more in detail.

[pfleck]

r12040 Introduced a parameter to adjust the range of layers used for creating a mating pool.

[pfleck]

r12045 Added a parameter in the MatingPoolCreator which controls the percentage of individuals used from the layers below.

[pfleck]

r12046 Added an OldestAverageYoungestAgeAnalyzer.

[pfleck]

r12048

• Changed default values of ALPS-GA.
• OldestAverageYoungesAgeAnalyzer only writes the datatable to the results instead of all values.

[pfleck]

r12071

• Added analyzers in Analyzers and LayerAnalyzers are now configured automatically (depth of scope tree parameters).
• Renamed per layer results to LayerResults.

[pfleck]

r12073: merged r12072 from trunk.

[pfleck]

r12080

• LayerUniformSubScopesProcessor does not longer derives from UniformSubScopesProcessor.
• Reverted changes of UniformSubScopesProcessor.

[pfleck]

r12081 Renamed ALPS branch r12082 Create new branch folder for ALPS which does not branch the whole trunk.

[pfleck]

r12083 Copied ALPS Plugin from old ALPS branch.

[pfleck]

r12084

• Changed the output and reference paths of the ALPS project.
• Added ALPS solution file.
• Added build and prebuild commands.

[pfleck]

r12092

• Use the new toint function of the ExpressionCalculator in the EldersEmigrator and remove the now obsolete MergingReducerCalculator.
• Removed some parameters from the EldersMigrator because the AlpsGeneticAlgorithmMainLoop already defines those parameters.

[pfleck]

r12094 Replaced the NumberOfSelectedSubScopesCalculator with an ExpressionCalculator.

[pfleck]

r12097 Replaced the OpenNewLayerCalculator with an ExpressionOperator.

[pfleck]

r12149 Removed AgingScheme type which inherited from EnumValue. Instead used EnumValue directly.

[pfleck]

r12186 Added the possibility for a plus-selection replacement scheme.

[pfleck]

r12197

• Put LayerAnalyzer after migrating and layer updates.
• Added missing StorableClassAttribute on Alps base class.

[pfleck]

r12260

• Changed default setting of selector for ALPS.
• Fixed automatic LayerResult wiring.

[pfleck]

r12271 Added AgeInheritance as own type and value for consistent configuration.

[pfleck]

r12426 Removed old ALPS branch.

[pfleck]

r12531 Added Termination Criteria to standard ALPS-GA.

[pfleck]

r12533 Re-added MaximumGenerations property based on the generations terminator.

[pfleck]

r12548 Moved updating of terminators to concrete ALPS implementation instead of abstract base class.

[pfleck]

r12570

• Added missing Hook.
• Sealed some classes.

[pfleck]

r12863: Added EvaluatedSolutionsHistoryAnalyzer to keep track of the number of evaluated solutions when the analyzers are called.

[ascheibe]

pfleck's TODO list:

• Change Population Size from array to int
• LayerAnalyzer should get all analyzers, but deactivates them by default. Also add ALPS-specific analyzers.
• Provide a sample for the start page
• Change AgeInheritance to a double value
• Set sensible default parameters
• Remove AgeInheritanceReduction parameter because only standard alps will be integrated in trunk
• Replace MatingPoolRange/MatingPoolSelectionPercentage with placeholder and own operator
• Unhide PlusSelection parameter
• Remove unused operators in GA main loop
• Remove EvaluatedSolutionsHistoryAnalyzer

[pfleck]

r12992

• Changed PopulationSize from array to int.
• Removed obsolete LayerUniformSubScopesProcessor.

[pfleck]

r12993 Removed Alps base class and integrated the code in AlpsGeneticAlgorithm.

[pfleck]

r12994

• Updated item and plugin descriptions.
• Set Creatable attributes.

[pfleck]

r12996

• Added age progression and distribution analyzers per default but disabled.
• Added all regular analyzers as layer analyzers but disabled.
• Removed obsolete EvaluatedSolutionsHistoryAnalyzer.

[pfleck]

r12997

• Removed AgeInheritance enum and used a double [0-1] instead.
• Added a WeightingReducer that uses the new double-weight for weighting between the lower and higher value.

[pfleck]

r12998

• Removed unused operators in modified GA mainloop.
• Unhide PlusSelection parameter.

[pfleck]

r12999 Removed MatingPoolSelectionPercentageParameter.

[pfleck]

r13031 Removed obsolete MatingPoolPreprocessor.

[pfleck]

r13035 Fixed removing unnecessary operators.

[pfleck]

r13037 When creating a new layer, reset the old results (e.g. quality chart) to NaN to symbolize that the layer did not exist during that time.

[pfleck]

r13046

• Changed the age type from int to double.
• Changed EldersSelector to make use of a ScopeTreeLookupParameter.
• Removed unused operators in LayerUpdator.

[pfleck]

r13079 Removed ShiftToRightMigrator and used UnidirectionalRingMigrator instead

[pfleck]

r13095

• Added the possibility of continuous reseeding (percentage based reseeding of layer 0).
• Restructured operator graph.
• Deleted LayerUpdator (replaced by LayerOpener)
• Deleted LayerSorter.
• Moved preparing of GeneticAlgorithmMainLoop to AlpsGeneticAlgorithmMainOperator.

[pfleck]

r13096

• Simplified operator graph in MainOperator.
• Added item descriptions.
• Removed unnecessary code.

[pfleck]

r13110

• Removed ContinuousReseeding because it does not bring any improvements and makes reseeding more complicated.
• Adapted changes from UnidirectionalRingMigrator.

[pfleck]

r13111

• Instead of hidden execution scope change logic in LayerReseeder, the new ReseedingController makes the scope change more obvious by using an OperatorParameter.
• Instead of the classes for EldersEmigrator, LayerOpener and LayerReseeder the operator graph is created in the AlpsGeneticAlgorithmMainLoop using CombinedOperator.

[pfleck]

r13113 Some small changes.

[pfleck]

r13117 Added ReduceToPopulationSize parameter to control if the population is reduced to the PopulationSize after elder migration (default) or the layer can have more than PopulationSize individuals until the next generation.

[pfleck]

r13124

• Implemented full wiring of ALPS.
• Created new AlpsGeneticAlgorithmMainOperator instead of using a modified GeneticAlgorithmMainLoop because of wiring issues.
• Separated LayerCreator into generic LastScopeCloner and ResultsHistoryWiper.

[pfleck]

r13125 Fixed wrong EvaluatedSolutions count when reevaluating elites.

[pfleck]

r13127

• Added some missing wiring.
• Unified some parameter properties.
• Removed some operators.

[pfleck]

r13128 Fixed wrong parameter descriptions.

[pfleck]

r13129 Removed unnecessary assembly reference.

[ascheibe]

Here is the first part of the review. I did have a look at the operator graph and all operators except the Analyzers and the AlpsGeneticAlgorithm* operators:

• AlpsGeneticAlgorithm initializes layer 0 and then, at the end, calls AlpsGeneticAlgorithmMainLoop. AlpsGeneticAlgorithmMainLoop again does some initialization in layer 0. This could be done in one step in my opinion so that the functionality for initializing layer 0 would then be in one place.

• I think that the default parameters of the algorithm are set reasonably. I only have a question concerning the selector: Is there a reason why you chose the GeneralizedRankSelector? If there is then it's ok, otherwise I would choose the ProportionalSelector just to be consistent to the other GA variants.

• Update version in AssemblyInfo.cs.frame and Plugin.cs.frame to 3.3.12

• Adapt project file for Mono (Prebuildevent in .csproj file, open any other HL project file with a text editor)

• MatingPoolCreator:
  • There is a bug in the description: "An operator which creating mating pools ..." -> should be "creates"
  • The description of the MatingPoolRange parameters is missing a ")"
  • In the summary comment: "n previous scopeS"

• EldersSelector:
  • Fix description: "toO old"
  • In the parameter descriptions: "layer" and "layers" should be written in lower case

• In EmigrateElders, in the UnidirectionalRingMigrator, also write "layer" in lower case to be more consistent

• EldersEmigrator
  • ReduceToPopulationSize == false: Do we get a problem if a layer is empty? Or is it impossible to generate such a case?
  • ReduceToPopulationSize == true is how it is described in the paper?

• OpenNewLayer: So this is done if Generations >= AgeLimits[OpenLayers-1]? Shouldn't this condition check if any of the individuals in the layer has reached the age limit and then a new layer is created? Or are there always in the last layer old-enough individuals at the time the age limit for the next layer hits generation?Or from a different angle: If I set AgeInheritance very low, couldn't I produce a case where I would not reach a certain age in a certain number of generations?

• LastScopeCloner:
  • NewScopeOperator description: "Operator" should be lower case
  • Though this is called a scope cloner, it probably only makes sense for layers: It assumes that the name is the layer number and increments it by 1 and also, the ArgumentExcpetion that may be thrown talks about a layer that has to exist. I therefore suggest to rename it to LastLayerCloner and also rename the NewScopeOperator to NewLayerOperator.

• ReseedingController:
  • FirstLayerOperator: Parameter description: "Operator" -> lower case

[ascheibe]

Just a few more points:

• Description of the PopulationSize parameter: "... IN each layer"

• Description of the AgeLimits parameter:
  • Layer -> lower case. Please check for all other operator names.
  • Maybe more precise: "The maximum age an individual can reach in a certain layer." ?

• In the name for the operators: Be consistent and either use "Init" or "Initialize"

• The global DiversityAnalyzer does not work. You should remove it from this collection because we should not offer something to the user where we know it won't work.

Ok, and that's it. I played a little bit around with the algorithm, seems to work so far. Reproducibility of results seems to be ok, also with parallel engine. I did not check in detail if the implementation of the algorithm is exactly like in the paper. So overall I think this is a good, HL-style implementation of ALPS.

[pfleck]

r13206 Fixed typos and renamed some stuff suggested by ascheibe and adapted project for mono.

• The initialization of layer 0 is done similar to other algorithms where general initialization is done in the algorithm itself and variables used and produced during the main-loop is initialized in the main-loop-operator.
• The GeneralizedRankSelector is used as default selector because it generally works the best (rank compensates the large quality range of multiple layers and high selection pressure via pressure-parameter). Proportional selection performs very badly because the selection pressure is too low for ALPS.
• Concerning ReduceToPopulationSize in the EldersEmigrator, the behavior it is not completely clear in the original paper. Reducing the population to the population size seems the more logical way, therefore it is default. An empty layer could happen in extremely rare situations, but it never happens to me so far.
• Concerning opening a new layer, when taking a closer look at the ages, all individual tends to be as old as possible, in the standard version with AgeInheritance==1. That means they usually get too old in exactly after the generation the AgeLimits for the current last layer states. This way it is not necessary to check if any individual becomes too old for the current last layer. For AgeInheritance<1 it can happen that there would actually be no need to open a new layer; however, it will be opened anyway.

[ascheibe]

r13208 fixed version info of plugin

[ascheibe]

Ok, thanks for implementing the review comments. I also again read the paper because of the thing with opening new layers. So it is ok that the layer is opened and that the individuals are copied from the previous layer. But it is assumed in the paper that AgeInheritance == 1.

[ascheibe]

Trunk Integration

r13214 moved ALPS from branch to trunk

[ascheibe]

r13215 deleted ALPS branch

[ascheibe]

TODO

• Decide if we should remove AgeInheritance parameter. We should discuss this. We could then also remove the WeightingReducer operator?
• Write unit test
• Add sample for start page

[ascheibe]

r13217 switched ALPS to project references

[pfleck]

r13223 Added ALPS TSP test sample.

[pfleck]

r13224 Forgot to commit HeuristicLab.Tests.csproj.

[pfleck]

r13226 Fixed ALPS reference in HeuristicLab.Tests.csproj.

[pfleck]

r13228 Added samples for ALPS to solve a TSP and for SymReg.

[pfleck]

r13231 Corrected output path of ALPS plugin. Also corrected the assembly dependencies for other assemblies.

[pfleck]

r13232 Sealed ResultsHistoryWiper.

[ascheibe]

Please also add the unit test for creating the alps GP regression sample.

[pfleck]

r13260

• Added create sample script in unittests for the SymReg Sample.
• Updated ALPS TSP and SymReg Samples.

Because generating the DataSet for the SymReg-sample is stochastic and the seed cannot be configured, there are no assertion for the qualities. Other unit-tests using stochastically generated sample data also does not assert the qualities (e.g. GeSymbolicRegressionSampleTest)

[ascheibe]

Thanks.

[ascheibe]

Merge after #2472.

[ascheibe]

r13285 merged r13214, r13217, r13223, r13224, r13226, r13228, r13231, r13232, r13260 into stable