Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ALPS/HeuristicLab.Algorithms.ALPS/3.3/AlpsGeneticAlgorithmMainLoop.cs @ 13117

Last change on this file since 13117 was 13117, checked in by pfleck, 9 years ago

#2269 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.

File size: 14.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System.Linq;
23using HeuristicLab.Algorithms.GeneticAlgorithm;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.Selection;
33
34namespace HeuristicLab.Algorithms.ALPS {
35
36  [Item("AlpsGeneticAlgorithmMainLoop", "An ALPS genetic algorithm main loop operator.")]
37  [StorableClass]
38  public sealed class AlpsGeneticAlgorithmMainLoop : AlgorithmOperator {
39    #region Parameter Properties
40    public ValueLookupParameter<BoolValue> MaximizationParameter {
41      get { return (ValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
42    }
43    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
44      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
45    }
46    public ILookupParameter<IOperator> AnalyzerParameter {
47      get { return (ILookupParameter<IOperator>)Parameters["Analyzer"]; }
48    }
49    public ILookupParameter<IOperator> LayerAnalyzerParameter {
50      get { return (ILookupParameter<IOperator>)Parameters["LayerAnalyzer"]; }
51    }
52    #endregion
53
54    public GeneticAlgorithmMainLoop MainOperator {
55      get { return OperatorGraph.Iterate().OfType<GeneticAlgorithmMainLoop>().First(); }
56    }
57
58    [StorableConstructor]
59    private AlpsGeneticAlgorithmMainLoop(bool deserializing)
60      : base(deserializing) { }
61    private AlpsGeneticAlgorithmMainLoop(AlpsGeneticAlgorithmMainLoop original, Cloner cloner)
62      : base(original, cloner) { }
63    public override IDeepCloneable Clone(Cloner cloner) {
64      return new AlpsGeneticAlgorithmMainLoop(this, cloner);
65    }
66    public AlpsGeneticAlgorithmMainLoop()
67      : base() {
68      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false.") { Hidden = true });
69      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The value which represents the quality of a solution."));
70      Parameters.Add(new LookupParameter<IntValue>("MaximumGenerations", "The maximum number of generations that the algorithm should process."));
71      Parameters.Add(new LookupParameter<IOperator>("Analyzer", "The operator used to the analyze all individuals."));
72      Parameters.Add(new LookupParameter<IOperator>("LayerAnalyzer", "The operator used to analyze each layer."));
73
74      var variableCreator = new VariableCreator() { Name = "Initialize" };
75      var initLayerAnalyzerProcessor = new SubScopesProcessor();
76      var layerVariableCreator = new VariableCreator() { Name = "Initialize Layer" };
77      var initLayerAnalyzerPlaceholder = new Placeholder() { Name = "LayerAnalyzer (Placeholder)" };
78      var initAnalyzerPlaceholder = new Placeholder() { Name = "Analyzer (Placeholder)" };
79      var resultsCollector = new ResultsCollector();
80      var matingPoolCreator = new MatingPoolCreator() { Name = "Create Mating Pools" };
81      var matingPoolProcessor = new UniformSubScopesProcessor() { Name = "Process Mating Pools" };
82      var initializeLayer = new Assigner() { Name = "Reset LayerEvaluatedSolutions" };
83      var mainOperator = AlpsGeneticAlgorithmMainOperator.Create();
84      var generationsIcrementor = new IntCounter() { Name = "Increment Generations" };
85      var evaluatedSolutionsReducer = new DataReducer() { Name = "Increment EvaluatedSolutions" };
86      var eldersEmigrator = CreateEldersEmigrator();
87      var layerOpener = CreateLayerOpener();
88      var layerReseeder = CreateReseeder();
89      var layerAnalyzerProcessor = new UniformSubScopesProcessor();
90      var layerAnalyzerPlaceholder = new Placeholder() { Name = "LayerAnalyzer (Placeholder)" };
91      var analyzerPlaceholder = new Placeholder() { Name = "Analyzer (Placeholder)" };
92      var termination = new TerminationOperator();
93
94      OperatorGraph.InitialOperator = variableCreator;
95
96      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Generations", new IntValue(0)));
97      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("OpenLayers", new IntValue(1)));
98      variableCreator.Successor = initLayerAnalyzerProcessor;
99
100      initLayerAnalyzerProcessor.Operators.Add(layerVariableCreator);
101      initLayerAnalyzerProcessor.Successor = initAnalyzerPlaceholder;
102
103      layerVariableCreator.CollectedValues.Add(new ValueParameter<IntValue>("LayerEvaluatedSolutions"));
104      layerVariableCreator.CollectedValues.Add(new ValueParameter<ResultCollection>("LayerResults"));
105      layerVariableCreator.Successor = initLayerAnalyzerPlaceholder;
106
107      initLayerAnalyzerPlaceholder.OperatorParameter.ActualName = LayerAnalyzerParameter.Name;
108      initLayerAnalyzerPlaceholder.Successor = null;
109
110      initAnalyzerPlaceholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
111      initAnalyzerPlaceholder.Successor = resultsCollector;
112
113      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
114      resultsCollector.CollectedValues.Add(new ScopeTreeLookupParameter<ResultCollection>("LayerResults", "Result set for each layer", "LayerResults"));
115      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("OpenLayers"));
116      resultsCollector.CopyValue = new BoolValue(false);
117      resultsCollector.Successor = matingPoolCreator;
118
119      matingPoolCreator.Successor = matingPoolProcessor;
120
121      matingPoolProcessor.Parallel.Value = true;
122      matingPoolProcessor.Operator = initializeLayer;
123      matingPoolProcessor.Successor = generationsIcrementor;
124
125      initializeLayer.LeftSideParameter.ActualName = "LayerEvaluatedSolutions";
126      initializeLayer.RightSideParameter.Value = new IntValue(0);
127      initializeLayer.Successor = mainOperator;
128
129      generationsIcrementor.ValueParameter.ActualName = "Generations";
130      generationsIcrementor.Increment = new IntValue(1);
131      generationsIcrementor.Successor = evaluatedSolutionsReducer;
132
133      evaluatedSolutionsReducer.ParameterToReduce.ActualName = "LayerEvaluatedSolutions";
134      evaluatedSolutionsReducer.TargetParameter.ActualName = "EvaluatedSolutions";
135      evaluatedSolutionsReducer.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
136      evaluatedSolutionsReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Sum);
137      evaluatedSolutionsReducer.Successor = eldersEmigrator;
138
139      eldersEmigrator.Successor = layerOpener;
140
141      layerOpener.Successor = layerReseeder;
142
143      layerReseeder.Successor = layerAnalyzerProcessor;
144
145      layerAnalyzerProcessor.Operator = layerAnalyzerPlaceholder;
146      layerAnalyzerProcessor.Successor = analyzerPlaceholder;
147
148      layerAnalyzerPlaceholder.OperatorParameter.ActualName = LayerAnalyzerParameter.Name;
149
150      analyzerPlaceholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
151      analyzerPlaceholder.Successor = termination;
152
153      termination.ContinueBranch = matingPoolCreator;
154    }
155
156    private static CombinedOperator CreateEldersEmigrator() {
157      var eldersEmigrator = new CombinedOperator() { Name = "Emigrate Elders" };
158      var selectorProsessor = new UniformSubScopesProcessor();
159      var eldersSelector = new EldersSelector();
160      var shiftToRightMigrator = new UnidirectionalRingMigrator() { Name = "Shift elders to next Layer" };
161      var mergingProsessor = new UniformSubScopesProcessor();
162      var mergingReducer = new MergingReducer();
163      var subScopesCounter = new SubScopesCounter();
164      var reduceToPopulationSizeBranch = new ConditionalBranch() { Name = "ReduceToPopulationSize?" };
165      var countCalculator = new ExpressionCalculator() { Name = "LayerPopulationSize = Min(LayerPopulationSize, PopulationSize)" };
166      var bestSelector = new BestSelector();
167      var rightReducer = new RightReducer();
168
169      eldersEmigrator.OperatorGraph.InitialOperator = selectorProsessor;
170
171      selectorProsessor.Operator = eldersSelector;
172      selectorProsessor.Successor = shiftToRightMigrator;
173
174      shiftToRightMigrator.ClockwiseMigrationParameter.Value = new BoolValue(true);
175      shiftToRightMigrator.Successor = mergingProsessor;
176
177      mergingProsessor.Operator = mergingReducer;
178
179      mergingReducer.Successor = subScopesCounter;
180
181      subScopesCounter.ValueParameter.ActualName = "LayerPopulationSize";
182      subScopesCounter.AccumulateParameter.Value = new BoolValue(false);
183      subScopesCounter.Successor = reduceToPopulationSizeBranch;
184
185      reduceToPopulationSizeBranch.ConditionParameter.ActualName = "ReduceToPopulationSize";
186      reduceToPopulationSizeBranch.TrueBranch = countCalculator;
187
188      countCalculator.CollectedValues.Add(new LookupParameter<IntValue>("PopulationSize"));
189      countCalculator.CollectedValues.Add(new LookupParameter<IntValue>("LayerPopulationSize"));
190      countCalculator.ExpressionParameter.Value = new StringValue("LayerPopulationSize PopulationSize LayerPopulationSize PopulationSize < if toint");
191      countCalculator.ExpressionResultParameter.ActualName = "LayerPopulationSize";
192      countCalculator.Successor = bestSelector;
193
194      bestSelector.NumberOfSelectedSubScopesParameter.ActualName = "LayerPopulationSize";
195      bestSelector.CopySelected = new BoolValue(false);
196      bestSelector.Successor = rightReducer;
197
198      return eldersEmigrator;
199    }
200
201    private static CombinedOperator CreateLayerOpener() {
202      var layerOpener = new CombinedOperator() { Name = "Open new Layer if needed" };
203      var maxLayerReached = new Comparator() { Name = "MaxLayersReached = OpenLayers >= NumberOfLayers" };
204      var maxLayerReachedBranch = new ConditionalBranch() { Name = "MaxLayersReached?" };
205      var openNewLayerCalculator = new ExpressionCalculator() { Name = "OpenNewLayer = Generations >= AgeLimits[OpenLayers - 1]" };
206      var openNewLayerBranch = new ConditionalBranch() { Name = "OpenNewLayer?" };
207      var layerCreator = new LayerCreator() { Name = "Create Layer" };
208      var createChildrenViaCrossover = AlpsGeneticAlgorithmMainOperator.Create();
209      var incrEvaluatedSolutionsForNewLayer = new SubScopesCounter() { Name = "Update EvaluatedSolutions" };
210      var incrOpenLayers = new IntCounter() { Name = "Incr. OpenLayers" };
211      var newLayerResultsCollector = new ResultsCollector() { Name = "Collect new Layer Results" };
212
213      layerOpener.OperatorGraph.InitialOperator = maxLayerReached;
214
215      maxLayerReached.LeftSideParameter.ActualName = "OpenLayers";
216      maxLayerReached.RightSideParameter.ActualName = "NumberOfLayers";
217      maxLayerReached.ResultParameter.ActualName = "MaxLayerReached";
218      maxLayerReached.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
219      maxLayerReached.Successor = maxLayerReachedBranch;
220
221      maxLayerReachedBranch.ConditionParameter.ActualName = "MaxLayerReached";
222      maxLayerReachedBranch.FalseBranch = openNewLayerCalculator;
223
224      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntArray>("AgeLimits"));
225      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
226      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("NumberOfLayers"));
227      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("OpenLayers"));
228      openNewLayerCalculator.ExpressionResultParameter.ActualName = "OpenNewLayer";
229      openNewLayerCalculator.ExpressionParameter.Value = new StringValue("Generations 1 + AgeLimits OpenLayers 1 - [] >");
230      openNewLayerCalculator.Successor = openNewLayerBranch;
231
232      openNewLayerBranch.ConditionParameter.ActualName = "OpenNewLayer";
233      openNewLayerBranch.TrueBranch = layerCreator;
234
235      layerCreator.NewLayerOperator = createChildrenViaCrossover;
236      layerCreator.Successor = incrOpenLayers;
237
238      createChildrenViaCrossover.Successor = incrEvaluatedSolutionsForNewLayer;
239
240      incrEvaluatedSolutionsForNewLayer.ValueParameter.ActualName = "EvaluatedSolutions";
241      incrEvaluatedSolutionsForNewLayer.AccumulateParameter.Value = new BoolValue(true);
242
243      incrOpenLayers.ValueParameter.ActualName = "OpenLayers";
244      incrOpenLayers.Increment = new IntValue(1);
245      incrOpenLayers.Successor = newLayerResultsCollector;
246
247      newLayerResultsCollector.CollectedValues.Add(new ScopeTreeLookupParameter<ResultCollection>("LayerResults", "Result set for each layer", "LayerResults"));
248      newLayerResultsCollector.CopyValue = new BoolValue(false);
249      newLayerResultsCollector.Successor = null;
250
251      return layerOpener;
252    }
253
254    private static CombinedOperator CreateReseeder() {
255      var reseeder = new CombinedOperator() { Name = "Reseed Layer Zero if needed" };
256      var reseedingController = new ReseedingController() { Name = "Reseeding needed (Generation % AgeGap == 0)?" };
257      var removeIndividuals = new SubScopesRemover();
258      var createIndividuals = new SolutionsCreator();
259      var initializeAgeProsessor = new UniformSubScopesProcessor();
260      var initializeAge = new VariableCreator() { Name = "Initialize Age" };
261      var incrEvaluatedSolutionsAfterReseeding = new SubScopesCounter() { Name = "Update EvaluatedSolutions" };
262
263      reseeder.OperatorGraph.InitialOperator = reseedingController;
264
265      reseedingController.FirstLayerOperator = removeIndividuals;
266
267      removeIndividuals.Successor = createIndividuals;
268
269      createIndividuals.NumberOfSolutionsParameter.ActualName = "PopulationSize";
270      createIndividuals.Successor = initializeAgeProsessor;
271
272      initializeAgeProsessor.Operator = initializeAge;
273      initializeAgeProsessor.Successor = incrEvaluatedSolutionsAfterReseeding;
274
275      initializeAge.CollectedValues.Add(new ValueParameter<DoubleValue>("Age", new DoubleValue(0)));
276
277      incrEvaluatedSolutionsAfterReseeding.ValueParameter.ActualName = "EvaluatedSolutions";
278      incrEvaluatedSolutionsAfterReseeding.AccumulateParameter.Value = new BoolValue(true);
279
280      return reseeder;
281    }
282  }
283}
Note: See TracBrowser for help on using the repository browser.