source: branches/ProblemRefactoring/HeuristicLab.Algorithms.ParameterlessPopulationPyramid/3.3/HillClimber.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: 4.7 KB
RevLine 
[11636]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.
[11636]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
[11791]23using System;
[11636]24using System.Collections.Generic;
25using System.Linq;
[11791]26using System.Threading;
[11636]27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
[11987]30using HeuristicLab.Encodings.BinaryVectorEncoding;
[11636]31using HeuristicLab.Optimization;
[11640]32using HeuristicLab.Parameters;
[11636]33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Random;
35
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
[13173]41  [Item("Hill Climber (HC)", "Binary Hill Climber.")]
[11636]42  [StorableClass]
[12504]43  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 150)]
[11791]44  public class HillClimber : BasicAlgorithm {
[11636]45    [Storable]
46    private IRandom random;
[11664]47
[11640]48    private const string IterationsParameterName = "Iterations";
[11636]49
[11791]50    public override Type ProblemType {
[13361]51      get { return typeof(ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector>); }
[11791]52    }
[13361]53    public new ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector> Problem {
54      get { return (ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector>)base.Problem; }
55      set { base.Problem = (IProblem)value; }
[11791]56    }
57
[11640]58    public IFixedValueParameter<IntValue> IterationsParameter {
59      get { return (IFixedValueParameter<IntValue>)Parameters[IterationsParameterName]; }
60    }
61
62    public int Iterations {
63      get { return IterationsParameter.Value.Value; }
64      set { IterationsParameter.Value.Value = value; }
65    }
66
[11636]67    [StorableConstructor]
68    protected HillClimber(bool deserializing) : base(deserializing) { }
69    protected HillClimber(HillClimber original, Cloner cloner)
70      : base(original, cloner) {
71    }
72    public override IDeepCloneable Clone(Cloner cloner) {
73      return new HillClimber(this, cloner);
74    }
75
76    public HillClimber()
77      : base() {
78      random = new MersenneTwister();
[11640]79      Parameters.Add(new FixedValueParameter<IntValue>(IterationsParameterName, "", new IntValue(100)));
[11636]80    }
[11791]81    protected override void Run(CancellationToken cancellationToken) {
[11640]82      var BestQuality = new DoubleValue(double.NaN);
83      Results.Add(new Result("Best quality", BestQuality));
84      for (int iteration = 0; iteration < Iterations; iteration++) {
[13339]85        var solution = new BinaryVector(Problem.Encoding.Length);
[11640]86        for (int i = 0; i < solution.Length; i++) {
87          solution[i] = random.Next(2) == 1;
88        }
89
[11987]90        var fitness = Problem.Evaluate(solution, random);
[11640]91
92        fitness = ImproveToLocalOptimum(Problem, solution, fitness, random);
93        if (double.IsNaN(BestQuality.Value) || Problem.IsBetter(fitness, BestQuality.Value)) {
94          BestQuality.Value = fitness;
95        }
[11636]96      }
97    }
[11838]98    // In the GECCO paper, Section 2.1
[13361]99    public static double ImproveToLocalOptimum(ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector> problem, BinaryVector solution, double fitness, IRandom rand) {
[11636]100      var tried = new HashSet<int>();
101      do {
102        var options = Enumerable.Range(0, solution.Length).Shuffle(rand);
103        foreach (var option in options) {
[11668]104          if (tried.Contains(option)) continue;
[11636]105          solution[option] = !solution[option];
[11987]106          double newFitness = problem.Evaluate(solution, rand);
[11640]107          if (problem.IsBetter(newFitness, fitness)) {
[11636]108            fitness = newFitness;
109            tried.Clear();
110          } else {
111            solution[option] = !solution[option];
112          }
113          tried.Add(option);
114        }
115      } while (tried.Count != solution.Length);
116      return fitness;
[11637]117    }
[11636]118  }
119}
Note: See TracBrowser for help on using the repository browser.