Changeset 11663

Timestamp:

12/05/14 12:25:32 (10 years ago)

Author:

bgoldman

Message:

#2282 Reworked Linkage Tree to provide interface for clusters, moved crossover into static class.

Location:

branches/Parameter-less Population Pyramid

Files:

• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageCrossover.cs (added)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs (modified) (6 diffs)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Population.cs (added)
• ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs (modified) (4 diffs)

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

@@ -100 +100 @@
   <ItemGroup>
     <Compile Include="AlgorithmBase.cs" />
+    <Compile Include="LinkageCrossover.cs" />
     <Compile Include="DeceptiveTrapProblem.cs" />
     <Compile Include="HillClimber.cs" />
     <Compile Include="LinkageTree.cs" />
+    <Compile Include="Population.cs" />
     <Compile Include="Problems\BinaryVectorProblem.cs" />
     <Compile Include="Plugin.cs" />

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

@@ -65 +65 @@
     private readonly int[][][] occurances;
     private readonly List<int>[] clusters;
-    private readonly List<int> clusterOrdering;
+    private List<int> clusterOrdering;
     private readonly int length;
-
-    public LinkageTree(int length) {
+    private readonly IRandom rand;
+    private bool rebuildRequired = false;
+
+    public LinkageTree(int length, IRandom rand) {
       this.length = length;
+      this.rand = rand;
       occurances = new int[length][][];
 
+      // Create a lower triangular matrix without the diagonal
       for (int i = 1; i < length; i++) {
         occurances[i] = new int[i][];
@@ -99 +103 @@
         }
       }
+      rebuildRequired = true;
     }
 
@@ -109 +114 @@
         var p = value / total;
         sum += (p * Math.Log(p));
-
       }
       return sum;
@@ -115 +119 @@
 
     private double EntropyDistance(int i, int j) {
+      // This ensures you are using the lower triangular part of "occurances"
       if (i < j) {
         int temp = i;
@@ -139 +144 @@
     }
 
-    public void Rebuild(IRandom rand) {
+    private void Rebuild() {
       // Keep track of which clusters have not been merged
       var topLevel = Enumerable.Range(0, length).ToList();
@@ -236 +241 @@
         if (useful[i]) clusterOrdering.Add(i);
       }
-      // TODO Shuffle cluster ordering
+
+      // Shuffle before sort to ensure ties are broken randomly
       clusterOrdering.ShuffleInPlace(rand);
-      clusterOrdering.Sort((i, j) => clusters[i].Count.CompareTo(clusters[j].Count));
-    }
-
-    public double ImproveUsingTree(bool[] solution, double fitness, BinaryVectorProblem problem) {
-      return fitness;
+      clusterOrdering = clusterOrdering.OrderBy(i => clusters[i].Count).ToList();
+    }
+
+    public IEnumerable<List<int>> Clusters {
+      get {
+        // Just in time rebuilding
+        if (rebuildRequired) Rebuild();
+        foreach (var index in clusterOrdering) {
+          // Send out the clusters in the desired order
+          yield return clusters[index];
+        }
+      }
     }
   }

branches/Parameter-less Population Pyramid/ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs

@@ -19 +19 @@
     };
 
+    // These are the clusters that should be built using "solutions" and the seed 123
     private static int[][] correctClusters = new int[][] {
       new int[] { 2, 3 },
@@ -30 +31 @@
     [TestMethod]
     public void LinkageTreeTestAdd() {
-      LinkageTree tree = new LinkageTree(Length);
+      MersenneTwister rand = new MersenneTwister();
+      LinkageTree tree = new LinkageTree(Length, rand);
       tree.Add(solutions[0]);
       tree.Add(solutions[1]);
@@ -43 +45 @@
     [TestMethod]
     public void LinkageTreeTestEntropyDistance() {
-      LinkageTree tree = new LinkageTree(Length);
+      MersenneTwister rand = new MersenneTwister();
+      LinkageTree tree = new LinkageTree(Length, rand);
       PrivateObject hidden = new PrivateObject(tree);
       // No information should result in a distance of 0
@@ -63 +66 @@
     [TestMethod]
     public void LinkageTreeTestRebuild() {
-      LinkageTree tree = new LinkageTree(Length);
+      // The seed matters as equal sized clusters can appear in any order
+      MersenneTwister rand = new MersenneTwister(123);
+      LinkageTree tree = new LinkageTree(Length, rand);
       foreach (var solution in solutions) {
         tree.Add(solution);
       }
-      MersenneTwister rand = new MersenneTwister(123);
-      tree.Rebuild(rand);
-      PrivateObject hidden = new PrivateObject(tree);
-      var ordering = (List<int>)hidden.GetField("clusterOrdering");
-      var clusters = (List<int>[])hidden.GetField("clusters");
-      int[][] comparable = new int[ordering.Count][];
-      for (int i = 0; i < ordering.Count; i++) {
-        var found = clusters[ordering[i]].ToArray();
-        Array.Sort(found);
-        Assert.IsTrue(correctClusters[i].SequenceEqual(found));
+
+      // Check if the clusters created contain the expected variables.
+      var found = tree.Clusters.ToArray();
+      Assert.AreEqual(correctClusters.Length, found.Length);
+      for (int i = 0; i < found.Length; i++) {
+        found[i].Sort();
+        Assert.IsTrue(found[i].SequenceEqual(correctClusters[i]), string.Format("Failed On Cluster {0}", i));
       }
     }