Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.MultiObjectiveLocalSearch/3.3/GSEMO.cs @ 18086

Last change on this file since 18086 was 18086, checked in by mkommend, 2 years ago

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