Free cookie consent management tool by TermsFeed Policy Generator

Opened 9 years ago

Closed 8 years ago

#2269 closed feature request (done)

Implement ALPS

Reported by: pfleck Owned by: ascheibe
Priority: medium Milestone: HeuristicLab 3.3.13
Component: Algorithms Version: branch
Keywords: Cc:

Description

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

Change History (108)

comment:1 Changed 9 years ago by pfleck

  • Status changed from new to accepted

comment:2 Changed 9 years ago by pfleck

r11507 Created ALPS branch

comment:3 Changed 9 years ago by pfleck

r11508 Added first ALPS concepts as UserDefinedAlgorithm.

comment:4 Changed 9 years ago by pfleck

r11509 Updated ALPS UserDefinedAlgorithm.

comment:5 Changed 9 years ago by pfleck

r11521 Simplified emigration of elders.

comment:6 Changed 9 years ago by pfleck

r11531 MatingPoolCreator now uses OpenLayers variable correctly.

comment:7 Changed 9 years ago by pfleck

r11558

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

comment:8 Changed 9 years ago by pfleck

r11566 Added ALPS-Plugin.

  • Updated Build-Configuration for DataPreprocessingViews.

comment:9 Changed 9 years ago by pfleck

r11567 Added AlpsGeneticAlgorithm and updated plugin description.

comment:10 Changed 9 years ago by pfleck

r11568 Added Parameters for ALPS-GA.

comment:11 Changed 9 years ago by 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.

comment:12 Changed 9 years ago by pfleck

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

comment:13 Changed 9 years ago by pfleck

r11580 Implemented AlpsGeneticAlgorithmMainLoop.

comment:14 Changed 9 years ago by pfleck

r11583

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

comment:15 Changed 9 years ago by pfleck

r11585 Implemented EldersEmigrator.

  • Implemented EldersSelector and ShiftToRightMigrator.

comment:16 Changed 9 years ago by 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.

comment:17 Changed 9 years ago by 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.

comment:18 Changed 9 years ago by pfleck

r11609

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

comment:19 Changed 9 years ago by pfleck

r11617

  • Fixed Bug in MatingPoolCreator.
  • Added AgeDiversityAnalyzer.

comment:20 Changed 9 years ago by pfleck

r11620

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

comment:21 Changed 9 years ago by pfleck

r11676 Added LayerPopulationSize variable (for PopulationSizeAnalyzer)

comment:22 Changed 9 years ago by pfleck

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

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

comment:24 Changed 9 years ago by pfleck

r11975 merged trunk

comment:25 Changed 9 years ago by bburlacu

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

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

comment:27 Changed 9 years ago by 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.

comment:28 Changed 9 years ago by 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.

comment:29 Changed 9 years ago by pfleck

r12038 Merged r12037 from trunk into ALPS.

comment:30 Changed 9 years ago by 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.

comment:31 Changed 9 years ago by pfleck

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

comment:32 Changed 9 years ago by pfleck

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

comment:33 Changed 9 years ago by pfleck

r12046 Added an OldestAverageYoungestAgeAnalyzer.

comment:34 Changed 9 years ago by pfleck

r12048

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

comment:35 Changed 9 years ago by pfleck

r12071

  • Added analyzers in Analyzers and LayerAnalyzers are now configured automatically (depth of scope tree parameters).
  • Renamed per layer results to LayerResults.
Last edited 9 years ago by pfleck (previous) (diff)

comment:36 Changed 9 years ago by pfleck

r12073: merged r12072 from trunk.

comment:37 Changed 9 years ago by pfleck

r12080

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

comment:38 Changed 9 years ago by pfleck

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

comment:39 Changed 9 years ago by pfleck

r12083 Copied ALPS Plugin from old ALPS branch.

comment:40 Changed 9 years ago by pfleck

r12084

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

comment:41 Changed 9 years ago by 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.

comment:42 Changed 9 years ago by pfleck

r12094 Replaced the NumberOfSelectedSubScopesCalculator with an ExpressionCalculator.

comment:43 Changed 9 years ago by pfleck

r12097 Replaced the OpenNewLayerCalculator with an ExpressionOperator.

comment:44 Changed 9 years ago by pfleck

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

comment:45 Changed 9 years ago by pfleck

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

comment:46 Changed 9 years ago by pfleck

r12197

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

comment:47 Changed 9 years ago by pfleck

r12260

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

comment:48 Changed 9 years ago by pfleck

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

comment:49 Changed 9 years ago by pfleck

r12426 Removed old ALPS branch.

comment:50 Changed 9 years ago by pfleck

r12531 Added Termination Criteria to standard ALPS-GA.

comment:51 Changed 9 years ago by pfleck

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

comment:52 Changed 9 years ago by pfleck

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

comment:53 Changed 9 years ago by pfleck

r12570

  • Added missing Hook.
  • Sealed some classes.

comment:54 Changed 9 years ago by pfleck

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

comment:55 Changed 8 years ago by ascheibe

  • Owner changed from pfleck to ascheibe
  • Status changed from accepted to reviewing

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

comment:57 Changed 8 years ago by ascheibe

  • Owner changed from ascheibe to pfleck
  • Status changed from reviewing to assigned

comment:58 Changed 8 years ago by ascheibe

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13

comment:59 Changed 8 years ago by pfleck

  • Status changed from assigned to accepted

comment:60 Changed 8 years ago by pfleck

r12992

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

comment:61 Changed 8 years ago by pfleck

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

comment:62 Changed 8 years ago by pfleck

r12994

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

comment:63 Changed 8 years ago by pfleck

r12996

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

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

comment:65 Changed 8 years ago by pfleck

r12998

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

comment:66 Changed 8 years ago by pfleck

r12999 Removed MatingPoolSelectionPercentageParameter.

comment:67 Changed 8 years ago by pfleck

r13031 Removed obsolete MatingPoolPreprocessor.

comment:68 Changed 8 years ago by pfleck

r13035 Fixed removing unnecessary operators.

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

comment:70 Changed 8 years ago by pfleck

r13046

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

comment:71 Changed 8 years ago by pfleck

r13079 Removed ShiftToRightMigrator and used UnidirectionalRingMigrator instead

comment:72 Changed 8 years ago by 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.
Last edited 8 years ago by pfleck (previous) (diff)

comment:73 Changed 8 years ago by pfleck

r13096

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

comment:74 Changed 8 years ago by pfleck

r13110

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

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

comment:76 Changed 8 years ago by pfleck

r13113 Some small changes.

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

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

comment:79 Changed 8 years ago by pfleck

r13125 Fixed wrong EvaluatedSolutions count when reevaluating elites.

comment:80 Changed 8 years ago by pfleck

r13127

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

comment:81 Changed 8 years ago by pfleck

r13128 Fixed wrong parameter descriptions.

comment:82 Changed 8 years ago by pfleck

r13129 Removed unnecessary assembly reference.

comment:83 Changed 8 years ago by pfleck

  • Owner changed from pfleck to ascheibe
  • Status changed from accepted to reviewing

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

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

comment:86 Changed 8 years ago by ascheibe

  • Owner changed from ascheibe to pfleck
  • Status changed from reviewing to assigned

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

comment:88 Changed 8 years ago by pfleck

  • Owner changed from pfleck to ascheibe
  • Status changed from assigned to reviewing

comment:89 Changed 8 years ago by ascheibe

r13208 fixed version info of plugin

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

comment:91 Changed 8 years ago by ascheibe

Trunk Integration

r13214 moved ALPS from branch to trunk

comment:92 Changed 8 years ago by ascheibe

r13215 deleted ALPS branch

comment:93 Changed 8 years ago by 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
Last edited 8 years ago by ascheibe (previous) (diff)

comment:94 Changed 8 years ago by ascheibe

r13217 switched ALPS to project references

comment:95 Changed 8 years ago by ascheibe

  • Owner changed from ascheibe to pfleck
  • Status changed from reviewing to assigned

comment:96 Changed 8 years ago by pfleck

  • Status changed from assigned to accepted

r13223 Added ALPS TSP test sample.

comment:97 Changed 8 years ago by pfleck

r13224 Forgot to commit HeuristicLab.Tests.csproj.

comment:98 Changed 8 years ago by pfleck

r13226 Fixed ALPS reference in HeuristicLab.Tests.csproj.

comment:99 Changed 8 years ago by pfleck

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

comment:100 Changed 8 years ago by pfleck

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

comment:101 Changed 8 years ago by pfleck

r13232 Sealed ResultsHistoryWiper.

comment:102 Changed 8 years ago by pfleck

  • Owner changed from pfleck to ascheibe
  • Status changed from accepted to reviewing

comment:103 Changed 8 years ago by ascheibe

  • Owner changed from ascheibe to pfleck
  • Status changed from reviewing to assigned

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

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

comment:105 Changed 8 years ago by ascheibe

  • Owner changed from pfleck to ascheibe
  • Status changed from assigned to reviewing

Thanks.

comment:106 Changed 8 years ago by ascheibe

Merge after #2472.

comment:107 Changed 8 years ago by ascheibe

  • Status changed from reviewing to readytorelease

comment:108 Changed 8 years ago by ascheibe

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