source: trunk/sources/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs @ 15051

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

#2783:

  • Implemented GetBestIndividual as public static and protected method in SingleObjectiveBasicProblem
  • Impblemented GetParetorFronts as public static and protected method in MultiObjectiveBasicProblem
  • Implemented AddOrUpdateResult as public method in ResultCollection
File size: 8.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Optimization {
32  [StorableClass]
33  public abstract class MultiObjectiveBasicProblem<TEncoding> : BasicProblem<TEncoding, MultiObjectiveEvaluator>, IMultiObjectiveHeuristicOptimizationProblem, IMultiObjectiveProblemDefinition
34  where TEncoding : class, IEncoding {
35    [StorableConstructor]
36    protected MultiObjectiveBasicProblem(bool deserializing) : base(deserializing) { }
37
38    protected MultiObjectiveBasicProblem(MultiObjectiveBasicProblem<TEncoding> original, Cloner cloner)
39      : base(original, cloner) {
40      ParameterizeOperators();
41    }
42
43    protected MultiObjectiveBasicProblem()
44      : base() {
45      Parameters.Add(new ValueParameter<BoolArray>("Maximization", "Set to false if the problem should be minimized.", (BoolArray)new BoolArray(Maximization).AsReadOnly()));
46
47      Operators.Add(Evaluator);
48      Operators.Add(new MultiObjectiveAnalyzer());
49
50      ParameterizeOperators();
51    }
52
53    [StorableHook(HookType.AfterDeserialization)]
54    private void AfterDeserialization() {
55      ParameterizeOperators();
56    }
57
58    public abstract bool[] Maximization { get; }
59    public abstract double[] Evaluate(Individual individual, IRandom random);
60    public virtual void Analyze(Individual[] individuals, double[][] qualities, ResultCollection results, IRandom random) { }
61
62    protected List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool dominateOnEqualQualities = true) {
63      return GetParetoFronts(individuals, qualities, Maximization, dominateOnEqualQualities);
64    }
65    public static List<List<Tuple<Individual, double[]>>> GetParetoFronts(Individual[] individuals, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
66      int populationSize = individuals.Length;
67
68      var fronts = new List<List<Tuple<Individual, double[]>>>();
69      fronts.Add(new List<Tuple<Individual, double[]>>());
70      Dictionary<Individual, List<int>> dominatedIndividuals = new Dictionary<Individual, List<int>>();
71      int[] dominationCounter = new int[populationSize];
72      ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
73
74      for (int pI = 0; pI < populationSize - 1; pI++) {
75        var p = individuals[pI];
76        List<int> dominatedIndividualsByp;
77        if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
78          dominatedIndividuals[p] = dominatedIndividualsByp = new List<int>();
79        for (int qI = pI + 1; qI < populationSize; qI++) {
80          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
81          if (test == 1) {
82            dominatedIndividualsByp.Add(qI);
83            dominationCounter[qI] += 1;
84          } else if (test == -1) {
85            dominationCounter[pI] += 1;
86            if (!dominatedIndividuals.ContainsKey(individuals[qI]))
87              dominatedIndividuals.Add(individuals[qI], new List<int>());
88            dominatedIndividuals[individuals[qI]].Add(pI);
89          }
90          if (pI == populationSize - 2
91            && qI == populationSize - 1
92            && dominationCounter[qI] == 0) {
93            rank[qI] = new IntValue(0);
94            fronts[0].Add(Tuple.Create(individuals[qI], qualities[qI]));
95          }
96        }
97        if (dominationCounter[pI] == 0) {
98          rank[pI] = new IntValue(0);
99          fronts[0].Add(Tuple.Create(p, qualities[pI]));
100        }
101      }
102      int i = 0;
103      while (i < fronts.Count && fronts[i].Count > 0) {
104        var nextFront = new List<Tuple<Individual, double[]>>();
105        foreach (var p in fronts[i]) {
106          List<int> dominatedIndividualsByp;
107          if (dominatedIndividuals.TryGetValue(p.Item1, out dominatedIndividualsByp)) {
108            for (int k = 0; k < dominatedIndividualsByp.Count; k++) {
109              int dominatedIndividual = dominatedIndividualsByp[k];
110              dominationCounter[dominatedIndividual] -= 1;
111              if (dominationCounter[dominatedIndividual] == 0) {
112                rank[dominatedIndividual] = new IntValue(i + 1);
113                nextFront.Add(Tuple.Create(individuals[dominatedIndividual], qualities[dominatedIndividual]));
114              }
115            }
116          }
117        }
118        i += 1;
119        fronts.Add(nextFront);
120      }
121      return fronts;
122    }
123
124    private static int Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
125      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
126      if (dominateOnEqualQualities) {
127        var equal = true;
128        for (int i = 0; i < left.Length; i++) {
129          if (left[i] != right[i]) {
130            equal = false;
131            break;
132          }
133        }
134        if (equal) return 1;
135      }
136
137      bool leftIsBetter = false, rightIsBetter = false;
138      for (int i = 0; i < left.Length; i++) {
139        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
140        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
141        if (leftIsBetter && rightIsBetter) break;
142      }
143
144      if (leftIsBetter && !rightIsBetter) return 1;
145      if (!leftIsBetter && rightIsBetter) return -1;
146      return 0;
147    }
148
149    private static bool IsDominated(double left, double right, bool maximization) {
150      return maximization && left < right
151        || !maximization && left > right;
152    }
153
154    protected override void OnOperatorsChanged() {
155      base.OnOperatorsChanged();
156      if (Encoding != null) {
157        PruneSingleObjectiveOperators(Encoding);
158        var multiEncoding = Encoding as MultiEncoding;
159        if (multiEncoding != null) {
160          foreach (var encoding in multiEncoding.Encodings.ToList()) {
161            PruneSingleObjectiveOperators(encoding);
162          }
163        }
164      }
165    }
166
167    private void PruneSingleObjectiveOperators(IEncoding encoding) {
168      if (encoding != null && encoding.Operators.Any(x => x is ISingleObjectiveOperator && !(x is IMultiObjectiveOperator)))
169        encoding.Operators = encoding.Operators.Where(x => !(x is ISingleObjectiveOperator) || x is IMultiObjectiveOperator).ToList();
170    }
171
172    protected override void OnEvaluatorChanged() {
173      base.OnEvaluatorChanged();
174      ParameterizeOperators();
175    }
176
177    private void ParameterizeOperators() {
178      foreach (var op in Operators.OfType<IMultiObjectiveEvaluationOperator>())
179        op.EvaluateFunc = Evaluate;
180      foreach (var op in Operators.OfType<IMultiObjectiveAnalysisOperator>())
181        op.AnalyzeAction = Analyze;
182    }
183
184
185    #region IMultiObjectiveHeuristicOptimizationProblem Members
186    IParameter IMultiObjectiveHeuristicOptimizationProblem.MaximizationParameter {
187      get { return Parameters["Maximization"]; }
188    }
189    IMultiObjectiveEvaluator IMultiObjectiveHeuristicOptimizationProblem.Evaluator {
190      get { return Evaluator; }
191    }
192    #endregion
193  }
194}
Note: See TracBrowser for help on using the repository browser.