Free cookie consent management tool by TermsFeed Policy Generator

# Changeset 11674

Ignore:
Timestamp:
12/09/14 17:00:53 (9 years ago)
Message:

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

Location:
branches/Parameter-less Population Pyramid
Files:
4 edited

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

 r11672 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid { public class LinkageTree { 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]++; } 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; // 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" } 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 } // 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(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]; } } 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 // 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; } // 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; } // 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

 r11672 #endregion using System.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; protected DeceptiveStepTrapProblem(DeceptiveStepTrapProblem original, Cloner cloner) : base(original, cloner) { RegisterParameterEvents(); } public override IDeepCloneable Clone(Cloner cloner) { : base() { Parameters.Add(new FixedValueParameter(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; } } } 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

 r11672 using System; using System.Collections.Generic; using HeuristicLab.Common; using HeuristicLab.Core; protected virtual int TrapMaximum { get { return TrapSize;  } get { return TrapSize; } } // 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; 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

 r11656 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
Note: See TracChangeset for help on using the changeset viewer.