source: branches/ProblemRefactoring/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs @ 13361

Last change on this file since 13361 was 13361, checked in by mkommend, 4 years ago

#2521: Adapted real vector encoding, test function problems, P3, CMA-ES and optimization.

File size: 11.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 * and the BEACON Center for the Study of Evolution in Action.
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21#endregion
22
23using System;
24using System.Collections.Generic;
25using System.Threading;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.BinaryVectorEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
37  // This code is based off the publication
38  // B. W. Goldman and W. F. Punch, "Parameter-less Population Pyramid," GECCO, pp. 785–792, 2014
39  // and the original source code in C++11 available from: https://github.com/brianwgoldman/Parameter-less_Population_Pyramid
40  [Item("Parameter-less Population Pyramid (P3)", "Binary value optimization algorithm which requires no configuration. B. W. Goldman and W. F. Punch, Parameter-less Population Pyramid, GECCO, pp. 785–792, 2014")]
41  [StorableClass]
42  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
43  public class ParameterlessPopulationPyramid : BasicAlgorithm {
44    public override Type ProblemType {
45      get { return typeof(ISingleObjectiveProblem<BinaryVectorEncoding, BinaryVector>); }
46    }
47    public new ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector> Problem {
48      get { return (ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector>)base.Problem; }
49      set { base.Problem = (IProblem)value; }
50    }
51
52    private readonly IRandom random = new MersenneTwister();
53    private List<Population> pyramid;
54    private EvaluationTracker tracker;
55
56    // Tracks all solutions in Pyramid for quick membership checks
57    private HashSet<BinaryVector> seen = new HashSet<BinaryVector>(new EnumerableBoolEqualityComparer());
58
59    #region ParameterNames
60    private const string MaximumIterationsParameterName = "Maximum Iterations";
61    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
62    private const string MaximumRuntimeParameterName = "Maximum Runtime";
63    private const string SeedParameterName = "Seed";
64    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
65    #endregion
66
67    #region ParameterProperties
68    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
69      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; }
70    }
71    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
72      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
73    }
74    public IFixedValueParameter<IntValue> MaximumRuntimeParameter {
75      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumRuntimeParameterName]; }
76    }
77    public IFixedValueParameter<IntValue> SeedParameter {
78      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
79    }
80    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
81      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
82    }
83    #endregion
84
85    #region Properties
86    public int MaximumIterations {
87      get { return MaximumIterationsParameter.Value.Value; }
88      set { MaximumIterationsParameter.Value.Value = value; }
89    }
90    public int MaximumEvaluations {
91      get { return MaximumEvaluationsParameter.Value.Value; }
92      set { MaximumEvaluationsParameter.Value.Value = value; }
93    }
94    public int MaximumRuntime {
95      get { return MaximumRuntimeParameter.Value.Value; }
96      set { MaximumRuntimeParameter.Value.Value = value; }
97    }
98    public int Seed {
99      get { return SeedParameter.Value.Value; }
100      set { SeedParameter.Value.Value = value; }
101    }
102    public bool SetSeedRandomly {
103      get { return SetSeedRandomlyParameter.Value.Value; }
104      set { SetSeedRandomlyParameter.Value.Value = value; }
105    }
106    #endregion
107
108    #region ResultsProperties
109    private double ResultsBestQuality {
110      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
111      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
112    }
113
114    private BinaryVector ResultsBestSolution {
115      get { return (BinaryVector)Results["Best Solution"].Value; }
116      set { Results["Best Solution"].Value = value; }
117    }
118
119    private int ResultsBestFoundOnEvaluation {
120      get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; }
121      set { ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value = value; }
122    }
123
124    private int ResultsEvaluations {
125      get { return ((IntValue)Results["Evaluations"].Value).Value; }
126      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
127    }
128    private int ResultsIterations {
129      get { return ((IntValue)Results["Iterations"].Value).Value; }
130      set { ((IntValue)Results["Iterations"].Value).Value = value; }
131    }
132
133    private DataTable ResultsQualities {
134      get { return ((DataTable)Results["Qualities"].Value); }
135    }
136    private DataRow ResultsQualitiesBest {
137      get { return ResultsQualities.Rows["Best Quality"]; }
138    }
139
140    private DataRow ResultsQualitiesIteration {
141      get { return ResultsQualities.Rows["Iteration Quality"]; }
142    }
143
144
145    private DataRow ResultsLevels {
146      get { return ((DataTable)Results["Pyramid Levels"].Value).Rows["Levels"]; }
147    }
148
149    private DataRow ResultsSolutions {
150      get { return ((DataTable)Results["Stored Solutions"].Value).Rows["Solutions"]; }
151    }
152    #endregion
153
154    [StorableConstructor]
155    protected ParameterlessPopulationPyramid(bool deserializing) : base(deserializing) { }
156
157    protected ParameterlessPopulationPyramid(ParameterlessPopulationPyramid original, Cloner cloner)
158      : base(original, cloner) {
159    }
160
161    public override IDeepCloneable Clone(Cloner cloner) {
162      return new ParameterlessPopulationPyramid(this, cloner);
163    }
164
165    public ParameterlessPopulationPyramid() {
166      Parameters.Add(new FixedValueParameter<IntValue>(MaximumIterationsParameterName, "", new IntValue(Int32.MaxValue)));
167      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
168      Parameters.Add(new FixedValueParameter<IntValue>(MaximumRuntimeParameterName, "The maximum runtime in seconds after which the algorithm stops. Use -1 to specify no limit for the runtime", new IntValue(3600)));
169      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
170      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
171    }
172
173    protected override void OnExecutionTimeChanged() {
174      base.OnExecutionTimeChanged();
175      if (CancellationTokenSource == null) return;
176      if (MaximumRuntime == -1) return;
177      if (ExecutionTime.TotalSeconds > MaximumRuntime) CancellationTokenSource.Cancel();
178    }
179
180    private void AddIfUnique(BinaryVector solution, int level) {
181      // Don't add things you have seen
182      if (seen.Contains(solution)) return;
183      if (level == pyramid.Count) {
184        pyramid.Add(new Population(Problem.Encoding.Length, random));
185      }
186      var copied = (BinaryVector)solution.Clone();
187      pyramid[level].Add(copied);
188      seen.Add(copied);
189    }
190
191    // In the GECCO paper, Figure 1
192    private double iterate() {
193      // Create a random solution
194      BinaryVector solution = new BinaryVector(Problem.Encoding.Length);
195      for (int i = 0; i < solution.Length; i++) {
196        solution[i] = random.Next(2) == 1;
197      }
198      double fitness = tracker.Evaluate(solution, random);
199      fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random);
200      AddIfUnique(solution, 0);
201
202      for (int level = 0; level < pyramid.Count; level++) {
203        var current = pyramid[level];
204        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random);
205        // add it to the next level if its a strict fitness improvement
206        if (tracker.IsBetter(newFitness, fitness)) {
207          fitness = newFitness;
208          AddIfUnique(solution, level + 1);
209        }
210      }
211      return fitness;
212    }
213
214    protected override void Run(CancellationToken cancellationToken) {
215      // Set up the algorithm
216      if (SetSeedRandomly) Seed = new System.Random().Next();
217      pyramid = new List<Population>();
218      seen.Clear();
219      random.Reset(Seed);
220      tracker = new EvaluationTracker(Problem, MaximumEvaluations);
221
222      // Set up the results display
223      Results.Add(new Result("Iterations", new IntValue(0)));
224      Results.Add(new Result("Evaluations", new IntValue(0)));
225      Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution)));
226      Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality)));
227      Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation)));
228      var table = new DataTable("Qualities");
229      table.Rows.Add(new DataRow("Best Quality"));
230      var iterationRows = new DataRow("Iteration Quality");
231      iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
232      table.Rows.Add(iterationRows);
233      Results.Add(new Result("Qualities", table));
234
235      table = new DataTable("Pyramid Levels");
236      table.Rows.Add(new DataRow("Levels"));
237      Results.Add(new Result("Pyramid Levels", table));
238
239      table = new DataTable("Stored Solutions");
240      table.Rows.Add(new DataRow("Solutions"));
241      Results.Add(new Result("Stored Solutions", table));
242
243      // Loop until iteration limit reached or canceled.
244      for (ResultsIterations = 0; ResultsIterations < MaximumIterations; ResultsIterations++) {
245        double fitness = double.NaN;
246
247        try {
248          fitness = iterate();
249          cancellationToken.ThrowIfCancellationRequested();
250        }
251        finally {
252          ResultsEvaluations = tracker.Evaluations;
253          ResultsBestSolution = new BinaryVector(tracker.BestSolution);
254          ResultsBestQuality = tracker.BestQuality;
255          ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation;
256          ResultsQualitiesBest.Values.Add(tracker.BestQuality);
257          ResultsQualitiesIteration.Values.Add(fitness);
258          ResultsLevels.Values.Add(pyramid.Count);
259          ResultsSolutions.Values.Add(seen.Count);
260        }
261      }
262    }
263  }
264}
Note: See TracBrowser for help on using the repository browser.