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