search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

Implement ALPS #2269

Closed HeuristicLab-Trac-Bot closed 8 years ago

HeuristicLab-Trac-Bot commented 9 years ago

Issue migrated from trac ticket # 2269

milestone: HeuristicLab 3.3.13 | component: Algorithms | priority: medium | resolution: done

2014-10-29 09:05:52: @NimZwei created the issue

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

HeuristicLab-Trac-Bot commented 9 years ago

2015-06-29 16:27:35: @NimZwei commented

r12531 Added Termination Criteria to standard ALPS-GA.

HeuristicLab-Trac-Bot commented 9 years ago

2015-06-29 17:07:29: @NimZwei commented

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

HeuristicLab-Trac-Bot commented 9 years ago

2015-06-30 12:40:26: @NimZwei commented

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

HeuristicLab-Trac-Bot commented 9 years ago

2015-07-02 11:50:42: @NimZwei commented

r12570

  • Added missing Hook.
  • Sealed some classes.
HeuristicLab-Trac-Bot commented 9 years ago

2015-08-14 14:36:08: @NimZwei commented

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

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 13:10:36: @Shabbafru changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 13:10:36: @Shabbafru changed owner from @NimZwei to @Shabbafru

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 14:31:01: @Shabbafru commented

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
HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 14:40:47: @Shabbafru changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 14:40:47: @Shabbafru changed owner from @Shabbafru to @NimZwei

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 14:44:34: @Shabbafru changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.13

HeuristicLab-Trac-Bot commented 9 years ago

2015-10-07 16:48:20: @NimZwei changed status from assigned to accepted

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-09 13:47:58: @NimZwei commented

r12992

  • Changed PopulationSize from array to int.
  • Removed obsolete LayerUniformSubScopesProcessor.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-09 14:37:26: @NimZwei commented

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

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-09 14:45:53: @NimZwei commented

r12994

  • Updated item and plugin descriptions.
  • Set Creatable attributes.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-09 15:38:05: @NimZwei commented

r12996

  • Added age progression and distribution analyzers per default but disabled.
  • Added all regular analyzers as layer analyzers but disabled.
  • Removed obsolete EvaluatedSolutionsHistoryAnalyzer.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-09 16:54:59: @NimZwei commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-13 09:57:58: @NimZwei commented

r12998

  • Removed unused operators in modified GA mainloop.
  • Unhide PlusSelection parameter.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-13 11:18:55: @NimZwei commented

r12999 Removed MatingPoolSelectionPercentageParameter.

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 14:26:44: @NimZwei commented

r13031 Removed obsolete MatingPoolPreprocessor.

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 16:27:38: @NimZwei commented

r13035 Fixed removing unnecessary operators.

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-19 17:34:05: @NimZwei commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-21 17:42:25: @NimZwei commented

r13046

  • Changed the age type from int to double.
  • Changed EldersSelector to make use of a ScopeTreeLookupParameter.
  • Removed unused operators in LayerUpdator.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-29 12:41:37: @NimZwei commented

r13079 Removed ShiftToRightMigrator and used UnidirectionalRingMigrator instead

HeuristicLab-Trac-Bot commented 8 years ago

2015-10-30 17:10:44: @NimZwei commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-10-30 17:10:44: @NimZwei

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-02 16:00:04: @NimZwei commented

r13096

  • Simplified operator graph in MainOperator.
  • Added item descriptions.
  • Removed unnecessary code.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-03 15:34:57: @NimZwei commented

r13110

  • Removed ContinuousReseeding because it does not bring any improvements and makes reseeding more complicated.
  • Adapted changes from UnidirectionalRingMigrator.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-03 17:09:51: @NimZwei commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-03 17:48:47: @NimZwei commented

r13113 Some small changes.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-04 17:28:16: @NimZwei commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-05 16:21:04: @NimZwei commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 10:09:53: @NimZwei commented

r13125 Fixed wrong EvaluatedSolutions count when reevaluating elites.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 11:48:00: @NimZwei commented

r13127

  • Added some missing wiring.
  • Unified some parameter properties.
  • Removed some operators.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 14:02:47: @NimZwei commented

r13128 Fixed wrong parameter descriptions.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 14:04:11: @NimZwei commented

r13129 Removed unnecessary assembly reference.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 15:01:14: @NimZwei changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-06 15:01:14: @NimZwei changed owner from @NimZwei to @Shabbafru

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-11 16:05:47: @Shabbafru commented

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
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 14:25:06: @Shabbafru commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 14:25:20: @Shabbafru changed status from reviewing to assigned

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-13 14:25:20: @Shabbafru changed owner from @Shabbafru to @NimZwei

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 12:15:12: @NimZwei commented

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.
HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 12:41:32: @NimZwei changed status from assigned to reviewing

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 12:41:32: @NimZwei changed owner from @NimZwei to @Shabbafru

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 12:56:38: @Shabbafru commented

r13208 fixed version info of plugin

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 13:46:12: @Shabbafru commented

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.

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 14:00:08: @Shabbafru commented

Trunk Integration

r13214 moved ALPS from branch to trunk

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 14:04:06: @Shabbafru commented

r13215 (not migrated) deleted ALPS branch

HeuristicLab-Trac-Bot commented 8 years ago

2015-11-17 14:06:33: @Shabbafru commented

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