source: branches/2931_OR-Tools_LP_MIP/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs @ 16139

Last change on this file since 16139 was 16139, checked in by ddorfmei, 14 months ago

#2931: Merged [16046-16138/trunk] into branch

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