Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Parameter-less Population Pyramid/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs @ 11667

Last change on this file since 11667 was 11667, checked in by bgoldman, 9 years ago

#2282 Major bug fixes, now gets answers close to correct.

File size: 8.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using System.Threading.Tasks;
27using HeuristicLab.Analysis;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Data;
31using HeuristicLab.Encodings.BinaryVectorEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
38  [Item("Parameter-less Population Pyramid", "Binary value optimization algorithm which requires no configuration.")]
39  [StorableClass]
40  [Creatable("Parameterless Population Pyramid")]
41
42  public class ParameterlessPopulationPyramid : AlgorithmBase {
43    private readonly IRandom random = new MersenneTwister();
44    private List<Population> pyramid;
45    private EvaluationTracker tracker;
46
47    // Tracks all solutions in Pyramid for quick membership checks
48    private HashSet<bool[]> seen = new HashSet<bool[]>(new EnumerableBoolEqualityComparer());
49
50    private const string MaximumIterationsParameterName = "Maximum Iterations";
51
52    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
53      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; }
54    }
55
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
133    [StorableConstructor]
134    protected ParameterlessPopulationPyramid(bool deserializing) : base(deserializing) { }
135
136    protected ParameterlessPopulationPyramid(ParameterlessPopulationPyramid original, Cloner cloner)
137      : base(original, cloner) {
138    }
139
140    public override IDeepCloneable Clone(Cloner cloner) {
141      return new ParameterlessPopulationPyramid(this, cloner);
142    }
143
144    public ParameterlessPopulationPyramid() {
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)));
149    }
150
151    private void AddIfUnique(bool[] solution, int level) {
152      // Don't add things you have seen
153      if (seen.Contains(solution)) return;
154      if (level == pyramid.Count) {
155        pyramid.Add(new Population(tracker.Length, random));
156      }
157      var copied = (bool[])solution.Clone();
158      pyramid[level].Add(copied);
159      seen.Add(copied);
160    }
161
162    private double iterate() {
163      // Create a random solution
164      bool[] solution = new bool[tracker.Length];
165      for (int i = 0; i < solution.Length; i++) {
166        solution[i] = random.Next(2) == 1;
167      }
168      double fitness = tracker.Evaluate(solution);
169      fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random);
170      AddIfUnique(solution, 0);
171
172      for (int level = 0; level < pyramid.Count; level++) {
173        var current = pyramid[level];
174        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random);
175        // add it to the next level if its a strict fitness improvement
176        if (tracker.IsBetter(newFitness, fitness)) {
177          fitness = newFitness;
178          AddIfUnique(solution, level + 1);
179        }
180      }
181      return fitness;
182    }
183
184    protected override void Run() {
185      if (SetSeedRandomly) Seed = new System.Random().Next();
186      pyramid = new List<Population>();
187      seen.Clear();
188      random.Reset(Seed);
189      tracker = new EvaluationTracker(Problem, MaximumEvaluations);
190      Results.Add(new Result("Iterations", new IntValue(0)));
191      Results.Add(new Result("Evaluations", new IntValue(0)));
192      Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution)));
193      Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality)));
194      Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation)));
195      var table = new DataTable("Qualities");
196      table.Rows.Add(new DataRow("Best Quality"));
197      var iterationRows = new DataRow("Iteration Quality");
198      iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
199      table.Rows.Add(iterationRows);
200      Results.Add(new Result("Qualities", table));
201      for (ResultsIterations = 0; ResultsIterations < MaximumIterations; ResultsIterations++) {
202        double fitness = double.NaN;
203
204        try {
205          fitness = iterate();
206        }
207        catch (OperationCanceledException) {
208          throw;
209        }
210        finally {
211          ResultsEvaluations = tracker.Evaluations;
212          ResultsBestSolution = new BinaryVector(tracker.BestSolution);
213          ResultsBestQuality = tracker.BestQuality;
214          ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation;
215          ResultsQualitiesBest.Values.Add(tracker.BestQuality);
216          ResultsQualitiesIteration.Values.Add(fitness);
217        }
218      }
219    }
220  }
221}
Note: See TracBrowser for help on using the repository browser.