source: branches/ProblemRefactoring/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/LocalSearch/ExhaustiveBitflip.cs @ 14429

Last change on this file since 14429 was 14429, checked in by abeham, 4 years ago

#2701, #2708: Made a new branch from ProblemRefactoring and removed ScopedBasicAlgorithm branch (which becomes MemPR branch)

File size: 4.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using System.Threading;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Optimization;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Random;
30
31namespace HeuristicLab.Encodings.BinaryVectorEncoding.LocalSearch {
32  [Item("Exhaustive Bitflip Local Search (binary)", "", ExcludeGenericTypeInfo = true)]
33  [StorableClass]
34  public class ExhaustiveBitflip<TProblem, TContext> : NamedItem, IBinaryLocalSearch<TContext>
35      where TProblem : class, ISingleObjectiveProblemDefinition<BinaryVectorEncoding, BinaryVector>, ISingleObjectiveProblem<BinaryVectorEncoding, BinaryVector> // need both, because one has Maximization, the other only the IParameter
36      where TContext : IProblemContext<TProblem, BinaryVectorEncoding, BinaryVector>,
37                       ISingleObjectiveSolutionContext<BinaryVector>, IStochasticContext,
38                       IEvaluatedSolutionsContext, ILongRunningOperationContext {
39
40    public override bool CanChangeName {
41      get { return false; }
42    }
43    public override bool CanChangeDescription {
44      get { return false; }
45    }
46
47    [StorableConstructor]
48    protected ExhaustiveBitflip(bool deserializing) : base(deserializing) { }
49    protected ExhaustiveBitflip(ExhaustiveBitflip<TProblem, TContext> original, Cloner cloner) : base(original, cloner) { }
50    public ExhaustiveBitflip() : base() {
51      name = ItemName;
52      description = ItemDescription;
53    }
54
55    public override IDeepCloneable Clone(Cloner cloner) {
56      return new ExhaustiveBitflip<TProblem, TContext>(this, cloner);
57    }
58
59    public void Optimize(TContext context) {
60      var quality = context.Solution.Fitness;
61      try {
62        var result = Search(context.Random, context.Solution.Solution, ref quality,
63          context.Problem.Maximization, context.Problem.Evaluate, context.CancellationToken);
64        context.IncEvaluatedSolutions(result.Item1);
65        var stepsContext = context as IImprovementStepsContext;
66        if (stepsContext != null)
67          stepsContext.ImprovementSteps = result.Item2;
68      } finally {
69        context.Solution.Fitness = quality;
70      }
71    }
72
73    private static bool IsBetter(bool maximization, double a, double b) {
74      return maximization && a > b
75        || !maximization && a < b;
76    }
77
78    public static Tuple<int, int> Search(IRandom random, BinaryVector solution, ref double quality, bool maximization, Func<BinaryVector, IRandom, double> evalFunc, CancellationToken token, bool[] subspace = null) {
79      if (double.IsNaN(quality)) quality = evalFunc(solution, null);
80      var improved = false;
81      var order = Enumerable.Range(0, solution.Length).Shuffle(random).ToArray();
82      var lastImp = -1;
83      var steps = 0;
84      var evaluations = 0;
85      do {
86        improved = false;
87        for (var i = 0; i < solution.Length; i++) {
88          // in case we didn't make an improvement this round and arrived at the index of the last improvement
89          // break means we don't need to try the remaining moves again as they have brought no improvement
90          if (!improved && lastImp == i) break;
91          var idx = order[i];
92          if (subspace != null && !subspace[idx]) continue;
93          // bitflip the solution
94          solution[idx] = !solution[idx];
95          var after = evalFunc(solution, null);
96          evaluations++;
97          if (IsBetter(maximization, after, quality)) {
98            steps++;
99            quality = after;
100            lastImp = i;
101            improved = true;
102          } else {
103            // undo the bitflip in case no improvement was made
104            solution[idx] = !solution[idx];
105          }
106          token.ThrowIfCancellationRequested();
107        }
108      } while (improved);
109
110      return Tuple.Create(evaluations, steps);
111    }
112  }
113}
Note: See TracBrowser for help on using the repository browser.