Free cookie consent management tool by TermsFeed Policy Generator

source: branches/crossvalidation-2434/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/ParameterlessPopulationPyramid.cs @ 15280

Last change on this file since 15280 was 14029, checked in by gkronber, 8 years ago

#2434: merged trunk changes r12934:14026 from trunk to branch

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