Changeset 15089

Timestamp:

06/29/17 14:11:04 (7 years ago)

Author:

bwerth

Message:

#2592 removed effectively unused field "rank" from Individual, removed non-dominated sorting

Location:

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3

Files:

• HeuristicLab.Algorithms.MOCMAEvolutionStrategy-3.3.csproj (modified) (2 diffs)
• Individual.cs (modified) (2 diffs)
• MOCMAEvolutionStrategy.cs (modified) (7 diffs)

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/HeuristicLab.Algorithms.MOCMAEvolutionStrategy-3.3.csproj

@@ -106 +106 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="IDominatingArchive.cs" />
     <Compile Include="Indicators\MinimalDistanceIndicator.cs" />
     <Compile Include="Indicators\CrowdingIndicator.cs" />
     <Compile Include="Indicators\HypervolumeIndicator.cs" />
     <Compile Include="IIndicator.cs" />
+    <Compile Include="Archives\ListArchive.cs" />
     <Compile Include="Individual.cs" />
     <Compile Include="MOCMAEvolutionStrategy.cs" />
@@ -116 +118 @@
     <Compile Include="DoubleMatrixHelper.cs" />
   </ItemGroup>
+  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <PropertyGroup>

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/Individual.cs

@@ -63 +63 @@
     public bool Selected { get; set; }
     [Storable]
-    public double Rank { get; set; }
-    [Storable]
     public double SuccessProbability { get; set; }
     #endregion
@@ -112 +110 @@
       PenalizedFitness = other.PenalizedFitness != null ? other.PenalizedFitness.Select(x => x).ToArray() : null;
       Selected = other.Selected;
-      Rank = other.Rank;
       SuccessProbability = other.SuccessProbability;
     }

branches/MOCMAEvolutionStrategy/HeuristicLab.Algorithms.MOCMAEvolutionStrategy/3.3/MOCMAEvolutionStrategy.cs

@@ -77 +77 @@
     [Storable]
     private double successThreshold; //ptresh
+
     #endregion
 
@@ -309 +310 @@
       random = cloner.Clone(original.random);
       gauss = cloner.Clone(original.gauss);
-      solutions = original.solutions.Select(cloner.Clone).ToArray();
+      solutions = original.solutions != null ? original.solutions.Select(cloner.Clone).ToArray() : null;
       stepSizeLearningRate = original.stepSizeLearningRate;
       stepSizeDampeningFactor = original.stepSizeDampeningFactor;
@@ -417 +418 @@
         }
       }
+
+
     }
     private void Iterate() {
@@ -478 +481 @@
     private void SelectParents(IReadOnlyList<Individual> parents, int length) {
       //perform a nondominated sort to assign the rank to every element
-      var fronts = NonDominatedSort(parents);
+      int[] ranks;
+      var fronts = DominationCalculator<Individual>.CalculateAllParetoFronts(parents.ToArray(), parents.Select(i => i.PenalizedFitness).ToArray(), Problem.Maximization, out ranks);
+      // NonDominatedSort(parents, individual => individual.PenalizedFitness);
 
       //deselect the highest rank fronts until we would end up with less or equal mu elements
@@ -485 +490 @@
       while (popSize - fronts[rank].Count >= length) {
         var front = fronts[rank];
-        foreach (var i in front) i.Selected = false;
+        foreach (var i in front) i.Item1.Selected = false;
         popSize -= front.Count;
         rank--;
@@ -491 +496 @@
 
       //now use the indicator to deselect the approximatingly worst elements of the last selected front
-      var front1 = fronts[rank].OrderBy(x => x.PenalizedFitness[0]).ToList();
+      var front1 = fronts[rank].OrderBy(x => x.Item1.PenalizedFitness[0]).ToList();
       for (; popSize > length; popSize--) {
-        var lc = Indicator.LeastContributer(front1, Problem);
-        front1[lc].Selected = false;
+        var lc = Indicator.LeastContributer(front1.Select(i => i.Item1).ToArray(), Problem);
+        front1[lc].Item1.Selected = false;
         front1.Swap(lc, front1.Count - 1);
         front1.RemoveAt(front1.Count - 1);
@@ -546 +551 @@
     }
 
-    #region FastNonDominatedSort
-    //blatantly stolen form HeuristicLab.Optimization.Operators.FastNonDominatedSort
-    //however: Operators.FastNonDominatedSort does not return ranked fronts => rerank after sorting would not be sensible
-
-    private enum DominationResult { Dominates, IsDominated, IsNonDominated };
-    private List<List<Individual>> NonDominatedSort(IReadOnlyList<Individual> individuals) {
-      const bool dominateOnEqualQualities = false;
-      var maximization = Problem.Maximization;
-      if (individuals == null) throw new InvalidOperationException(Name + ": No qualities found.");
-      var populationSize = individuals.Count;
-
-      var fronts = new List<List<Individual>>();
-      var dominatedScopes = new Dictionary<Individual, List<int>>();
-      var dominationCounter = new int[populationSize];
-
-      for (var pI = 0; pI < populationSize - 1; pI++) {
-        var p = individuals[pI];
-        List<int> dominatedScopesByp;
-        if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp))
-          dominatedScopes[p] = dominatedScopesByp = new List<int>();
-        for (var qI = pI + 1; qI < populationSize; qI++) {
-          var test = Dominates(individuals[pI], individuals[qI], maximization, dominateOnEqualQualities);
-          if (test == DominationResult.Dominates) {
-            dominatedScopesByp.Add(qI);
-            dominationCounter[qI] += 1;
-          } else if (test == DominationResult.IsDominated) {
-            dominationCounter[pI] += 1;
-            if (!dominatedScopes.ContainsKey(individuals[qI]))
-              dominatedScopes.Add(individuals[qI], new List<int>());
-            dominatedScopes[individuals[qI]].Add(pI);
-          }
-          if (pI == populationSize - 2
-            && qI == populationSize - 1
-            && dominationCounter[qI] == 0) {
-            AddToFront(individuals[qI], fronts, 0);
-          }
-        }
-        if (dominationCounter[pI] == 0) {
-          AddToFront(p, fronts, 0);
-        }
-      }
-      var i = 0;
-      while (i < fronts.Count && fronts[i].Count > 0) {
-        var nextFront = new List<Individual>();
-        foreach (var p in fronts[i]) {
-          List<int> dominatedScopesByp;
-          if (!dominatedScopes.TryGetValue(p, out dominatedScopesByp)) continue;
-          foreach (var dominatedScope in dominatedScopesByp) {
-            dominationCounter[dominatedScope] -= 1;
-            if (dominationCounter[dominatedScope] != 0) continue;
-            nextFront.Add(individuals[dominatedScope]);
-          }
-        }
-        i += 1;
-        fronts.Add(nextFront);
-      }
-
-      for (i = 0; i < fronts.Count; i++) {
-        foreach (var p in fronts[i]) {
-          p.Rank = i;
-        }
-      }
-      return fronts;
-    }
-    private static void AddToFront(Individual p, IList<List<Individual>> fronts, int i) {
-      if (i == fronts.Count) fronts.Add(new List<Individual>());
-      fronts[i].Add(p);
-    }
-    private static DominationResult Dominates(Individual left, Individual right, bool[] maximizations, bool dominateOnEqualQualities) {
-      return Dominates(left.PenalizedFitness, right.PenalizedFitness, maximizations, dominateOnEqualQualities);
-    }
-    private static DominationResult Dominates(IReadOnlyList<double> left, IReadOnlyList<double> right, IReadOnlyList<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 (var i = 0; i < left.Count; i++) {
-          if (left[i] != right[i]) {
-            equal = false;
-            break;
-          }
-        }
-        if (equal) return DominationResult.Dominates;
-      }
-
-      bool leftIsBetter = false, rightIsBetter = false;
-      for (var i = 0; i < left.Count; 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;
-    }
-    #endregion
   }
 }