Changeset 11674


Ignore:
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:
4 edited

Legend:

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

    r11672 r11674  
    2727
    2828namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
    29  
     29
    3030  public class LinkageTree {
    3131
     
    6666        for (int j = 0; j < i; j++) {
    6767          // Updates the entry of the 4 long array based on the two bits
    68           var pattern = (Convert.ToInt32(solution[j]) << 1) + Convert.ToInt32(solution[i]);
     68
     69          var pattern = (Convert.ToByte(solution[j]) << 1) + Convert.ToByte(solution[i]);
    6970          occurances[i][j][pattern]++;
    7071        }
     
    7879    private static double NegativeEntropy(int[] counts, double total) {
    7980      double sum = 0;
    80       foreach (var value in counts) {
    81         if (value == 0) continue;
    82         var p = value / total;
    83         sum += (p * Math.Log(p));
     81      for (int i = 0; i < counts.Length; i++) {
     82        if (counts[i] != 0) {
     83          sum += ((counts[i] / total) * Math.Log(counts[i] / total));
     84        }
    8485      }
    8586      return sum;
     
    8889    // Uses the frequency table to calcuate the entropy distance between two indices.
    8990    // In the GECCO paper, calculates Equation 1
     91    private int[] bits = new int[4];
    9092    private double EntropyDistance(int i, int j) {
    9193      // This ensures you are using the lower triangular part of "occurances"
     
    9698      }
    9799      var entry = occurances[i][j];
    98       int[] bits = new int[4];
    99100      // extracts the occurrences of the individual bits
    100101      bits[0] = entry[0] + entry[2];  // i zero
     
    114115    }
    115116
     117
     118
    116119    // Performs O(N^2) clustering based on the method described in:
    117120    // "Optimal implementations of UPGMA and other common clustering algorithms"
    118121    // by I. Gronau and S. Moran
    119122    // In the GECCO paper, Figure 2 is a simplified version of this algorithm.
     123    private double[][] distances;
    120124    private void Rebuild() {
     125      if (distances == null) {
     126        distances = new double[clusters.Length * 2 - 1][];
     127        for (int i = 0; i < distances.Length; i++)
     128          distances[i] = new double[clusters.Length * 2 - 1];
     129      }
     130
     131
    121132      // Keep track of which clusters have not been merged
    122       var topLevel = Enumerable.Range(0, length).ToList();
    123       bool[] useful = Enumerable.Repeat(true, clusters.Length).ToArray();
     133      var topLevel = new List<int>(length);
     134      for (int i = 0; i < length; i++)
     135        topLevel.Add(i);
     136
     137      bool[] useful = new bool[clusters.Length];
     138      for (int i = 0; i < useful.Length; i++)
     139        useful[i] = true;
    124140
    125141      // Store the distances between all clusters
    126       double[,] distances = new double[clusters.Length, clusters.Length];
    127142      for (int i = 1; i < length; i++) {
    128143        for (int j = 0; j < i; j++) {
    129           distances[i, j] = EntropyDistance(clusters[i][0], clusters[j][0]);
     144          distances[i][j] = EntropyDistance(clusters[i][0], clusters[j][0]);
    130145          // make it symmetric
    131           distances[j, i] = distances[i, j];
     146          distances[j][i] = distances[i][j];
    132147        }
    133148      }
     
    139154      for (int index = length; index < clusters.Length; index++) {
    140155        // Shuffle everything not yet in the path
    141         topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1);
     156        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count - 1);
    142157
    143158        // if nothing in the path, just add a random usable node
     
    151166          // best_index stores the location of the best thing in the top level
    152167          int best_index = end_of_path;
    153           double min_dist = distances[final, topLevel[best_index]];
     168          double min_dist = distances[final][topLevel[best_index]];
    154169          // check all options which might be closer to "final" than "topLevel[best_index]"
    155170          for (int option = end_of_path + 1; option < topLevel.Count; option++) {
    156             if (distances[final, topLevel[option]] < min_dist) {
    157               min_dist = distances[final, topLevel[option]];
     171            if (distances[final][topLevel[option]] < min_dist) {
     172              min_dist = distances[final][topLevel[option]];
    158173              best_index = option;
    159174            }
    160175          }
    161176          // If the current last two in the path are minimally distant
    162           if (end_of_path > 1 && min_dist >= distances[final, topLevel[end_of_path - 2]]) {
     177          if (end_of_path > 1 && min_dist >= distances[final][topLevel[end_of_path - 2]]) {
    163178            break;
    164179          }
     
    173188
    174189        // Only keep a cluster if the distance between the joining clusters is > zero
    175         bool keep = !distances[first, second].IsAlmost(0.0);
     190        bool keep = !distances[first][second].IsAlmost(0.0);
    176191        useful[first] = keep;
    177192        useful[second] = keep;
     
    191206          }
    192207          // Use the previous distances to calculate the joined distance
    193           double first_distance = distances[first, x];
     208          double first_distance = distances[first][x];
    194209          first_distance *= clusters[first].Count;
    195           double second_distance = distances[second, x];
     210          double second_distance = distances[second][x];
    196211          second_distance *= clusters[second].Count;
    197           distances[x, index] = ((first_distance + second_distance)
     212          distances[x][index] = ((first_distance + second_distance)
    198213              / (clusters[first].Count + clusters[second].Count));
    199214          // make it symmetric
    200           distances[index, x] = distances[x, index];
     215          distances[index][x] = distances[x][index];
    201216          i++;
    202217        }
  • branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveStepTrapProblem.cs

    r11672 r11674  
    2020#endregion
    2121
    22 using System.Collections.Generic;
    2322using HeuristicLab.Common;
    2423using HeuristicLab.Core;
     
    3736    protected DeceptiveStepTrapProblem(DeceptiveStepTrapProblem original, Cloner cloner)
    3837      : base(original, cloner) {
     38      RegisterParameterEvents();
    3939    }
    4040    public override IDeepCloneable Clone(Cloner cloner) {
     
    5656      : base() {
    5757      Parameters.Add(new FixedValueParameter<IntValue>(StepSizeParameterName, "", new IntValue(2)));
     58      RegisterParameterEvents();
    5859    }
    5960
     61    [StorableHook(HookType.AfterDeserialization)]
     62    private void AfterDeserialization() {
     63      RegisterParameterEvents();
     64    }
     65
     66    private void RegisterParameterEvents() {
     67      TrapSizeParameter.Value.ValueChanged += (o, e) => { offset = -1; };
     68      StepSizeParameter.Value.ValueChanged += (o, e) => { offset = -1; };
     69    }
     70
     71
     72    private int offset = -1;
    6073    private int Offset {
    61       get { return (TrapSize - StepSize) % StepSize; }
     74      get {
     75        if (offset == -1) offset = (TrapSize - StepSize) % StepSize;
     76        return offset;
     77      }
    6278    }
    6379
     
    6682    }
    6783
    68     protected override int Score(bool[] individual, int trapIndex) {
    69       int partial = base.Score(individual, trapIndex);
     84    protected override int Score(bool[] individual, int trapIndex, int trapSize) {
     85      int partial = base.Score(individual, trapIndex, trapSize);
    7086      // introduce plateaus using integer division
    7187      return (Offset + partial) / StepSize;
  • branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/Problems/DeceptiveTrapProblem.cs

    r11672 r11674  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using HeuristicLab.Common;
    2524using HeuristicLab.Core;
     
    5958
    6059    protected virtual int TrapMaximum {
    61       get { return TrapSize;  }
     60      get { return TrapSize; }
    6261    }
    6362
     
    6968
    7069    // In the GECCO paper, calculates Equation 3
    71     protected virtual int Score(bool[] individual, int trapIndex) {
     70    protected virtual int Score(bool[] individual, int trapIndex, int trapSize) {
    7271      int result = 0;
    7372      // count number of bits in trap set to 1
    74       for (int index = trapIndex; index < trapIndex + TrapSize; index++) {
     73      for (int index = trapIndex; index < trapIndex + trapSize; index++) {
    7574        if (individual[index]) result++;
    7675      }
    7776
    7877      // Make it deceptive
    79       if (result < TrapSize) {
    80         result = TrapSize - result - 1;
     78      if (result < trapSize) {
     79        result = trapSize - result - 1;
    8180      }
    8281      return result;
     
    8685      if (individual.Length != Length) throw new ArgumentException("The individual has not the correct length.");
    8786      int total = 0;
    88       for (int i = 0; i < individual.Length; i += TrapSize) {
    89         total += Score(individual, i);
     87      var trapSize = TrapSize;
     88      for (int i = 0; i < individual.Length; i += trapSize) {
     89        total += Score(individual, i, trapSize);
    9090      }
    91       return (double)(total * TrapSize) / (TrapMaximum * individual.Length);
     91      return (double)(total * trapSize) / (TrapMaximum * individual.Length);
    9292    }
    9393  }
  • branches/Parameter-less Population Pyramid/Parameter-less Population Pyramid.sln

    r11656 r11674  
    22Microsoft Visual Studio Solution File, Format Version 12.00
    33# Visual Studio 2013
    4 VisualStudioVersion = 12.0.21005.1
     4VisualStudioVersion = 12.0.31101.0
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{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}"
    77EndProject
    88Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "ParameterlessPopulationPyramid.Test", "ParameterlessPopulationPyramid.Test\ParameterlessPopulationPyramid.Test.csproj", "{0B349086-8EB7-4BC2-8373-44E9CB68B258}"
     9  ProjectSection(ProjectDependencies) = postProject
     10    {9319C447-8183-4DBC-8145-0E3CF98084CC} = {9319C447-8183-4DBC-8145-0E3CF98084CC}
     11  EndProjectSection
    912EndProject
    1013Global
Note: See TracChangeset for help on using the changeset viewer.