Changeset 11666 for branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3

Timestamp:

12/05/14 18:25:03 (10 years ago)

Author:

bgoldman

Message:

#2282 Evaluation counting, results and graphing, HIFF problem.

Location:

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

Files:

• DeceptiveTrapProblem.cs (deleted)
• HeuristicLab.Algorithms.ParameterlessPopulationPyramid-3.3.csproj (modified) (3 diffs)
• HillClimber.cs (modified) (1 diff)
• LinkageCrossover.cs (modified) (3 diffs)
• LinkageTree.cs (modified) (4 diffs)
• ParameterlessPopulationPyramid.cs (modified) (6 diffs)
• Problems/BinaryVectorProblem.cs (modified) (1 diff)
• Problems/DeceptiveTrapProblem.cs (added)
• Problems/EvaluationTracker.cs (added)
• Problems/HIFFProblem.cs (added)
• Problems/IBinaryVectorProblem.cs (added)

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

@@ -37 +37 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
       <SpecificVersion>False</SpecificVersion>
@@ -101 +105 @@
     <Compile Include="AlgorithmBase.cs" />
     <Compile Include="LinkageCrossover.cs" />
-    <Compile Include="DeceptiveTrapProblem.cs" />
+    <Compile Include="Problems\DeceptiveTrapProblem.cs" />
     <Compile Include="HillClimber.cs" />
     <Compile Include="LinkageTree.cs" />
@@ -108 +112 @@
     <Compile Include="Problems\BinaryVectorProblem.cs" />
     <Compile Include="Plugin.cs" />
+    <Compile Include="Problems\EvaluationTracker.cs" />
+    <Compile Include="Problems\HIFFProblem.cs" />
+    <Compile Include="Problems\IBinaryVectorProblem.cs" />
     <Compile Include="Problems\OneMaxProblem.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />

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

@@ -82 +82 @@
       }
     }
-    public static double ImproveToLocalOptimum(BinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) {
+    public static double ImproveToLocalOptimum(IBinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) {
       var tried = new HashSet<int>();
       do {

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

@@ -30 +30 @@
   public static class LinkageCrossover {
 
-    public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, BinaryVectorProblem problem, IRandom rand) {
+    public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, IBinaryVectorProblem problem, IRandom rand) {
       var options = Enumerable.Range(0, donors.Count).ToArray();
       foreach (var cluster in tree.Clusters) {
@@ -36 +36 @@
         // from the current solution for this cluster of genes
         bool donorFound = false;
-        foreach (var donorIndex in options.Shuffle(rand)) {
+        foreach (var donorIndex in options.ShuffleList(rand)) {
           // Attempt the donation
           fitness = Donate(solution, fitness, donors[donorIndex], cluster, problem, out donorFound);
@@ -45 +45 @@
     }
 
-    private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, BinaryVectorProblem problem, out bool changed) {
+    private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, IBinaryVectorProblem problem, out bool changed) {
       // keep track of which bits flipped to make the donation
       List<int> flipped = new List<int>();

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

@@ -35 +35 @@
     }
     public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random) {
-      return list.ShuffleInPlace(random, 0, list.Count);
+      return list.ShuffleInPlace(random, 0, list.Count - 1);
     }
     public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int maxIndex) {
@@ -41 +41 @@
     }
     public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int minIndex, int maxIndex) {
-      for (int i = list.Count - 1; i > 0; i--) {
-        int swapIndex = random.Next(i + 1);
+      for (int i = maxIndex; i > minIndex; i--) {
+        int swapIndex = random.Next(minIndex, i + 1);
         list.Swap(i, swapIndex);
       }
@@ -48 +48 @@
     }
 
-    public static IEnumerable<T> Shuffle<T>(this IList<T> source, IRandom random) {
+    public static IEnumerable<T> ShuffleList<T>(this IList<T> source, IRandom random) {
       for (int i = source.Count - 1; i > 0; i--) {
         // Swap element "i" with a random earlier element (including itself)
@@ -166 +166 @@
       for (int index = length; index < clusters.Length; index++) {
         // Shuffle everything not yet in the path
-        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count);
+        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1);
 
         // if nothing in the path, just add a random usable node

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

@@ -25 +25 @@
 using System.Text;
 using System.Threading.Tasks;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.BinaryVectorEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
@@ -39 +41 @@
   
   public class ParameterlessPopulationPyramid : AlgorithmBase {
-    [Storable]
-    private IRandom random;
-
-    [Storable]
+    private readonly IRandom random = new MersenneTwister();
     private List<Population> pyramid;
+    private EvaluationTracker tracker;
 
     // Tracks all solutions in Pyramid for quick membership checks
     private readonly HashSet<bool[]> seen = new HashSet<bool[]>();
 
-    private const string IterationsParameterName = "Iterations";
-
-    public IFixedValueParameter<IntValue> IterationsParameter {
-      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
+    private const string MaximumIterationsParameterName = "Maximum Iterations";
+
+    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; }
     }
     
-    public int Iterations {
-      get { return IterationsParameter.Value.Value; }
-      set { IterationsParameter.Value.Value = value; }
-    }
+    public int MaximumIterations {
+      get { return MaximumIterationsParameter.Value.Value; }
+      set { MaximumIterationsParameter.Value.Value = value; }
+    }
+
+    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
+
+    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
+    }
+
+    public int MaximumEvaluations {
+      get { return MaximumEvaluationsParameter.Value.Value; }
+      set { MaximumEvaluationsParameter.Value.Value = value; }
+    }
+
+    
+    private const string SeedParameterName = "Seed";
+
+    public IFixedValueParameter<IntValue> SeedParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
+    }
+
+    public int Seed {
+      get { return SeedParameter.Value.Value; }
+      set { SeedParameter.Value.Value = value; }
+    }
+
+    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
+
+    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
+      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
+    }
+
+    public bool SetSeedRandomly {
+      get { return SetSeedRandomlyParameter.Value.Value; }
+      set { SetSeedRandomlyParameter.Value.Value = value; }
+    }
+
+    #region ResultsProperties
+    private double ResultsBestQuality {
+      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
+      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
+    }
+
+    private BinaryVector ResultsBestSolution {
+      get { return (BinaryVector)Results["Best Solution"].Value; }
+      set { Results["Best Solution"].Value = value; }
+    }
+
+    private int ResultsBestFoundOnEvaluation {
+      get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; }
+      set { ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value = value; }
+    }
+
+    private int ResultsEvaluations {
+      get { return ((IntValue)Results["Evaluations"].Value).Value; }
+      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
+    }
+    private int ResultsIterations {
+      get { return ((IntValue)Results["Iterations"].Value).Value; }
+      set { ((IntValue)Results["Iterations"].Value).Value = value; }
+    }
+
+    private DataTable ResultsQualities {
+      get { return ((DataTable)Results["Qualities"].Value); }
+    }
+    private DataRow ResultsQualitiesBest {
+      get { return ResultsQualities.Rows["Best Quality"]; }
+    }
+
+    private DataRow ResultsQualitiesIteration {
+      get { return ResultsQualities.Rows["Iteration Quality"]; }
+    }
+
+    #endregion
+
     [StorableConstructor]
     protected ParameterlessPopulationPyramid(bool deserializing) : base(deserializing) { }
@@ -70 +143 @@
 
     public ParameterlessPopulationPyramid() {
-      Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "", new IntValue(100)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaximumIterationsParameterName, "", new IntValue(100)));
+      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(1000)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
     }
 
@@ -78 +154 @@
       if (seen.Contains(solution)) return;
       if (level == pyramid.Count) {
-        pyramid.Add(new Population(Problem.Length, random));
+        pyramid.Add(new Population(tracker.Length, random));
       }
       pyramid[level].Add(solution);
@@ -86 +162 @@
     private double iterate() {
       // Create a random solution
-      bool[] solution = new bool[Problem.Length];
+      bool[] solution = new bool[tracker.Length];
       for (int i = 0; i < solution.Length; i++) {
         solution[i] = random.Next(2) == 1;
       }
-      double fitness = Problem.Evaluate(solution);
-      fitness = HillClimber.ImproveToLocalOptimum(Problem, solution, fitness, random);
+      double fitness = tracker.Evaluate(solution);
+      fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random);
       AddIfUnique(solution, 0);
       for (int level = 0; level < pyramid.Count; level++) {
         var current = pyramid[level];
-        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, Problem, random);
+        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random);
         // add it to the next level if its a strict fitness improvement
-        if (Problem.IsBetter(newFitness, fitness)) {
+        if (tracker.IsBetter(newFitness, fitness)) {
           fitness = newFitness;
           AddIfUnique(solution, level + 1);
@@ -106 +182 @@
 
     protected override void Run() {
+      if (SetSeedRandomly) Seed = new System.Random().Next();
       pyramid = new List<Population>();
-      random = new MersenneTwister();
-      var BestQuality = new DoubleValue(double.NaN);
-      Results.Add(new Result("Best quality", BestQuality));
-      for (int iteration = 0; iteration < Iterations; iteration++) {
-        var fitness = iterate();
-        if (double.IsNaN(BestQuality.Value) || Problem.IsBetter(fitness, BestQuality.Value)) {
-          BestQuality.Value = fitness;
+      random.Reset(Seed);
+      tracker = new EvaluationTracker(Problem, MaximumEvaluations);
+      Results.Add(new Result("Iterations", new IntValue(0)));
+      Results.Add(new Result("Evaluations", new IntValue(0)));
+      Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution)));
+      Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality)));
+      Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation)));
+      var table = new DataTable("Qualities");
+      table.Rows.Add(new DataRow("Best Quality"));
+      var iterationRows = new DataRow("Iteration Quality");
+      iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
+      table.Rows.Add(iterationRows);
+      Results.Add(new Result("Qualities", table));
+      for (ResultsIterations = 0; ResultsIterations < MaximumIterations; ResultsIterations++) {
+        double fitness = double.NaN;
+
+        try {
+          fitness = iterate();
         }
+        catch (OperationCanceledException) {
+          throw;
+        }
+        finally {
+          ResultsEvaluations = tracker.Evaluations;
+          ResultsBestSolution = new BinaryVector(tracker.BestSolution);
+          ResultsBestQuality = tracker.BestQuality;
+          ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation;
+          ResultsQualitiesBest.Values.Add(tracker.BestQuality);
+          ResultsQualitiesIteration.Values.Add(fitness);
+        }        
       }
     }

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

@@ -29 +29 @@
 namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
   [StorableClass]
-  public abstract class BinaryVectorProblem : Problem {
+  public abstract class BinaryVectorProblem : Problem, IBinaryVectorProblem {
     private const string LengthParameterName = "Length";