Changeset 15109

Timestamp:

07/03/17 09:40:13 (7 years ago)

Author:

abeham

Message:

#2783: merged r15051,r15080,r15086,r15087 to stable

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Optimization (modified) (1 prop)
• HeuristicLab.Optimization.Operators/3.3/MultiObjective/FastNonDominatedSort.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/BasicProblems/SingleObjectiveBasicProblem.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj (modified) (1 diff)
• HeuristicLab.Optimization/3.3/MultiObjective (copied) (copied from trunk/sources/HeuristicLab.Optimization/3.3/MultiObjective)
• HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs (modified) (5 diffs)
• HeuristicLab.Optimization/3.3/Results/ResultCollection.cs (modified) (1 diff)

stable/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);
     }
 

stable/HeuristicLab.Optimization/3.3/BasicProblems/MultiObjectiveBasicProblem.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -57 +59 @@
     public abstract double[] Evaluate(Individual individual, IRandom random);
     public virtual void Analyze(Individual[] individuals, double[][] qualities, ResultCollection results, IRandom random) { }
-
+    
     protected override void OnOperatorsChanged() {
       base.OnOperatorsChanged();

stable/HeuristicLab.Optimization/3.3/BasicProblems/SingleObjectiveBasicProblem.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -84 +85 @@
     }
 
+    protected Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities) {
+      return GetBestIndividual(individuals, qualities, Maximization);
+    }
+    public static Tuple<Individual, double> GetBestIndividual(Individual[] individuals, double[] qualities, bool maximization) {
+      var zipped = individuals.Zip(qualities, (i, q) => new { Individual = i, Quality = q });
+      var best = (maximization ? zipped.OrderByDescending(z => z.Quality) : zipped.OrderBy(z => z.Quality)).First();
+      return Tuple.Create(best.Individual, best.Quality);
+    }
+
     protected override void OnOperatorsChanged() {
       base.OnOperatorsChanged();

stable/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj

@@ -156 +156 @@
     <Compile Include="Interfaces\ILocalImprovementAlgorithmOperator.cs" />
     <Compile Include="Interfaces\IMultiObjectiveOperator.cs" />
+    <Compile Include="MultiObjective\DominationCalculator.cs" />
     <Compile Include="Results\IResultParameter.cs" />
     <Compile Include="Interfaces\ISingleObjectiveOperator.cs" />

stable/HeuristicLab.Optimization/3.3/MultiObjective/DominationCalculator.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
-using HeuristicLab.Core;
-using HeuristicLab.Data;
 
 namespace HeuristicLab.Optimization {
@@ -100 +98 @@
     }
 
-    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) {
+    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) {
       var front = new List<Tuple<T, double[]>>();
       dominatedIndividuals = new Dictionary<T, List<int>>();
@@ -106 +104 @@
       rank = new int[populationSize];
       for (int pI = 0; pI < populationSize - 1; pI++) {
-        var p = individuals[pI];
+        var p = solutions[pI];
         List<int> dominatedIndividualsByp;
         if (!dominatedIndividuals.TryGetValue(p, out dominatedIndividualsByp))
@@ -117 +115 @@
           } else if (test == DominationResult.IsDominated) {
             dominationCounter[pI] += 1;
-            if (!dominatedIndividuals.ContainsKey(individuals[qI]))
-              dominatedIndividuals.Add(individuals[qI], new List<int>());
-            dominatedIndividuals[individuals[qI]].Add(pI);
+            if (!dominatedIndividuals.ContainsKey(solutions[qI]))
+              dominatedIndividuals.Add(solutions[qI], new List<int>());
+            dominatedIndividuals[solutions[qI]].Add(pI);
           }
           if (pI == populationSize - 2
@@ -125 +123 @@
             && dominationCounter[qI] == 0) {
             rank[qI] = 0;
-            front.Add(Tuple.Create(individuals[qI], qualities[qI]));
+            front.Add(Tuple.Create(solutions[qI], qualities[qI]));
           }
         }

stable/HeuristicLab.Optimization/3.3/Results/ResultCollection.cs

@@ -75 +75 @@
     }
 
+    public void AddOrUpdateResult(string name, IItem value) {
+      IResult res;
+      if (!TryGetValue(name, out res)) {
+        res = new Result(name, value);
+        Add(res);
+      } else res.Value = value;
+    }
   }
 }