source: trunk/sources/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs @ 15080

Last change on this file since 15080 was 15080, checked in by abeham, 3 years ago

#2783: Moved pareto front calculation from MultiObjectiveBasicProblem to a new class DominationCalculator<T>. Changed FastNonDominatedSort to use the new class.

File size: 9.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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 HeuristicLab.Core;
25using HeuristicLab.Data;
26
27namespace HeuristicLab.Optimization {
28  public enum DominationResult { Dominates, IsDominated, IsNonDominated };
29
30  public static class DominationCalculator<T> {
31    /// <summary>
32    /// Calculates the best pareto front only. The fast non-dominated sorting algorithm is used
33    /// as described in Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
34    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
35    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
36    /// </summary>
37    /// <remarks>
38    /// When there are plateaus in the fitness landscape several solutions might have exactly
39    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
40    /// can be set to true to avoid plateaus becoming too attractive for the search process.
41    /// </remarks>
42    /// <param name="solutions">The solutions of the population.</param>
43    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
44    /// <param name="maximization">The objective in each dimension.</param>
45    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
46    /// <returns>The pareto front containing the best solutions and their associated quality resp. fitness.</returns>
47    public static List<Tuple<T, double[]>> CalculateBestParetoFront(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
48      int populationSize = solutions.Length;
49
50      Dictionary<T, List<int>> dominatedIndividuals;
51      int[] dominationCounter, rank;
52      return CalculateBestFront(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, out dominatedIndividuals, out dominationCounter, out rank);
53    }
54
55    /// <summary>
56    /// Calculates all pareto fronts. The first in the list is the best front.
57    /// The fast non-dominated sorting algorithm is used as described in
58    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
59    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
60    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
61    /// </summary>
62    /// <remarks>
63    /// When there are plateaus in the fitness landscape several solutions might have exactly
64    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
65    /// can be set to true to avoid plateaus becoming too attractive for the search process.
66    /// </remarks>
67    /// <param name="solutions">The solutions of the population.</param>
68    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
69    /// <param name="maximization">The objective in each dimension.</param>
70    /// <param name="rank">The rank of each of the solutions, corresponds to the front it is put in.</param>
71    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
72    /// <returns>A sorted list of the pareto fronts from best to worst.</returns>
73    public static List<List<Tuple<T, double[]>>> CalculateAllParetoFronts(T[] solutions, double[][] qualities, bool[] maximization, out int[] rank, bool dominateOnEqualQualities = true) {
74      int populationSize = solutions.Length;
75
76      Dictionary<T, List<int>> dominatedIndividuals;
77      int[] dominationCounter;
78      var fronts = new List<List<Tuple<T, double[]>>>();
79      fronts.Add(CalculateBestFront(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, out dominatedIndividuals, out dominationCounter, out rank));
80      int i = 0;
81      while (i < fronts.Count && fronts[i].Count > 0) {
82        var nextFront = new List<Tuple<T, double[]>>();
83        foreach (var p in fronts[i]) {
84          List<int> dominatedIndividualsByp;
85          if (dominatedIndividuals.TryGetValue(p.Item1, out dominatedIndividualsByp)) {
86            for (int k = 0; k < dominatedIndividualsByp.Count; k++) {
87              int dominatedIndividual = dominatedIndividualsByp[k];
88              dominationCounter[dominatedIndividual] -= 1;
89              if (dominationCounter[dominatedIndividual] == 0) {
90                rank[dominatedIndividual] = i + 1;
91                nextFront.Add(Tuple.Create(solutions[dominatedIndividual], qualities[dominatedIndividual]));
92              }
93            }
94          }
95        }
96        i += 1;
97        fronts.Add(nextFront);
98      }
99      return fronts;
100    }
101
102    private static List<Tuple<T, double[]>> CalculateBestFront(T[] individuals, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, out Dictionary<T, List<int>> dominatedIndividuals, out int[] dominationCounter, out int[] rank) {
103      var front = new List<Tuple<T, double[]>>();
104      dominatedIndividuals = new Dictionary<T, List<int>>();
105      dominationCounter = new int[populationSize];
106      rank = new int[populationSize];
107      for (int pI = 0; pI < populationSize - 1; pI++) {
108        var p = individuals[pI];
109        List<int> dominatedIndividualsByp;
110        if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
111          dominatedIndividuals[p] = dominatedIndividualsByp = new List<int>();
112        for (int qI = pI + 1; qI < populationSize; qI++) {
113          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
114          if (test == DominationResult.Dominates) {
115            dominatedIndividualsByp.Add(qI);
116            dominationCounter[qI] += 1;
117          } else if (test == DominationResult.IsDominated) {
118            dominationCounter[pI] += 1;
119            if (!dominatedIndividuals.ContainsKey(individuals[qI]))
120              dominatedIndividuals.Add(individuals[qI], new List<int>());
121            dominatedIndividuals[individuals[qI]].Add(pI);
122          }
123          if (pI == populationSize - 2
124            && qI == populationSize - 1
125            && dominationCounter[qI] == 0) {
126            rank[qI] = 0;
127            front.Add(Tuple.Create(individuals[qI], qualities[qI]));
128          }
129        }
130        if (dominationCounter[pI] == 0) {
131          rank[pI] = 0;
132          front.Add(Tuple.Create(p, qualities[pI]));
133        }
134      }
135      return front;
136    }
137
138    /// <summary>
139    /// Calculates the domination result of two solutions which are given in form
140    /// of their quality resp. fitness vector.
141    /// </summary>
142    /// <param name="left">The fitness of the solution that is to be compared.</param>
143    /// <param name="right">The fitness of the solution which is compared against.</param>
144    /// <param name="maximizations">The objective in each dimension.</param>
145    /// <param name="dominateOnEqualQualities">Whether the result should be Dominates in case both fitness vectors are exactly equal</param>
146    /// <returns>Dominates if left dominates right, IsDominated if right dominates left and IsNonDominated otherwise.</returns>
147    public static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
148      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
149      if (dominateOnEqualQualities) {
150        var equal = true;
151        for (int i = 0; i < left.Length; i++) {
152          if (left[i] != right[i]) {
153            equal = false;
154            break;
155          }
156        }
157        if (equal) return DominationResult.Dominates;
158      }
159
160      bool leftIsBetter = false, rightIsBetter = false;
161      for (int i = 0; i < left.Length; i++) {
162        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
163        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
164        if (leftIsBetter && rightIsBetter) break;
165      }
166
167      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
168      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
169      return DominationResult.IsNonDominated;
170    }
171
172    /// <summary>
173    /// A simple check if the quality resp. fitness in <paramref name="left"/> is better than
174    /// that given in <paramref name="right"/>.
175    /// </summary>
176    /// <param name="left">The first fitness value</param>
177    /// <param name="right">The second fitness value</param>
178    /// <param name="maximization">The objective direction</param>
179    /// <returns>True if left is better than right, false if it is not.</returns>
180    public static bool IsDominated(double left, double right, bool maximization) {
181      return maximization && left < right
182        || !maximization && left > right;
183    }
184  }
185}
Note: See TracBrowser for help on using the repository browser.