Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs @ 16723

Last change on this file since 16723 was 16723, checked in by abeham, 5 years ago

#2521: merged changes from r15684 to trunk HEAD (r16716) and resolved all merge conflicts

  • it doesn't build
File size: 12.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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.Linq;
26using System.Threading;
27using HeuristicLab.Analysis;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Data;
31using HeuristicLab.Encodings.BinaryVectorEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HEAL.Attic;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.ParameterlessPopulationPyramid {
38  // This code is based off the publication
39  // B. W. Goldman and W. F. Punch, "Parameter-less Population Pyramid," GECCO, pp. 785–792, 2014
40  // and the original source code in C++11 available from: https://github.com/brianwgoldman/Parameter-less_Population_Pyramid
41  [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")]
42  [StorableType("CAD84CAB-1ECC-4D76-BDC5-701AAF690E17")]
43  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 400)]
44  public class ParameterlessPopulationPyramid : BasicAlgorithm {
45    public override Type ProblemType {
46      get { return typeof(SingleObjectiveProblem<BinaryVectorEncoding, BinaryVector>); }
47    }
48    public new SingleObjectiveProblem<BinaryVectorEncoding, BinaryVector> Problem {
49      get { return (SingleObjectiveProblem<BinaryVectorEncoding, BinaryVector>)base.Problem; }
50      set { base.Problem = value; }
51    }
52
53    [Storable]
54    private readonly IRandom random = new MersenneTwister();
55    [Storable]
56    private List<Population> pyramid = new List<Population>();
57    [Storable]
58    private EvaluationTracker tracker;
59
60    // Tracks all solutions in Pyramid for quick membership checks
61
62    private HashSet<BinaryVector> seen = new HashSet<BinaryVector>(new EnumerableBoolEqualityComparer());
63    [Storable]
64    private IEnumerable<BinaryVector> StorableSeen {
65      get { return seen; }
66      set { seen = new HashSet<BinaryVector>(value, new EnumerableBoolEqualityComparer()); }
67    }
68
69    #region ParameterNames
70    private const string MaximumIterationsParameterName = "Maximum Iterations";
71    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
72    private const string MaximumRuntimeParameterName = "Maximum Runtime";
73    private const string SeedParameterName = "Seed";
74    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
75    #endregion
76
77    #region ParameterProperties
78    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
79      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumIterationsParameterName]; }
80    }
81    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
82      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
83    }
84    public IFixedValueParameter<IntValue> MaximumRuntimeParameter {
85      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumRuntimeParameterName]; }
86    }
87    public IFixedValueParameter<IntValue> SeedParameter {
88      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
89    }
90    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
91      get { return (FixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
92    }
93    #endregion
94
95    #region Properties
96    public int MaximumIterations {
97      get { return MaximumIterationsParameter.Value.Value; }
98      set { MaximumIterationsParameter.Value.Value = value; }
99    }
100    public int MaximumEvaluations {
101      get { return MaximumEvaluationsParameter.Value.Value; }
102      set { MaximumEvaluationsParameter.Value.Value = value; }
103    }
104    public int MaximumRuntime {
105      get { return MaximumRuntimeParameter.Value.Value; }
106      set { MaximumRuntimeParameter.Value.Value = value; }
107    }
108    public int Seed {
109      get { return SeedParameter.Value.Value; }
110      set { SeedParameter.Value.Value = value; }
111    }
112    public bool SetSeedRandomly {
113      get { return SetSeedRandomlyParameter.Value.Value; }
114      set { SetSeedRandomlyParameter.Value.Value = value; }
115    }
116    #endregion
117
118    #region ResultsProperties
119    private double ResultsBestQuality {
120      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
121      set { ((DoubleValue)Results["Best Quality"].Value).Value = value; }
122    }
123
124    private BinaryVector ResultsBestSolution {
125      get { return (BinaryVector)Results["Best Solution"].Value; }
126      set { Results["Best Solution"].Value = value; }
127    }
128
129    private int ResultsBestFoundOnEvaluation {
130      get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; }
131      set { ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value = value; }
132    }
133
134    private int ResultsEvaluations {
135      get { return ((IntValue)Results["Evaluations"].Value).Value; }
136      set { ((IntValue)Results["Evaluations"].Value).Value = value; }
137    }
138    private int ResultsIterations {
139      get { return ((IntValue)Results["Iterations"].Value).Value; }
140      set { ((IntValue)Results["Iterations"].Value).Value = value; }
141    }
142
143    private DataTable ResultsQualities {
144      get { return ((DataTable)Results["Qualities"].Value); }
145    }
146    private DataRow ResultsQualitiesBest {
147      get { return ResultsQualities.Rows["Best Quality"]; }
148    }
149
150    private DataRow ResultsQualitiesIteration {
151      get { return ResultsQualities.Rows["Iteration Quality"]; }
152    }
153
154
155    private DataRow ResultsLevels {
156      get { return ((DataTable)Results["Pyramid Levels"].Value).Rows["Levels"]; }
157    }
158
159    private DataRow ResultsSolutions {
160      get { return ((DataTable)Results["Stored Solutions"].Value).Rows["Solutions"]; }
161    }
162    #endregion
163
164    public override bool SupportsPause { get { return true; } }
165
166    [StorableConstructor]
167    protected ParameterlessPopulationPyramid(StorableConstructorFlag _) : base(_) { }
168
169    protected ParameterlessPopulationPyramid(ParameterlessPopulationPyramid original, Cloner cloner)
170      : base(original, cloner) {
171      random = cloner.Clone(original.random);
172      pyramid = original.pyramid.Select(cloner.Clone).ToList();
173      tracker = cloner.Clone(original.tracker);
174      seen = new HashSet<BinaryVector>(original.seen.Select(cloner.Clone), new EnumerableBoolEqualityComparer());
175    }
176
177    public override IDeepCloneable Clone(Cloner cloner) {
178      return new ParameterlessPopulationPyramid(this, cloner);
179    }
180
181    public ParameterlessPopulationPyramid() : base() {
182      Parameters.Add(new FixedValueParameter<IntValue>(MaximumIterationsParameterName, "", new IntValue(Int32.MaxValue)));
183      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(Int32.MaxValue)));
184      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)));
185      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
186      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
187    }
188
189    protected override void OnExecutionTimeChanged() {
190      base.OnExecutionTimeChanged();
191      if (CancellationTokenSource == null) return;
192      if (MaximumRuntime == -1) return;
193      if (ExecutionTime.TotalSeconds > MaximumRuntime) CancellationTokenSource.Cancel();
194    }
195
196    private void AddIfUnique(BinaryVector solution, int level) {
197      // Don't add things you have seen
198      if (seen.Contains(solution)) return;
199      if (level == pyramid.Count) {
200        pyramid.Add(new Population(Problem.Encoding.Length, random));
201      }
202      var copied = (BinaryVector)solution.Clone();
203      pyramid[level].Add(copied);
204      seen.Add(copied);
205    }
206
207    // In the GECCO paper, Figure 1
208    private double iterate() {
209      // Create a random solution
210      BinaryVector solution = new BinaryVector(Problem.Encoding.Length);
211      for (int i = 0; i < solution.Length; i++) {
212        solution[i] = random.Next(2) == 1;
213      }
214      double fitness = tracker.Evaluate(solution, random);
215      fitness = HillClimber.ImproveToLocalOptimum(tracker, solution, fitness, random);
216      AddIfUnique(solution, 0);
217
218      for (int level = 0; level < pyramid.Count; level++) {
219        var current = pyramid[level];
220        double newFitness = LinkageCrossover.ImproveUsingTree(current.Tree, current.Solutions, solution, fitness, tracker, random);
221        // add it to the next level if its a strict fitness improvement
222        if (tracker.IsBetter(newFitness, fitness)) {
223          fitness = newFitness;
224          AddIfUnique(solution, level + 1);
225        }
226      }
227      return fitness;
228    }
229
230    protected override void Initialize(CancellationToken cancellationToken) {
231      // Set up the algorithm
232      if (SetSeedRandomly) Seed = RandomSeedGenerator.GetSeed();
233      pyramid = new List<Population>();
234      seen.Clear();
235      random.Reset(Seed);
236      tracker = new EvaluationTracker(Problem, MaximumEvaluations);
237
238      // Set up the results display
239      Results.Add(new Result("Iterations", new IntValue(0)));
240      Results.Add(new Result("Evaluations", new IntValue(0)));
241      Results.Add(new Result("Best Solution", new BinaryVector(tracker.BestSolution)));
242      Results.Add(new Result("Best Quality", new DoubleValue(tracker.BestQuality)));
243      Results.Add(new Result("Evaluation Best Solution Was Found", new IntValue(tracker.BestFoundOnEvaluation)));
244      var table = new DataTable("Qualities");
245      table.Rows.Add(new DataRow("Best Quality"));
246      var iterationRows = new DataRow("Iteration Quality");
247      iterationRows.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
248      table.Rows.Add(iterationRows);
249      Results.Add(new Result("Qualities", table));
250
251      table = new DataTable("Pyramid Levels");
252      table.Rows.Add(new DataRow("Levels"));
253      Results.Add(new Result("Pyramid Levels", table));
254
255      table = new DataTable("Stored Solutions");
256      table.Rows.Add(new DataRow("Solutions"));
257      Results.Add(new Result("Stored Solutions", table));
258
259      base.Initialize(cancellationToken);
260    }
261
262    protected override void Run(CancellationToken cancellationToken) {
263      // Loop until iteration limit reached or canceled.
264      while (ResultsIterations < MaximumIterations) {
265        double fitness = double.NaN;
266
267        try {
268          fitness = iterate();
269          ResultsIterations++;
270          cancellationToken.ThrowIfCancellationRequested();
271        }
272        finally {
273          ResultsEvaluations = tracker.Evaluations;
274          ResultsBestSolution = new BinaryVector(tracker.BestSolution);
275          ResultsBestQuality = tracker.BestQuality;
276          ResultsBestFoundOnEvaluation = tracker.BestFoundOnEvaluation;
277          ResultsQualitiesBest.Values.Add(tracker.BestQuality);
278          ResultsQualitiesIteration.Values.Add(fitness);
279          ResultsLevels.Values.Add(pyramid.Count);
280          ResultsSolutions.Values.Add(seen.Count);
281        }
282      }
283    }
284  }
285}
Note: See TracBrowser for help on using the repository browser.