source: branches/2521_ProblemRefactoring/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs @ 17230

Last change on this file since 17230 was 17230, checked in by abeham, 11 months ago

#2521: add multi-objective analysis to all multi-objective encoding-base problems

File size: 15.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HEAL.Attic;
26
27namespace HeuristicLab.Optimization {
28
29  [StorableType("d76eb753-5088-4490-ad18-e78d3629c60b")]
30  public enum DominationResult { Dominates, IsDominated, IsNonDominated };
31
32  public static class DominationCalculator {
33    /// <summary>
34    /// Calculates the best pareto front only. The fast non-dominated sorting algorithm is used
35    /// as described in Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
36    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
37    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
38    /// </summary>
39    /// <remarks>
40    /// When there are plateaus in the fitness landscape several solutions might have exactly
41    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
42    /// can be set to true to avoid plateaus becoming too attractive for the search process.
43    /// </remarks>
44    /// <param name="solutions">The solutions of the population.</param>
45    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
46    /// <param name="maximization">The objective in each dimension.</param>
47    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
48    /// <returns>The pareto front containing the best solutions and their associated quality resp. fitness.</returns>
49    public static List<Tuple<T, double[]>> CalculateBestParetoFront<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
50      var populationSize = solutions.Length;
51      Dictionary<T, List<int>> dominatedIndividuals;
52      int[] dominationCounter, rank;
53      return CalculateBestFront(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, out dominatedIndividuals, out dominationCounter, out rank);
54    }
55
56    /// <summary>
57    /// Calculates all pareto fronts. The first in the list is the best front.
58    /// The fast non-dominated sorting algorithm is used as described in
59    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
60    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
61    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
62    /// </summary>
63    /// <remarks>
64    /// When there are plateaus in the fitness landscape several solutions might have exactly
65    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
66    /// can be set to true to avoid plateaus becoming too attractive for the search process.
67    /// </remarks>
68    /// <param name="solutions">The solutions of the population.</param>
69    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
70    /// <param name="maximization">The objective in each dimension.</param>
71    /// <param name="rank">The rank of each of the solutions, corresponds to the front it is put in.</param>
72    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
73    /// <returns>A sorted list of the pareto fronts from best to worst.</returns>
74    public static List<List<Tuple<T, double[]>>> CalculateAllParetoFronts<T>(T[] solutions, double[][] qualities, bool[] maximization, out int[] rank, bool dominateOnEqualQualities = true) {
75      var populationSize = solutions.Length;
76
77      Dictionary<T, List<int>> dominatedIndividuals;
78      int[] dominationCounter;
79      var fronts = new List<List<Tuple<T, double[]>>>();
80      fronts.Add(CalculateBestFront(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, out dominatedIndividuals, out dominationCounter, out rank));
81      var i = 0;
82      while (i < fronts.Count && fronts[i].Count > 0) {
83        var nextFront = new List<Tuple<T, double[]>>();
84        foreach (var p in fronts[i]) {
85          List<int> dominatedIndividualsByp;
86          if (dominatedIndividuals.TryGetValue(p.Item1, out dominatedIndividualsByp)) {
87            for (var k = 0; k < dominatedIndividualsByp.Count; k++) {
88              var dominatedIndividual = dominatedIndividualsByp[k];
89              dominationCounter[dominatedIndividual] -= 1;
90              if (dominationCounter[dominatedIndividual] == 0) {
91                rank[dominatedIndividual] = i + 1;
92                nextFront.Add(Tuple.Create(solutions[dominatedIndividual], qualities[dominatedIndividual]));
93              }
94            }
95          }
96        }
97        i += 1;
98        fronts.Add(nextFront);
99      }
100      return fronts;
101    }
102
103    private static List<Tuple<T, double[]>> CalculateBestFront<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, out Dictionary<T, List<int>> dominatedIndividuals, out int[] dominationCounter, out int[] rank) {
104      var front = new List<Tuple<T, double[]>>();
105      dominatedIndividuals = new Dictionary<T, List<int>>();
106      dominationCounter = new int[populationSize];
107      rank = new int[populationSize];
108      for (var pI = 0; pI < populationSize - 1; pI++) {
109        var p = solutions[pI];
110        List<int> dominatedIndividualsByp;
111        if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
112          dominatedIndividuals[p] = dominatedIndividualsByp = new List<int>();
113        for (var qI = pI + 1; qI < populationSize; qI++) {
114          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
115          if (test == DominationResult.Dominates) {
116            dominatedIndividualsByp.Add(qI);
117            dominationCounter[qI] += 1;
118          } else if (test == DominationResult.IsDominated) {
119            dominationCounter[pI] += 1;
120            if (!dominatedIndividuals.ContainsKey(solutions[qI]))
121              dominatedIndividuals.Add(solutions[qI], new List<int>());
122            dominatedIndividuals[solutions[qI]].Add(pI);
123          }
124          if (pI == populationSize - 2
125            && qI == populationSize - 1
126            && dominationCounter[qI] == 0) {
127            rank[qI] = 0;
128            front.Add(Tuple.Create(solutions[qI], qualities[qI]));
129          }
130        }
131        if (dominationCounter[pI] == 0) {
132          rank[pI] = 0;
133          front.Add(Tuple.Create(p, qualities[pI]));
134        }
135      }
136      return front;
137    }
138
139    /// <summary>
140    /// Calculates all pareto fronts by returning the index of the parameters in each front.
141    /// The first in the list is the best front.
142    /// The fast non-dominated sorting algorithm is used as described in
143    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
144    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
145    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
146    /// </summary>
147    /// <remarks>
148    /// When there are plateaus in the fitness landscape several solutions might have exactly
149    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
150    /// can be set to true to avoid plateaus becoming too attractive for the search process.
151    /// </remarks>
152    /// <param name="solutions">The solutions of the population.</param>
153    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
154    /// <param name="maximization">The objective in each dimension.</param>
155    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
156    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
157    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities = true) {
158      return CalculateAllParetoFrontsIndices(solutions, qualities, maximization, out var rank, dominateOnEqualQualities);
159    }
160
161    /// <summary>
162    /// Calculates all pareto fronts by returning the index of the parameters in each front.
163    /// The first in the list is the best front.
164    /// The fast non-dominated sorting algorithm is used as described in
165    /// Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002).
166    /// A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II.
167    /// IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
168    /// </summary>
169    /// <remarks>
170    /// When there are plateaus in the fitness landscape several solutions might have exactly
171    /// the same fitness vector. In this case parameter <paramref name="dominateOnEqualQualities"/>
172    /// can be set to true to avoid plateaus becoming too attractive for the search process.
173    /// </remarks>
174    /// <param name="solutions">The solutions of the population.</param>
175    /// <param name="qualities">The qualities resp. fitness for each solution.</param>
176    /// <param name="maximization">The objective in each dimension.</param>
177    /// <param name="rank">The rank of each of the solutions, corresponds to the front it is put in.</param>
178    /// <param name="dominateOnEqualQualities">Whether solutions of exactly equal quality should dominate one another.</param>
179    /// <returns>A sorted list of the pareto fronts where each front contains the indices of the <paramref name="solutions"/> and <paramref name="qualities"/>.</returns>
180    public static List<List<int>> CalculateAllParetoFrontsIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, out int[] rank, bool dominateOnEqualQualities = true) {
181      var populationSize = solutions.Length;
182
183      var dominatedIndividuals = Enumerable.Range(0, qualities.Length).Select(x => new List<int>()).ToArray();
184      var dominationCounter = new int[populationSize];
185      rank = new int[populationSize];
186      var fronts = new List<List<int>>();
187      fronts.Add(CalculateBestFrontIndices(solutions, qualities, maximization, dominateOnEqualQualities, populationSize, dominatedIndividuals, dominationCounter, rank));
188      var i = 0;
189      while (i < fronts.Count && fronts[i].Count > 0) {
190        var nextFront = new List<int>();
191        foreach (var p in fronts[i]) {
192          if (dominatedIndividuals[p].Count > 0) {
193            for (var k = 0; k < dominatedIndividuals[p].Count; k++) {
194              var dominatedIndividual = dominatedIndividuals[p][k];
195              dominationCounter[dominatedIndividual] -= 1;
196              if (dominationCounter[dominatedIndividual] == 0) {
197                rank[dominatedIndividual] = i + 1;
198                nextFront.Add(dominatedIndividual);
199              }
200            }
201          }
202        }
203        i += 1;
204        fronts.Add(nextFront);
205      }
206      return fronts;
207    }
208
209    private static List<int> CalculateBestFrontIndices<T>(T[] solutions, double[][] qualities, bool[] maximization, bool dominateOnEqualQualities, int populationSize, List<int>[] dominatedIndividuals, int[] dominationCounter, int[] rank) {
210      var front = new List<int>();
211      for (var pI = 0; pI < populationSize - 1; pI++) {
212        var p = solutions[pI];
213        for (var qI = pI + 1; qI < populationSize; qI++) {
214          var test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
215          if (test == DominationResult.Dominates) {
216            dominatedIndividuals[pI].Add(qI);
217            dominationCounter[qI] += 1;
218          } else if (test == DominationResult.IsDominated) {
219            dominationCounter[pI] += 1;
220            dominatedIndividuals[qI].Add(pI);
221          }
222          if (pI == populationSize - 2
223            && qI == populationSize - 1
224            && dominationCounter[qI] == 0) {
225            rank[qI] = 0;
226            front.Add(qI);
227          }
228        }
229        if (dominationCounter[pI] == 0) {
230          rank[pI] = 0;
231          front.Add(pI);
232        }
233      }
234      return front;
235    }
236
237    /// <summary>
238    /// Calculates the domination result of two solutions which are given in form
239    /// of their quality resp. fitness vector.
240    /// </summary>
241    /// <param name="left">The fitness of the solution that is to be compared.</param>
242    /// <param name="right">The fitness of the solution which is compared against.</param>
243    /// <param name="maximizations">The objective in each dimension.</param>
244    /// <param name="dominateOnEqualQualities">Whether the result should be Dominates in case both fitness vectors are exactly equal</param>
245    /// <returns>Dominates if left dominates right, IsDominated if right dominates left and IsNonDominated otherwise.</returns>
246    public static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
247      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
248      if (dominateOnEqualQualities) {
249        var equal = true;
250        for (var i = 0; i < left.Length; i++) {
251          if (left[i] != right[i]) {
252            equal = false;
253            break;
254          }
255        }
256        if (equal) return DominationResult.Dominates;
257      }
258
259      bool leftIsBetter = false, rightIsBetter = false;
260      for (var i = 0; i < left.Length; i++) {
261        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
262        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
263        if (leftIsBetter && rightIsBetter) break;
264      }
265
266      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
267      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
268      return DominationResult.IsNonDominated;
269    }
270
271    /// <summary>
272    /// A simple check if the quality resp. fitness in <paramref name="left"/> is better than
273    /// that given in <paramref name="right"/>.
274    /// </summary>
275    /// <param name="left">The first fitness value</param>
276    /// <param name="right">The second fitness value</param>
277    /// <param name="maximization">The objective direction</param>
278    /// <returns>True if left is better than right, false if it is not.</returns>
279    public static bool IsDominated(double left, double right, bool maximization) {
280      return maximization && left < right
281        || !maximization && left > right;
282    }
283  }
284}
Note: See TracBrowser for help on using the repository browser.