Changeset 11674

Timestamp:

12/09/14 17:00:53 (8 years ago)

Author:

mkommend

Message:

#2282: Performance improvements in PPP (reduced memory allocations and more efficient implementation).

Location:

branches/Parameter-less Population Pyramid

Files:

• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs (modified) (10 diffs)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveStepTrapProblem.cs (modified) (4 diffs)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveTrapProblem.cs (modified) (4 diffs)
• Parameter-less Population Pyramid.sln (modified) (1 diff)

branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs

@@ -27 +27 @@
 
 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
-  
+
   public class LinkageTree {
 
@@ -66 +66 @@
         for (int j = 0; j < i; j++) {
           // Updates the entry of the 4 long array based on the two bits
-          var pattern = (Convert.ToInt32(solution[j]) << 1) + Convert.ToInt32(solution[i]);
+
+          var pattern = (Convert.ToByte(solution[j]) << 1) + Convert.ToByte(solution[i]);
           occurances[i][j][pattern]++;
         }
@@ -78 +79 @@
     private static double NegativeEntropy(int[] counts, double total) {
       double sum = 0;
-      foreach (var value in counts) {
-        if (value == 0) continue;
-        var p = value / total;
-        sum += (p * Math.Log(p));
+      for (int i = 0; i < counts.Length; i++) {
+        if (counts[i] != 0) {
+          sum += ((counts[i] / total) * Math.Log(counts[i] / total));
+        }
       }
       return sum;
@@ -88 +89 @@
     // Uses the frequency table to calcuate the entropy distance between two indices.
     // In the GECCO paper, calculates Equation 1
+    private int[] bits = new int[4];
     private double EntropyDistance(int i, int j) {
       // This ensures you are using the lower triangular part of "occurances"
@@ -96 +98 @@
       }
       var entry = occurances[i][j];
-      int[] bits = new int[4];
       // extracts the occurrences of the individual bits
       bits[0] = entry[0] + entry[2];  // i zero
@@ -114 +115 @@
     }
 
+
+
     // Performs O(N^2) clustering based on the method described in:
     // "Optimal implementations of UPGMA and other common clustering algorithms"
     // by I. Gronau and S. Moran
     // In the GECCO paper, Figure 2 is a simplified version of this algorithm.
+    private double[][] distances;
     private void Rebuild() {
+      if (distances == null) {
+        distances = new double[clusters.Length * 2 - 1][];
+        for (int i = 0; i < distances.Length; i++)
+          distances[i] = new double[clusters.Length * 2 - 1];
+      }
+
+
       // Keep track of which clusters have not been merged
-      var topLevel = Enumerable.Range(0, length).ToList();
-      bool[] useful = Enumerable.Repeat(true, clusters.Length).ToArray();
+      var topLevel = new List<int>(length);
+      for (int i = 0; i < length; i++)
+        topLevel.Add(i);
+
+      bool[] useful = new bool[clusters.Length];
+      for (int i = 0; i < useful.Length; i++)
+        useful[i] = true;
 
       // Store the distances between all clusters
-      double[,] distances = new double[clusters.Length, clusters.Length];
       for (int i = 1; i < length; i++) {
         for (int j = 0; j < i; j++) {
-          distances[i, j] = EntropyDistance(clusters[i][0], clusters[j][0]);
+          distances[i][j] = EntropyDistance(clusters[i][0], clusters[j][0]);
           // make it symmetric
-          distances[j, i] = distances[i, j];
+          distances[j][i] = distances[i][j];
         }
       }
@@ -139 +154 @@
       for (int index = length; index < clusters.Length; index++) {
         // Shuffle everything not yet in the path
-        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1);
+        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count - 1);
 
         // if nothing in the path, just add a random usable node
@@ -151 +166 @@
           // best_index stores the location of the best thing in the top level
           int best_index = end_of_path;
-          double min_dist = distances[final, topLevel[best_index]];
+          double min_dist = distances[final][topLevel[best_index]];
           // check all options which might be closer to "final" than "topLevel[best_index]"
           for (int option = end_of_path + 1; option < topLevel.Count; option++) {
-            if (distances[final, topLevel[option]] < min_dist) {
-              min_dist = distances[final, topLevel[option]];
+            if (distances[final][topLevel[option]] < min_dist) {
+              min_dist = distances[final][topLevel[option]];
               best_index = option;
             }
           }
           // If the current last two in the path are minimally distant
-          if (end_of_path > 1 && min_dist >= distances[final, topLevel[end_of_path - 2]]) {
+          if (end_of_path > 1 && min_dist >= distances[final][topLevel[end_of_path - 2]]) {
             break;
           }
@@ -173 +188 @@
 
         // Only keep a cluster if the distance between the joining clusters is > zero
-        bool keep = !distances[first, second].IsAlmost(0.0);
+        bool keep = !distances[first][second].IsAlmost(0.0);
         useful[first] = keep;
         useful[second] = keep;
@@ -191 +206 @@
           }
           // Use the previous distances to calculate the joined distance
-          double first_distance = distances[first, x];
+          double first_distance = distances[first][x];
           first_distance *= clusters[first].Count;
-          double second_distance = distances[second, x];
+          double second_distance = distances[second][x];
           second_distance *= clusters[second].Count;
-          distances[x, index] = ((first_distance + second_distance)
+          distances[x][index] = ((first_distance + second_distance)
               / (clusters[first].Count + clusters[second].Count));
           // make it symmetric
-          distances[index, x] = distances[x, index];
+          distances[index][x] = distances[x][index];
           i++;
         }

branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveStepTrapProblem.cs

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -37 +36 @@
     protected DeceptiveStepTrapProblem(DeceptiveStepTrapProblem original, Cloner cloner)
       : base(original, cloner) {
+      RegisterParameterEvents();
     }
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -56 +56 @@
       : base() {
       Parameters.Add(new FixedValueParameter<IntValue>(StepSizeParameterName, "", new IntValue(2)));
+      RegisterParameterEvents();
     }
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterParameterEvents();
+    }
+
+    private void RegisterParameterEvents() {
+      TrapSizeParameter.Value.ValueChanged += (o, e) => { offset = -1; };
+      StepSizeParameter.Value.ValueChanged += (o, e) => { offset = -1; };
+    }
+
+
+    private int offset = -1;
     private int Offset {
-      get { return (TrapSize - StepSize) % StepSize; }
+      get {
+        if (offset == -1) offset = (TrapSize - StepSize) % StepSize;
+        return offset;
+      }
     }
 
@@ -66 +82 @@
     }
 
-    protected override int Score(bool[] individual, int trapIndex) {
-      int partial = base.Score(individual, trapIndex);
+    protected override int Score(bool[] individual, int trapIndex, int trapSize) {
+      int partial = base.Score(individual, trapIndex, trapSize);
       // introduce plateaus using integer division
       return (Offset + partial) / StepSize;

branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveTrapProblem.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -59 +58 @@
 
     protected virtual int TrapMaximum {
-      get { return TrapSize;  }
+      get { return TrapSize; }
     }
 
@@ -69 +68 @@
 
     // In the GECCO paper, calculates Equation 3
-    protected virtual int Score(bool[] individual, int trapIndex) {
+    protected virtual int Score(bool[] individual, int trapIndex, int trapSize) {
       int result = 0;
       // count number of bits in trap set to 1
-      for (int index = trapIndex; index < trapIndex + TrapSize; index++) {
+      for (int index = trapIndex; index < trapIndex + trapSize; index++) {
         if (individual[index]) result++;
       }
 
       // Make it deceptive
-      if (result < TrapSize) {
-        result = TrapSize - result - 1;
+      if (result < trapSize) {
+        result = trapSize - result - 1;
       }
       return result;
@@ -86 +85 @@
       if (individual.Length != Length) throw new ArgumentException("The individual has not the correct length.");
       int total = 0;
-      for (int i = 0; i < individual.Length; i += TrapSize) {
-        total += Score(individual, i);
+      var trapSize = TrapSize;
+      for (int i = 0; i < individual.Length; i += trapSize) {
+        total += Score(individual, i, trapSize);
       }
-      return (double)(total * TrapSize) / (TrapMaximum * individual.Length);
+      return (double)(total * trapSize) / (TrapMaximum * individual.Length);
     }
   }

branches/Parameter-less Population Pyramid/Parameter-less Population Pyramid.sln

@@ -2 +2 @@
 Microsoft Visual Studio Solution File, Format Version 12.00
 # Visual Studio 2013
-VisualStudioVersion = 12.0.21005.1
+VisualStudioVersion = 12.0.31101.0
 MinimumVisualStudioVersion = 10.0.40219.1
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3", "HeuristicLab.Algorithms.ParameterlessPopulationPyramid\3.3\HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3.csproj", "{9319C447-8183-4DBC-8145-0E3CF98084CC}"
 EndProject
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "ParameterlessPopulationPyramid.Test", "ParameterlessPopulationPyramid.Test\ParameterlessPopulationPyramid.Test.csproj", "{0B349086-8EB7-4BC2-8373-44E9CB68B258}"
+  ProjectSection(ProjectDependencies) = postProject
+    {9319C447-8183-4DBC-8145-0E3CF98084CC} = {9319C447-8183-4DBC-8145-0E3CF98084CC}
+  EndProjectSection
 EndProject
 Global