Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11663


Ignore:
Timestamp:
12/05/14 12:25:32 (9 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:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3.csproj

    r11656 r11663  
    100100  <ItemGroup>
    101101    <Compile Include="AlgorithmBase.cs" />
     102    <Compile Include="LinkageCrossover.cs" />
    102103    <Compile Include="DeceptiveTrapProblem.cs" />
    103104    <Compile Include="HillClimber.cs" />
    104105    <Compile Include="LinkageTree.cs" />
     106    <Compile Include="Population.cs" />
    105107    <Compile Include="Problems\BinaryVectorProblem.cs" />
    106108    <Compile Include="Plugin.cs" />
  • branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/LinkageTree.cs

    r11662 r11663  
    6565    private readonly int[][][] occurances;
    6666    private readonly List<int>[] clusters;
    67     private readonly List<int> clusterOrdering;
     67    private List<int> clusterOrdering;
    6868    private readonly int length;
    69 
    70     public LinkageTree(int length) {
     69    private readonly IRandom rand;
     70    private bool rebuildRequired = false;
     71
     72    public LinkageTree(int length, IRandom rand) {
    7173      this.length = length;
     74      this.rand = rand;
    7275      occurances = new int[length][][];
    7376
     77      // Create a lower triangular matrix without the diagonal
    7478      for (int i = 1; i < length; i++) {
    7579        occurances[i] = new int[i][];
     
    99103        }
    100104      }
     105      rebuildRequired = true;
    101106    }
    102107
     
    109114        var p = value / total;
    110115        sum += (p * Math.Log(p));
    111 
    112116      }
    113117      return sum;
     
    115119
    116120    private double EntropyDistance(int i, int j) {
     121      // This ensures you are using the lower triangular part of "occurances"
    117122      if (i < j) {
    118123        int temp = i;
     
    139144    }
    140145
    141     public void Rebuild(IRandom rand) {
     146    private void Rebuild() {
    142147      // Keep track of which clusters have not been merged
    143148      var topLevel = Enumerable.Range(0, length).ToList();
     
    236241        if (useful[i]) clusterOrdering.Add(i);
    237242      }
    238       // TODO Shuffle cluster ordering
     243
     244      // Shuffle before sort to ensure ties are broken randomly
    239245      clusterOrdering.ShuffleInPlace(rand);
    240       clusterOrdering.Sort((i, j) => clusters[i].Count.CompareTo(clusters[j].Count));
    241     }
    242 
    243     public double ImproveUsingTree(bool[] solution, double fitness, BinaryVectorProblem problem) {
    244       return fitness;
     246      clusterOrdering = clusterOrdering.OrderBy(i => clusters[i].Count).ToList();
     247    }
     248
     249    public IEnumerable<List<int>> Clusters {
     250      get {
     251        // Just in time rebuilding
     252        if (rebuildRequired) Rebuild();
     253        foreach (var index in clusterOrdering) {
     254          // Send out the clusters in the desired order
     255          yield return clusters[index];
     256        }
     257      }
    245258    }
    246259  }
  • branches/Parameter-less Population Pyramid/ParameterlessPopulationPyramid.Test/LinkageTreeTest.cs

    r11662 r11663  
    1919    };
    2020
     21    // These are the clusters that should be built using "solutions" and the seed 123
    2122    private static int[][] correctClusters = new int[][] {
    2223      new int[] { 2, 3 },
     
    3031    [TestMethod]
    3132    public void LinkageTreeTestAdd() {
    32       LinkageTree tree = new LinkageTree(Length);
     33      MersenneTwister rand = new MersenneTwister();
     34      LinkageTree tree = new LinkageTree(Length, rand);
    3335      tree.Add(solutions[0]);
    3436      tree.Add(solutions[1]);
     
    4345    [TestMethod]
    4446    public void LinkageTreeTestEntropyDistance() {
    45       LinkageTree tree = new LinkageTree(Length);
     47      MersenneTwister rand = new MersenneTwister();
     48      LinkageTree tree = new LinkageTree(Length, rand);
    4649      PrivateObject hidden = new PrivateObject(tree);
    4750      // No information should result in a distance of 0
     
    6366    [TestMethod]
    6467    public void LinkageTreeTestRebuild() {
    65       LinkageTree tree = new LinkageTree(Length);
     68      // The seed matters as equal sized clusters can appear in any order
     69      MersenneTwister rand = new MersenneTwister(123);
     70      LinkageTree tree = new LinkageTree(Length, rand);
    6671      foreach (var solution in solutions) {
    6772        tree.Add(solution);
    6873      }
    69       MersenneTwister rand = new MersenneTwister(123);
    70       tree.Rebuild(rand);
    71       PrivateObject hidden = new PrivateObject(tree);
    72       var ordering = (List<int>)hidden.GetField("clusterOrdering");
    73       var clusters = (List<int>[])hidden.GetField("clusters");
    74       int[][] comparable = new int[ordering.Count][];
    75       for (int i = 0; i < ordering.Count; i++) {
    76         var found = clusters[ordering[i]].ToArray();
    77         Array.Sort(found);
    78         Assert.IsTrue(correctClusters[i].SequenceEqual(found));
     74
     75      // Check if the clusters created contain the expected variables.
     76      var found = tree.Clusters.ToArray();
     77      Assert.AreEqual(correctClusters.Length, found.Length);
     78      for (int i = 0; i < found.Length; i++) {
     79        found[i].Sort();
     80        Assert.IsTrue(found[i].SequenceEqual(correctClusters[i]), string.Format("Failed On Cluster {0}", i));
    7981      }
    8082    }
Note: See TracChangeset for help on using the changeset viewer.