Changeset 15080 for trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

Timestamp:

06/28/17 22:05:14 (7 years ago)

Author:

abeham

Message:

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

File:

• trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs

@@ -39 +39 @@
   [StorableClass]
   public class FastNonDominatedSort : SingleSuccessorOperator, IMultiObjectiveOperator {
-    private enum DominationResult { Dominates, IsDominated, IsNonDominated };
 
     #region Parameter properties
@@ -75 +74 @@
       int populationSize = scope.SubScopes.Count;
 
-      List<ScopeList> fronts = new List<ScopeList>();
-      Dictionary<IScope, List<int>> dominatedScopes = new Dictionary<IScope, List<int>>();
-      int[] dominationCounter = new int[populationSize];
-      ItemArray<IntValue> rank = new ItemArray<IntValue>(populationSize);
+      int[] rank;
+      var fronts = DominationCalculator<IScope>.CalculateAllParetoFronts(scope.SubScopes.ToArray(), qualities, maximization, out rank, dominateOnEqualQualities);
 
-      for (int pI = 0; pI < populationSize - 1; pI++) {
-        IScope p = scope.SubScopes[pI];
-        List<int> dominatedScopesByp;
-        if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
-          dominatedScopes[p] = dominatedScopesByp = new List<int>();
-        for (int qI = pI + 1; qI < populationSize; qI++) {
-          DominationResult test = Dominates(qualities[pI], qualities[qI], maximization, dominateOnEqualQualities);
-          if (test == DominationResult.Dominates) {
-            dominatedScopesByp.Add(qI);
-            dominationCounter[qI] += 1;
-          } else if (test == DominationResult.IsDominated) {
-            dominationCounter[pI] += 1;
-            if (!dominatedScopes.ContainsKey(scope.SubScopes[qI]))
-              dominatedScopes.Add(scope.SubScopes[qI], new List<int>());
-            dominatedScopes[scope.SubScopes[qI]].Add(pI);
-          }
-          if (pI == populationSize - 2
-            && qI == populationSize - 1
-            && dominationCounter[qI] == 0) {
-            rank[qI] = new IntValue(0);
-            AddToFront(scope.SubScopes[qI], fronts, 0);
-          }
-        }
-        if (dominationCounter[pI] == 0) {
-          rank[pI] = new IntValue(0);
-          AddToFront(p, fronts, 0);
-        }
-      }
-      int i = 0;
-      while (i < fronts.Count && fronts[i].Count > 0) {
-        ScopeList nextFront = new ScopeList();
-        foreach (IScope p in fronts[i]) {
-          List<int> dominatedScopesByp;
-          if (dominatedScopes.TryGetValue(p, out dominatedScopesByp)) {
-            for (int k = 0; k < dominatedScopesByp.Count; k++) {
-              int dominatedScope = dominatedScopesByp[k];
-              dominationCounter[dominatedScope] -= 1;
-              if (dominationCounter[dominatedScope] == 0) {
-                rank[dominatedScope] = new IntValue(i + 1);
-                nextFront.Add(scope.SubScopes[dominatedScope]);
-              }
-            }
-          }
-        }
-        i += 1;
-        fronts.Add(nextFront);
-      }
-
-      RankParameter.ActualValue = rank;
+      RankParameter.ActualValue = new ItemArray<IntValue>(rank.Select(x => new IntValue(x)));
 
       scope.SubScopes.Clear();
 
-      for (i = 0; i < fronts.Count; i++) {
+      for (var i = 0; i < fronts.Count; i++) {
         Scope frontScope = new Scope("Front " + i);
         foreach (var p in fronts[i])
-          frontScope.SubScopes.Add(p);
+          frontScope.SubScopes.Add(p.Item1);
         if (frontScope.SubScopes.Count > 0)
           scope.SubScopes.Add(frontScope);
       }
       return base.Apply();
-    }
-
-    private static DominationResult Dominates(double[] left, double[] right, bool[] maximizations, bool dominateOnEqualQualities) {
-      //mkommend Caution: do not use LINQ.SequenceEqual for comparing the two quality arrays (left and right) due to performance reasons
-      if (dominateOnEqualQualities) {
-        var equal = true;
-        for (int i = 0; i < left.Length; i++) {
-          if (left[i] != right[i]) {
-            equal = false;
-            break;
-          }
-        }
-        if (equal) return DominationResult.Dominates;
-      }
-
-      bool leftIsBetter = false, rightIsBetter = false;
-      for (int i = 0; i < left.Length; i++) {
-        if (IsDominated(left[i], right[i], maximizations[i])) rightIsBetter = true;
-        else if (IsDominated(right[i], left[i], maximizations[i])) leftIsBetter = true;
-        if (leftIsBetter && rightIsBetter) break;
-      }
-
-      if (leftIsBetter && !rightIsBetter) return DominationResult.Dominates;
-      if (!leftIsBetter && rightIsBetter) return DominationResult.IsDominated;
-      return DominationResult.IsNonDominated;
-    }
-
-    private static bool IsDominated(double left, double right, bool maximization) {
-      return maximization && left < right
-        || !maximization && left > right;
-    }
-
-    private static void AddToFront(IScope p, List<ScopeList> fronts, int i) {
-      if (i == fronts.Count) fronts.Add(new ScopeList());
-      fronts[i].Add(p);
     }