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

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

#2701:

  • Reusing similiarty calculator in BinaryMemPR
  • Fixing distance calculation for linear linkage and LinearLinkageMemPR
  • Small changes to base algorithm
  • Added biased model trainer for permutation (rank and fitness)
  • Fixing best known quality calculation for GCP
File size: 11.2 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    private const double UncommonBitSubsetMutationProbabilityMagicConst = 0.05;
41   
42    [StorableConstructor]
43    protected BinaryMemPR(bool deserializing) : base(deserializing) { }
44    protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
45    public BinaryMemPR() {
46      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<BinaryMemPRPopulationContext>>())
47        SolutionModelTrainerParameter.ValidValues.Add(trainer);
48     
49      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<BinaryMemPRSolutionContext>>()) {
50        LocalSearchParameter.ValidValues.Add(localSearch);
51      }
52    }
53
54    public override IDeepCloneable Clone(Cloner cloner) {
55      return new BinaryMemPR(this, cloner);
56    }
57
58    protected override bool Eq(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
59      var len = a.Solution.Length;
60      var acode = a.Solution;
61      var bcode = b.Solution;
62      for (var i = 0; i < len; i++)
63        if (acode[i] != bcode[i]) return false;
64      return true;
65    }
66
67    protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
68      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
69    }
70
71    protected override ISingleObjectiveSolutionScope<BinaryVector> ToScope(BinaryVector code, double fitness = double.NaN) {
72      var creator = Problem.SolutionCreator as IBinaryVectorCreator;
73      if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
74      return new SingleObjectiveSolutionScope<BinaryVector>(code, creator.BinaryVectorParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
75        Parent = Context.Scope
76      };
77    }
78
79    protected override ISolutionSubspace<BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
80      var pop = solutions.ToList();
81      var N = pop[0].Length;
82      var subspace = new bool[N];
83      for (var i = 0; i < N; i++) {
84        var val = pop[0][i];
85        if (inverse) subspace[i] = true;
86        for (var p = 1; p < pop.Count; p++) {
87          if (pop[p][i] != val) subspace[i] = !inverse;
88        }
89      }
90      return new BinarySolutionSubspace(subspace);
91    }
92
93    protected override int TabuWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
94      var evaluations = 0;
95      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
96      if (double.IsNaN(scope.Fitness)) {
97        Evaluate(scope, token);
98        evaluations++;
99      }
100      SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
101      var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
102      var current = currentScope.Solution;
103      var N = current.Length;
104      var tabu = new Tuple<double, double>[N];
105      for (var i = 0; i < N; i++) tabu[i] = Tuple.Create(current[i] ? double.NaN : currentScope.Fitness, !current[i] ? double.NaN : currentScope.Fitness);
106      var subN = subset != null ? subset.Count(x => x) : N;
107      if (subN == 0) return 0;
108      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
109
110      var steps = 0;
111      var stepsUntilBestOfWalk = 0;
112      for (var iter = 0; iter < int.MaxValue; iter++) {
113        var allTabu = true;
114        var bestOfTheRestF = double.NaN;
115        int bestOfTheRest = -1;
116        var improved = false;
117
118        for (var i = 0; i < subN; i++) {
119          var idx = order[i];
120          var before = currentScope.Fitness;
121          current[idx] = !current[idx];
122          Evaluate(currentScope, token);
123          evaluations++;
124          var after = currentScope.Fitness;
125
126          if (IsBetter(after, before) && (bestOfTheWalk == null || IsBetter(after, bestOfTheWalk.Fitness))) {
127            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
128            stepsUntilBestOfWalk = steps;
129          }
130
131          var qualityToBeat = current[idx] ? tabu[idx].Item2 : tabu[idx].Item1;
132          var isTabu = !IsBetter(after, qualityToBeat);
133          if (!isTabu) allTabu = false;
134
135          if (IsBetter(after, before) && !isTabu) {
136            improved = true;
137            steps++;
138            tabu[idx] = current[idx] ? Tuple.Create(after, tabu[idx].Item2) : Tuple.Create(tabu[idx].Item1, after);
139          } else { // undo the move
140            if (!isTabu && IsBetter(after, bestOfTheRestF)) {
141              bestOfTheRest = idx;
142              bestOfTheRestF = after;
143            }
144            current[idx] = !current[idx];
145            currentScope.Fitness = before;
146          }
147          if (evaluations >= maxEvals) break;
148        }
149        if (!allTabu && !improved) {
150          var better = currentScope.Fitness;
151          current[bestOfTheRest] = !current[bestOfTheRest];
152          tabu[bestOfTheRest] = current[bestOfTheRest] ? Tuple.Create(better, tabu[bestOfTheRest].Item2) : Tuple.Create(tabu[bestOfTheRest].Item1, better);
153          currentScope.Fitness = bestOfTheRestF;
154          steps++;
155        } else if (allTabu) break;
156        if (evaluations >= maxEvals) break;
157      }
158
159      Context.IncrementEvaluatedSolutions(evaluations);
160      scope.Adopt(bestOfTheWalk ?? currentScope);
161      return stepsUntilBestOfWalk;
162    }
163
164    protected override ISingleObjectiveSolutionScope<BinaryVector> Cross(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
165      var offspring = (ISingleObjectiveSolutionScope<BinaryVector>)p1.Clone();
166      offspring.Fitness = double.NaN;
167      var code = offspring.Solution;
168      var p2Code = p2.Solution;
169      var bp = 0;
170      var lastbp = 0;
171      for (var i = 0; i < code.Length; i++) {
172        if (bp % 2 == 1) {
173          code[i] = p2Code[i];
174        }
175        if (Context.Random.Next(code.Length) < i - lastbp + 1) {
176          bp = (bp + 1) % 2;
177          lastbp = i;
178        }
179      }
180      return offspring;
181    }
182
183    protected override void Mutate(ISingleObjectiveSolutionScope<BinaryVector> offspring, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
184      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
185      offspring.Fitness = double.NaN;
186      var code = offspring.Solution;
187      for (var i = 0; i < code.Length; i++) {
188        if (subset != null && subset[i]) continue;
189        if (Context.Random.NextDouble() < UncommonBitSubsetMutationProbabilityMagicConst) {
190          code[i] = !code[i];
191          if (subset != null) subset[i] = true;
192        }
193      }
194    }
195
196    protected override ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token) {
197      if (double.IsNaN(a.Fitness)) {
198        Evaluate(a, token);
199        Context.IncrementEvaluatedSolutions(1);
200      }
201      if (double.IsNaN(b.Fitness)) {
202        Evaluate(b, token);
203        Context.IncrementEvaluatedSolutions(1);
204      }
205      if (Context.Random.NextDouble() < 0.5)
206        return IsBetter(a, b) ? Relink(a, b, token, false) : Relink(b, a, token, true);
207      else return IsBetter(a, b) ? Relink(b, a, token, true) : Relink(a, b, token, false);
208    }
209
210    protected virtual ISingleObjectiveSolutionScope<BinaryVector> Relink(ISingleObjectiveSolutionScope<BinaryVector> betterScope, ISingleObjectiveSolutionScope<BinaryVector> worseScope, CancellationToken token, bool fromWorseToBetter) {
211      var evaluations = 0;
212      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)(fromWorseToBetter ? worseScope : betterScope).Clone();
213      var child = childScope.Solution;
214      var better = betterScope.Solution;
215      var worse = worseScope.Solution;
216      ISingleObjectiveSolutionScope<BinaryVector> best = null;
217      var cF = fromWorseToBetter ? worseScope.Fitness : betterScope.Fitness;
218      var bF = double.NaN;
219      var order = Enumerable.Range(0, better.Length).Shuffle(Context.Random).ToArray();
220      while (true) {
221        var bestS = double.NaN;
222        var bestIdx = -1;
223        for (var i = 0; i < child.Length; i++) {
224          var idx = order[i];
225          // either move from worse to better or move from better away from worse
226          if (fromWorseToBetter && child[idx] == better[idx] ||
227            !fromWorseToBetter && child[idx] != worse[idx]) continue;
228          child[idx] = !child[idx]; // move
229          Evaluate(childScope, token);
230          evaluations++;
231          var s = childScope.Fitness;
232          childScope.Fitness = cF;
233          child[idx] = !child[idx]; // undo move
234          if (IsBetter(s, cF)) {
235            bestS = s;
236            bestIdx = idx;
237            break; // first-improvement
238          }
239          if (double.IsNaN(bestS) || IsBetter(s, bestS)) {
240            // least-degrading
241            bestS = s;
242            bestIdx = idx;
243          }
244        }
245        if (bestIdx < 0) break;
246        child[bestIdx] = !child[bestIdx];
247        cF = bestS;
248        childScope.Fitness = cF;
249        if (IsBetter(cF, bF)) {
250          bF = cF;
251          best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
252        }
253      }
254      Context.IncrementEvaluatedSolutions(evaluations);
255      return best ?? childScope;
256    }
257  }
258}
Note: See TracBrowser for help on using the repository browser.