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 


22  using System;


23  using System.Collections.Generic;


24  using System.Linq;


25  using HEAL.Attic;


26 


27  namespace HeuristicLab.Optimization {


28 


29  [StorableType("d76eb75350884490ad18e78d3629c60b")]


30  public enum DominationResult { Dominates, IsDominated, IsNonDominated };


31 


32  public static class DominationCalculator {


33  /// <summary>


34  /// Calculates the best pareto front only. The fast nondominated 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: NSGAII.


37  /// IEEE Transactions on Evolutionary Computation, 6(2), 182197.


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, IReadOnlyList<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 nondominated 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: NSGAII.


61  /// IEEE Transactions on Evolutionary Computation, 6(2), 182197.


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, IReadOnlyList<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, IReadOnlyList<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 nondominated 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: NSGAII.


145  /// IEEE Transactions on Evolutionary Computation, 6(2), 182197.


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, IReadOnlyList<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 nondominated 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: NSGAII.


167  /// IEEE Transactions on Evolutionary Computation, 6(2), 182197.


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, IReadOnlyList<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, IReadOnlyList<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, IReadOnlyList<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  }

