source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs @ 14544

Last change on this file since 14544 was 14544, checked in by abeham, 3 years ago

#2701:

  • LLE: Added equality comparer
  • MemPR:
    • Added GPR to learn about heuristic performance
    • Changed Breeding to do more exhaustive search on crossover
    • Added Delinking separately to Relinking
    • Rewrote d/relinking for LLE
    • Reduce usage of local search
    • Renamed TabuWalk to AdaptiveWalk
    • Rewrote adaptive walk for binary problems
    • Renamed LLE namespace to Grouping to avoid namespace clashes
File size: 10.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.Collections.Generic;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Algorithms.MemPR.Interfaces;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Encodings.BinaryVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Random;
34
35namespace HeuristicLab.Algorithms.MemPR.Binary {
36  [Item("MemPR (binary)", "MemPR implementation for binary vectors.")]
37  [StorableClass]
38  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
39  public class BinaryMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<BinaryVectorEncoding>, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
40    [StorableConstructor]
41    protected BinaryMemPR(bool deserializing) : base(deserializing) { }
42    protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
43    public BinaryMemPR() {
44      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<BinaryMemPRPopulationContext>>())
45        SolutionModelTrainerParameter.ValidValues.Add(trainer);
46     
47      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<BinaryMemPRSolutionContext>>()) {
48        LocalSearchParameter.ValidValues.Add(localSearch);
49      }
50    }
51
52    public override IDeepCloneable Clone(Cloner cloner) {
53      return new BinaryMemPR(this, cloner);
54    }
55
56    protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
57      var len = a.Solution.Length;
58      var acode = a.Solution;
59      var bcode = b.Solution;
60      for (var i = 0; i < len; i++)
61        if (acode[i] != bcode[i]) return false;
62      return true;
63    }
64
65    protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
66      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
67    }
68
69    protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) {
70      var creator = Problem.SolutionCreator as IBinaryVectorCreator;
71      if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
72      return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
73        Parent = Context.Scope
74      };
75    }
76
77    protected override ISolutionSubspace<BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
78      var pop = solutions.ToList();
79      var N = pop[0].Length;
80      var subspace = new bool[N];
81      for (var i = 0; i < N; i++) {
82        var val = pop[0][i];
83        if (inverse) subspace[i] = true;
84        for (var p = 1; p < pop.Count; p++) {
85          if (pop[p][i] != val) subspace[i] = !inverse;
86        }
87      }
88      return new BinarySolutionSubspace(subspace);
89    }
90
91    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
92      var evaluations = 0;
93      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
94      if (double.IsNaN(scope.Fitness)) {
95        Evaluate(scope, token);
96        evaluations++;
97      }
98      SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
99      var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
100      var current = currentScope.Solution;
101      var N = current.Length;
102
103      var subN = subset != null ? subset.Count(x => x) : N;
104      if (subN == 0) return;
105      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
106
107      var max = Context.Population.Max(x => x.Fitness);
108      var min = Context.Population.Min(x => x.Fitness);
109      var range = (max - min);
110      if (range.IsAlmost(0)) range = Math.Abs(max * 0.05);
111      //else range += range * 0.05;
112      if (range.IsAlmost(0)) { // because min = max = 0
113        Context.IncrementEvaluatedSolutions(evaluations);
114        return;
115      }
116
117      //var upperBound = Problem.Maximization ? min - range : max + range;
118      //var lowerBound = Problem.Maximization ? max : min;
119      var temp = 1.0;
120      for (var iter = 0; iter < int.MaxValue; iter++) {
121        var moved = false;
122
123        for (var i = 0; i < subN; i++) {
124          var idx = order[i];
125          var before = currentScope.Fitness;
126          current[idx] = !current[idx];
127          Evaluate(currentScope, token);
128          evaluations++;
129          var after = currentScope.Fitness;
130
131          if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) {
132            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
133          }
134          var diff = Problem.Maximization ? after - before : before - after;
135          if (diff > 0) moved = true;
136          else {
137            var prob = Math.Exp(temp * diff / range);
138            if (Context.Random.NextDouble() >= prob) {
139              // the move is not good enough -> undo the move
140              current[idx] = !current[idx];
141              currentScope.Fitness = before;
142            }
143          }
144          temp += 100.0 / maxEvals;
145          if (evaluations >= maxEvals) break;
146        }
147        if (!moved) break;
148        if (evaluations >= maxEvals) break;
149      }
150
151      Context.IncrementEvaluatedSolutions(evaluations);
152      scope.Adopt(bestOfTheWalk ?? currentScope);
153    }
154
155    protected override ISingleObjectiveSolutionScope<BinaryVector> Breed(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
156      var evaluations = 0;
157      var N = p1.Solution.Length;
158      if (double.IsNaN(p1.Fitness)) {
159        Evaluate(p1, token);
160        evaluations++;
161      }
162      if (double.IsNaN(p2.Fitness)) {
163        Evaluate(p2, token);
164        evaluations++;
165      }
166      var better = Problem.Maximization ? Math.Max(p1.Fitness, p2.Fitness)
167                                        : Math.Min(p1.Fitness, p2.Fitness);
168
169      var offspring = ToScope(null);
170      var probe = ToScope(new BinaryVector(N));
171      var order = Enumerable.Range(0, N - 1).Shuffle(Context.Random).ToList();
172      for (var x = 0; x < N - 1; x++) {
173        var b = order[x];
174        if (p1.Solution[b] == p2.Solution[b]) continue;
175        for (var i = 0; i <= b; i++)
176          probe.Solution[i] = p1.Solution[i];
177        for (var i = b + 1; i < probe.Solution.Length; i++)
178          probe.Solution[i] = p2.Solution[i];
179
180        Evaluate(probe, token);
181        evaluations++;
182        if (Context.IsBetter(probe, offspring)) {
183          if (Context.IsBetter(probe.Fitness, better)) {
184            Context.IncrementEvaluatedSolutions(evaluations);
185            return probe;
186          }
187          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
188        }
189      }
190
191      while (evaluations < Context.LocalSearchEvaluations) {
192        probe.Solution = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
193        Evaluate(probe, token);
194        evaluations++;
195        if (Context.IsBetter(probe, offspring)) {
196          if (Context.IsBetter(probe.Fitness, better)) {
197            Context.IncrementEvaluatedSolutions(evaluations);
198            return probe;
199          }
200          offspring = (ISingleObjectiveSolutionScope<BinaryVector>)probe.Clone();
201        }
202      }
203      Context.IncrementEvaluatedSolutions(evaluations);
204      return offspring;
205    }
206
207    protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
208      var evaluations = 0;
209      if (double.IsNaN(a.Fitness)) {
210        Evaluate(a, token);
211        evaluations++;
212      }
213      if (double.IsNaN(b.Fitness)) {
214        Evaluate(b, token);
215        evaluations++;
216      }
217
218      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
219      var child = childScope.Solution;
220      ISingleObjectiveSolutionScope<BinaryVector> best = null;
221      var cF = a.Fitness;
222      var bF = double.NaN;
223      var order = Enumerable.Range(0, child.Length)
224        .Where(x => !delink && child[x] != b.Solution[x] || delink && child[x] == b.Solution[x])
225        .Shuffle(Context.Random).ToList();
226      if (order.Count == 0) return childScope;
227
228      while (true) {
229        var bestS = double.NaN;
230        var bestI = -1;
231        for (var i = 0; i < order.Count; i++) {
232          var idx = order[i];
233          child[idx] = !child[idx]; // move
234          Evaluate(childScope, token);
235          evaluations++;
236          var s = childScope.Fitness;
237          childScope.Fitness = cF;
238          child[idx] = !child[idx]; // undo move
239          if (Context.IsBetter(s, cF)) {
240            bestS = s;
241            bestI = i;
242            break; // first-improvement
243          }
244          if (Context.IsBetter(s, bestS)) {
245            // least-degrading
246            bestS = s;
247            bestI = i;
248          }
249        }
250        child[order[bestI]] = !child[order[bestI]];
251        order.RemoveAt(bestI);
252        cF = bestS;
253        childScope.Fitness = cF;
254        if (Context.IsBetter(cF, bF)) {
255          bF = cF;
256          best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
257        }
258        if (order.Count == 0) break;
259      }
260      Context.IncrementEvaluatedSolutions(evaluations);
261      return best ?? childScope;
262    }
263  }
264}
Note: See TracBrowser for help on using the repository browser.