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

Last change on this file since 13111 was 13111, checked in by pfleck, 7 years ago

#2269

  • 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.
File size: 14.6 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();
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>("GenerationsSinceLastRefresh", new IntValue(0)));
98      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("OpenLayers", new IntValue(1)));
99      variableCreator.Successor = initLayerAnalyzerProcessor;
100
101      initLayerAnalyzerProcessor.Operators.Add(layerVariableCreator);
102      initLayerAnalyzerProcessor.Successor = initAnalyzerPlaceholder;
103
104      layerVariableCreator.CollectedValues.Add(new ValueParameter<IntValue>("LayerEvaluatedSolutions"));
105      layerVariableCreator.CollectedValues.Add(new ValueParameter<ResultCollection>("LayerResults"));
106      layerVariableCreator.Successor = initLayerAnalyzerPlaceholder;
107
108      initLayerAnalyzerPlaceholder.OperatorParameter.ActualName = LayerAnalyzerParameter.Name;
109      initLayerAnalyzerPlaceholder.Successor = null;
110
111      initAnalyzerPlaceholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
112      initAnalyzerPlaceholder.Successor = resultsCollector;
113
114      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
115      resultsCollector.CollectedValues.Add(new ScopeTreeLookupParameter<ResultCollection>("LayerResults", "Result set for each layer", "LayerResults"));
116      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("OpenLayers"));
117      resultsCollector.CopyValue = new BoolValue(false);
118      resultsCollector.Successor = matingPoolCreator;
119
120      matingPoolCreator.Successor = matingPoolProcessor;
121
122      matingPoolProcessor.Parallel.Value = true;
123      matingPoolProcessor.Operator = initializeLayer;
124      matingPoolProcessor.Successor = generationsIcrementor;
125
126      initializeLayer.LeftSideParameter.ActualName = "LayerEvaluatedSolutions";
127      initializeLayer.RightSideParameter.Value = new IntValue(0);
128      initializeLayer.Successor = mainOperator;
129
130      generationsIcrementor.ValueParameter.ActualName = "Generations";
131      generationsIcrementor.Increment = new IntValue(1);
132      generationsIcrementor.Successor = evaluatedSolutionsReducer;
133
134      evaluatedSolutionsReducer.ParameterToReduce.ActualName = "LayerEvaluatedSolutions";
135      evaluatedSolutionsReducer.TargetParameter.ActualName = "EvaluatedSolutions";
136      evaluatedSolutionsReducer.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
137      evaluatedSolutionsReducer.TargetOperation.Value = new ReductionOperation(ReductionOperations.Sum);
138      evaluatedSolutionsReducer.Successor = eldersEmigrator;
139
140      eldersEmigrator.Successor = layerOpener;
141
142      layerOpener.Successor = layerReseeder;
143
144      layerReseeder.Successor = layerAnalyzerProcessor;
145
146      layerAnalyzerProcessor.Operator = layerAnalyzerPlaceholder;
147      layerAnalyzerProcessor.Successor = analyzerPlaceholder;
148
149      layerAnalyzerPlaceholder.OperatorParameter.ActualName = LayerAnalyzerParameter.Name;
150
151      analyzerPlaceholder.OperatorParameter.ActualName = AnalyzerParameter.Name;
152      analyzerPlaceholder.Successor = termination;
153
154      termination.ContinueBranch = matingPoolCreator;
155    }
156
157    private static CombinedOperator CreateEldersEmigrator() {
158      var eldersEmigrator = new CombinedOperator() { Name = "Emigrate Elders" };
159      var selectorProsessor = new UniformSubScopesProcessor();
160      var eldersSelector = new EldersSelector();
161      var shiftToRightMigrator = new UnidirectionalRingMigrator();
162      var mergingProsessor = new UniformSubScopesProcessor();
163      var mergingReducer = new MergingReducer();
164      var subScopesCounter = new SubScopesCounter();
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 = countCalculator;
184
185      countCalculator.CollectedValues.Add(new LookupParameter<IntValue>("PopulationSize"));
186      countCalculator.CollectedValues.Add(new LookupParameter<IntValue>("LayerPopulationSize"));
187      countCalculator.ExpressionParameter.Value = new StringValue("LayerPopulationSize PopulationSize LayerPopulationSize PopulationSize < if toint");
188      countCalculator.ExpressionResultParameter.ActualName = "LayerPopulationSize";
189      countCalculator.Successor = bestSelector;
190
191      bestSelector.NumberOfSelectedSubScopesParameter.ActualName = "LayerPopulationSize";
192      bestSelector.CopySelected = new BoolValue(false);
193      bestSelector.Successor = rightReducer;
194
195      return eldersEmigrator;
196    }
197
198    private static CombinedOperator CreateLayerOpener() {
199      var layerOpener = new CombinedOperator() { Name = "Open new Layer if needed" };
200      var maxLayerReached = new Comparator() { Name = "MaxLayersReached = OpenLayers >= NumberOfLayers" };
201      var maxLayerReachedBranch = new ConditionalBranch() { Name = "MaxLayersReached?" };
202      var openNewLayerCalculator = new ExpressionCalculator() { Name = "OpenNewLayer = Generations >= AgeLimits[OpenLayers - 1]" };
203      var openNewLayerBranch = new ConditionalBranch() { Name = "OpenNewLayer?" };
204      var layerCreator = new LayerCreator() { Name = "Create Layer" };
205      var createChildrenViaCrossover = AlpsGeneticAlgorithmMainOperator.Create();
206      var incrEvaluatedSolutionsForNewLayer = new SubScopesCounter() { Name = "Update EvaluatedSolutions" };
207      var incrOpenLayers = new IntCounter() { Name = "Incr. OpenLayers" };
208      var newLayerResultsCollector = new ResultsCollector() { Name = "Collect new Layer Results" };
209
210      layerOpener.OperatorGraph.InitialOperator = maxLayerReached;
211
212      maxLayerReached.LeftSideParameter.ActualName = "OpenLayers";
213      maxLayerReached.RightSideParameter.ActualName = "NumberOfLayers";
214      maxLayerReached.ResultParameter.ActualName = "MaxLayerReached";
215      maxLayerReached.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
216      maxLayerReached.Successor = maxLayerReachedBranch;
217
218      maxLayerReachedBranch.ConditionParameter.ActualName = "MaxLayerReached";
219      maxLayerReachedBranch.FalseBranch = openNewLayerCalculator;
220
221      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntArray>("AgeLimits"));
222      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
223      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("NumberOfLayers"));
224      openNewLayerCalculator.CollectedValues.Add(new LookupParameter<IntValue>("OpenLayers"));
225      openNewLayerCalculator.ExpressionResultParameter.ActualName = "OpenNewLayer";
226      openNewLayerCalculator.ExpressionParameter.Value = new StringValue("Generations 1 + AgeLimits OpenLayers 1 - [] >");
227      openNewLayerCalculator.Successor = openNewLayerBranch;
228
229      openNewLayerBranch.ConditionParameter.ActualName = "OpenNewLayer";
230      openNewLayerBranch.TrueBranch = layerCreator;
231
232      layerCreator.NewLayerOperator = createChildrenViaCrossover;
233      layerCreator.Successor = incrOpenLayers;
234
235      createChildrenViaCrossover.Successor = incrEvaluatedSolutionsForNewLayer;
236
237      incrEvaluatedSolutionsForNewLayer.ValueParameter.ActualName = "EvaluatedSolutions";
238      incrEvaluatedSolutionsForNewLayer.AccumulateParameter.Value = new BoolValue(true);
239
240      incrOpenLayers.ValueParameter.ActualName = "OpenLayers";
241      incrOpenLayers.Increment = new IntValue(1);
242      incrOpenLayers.Successor = newLayerResultsCollector;
243
244      newLayerResultsCollector.CollectedValues.Add(new ScopeTreeLookupParameter<ResultCollection>("LayerResults", "Result set for each layer", "LayerResults"));
245      newLayerResultsCollector.CopyValue = new BoolValue(false);
246      newLayerResultsCollector.Successor = null;
247
248      return layerOpener;
249    }
250
251    private static CombinedOperator CreateReseeder() {
252      var reseeder = new CombinedOperator() { Name = "Reseed Layer Zero if needed" };
253      var reseedingController = new ReseedingController() { Name = "Reseeding needed (Generation % AgeGap == 0)?" };
254      var removeIndividuals = new SubScopesRemover();
255      var createIndividuals = new SolutionsCreator();
256      var initializeAgeProsessor = new UniformSubScopesProcessor();
257      var initializeAge = new VariableCreator() { Name = "Initialize Age" };
258      var incrEvaluatedSolutionsAfterReseeding = new SubScopesCounter() { Name = "Update EvaluatedSolutions" };
259
260      reseeder.OperatorGraph.InitialOperator = reseedingController;
261
262      reseedingController.FirstLayerOperator = removeIndividuals;
263
264      removeIndividuals.Successor = createIndividuals;
265
266      createIndividuals.NumberOfSolutionsParameter.ActualName = "PopulationSize";
267      createIndividuals.Successor = initializeAgeProsessor;
268
269      initializeAgeProsessor.Operator = initializeAge;
270      initializeAgeProsessor.Successor = incrEvaluatedSolutionsAfterReseeding;
271
272      initializeAge.CollectedValues.Add(new ValueParameter<DoubleValue>("Age", new DoubleValue(0)));
273
274      incrEvaluatedSolutionsAfterReseeding.ValueParameter.ActualName = "EvaluatedSolutions";
275      incrEvaluatedSolutionsAfterReseeding.AccumulateParameter.Value = new BoolValue(true);
276
277      return reseeder;
278    }
279  }
280}
Note: See TracBrowser for help on using the repository browser.