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

Last change on this file since 15086 was 15086, checked in by mkommend, 3 years ago

#2783: Renamed individuals to solutions in DominationCalculator to be consistent with other methods.

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