Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Algorithms.MultiObjectiveLocalSearch/3.3/GSEMO.cs @ 18190

Last change on this file since 18190 was 17836, checked in by abeham, 4 years ago

#3103: Add first draft of G-SEMO algorithm
File size: 20.4 KB
RevLine 
[17836]1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2021 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;
23using System.Linq;
24using HEAL.Attic;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Random;
34using HeuristicLab.Selection;
35
36namespace HeuristicLab.Algorithms.MultiObjectiveLocalSearch {
37  [Item("Simple Evolutionary Multiobjective Algorithm (G-SEMO)", "Global Simple Evolutionary MultiObjective Algorithm is implemented as described in the literature (e.g. Laumanns, M., Thiele, L. and Zitzler, E., 2004. Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem. Natural Computing, 3(1), pp. 37-51), but adds the option to evaluate additional children in each generation.")]
38  [StorableType("D9025144-B783-4484-B35B-7543C5A6D031")]
39  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
40  public class GSEMO : HeuristicOptimizationEngineAlgorithm, IStorableContent {
41    public string Filename { get; set; }
42
43    public override Type ProblemType => typeof(IMultiObjectiveHeuristicOptimizationProblem);
44
45    public new IMultiObjectiveHeuristicOptimizationProblem Problem {
46      get { return (IMultiObjectiveHeuristicOptimizationProblem)base.Problem; }
47      set { base.Problem = value; }
48    }
49
50    private IFixedValueParameter<IntValue> SeedParameter {
51      get { return (IFixedValueParameter<IntValue>)Parameters["Seed"]; }
52    }
53
54    private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
55      get { return (IFixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
56    }
57
58    public IFixedValueParameter<IntValue> MaximumGenerationsParameter {
59      get { return (IFixedValueParameter<IntValue>)Parameters["MaximumGenerations"]; }
60    }
61
62
63    public IFixedValueParameter<IntValue> PopulationSizeParameter {
64      get { return (IFixedValueParameter<IntValue>)Parameters["PopulationSize"]; }
65    }
66
67    public IFixedValueParameter<IntValue> OffspringParameter {
68      get { return (IFixedValueParameter<IntValue>)Parameters["Offspring"]; }
69    }
70
71    public IConstrainedValueParameter<IManipulator> MutatorParameter {
72      get { return (IConstrainedValueParameter<IManipulator>)Parameters["Mutator"]; }
73    }
74
75    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
76      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
77    }
78
79    public IFixedValueParameter<BoolValue> DominateOnEqualQualitiesParameter {
80      get { return (IFixedValueParameter<BoolValue>)Parameters["DominateOnEqualQualities"]; }
81    }
82
83    public int Seed {
84      get { return SeedParameter.Value.Value; }
85      set { SeedParameter.Value.Value = value; }
86    }
87
88    public bool SetSeedRandomly {
89      get { return SetSeedRandomlyParameter.Value.Value; }
90      set { SetSeedRandomlyParameter.Value.Value = value; }
91    }
92
93    public int MaximumGenerations {
94      get { return MaximumGenerationsParameter.Value.Value; }
95      set { MaximumGenerationsParameter.Value.Value = value; }
96    }
97
98    public int PopulationSize {
99      get { return PopulationSizeParameter.Value.Value; }
100      set { PopulationSizeParameter.Value.Value = value; }
101    }
102
103    public int Offspring {
104      get { return OffspringParameter.Value.Value; }
105      set { OffspringParameter.Value.Value = value; }
106    }
107
108    public IManipulator Mutator {
109      get { return MutatorParameter.Value; }
110      set {
111        if (!MutatorParameter.ValidValues.Contains(value))
112          MutatorParameter.ValidValues.Add(value);
113        MutatorParameter.Value = value;
114      }
115    }
116
117    public MultiAnalyzer Analyzer {
118      get { return AnalyzerParameter.Value; }
119      set { AnalyzerParameter.Value = value; }
120    }
121
122    public bool DominateOnEqualQualities {
123      get { return DominateOnEqualQualitiesParameter.Value.Value; }
124      set { DominateOnEqualQualitiesParameter.Value.Value = value; }
125    }
126
127    [Storable]
128    private RankBasedParetoFrontAnalyzer paretoFrontAnalyzer;
129    [Storable]
130    private RandomCreator randomCreator;
131    [Storable]
132    private SolutionsCreator solutionsCreator;
133    [Storable]
134    private CrowdingDistanceAssignment popSizeCrowding;
135
136    [StorableConstructor]
137    protected GSEMO(StorableConstructorFlag _) : base(_) { }
138    protected GSEMO(GSEMO original, Cloner cloner)
139    : base(original, cloner) {
140      paretoFrontAnalyzer = cloner.Clone(original.paretoFrontAnalyzer);
141      randomCreator = cloner.Clone(original.randomCreator);
142      solutionsCreator = cloner.Clone(original.solutionsCreator);
143      popSizeCrowding = cloner.Clone(original.popSizeCrowding);
144      RegisterEventhandlers();
145    }
146    public GSEMO() {
147      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
148      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
149      Parameters.Add(new FixedValueParameter<IntValue>("MaximumGenerations", "Stopping criterion, terminates after this number of generations.", new IntValue(1000)));
150      Parameters.Add(new FixedValueParameter<IntValue>("PopulationSize", "The size of the pareto archive, the NSGA-II's rank and crowding sorter will be used to determine which solutions remain in the population.", new IntValue(int.MaxValue)));
151      Parameters.Add(new FixedValueParameter<IntValue>("Offspring", "The number of offspring to generate in each generation.", new IntValue(1)));
152      Parameters.Add(new ConstrainedValueParameter<IManipulator>("Mutator", "The operator that mutates a solutions slightly."));
153      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
154      Parameters.Add(new FixedValueParameter<BoolValue>("DominateOnEqualQualities", "Flag which determines wether solutions with equal quality values should be treated as dominated.", new BoolValue(false)) { Hidden = true });
155
156      randomCreator = new RandomCreator();
157      solutionsCreator = new SolutionsCreator();
158      var countInitialEvaluatedSolutions = new SubScopesCounter();
159      var resultsCollectorLoop = new ResultsCollector();
160      var variableCreator = new VariableCreator();
161      var analyzerLoop = new Placeholder();
162      var selector = new RandomSelector();
163      var generationProcessor = new SubScopesProcessor();
164      var usspManipulation = new UniformSubScopesProcessor();
165      var manipulatorPlaceholder = new Placeholder();
166      var usspEvaluation = new UniformSubScopesProcessor();
167      var evaluatorPlaceholder = new Placeholder();
168      var countEvaluatedSolutions = new SubScopesCounter();
169      var merge = new MergingReducer();
170      var nonDominatedSort = new FastNonDominatedSort();
171      var frontSelector = new LeftReducer();
172
173      var popSizeCounter = new SubScopesCounter();
174      var popSizeComparator = new Comparator();
175      var popSizeBranch = new ConditionalBranch();
176      popSizeCrowding = new CrowdingDistanceAssignment();
177      var popSizeSorter = new CrowdedComparisonSorter();
178      var popSizeSelector = new LeftSelector();
179      var popSizeTrimmer = new RightReducer();
180
181      var incrementGenerations = new IntCounter();
182      var comparator = new Comparator();
183      var conditionalBranch = new ConditionalBranch();
184      var resultsCollectorFinish = new ResultsCollector();
185      var analyzerFinish = new Placeholder();
186
187      OperatorGraph.InitialOperator = randomCreator;
188
189      randomCreator.RandomParameter.ActualName = "Random";
190      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
191      randomCreator.SeedParameter.Value = null;
192      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
193      randomCreator.SetSeedRandomlyParameter.Value = null;
194      randomCreator.Successor = variableCreator;
195
196      variableCreator.Name = "Generations := 0";
197      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Generations", new IntValue(0)));
198      variableCreator.Successor = solutionsCreator;
199
200      solutionsCreator.Name = "Create initial solution";
201      solutionsCreator.NumberOfSolutionsParameter.Value = new IntValue(1);
202      solutionsCreator.Successor = countInitialEvaluatedSolutions;
203
204      countInitialEvaluatedSolutions.Name = "Initialize EvaluatedSolutions";
205      countInitialEvaluatedSolutions.ValueParameter.ActualName = "EvaluatedSolutions";
206      countInitialEvaluatedSolutions.Successor = resultsCollectorLoop;
207
208      resultsCollectorLoop.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
209      resultsCollectorLoop.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
210      resultsCollectorLoop.ResultsParameter.ActualName = "Results";
211      resultsCollectorLoop.Successor = analyzerLoop;
212
213      analyzerLoop.Name = "(Analyzer)";
214      analyzerLoop.OperatorParameter.ActualName = AnalyzerParameter.Name;
215      analyzerLoop.Successor = selector;
216
217      selector.NumberOfSelectedSubScopesParameter.Value = null;
218      selector.NumberOfSelectedSubScopesParameter.ActualName = OffspringParameter.Name;
219      selector.RandomParameter.ActualName = "Random";
220      selector.CopySelected = new BoolValue(true);
221      selector.Successor = generationProcessor;
222
223      generationProcessor.Name = "Process Generations";
224      generationProcessor.Operators.Add(new EmptyOperator() { Name = "Leave Parent Population" });
225      generationProcessor.Operators.Add(usspManipulation);
226      generationProcessor.Successor = merge;
227
228      usspManipulation.Name = "Mutate Child Population";
229      usspManipulation.Parallel = new BoolValue(false);
230      usspManipulation.Operator = manipulatorPlaceholder;
231      usspManipulation.Successor = usspEvaluation;
232
233      manipulatorPlaceholder.Name = "(Manipulator)";
234      manipulatorPlaceholder.OperatorParameter.ActualName = MutatorParameter.Name;
235
236      usspEvaluation.Parallel = new BoolValue(true);
237      usspEvaluation.Operator = evaluatorPlaceholder;
238      usspEvaluation.Successor = countEvaluatedSolutions;
239
240      evaluatorPlaceholder.Name = "(Evaluate)";
241      evaluatorPlaceholder.OperatorParameter.ActualName = "Evaluator";
242
243      countEvaluatedSolutions.Name = "Increment EvaluatedSolutions";
244      countEvaluatedSolutions.ValueParameter.ActualName = "EvaluatedSolutions";
245
246      merge.Successor = nonDominatedSort;
247
248      nonDominatedSort.Name = "Calculate Fronts";
249      nonDominatedSort.DominateOnEqualQualitiesParameter.ActualName = DominateOnEqualQualitiesParameter.Name;
250      nonDominatedSort.Successor = frontSelector;
251
252      frontSelector.Name = "Keep Best Front";
253      frontSelector.Successor = popSizeCounter;
254
255      popSizeCounter.Name = "Count Population";
256      popSizeCounter.AccumulateParameter.Value = new BoolValue(false);
257      popSizeCounter.ValueParameter.ActualName = "CurrentPopulationSize";
258      popSizeCounter.Successor = popSizeComparator;
259
260      popSizeComparator.Name = "CurrentPopulationSize > PopulationSize ?";
261      popSizeComparator.LeftSideParameter.ActualName = "CurrentPopulationSize";
262      popSizeComparator.RightSideParameter.Value = null;
263      popSizeComparator.RightSideParameter.ActualName = PopulationSizeParameter.Name;
264      popSizeComparator.Comparison.Value = ComparisonType.Greater;
265      popSizeComparator.ResultParameter.ActualName = "TrimPopulation";
266      popSizeComparator.Successor = popSizeBranch;
267
268      popSizeBranch.Name = "Trim Population ?";
269      popSizeBranch.ConditionParameter.ActualName = "TrimPopulation";
270      popSizeBranch.TrueBranch = popSizeCrowding;
271      popSizeBranch.Successor = incrementGenerations;
272
273      popSizeCrowding.CrowdingDistanceParameter.Depth = 1;
274      popSizeCrowding.Successor = popSizeSorter;
275
276      popSizeSorter.CrowdingDistanceParameter.ActualName = popSizeCrowding.CrowdingDistanceParameter.ActualName;
277      popSizeSorter.RankParameter.ActualName = nonDominatedSort.RankParameter.ActualName;
278      popSizeSorter.RankParameter.Depth = 1;
279      popSizeSorter.Successor = popSizeSelector;
280
281      popSizeSelector.CopySelected = new BoolValue(false);
282      popSizeSelector.NumberOfSelectedSubScopesParameter.Value = null;
283      popSizeSelector.NumberOfSelectedSubScopesParameter.ActualName = PopulationSizeParameter.Name;
284      popSizeSelector.Successor = popSizeTrimmer;
285
286      popSizeTrimmer.Name = "Trim PopulationSize";
287      popSizeTrimmer.Successor = null;
288
289      incrementGenerations.Name = "Generations++";
290      incrementGenerations.Increment = new IntValue(1);
291      incrementGenerations.ValueParameter.ActualName = "Generations";
292      incrementGenerations.Successor = comparator;
293
294      comparator.Name = "Generations >= MaximumGenerations ?";
295      comparator.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
296      comparator.LeftSideParameter.ActualName = "Generations";
297      comparator.ResultParameter.ActualName = "Terminate";
298      comparator.RightSideParameter.ActualName = "MaximumGenerations";
299      comparator.Successor = conditionalBranch;
300
301      conditionalBranch.Name = "Terminate?";
302      conditionalBranch.ConditionParameter.ActualName = "Terminate";
303      conditionalBranch.FalseBranch = resultsCollectorLoop;
304      conditionalBranch.TrueBranch = resultsCollectorFinish;
305
306      resultsCollectorFinish.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
307      resultsCollectorFinish.CollectedValues.Add(new LookupParameter<IntValue>("Generations"));
308      resultsCollectorFinish.ResultsParameter.ActualName = "Results";
309      resultsCollectorFinish.Successor = analyzerFinish;
310
311      analyzerFinish.Name = "(Analyzer)";
312      analyzerFinish.OperatorParameter.ActualName = AnalyzerParameter.Name;
313
314      paretoFrontAnalyzer = new RankBasedParetoFrontAnalyzer();
315      paretoFrontAnalyzer.RankParameter.ActualName = "Rank";
316      paretoFrontAnalyzer.RankParameter.Depth = 1;
317      paretoFrontAnalyzer.ResultsParameter.ActualName = "Results";
318
319      ParameterizeAnalyzers();
320      UpdateAnalyzers();
321
322      RegisterEventhandlers();
323    }
324
325    public override IDeepCloneable Clone(Cloner cloner) {
326      return new GSEMO(this, cloner);
327    }
328
329    [StorableHook(HookType.AfterDeserialization)]
330    private void AfterDeserialization() {
331      RegisterEventhandlers();
332    }
333
334    private void RegisterEventhandlers() {
335      if (Problem != null) {
336        Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
337      }
338    }
339
340    public override void Prepare() {
341      if (Problem != null) base.Prepare();
342    }
343
344    #region Events
345    protected override void OnProblemChanged() {
346      ParameterizeStochasticOperator(Problem.SolutionCreator);
347      ParameterizeStochasticOperator(Problem.Evaluator);
348      foreach (var op in Problem.Operators.OfType<IOperator>()) ParameterizeStochasticOperator(op);
349      ParameterizeSolutionsCreator();
350      ParameterizeAnalyzers();
351      ParameterizeQualitiesOperators();
352      ParameterizeIterationBasedOperators();
353      UpdateMutators();
354      UpdateAnalyzers();
355      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
356      base.OnProblemChanged();
357    }
358
359    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
360      ParameterizeStochasticOperator(Problem.SolutionCreator);
361      ParameterizeSolutionsCreator();
362      base.Problem_SolutionCreatorChanged(sender, e);
363    }
364    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
365      ParameterizeStochasticOperator(Problem.Evaluator);
366      ParameterizeSolutionsCreator();
367      ParameterizeAnalyzers();
368      ParameterizeQualitiesOperators();
369      Problem.Evaluator.QualitiesParameter.ActualNameChanged += new EventHandler(Evaluator_QualitiesParameter_ActualNameChanged);
370      base.Problem_EvaluatorChanged(sender, e);
371    }
372    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
373      foreach (var op in Problem.Operators.OfType<IOperator>()) ParameterizeStochasticOperator(op);
374      ParameterizeIterationBasedOperators();
375      UpdateMutators();
376      UpdateAnalyzers();
377      base.Problem_OperatorsChanged(sender, e);
378    }
379    private void Evaluator_QualitiesParameter_ActualNameChanged(object sender, EventArgs e) {
380      ParameterizeAnalyzers();
381      ParameterizeQualitiesOperators();
382    }
383    #endregion
384
385    private void ParameterizeSolutionsCreator() {
386      solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
387      solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
388    }
389    private void ParameterizeStochasticOperator(IOperator op) {
390      var stochasticOp = op as IStochasticOperator;
391      if (stochasticOp != null) {
392        stochasticOp.RandomParameter.ActualName = randomCreator.RandomParameter.ActualName;
393        stochasticOp.RandomParameter.Hidden = true;
394      }
395    }
396    private void ParameterizeAnalyzers() {
397      paretoFrontAnalyzer.ResultsParameter.ActualName = "Results";
398      paretoFrontAnalyzer.ResultsParameter.Hidden = true;
399      if (Problem != null) {
400        paretoFrontAnalyzer.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.ActualName;
401        paretoFrontAnalyzer.QualitiesParameter.Depth = 1;
402        paretoFrontAnalyzer.QualitiesParameter.Hidden = true;
403      }
404    }
405    private void ParameterizeIterationBasedOperators() {
406      if (Problem != null) {
407        foreach (var op in Problem.Operators.OfType<IIterationBasedOperator>()) {
408          op.IterationsParameter.ActualName = "Generations";
409          op.IterationsParameter.Hidden = true;
410          op.MaximumIterationsParameter.ActualName = "MaximumGenerations";
411          op.MaximumIterationsParameter.Hidden = true;
412        }
413      }
414    }
415    private void ParameterizeQualitiesOperators() {
416      if (Problem != null) {
417        popSizeCrowding.QualitiesParameter.ActualName = Problem.Evaluator.QualitiesParameter.Name;
418      }
419    }
420    private void UpdateMutators() {
421      var oldMutator = MutatorParameter.Value;
422      MutatorParameter.ValidValues.Clear();
423      var defaultMutator = Problem.Operators.Where(x => !(x is ISingleObjectiveOperator)).OfType<IManipulator>().FirstOrDefault();
424
425      foreach (var mutator in Problem.Operators.Where(x => !(x is ISingleObjectiveOperator)).OfType<IManipulator>().OrderBy(x => x.Name))
426        MutatorParameter.ValidValues.Add(mutator);
427
428      if (oldMutator != null) {
429        var mutator = MutatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMutator.GetType());
430        if (mutator != null) MutatorParameter.Value = mutator;
431        else oldMutator = null;
432      }
433
434      if (oldMutator == null && defaultMutator != null)
435        MutatorParameter.Value = defaultMutator;
436    }
437    private void UpdateAnalyzers() {
438      Analyzer.Operators.Clear();
439      if (Problem != null) {
440        foreach (var analyzer in Problem.Operators.Where(x => !(x is ISingleObjectiveOperator)).OfType<IAnalyzer>()) {
441          foreach (var param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
442            param.Depth = 1;
443          Analyzer.Operators.Add(analyzer, analyzer.EnabledByDefault);
444        }
445      }
446      Analyzer.Operators.Add(paretoFrontAnalyzer, paretoFrontAnalyzer.EnabledByDefault);
447    }
448
449  }
450}
Note: See TracBrowser for help on using the repository browser.