source: trunk/sources/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HillClimber.cs @ 14517

Last change on this file since 14517 was 14517, checked in by jkarder, 6 years ago

#2524: made BasicAlgorithm pausable

File size: 5.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.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.Problems.Binary;
35using HeuristicLab.Random;
36
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("Hill Climber (HC)", "Binary Hill Climber.")]
43  [StorableClass]
44  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 150)]
45  public class HillClimber : BasicAlgorithm {
46    [Storable]
47    private IRandom random;
48
49    private const string IterationsParameterName = "Iterations";
50    private const string BestQualityResultName = "Best quality";
51    private const string IterationsResultName = "Iterations";
52
53    public override Type ProblemType {
54      get { return typeof(BinaryProblem); }
55    }
56    public new BinaryProblem Problem {
57      get { return (BinaryProblem)base.Problem; }
58      set { base.Problem = value; }
59    }
60
61    public IFixedValueParameter<IntValue> IterationsParameter {
62      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
63    }
64
65    public int Iterations {
66      get { return IterationsParameter.Value.Value; }
67      set { IterationsParameter.Value.Value = value; }
68    }
69
70    #region ResultsProperties
71    private double ResultsBestQuality {
72      get { return ((DoubleValue)Results[BestQualityResultName].Value).Value; }
73      set { ((DoubleValue)Results[BestQualityResultName].Value).Value = value; }
74    }
75    private int ResultsIterations {
76      get { return ((IntValue)Results[IterationsResultName].Value).Value; }
77      set { ((IntValue)Results[IterationsResultName].Value).Value = value; }
78    }
79    #endregion
80
81    [StorableConstructor]
82    protected HillClimber(bool deserializing) : base(deserializing) { }
83    protected HillClimber(HillClimber original, Cloner cloner)
84      : base(original, cloner) {
85    }
86    public override IDeepCloneable Clone(Cloner cloner) {
87      return new HillClimber(this, cloner);
88    }
89
90    public HillClimber()
91      : base() {
92      pausable = true;
93      random = new MersenneTwister();
94      Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "", new IntValue(100)));
95    }
96
97    [StorableHook(HookType.AfterDeserialization)]
98    private void AfterDeserialization() {
99      // BackwardsCompatibility3.3
100      #region Backwards compatible code, remove with 3.4
101      pausable = true;
102      #endregion
103    }
104
105    protected override void Initialize(CancellationToken cancellationToken) {
106      Results.Add(new Result(BestQualityResultName, new DoubleValue(double.NaN)));
107      Results.Add(new Result(IterationsResultName, new IntValue(0)));
108      base.Initialize(cancellationToken);
109    }
110    protected override void Run(CancellationToken cancellationToken) {
111      while (ResultsIterations < Iterations) {
112        cancellationToken.ThrowIfCancellationRequested();
113
114        var solution = new BinaryVector(Problem.Length);
115        for (int i = 0; i < solution.Length; i++) {
116          solution[i] = random.Next(2) == 1;
117        }
118
119        var fitness = Problem.Evaluate(solution, random);
120
121        fitness = ImproveToLocalOptimum(Problem, solution, fitness, random);
122        if (double.IsNaN(ResultsBestQuality) || Problem.IsBetter(fitness, ResultsBestQuality)) {
123          ResultsBestQuality = fitness;
124        }
125
126        ResultsIterations++;
127      }
128    }
129    // In the GECCO paper, Section 2.1
130    public static double ImproveToLocalOptimum(BinaryProblem problem, BinaryVector solution, double fitness, IRandom rand) {
131      var tried = new HashSet<int>();
132      do {
133        var options = Enumerable.Range(0, solution.Length).Shuffle(rand);
134        foreach (var option in options) {
135          if (tried.Contains(option)) continue;
136          solution[option] = !solution[option];
137          double newFitness = problem.Evaluate(solution, rand);
138          if (problem.IsBetter(newFitness, fitness)) {
139            fitness = newFitness;
140            tried.Clear();
141          } else {
142            solution[option] = !solution[option];
143          }
144          tried.Add(option);
145        }
146      } while (tried.Count != solution.Length);
147      return fitness;
148    }
149  }
150}
Note: See TracBrowser for help on using the repository browser.