1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022017 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 HeuristicLab.Core;


25  using HeuristicLab.Data;


26 


27  namespace 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 nondominated 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: NSGAII.


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


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


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


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  }

