Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11666


Ignore:
Timestamp:
12/05/14 18:25:03 (9 years ago)
Author:
bgoldman
Message:

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

Location:
branches/Parameter-less Population Pyramid
Files:
4 added
1 deleted
7 edited

Legend:

Unmodified
Added
Removed

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

    r11664 r11666  
    3737  </PropertyGroup>
    3838  <ItemGroup>
     39    <Reference Include="HeuristicLab.Analysis-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     40      <SpecificVersion>False</SpecificVersion>
     41      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Analysis-3.3.dll</HintPath>
     42    </Reference>
    3943    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
    4044      <SpecificVersion>False</SpecificVersion>
    … …  
    101105    <Compile Include="AlgorithmBase.cs" />
    102106    <Compile Include="LinkageCrossover.cs" />
    103     <Compile Include="DeceptiveTrapProblem.cs" />
     107    <Compile Include="Problems\DeceptiveTrapProblem.cs" />
    104108    <Compile Include="HillClimber.cs" />
    105109    <Compile Include="LinkageTree.cs" />
    … …  
    108112    <Compile Include="Problems\BinaryVectorProblem.cs" />
    109113    <Compile Include="Plugin.cs" />
     114    <Compile Include="Problems\EvaluationTracker.cs" />
     115    <Compile Include="Problems\HIFFProblem.cs" />
     116    <Compile Include="Problems\IBinaryVectorProblem.cs" />
    110117    <Compile Include="Problems\OneMaxProblem.cs" />
    111118    <Compile Include="Properties\AssemblyInfo.cs" />

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

    r11664 r11666  
    8282      }
    8383    }
    84     public static double ImproveToLocalOptimum(BinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) {
     84    public static double ImproveToLocalOptimum(IBinaryVectorProblem problem, bool[] solution, double fitness, IRandom rand) {
    8585      var tried = new HashSet<int>();
    8686      do {

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

    r11663 r11666  
    3030  public static class LinkageCrossover {
    3131
    32     public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, BinaryVectorProblem problem, IRandom rand) {
     32    public static double ImproveUsingTree(LinkageTree tree, IList<bool[]> donors, bool[] solution, double fitness, IBinaryVectorProblem problem, IRandom rand) {
    3333      var options = Enumerable.Range(0, donors.Count).ToArray();
    3434      foreach (var cluster in tree.Clusters) {
    … …  
    3636        // from the current solution for this cluster of genes
    3737        bool donorFound = false;
    38         foreach (var donorIndex in options.Shuffle(rand)) {
     38        foreach (var donorIndex in options.ShuffleList(rand)) {
    3939          // Attempt the donation
    4040          fitness = Donate(solution, fitness, donors[donorIndex], cluster, problem, out donorFound);
    … …  
    4545    }
    4646
    47     private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, BinaryVectorProblem problem, out bool changed) {
     47    private static double Donate(bool[] solution, double fitness, bool[] source, IEnumerable<int> cluster, IBinaryVectorProblem problem, out bool changed) {
    4848      // keep track of which bits flipped to make the donation
    4949      List<int> flipped = new List<int>();

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

    r11663 r11666  
    3535    }
    3636    public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random) {
    37       return list.ShuffleInPlace(random, 0, list.Count);
     37      return list.ShuffleInPlace(random, 0, list.Count - 1);
    3838    }
    3939    public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int maxIndex) {
    … …  
    4141    }
    4242    public static IList<T> ShuffleInPlace<T>(this IList<T> list, IRandom random, int minIndex, int maxIndex) {
    43       for (int i = list.Count - 1; i > 0; i--) {
    44         int swapIndex = random.Next(i + 1);
     43      for (int i = maxIndex; i > minIndex; i--) {
     44        int swapIndex = random.Next(minIndex, i + 1);
    4545        list.Swap(i, swapIndex);
    4646      }
    … …  
    4848    }
    4949
    50     public static IEnumerable<T> Shuffle<T>(this IList<T> source, IRandom random) {
     50    public static IEnumerable<T> ShuffleList<T>(this IList<T> source, IRandom random) {
    5151      for (int i = source.Count - 1; i > 0; i--) {
    5252        // Swap element "i" with a random earlier element (including itself)
    … …  
    166166      for (int index = length; index < clusters.Length; index++) {
    167167        // Shuffle everything not yet in the path
    168         topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count);
     168        topLevel.ShuffleInPlace(rand, end_of_path, topLevel.Count-1);
    169169
    170170        // if nothing in the path, just add a random usable node

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

    r11664 r11666  
    2525using System.Text;
    2626using System.Threading.Tasks;
     27using HeuristicLab.Analysis;
    2728using HeuristicLab.Common;
    2829using HeuristicLab.Core;
    2930using HeuristicLab.Data;
     31using HeuristicLab.Encodings.BinaryVectorEncoding;
    3032using HeuristicLab.Optimization;
    3133using HeuristicLab.Parameters;
    … …  
    3941 
    4042  public class ParameterlessPopulationPyramid : AlgorithmBase {
    41     [Storable]
    42     private IRandom random;
    43 
    44     [Storable]
     43    private readonly IRandom random = new MersenneTwister();
    4544    private List<Population> pyramid;
     45    private EvaluationTracker tracker;
    4646
    4747    // Tracks all solutions in Pyramid for quick membership checks
    4848    private readonly HashSet<bool[]> seen = new HashSet<bool[]>();
    4949
    50     private const string IterationsParameterName = "Iterations";
    51 
    52     public IFixedValueParameter<IntValue> IterationsParameter {
    53       get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
     50    private const string MaximumIterationsParameterName = "Maximum Iterations";
     51
     52    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
     53      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; }
    5454    }
    5555   
    56     public int Iterations {
    57       get { return IterationsParameter.Value.Value; }
    58       set { IterationsParameter.Value.Value = value; }
    59     }
     56    public int MaximumIterations {
     57      get { return MaximumIterationsParameter.Value.Value; }
     58      set { MaximumIterationsParameter.Value.Value = value; }
     59    }
     60
     61    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
     62
     63    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
     64      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
     65    }
     66
     67    public int MaximumEvaluations {
     68      get { return MaximumEvaluationsParameter.Value.Value; }
     69      set { MaximumEvaluationsParameter.Value.Value = value; }
     70    }
     71
     72   
     73    private const string SeedParameterName = "Seed";
     74
     75    public IFixedValueParameter<IntValue> SeedParameter {
     76      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
     77    }
     78
     79    public int Seed {
     80      get { return SeedParameter.Value.Value; }
     81      set { SeedParameter.Value.Value = value; }
     82    }
     83
     84    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
     85
     86    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
     87      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
     88    }
     89
     90    public bool SetSeedRandomly {
     91      get { return SetSeedRandomlyParameter.Value.Value; }
     92      set { SetSeedRandomlyParameter.Value.Value = value; }
     93    }
     94
     95    #region ResultsProperties
     96    private double ResultsBestQuality {
     97      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
     98      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
     99    }
     100
     101    private BinaryVector ResultsBestSolution {
     102      get { return (BinaryVector)Results["Best Solution"].Value; }
     103      set { Results["Best Solution"].Value = value; }
     104    }
     105
     106    private int ResultsBestFoundOnEvaluation {
     107      get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; }
     108      set { ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value = value; }
     109    }
     110
     111    private int ResultsEvaluations {
     112      get { return ((IntValue)Results["Evaluations"].Value).Value; }
     113      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
     114    }
     115    private int ResultsIterations {
     116      get { return ((IntValue)Results["Iterations"].Value).Value; }
     117      set { ((IntValue)Results["Iterations"].Value).Value = value; }
     118    }
     119
     120    private DataTable ResultsQualities {
     121      get { return ((DataTable)Results["Qualities"].Value); }
     122    }
     123    private DataRow ResultsQualitiesBest {
     124      get { return ResultsQualities.Rows["Best Quality"]; }
     125    }
     126
     127    private DataRow ResultsQualitiesIteration {
     128      get { return ResultsQualities.Rows["Iteration Quality"]; }
     129    }
     130
     131    #endregion
     132
    60133    [StorableConstructor]
    61134    protected ParameterlessPopulationPyramid(bool deserializing) : base(deserializing) { }
    … …  
    70143
    71144    public ParameterlessPopulationPyramid() {
    72       Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "", new IntValue(100)));
     145      Parameters.Add(new FixedValueParameter<IntValue>(MaximumIterationsParameterName, "", new IntValue(100)));
     146      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(1000)));
     147      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
     148      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
    73149    }
    74150
    … …  
    78154      if (seen.Contains(solution)) return;
    79155      if (level == pyramid.Count) {
    80         pyramid.Add(new Population(Problem.Length, random));
     156        pyramid.Add(new Population(tracker.Length, random));
    81157      }
    82158      pyramid[level].Add(solution);
    … …  
    86162    private double iterate() {
    87163      // Create a random solution
    88       bool[] solution = new bool[Problem.Length];
     164      bool[] solution = new bool[tracker.Length];
    89165      for (int i = 0; i < solution.Length; i++) {
    90166        solution[i] = random.Next(2) == 1;
    91167      }
    92       double fitness = Problem.Evaluate(solution);
    93       fitness = HillClimber.ImproveToLocalOptimum(Problem, solution, fitness, random);
     168      double fitness = tracker.Evaluate(solution);
     169      fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random);
    94170      AddIfUnique(solution, 0);
    95171      for (int level = 0; level < pyramid.Count; level++) {
    96172        var current = pyramid[level];
    97         double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, Problem, random);
     173        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random);
    98174        // add it to the next level if its a strict fitness improvement
    99         if (Problem.IsBetter(newFitness, fitness)) {
     175        if (tracker.IsBetter(newFitness, fitness)) {
    100176          fitness = newFitness;
    101177          AddIfUnique(solution, level + 1);
    … …  
    106182
    107183    protected override void Run() {
     184      if (SetSeedRandomly) Seed = new System.Random().Next();
    108185      pyramid = new List<Population>();
    109       random = new MersenneTwister();
    110       var BestQuality = new DoubleValue(double.NaN);
    111       Results.Add(new Result("Best quality", BestQuality));
    112       for (int iteration = 0; iteration < Iterations; iteration++) {
    113         var fitness = iterate();
    114         if (double.IsNaN(BestQuality.Value) || Problem.IsBetter(fitness, BestQuality.Value)) {
    115           BestQuality.Value = fitness;
     186      random.Reset(Seed);
     187      tracker = new EvaluationTracker(Problem, MaximumEvaluations);
     188      Results.Add(new Result("Iterations", new IntValue(0)));
     189      Results.Add(new Result("Evaluations", new IntValue(0)));
     190      Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution)));
     191      Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality)));
     192      Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation)));
     193      var table = new DataTable("Qualities");
     194      table.Rows.Add(new DataRow("Best Quality"));
     195      var iterationRows = new DataRow("Iteration Quality");
     196      iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
     197      table.Rows.Add(iterationRows);
     198      Results.Add(new Result("Qualities", table));
     199      for (ResultsIterations = 0; ResultsIterations < MaximumIterations; ResultsIterations++) {
     200        double fitness = double.NaN;
     201
     202        try {
     203          fitness = iterate();
    116204        }
     205        catch (OperationCanceledException) {
     206          throw;
     207        }
     208        finally {
     209          ResultsEvaluations = tracker.Evaluations;
     210          ResultsBestSolution = new BinaryVector(tracker.BestSolution);
     211          ResultsBestQuality = tracker.BestQuality;
     212          ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation;
     213          ResultsQualitiesBest.Values.Add(tracker.BestQuality);
     214          ResultsQualitiesIteration.Values.Add(fitness);
     215        }       
    117216      }
    118217    }

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

    r11640 r11666  
    2929namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
    3030  [StorableClass]
    31   public abstract class BinaryVectorProblem : Problem {
     31  public abstract class BinaryVectorProblem : Problem, IBinaryVectorProblem {
    3232    private const string LengthParameterName = "Length";
    3333

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

    r11663 r11666  
    2121    // These are the clusters that should be built using "solutions" and the seed 123
    2222    private static int[][] correctClusters = new int[][] {
     23      new int[] { 4, 5 },
    2324      new int[] { 2, 3 },
    24       new int[] { 4, 5 },
    2525      new int[] { 0, 1 },
    2626      new int[] { 6, 7, 8 },
Note: See TracChangeset for help on using the changeset viewer.