Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14552 was 14552, checked in by abeham, 7 years ago

#2701:

  • Added alternating bits binary test Problem
  • Refactored MemPR to work with programmable problem in current trunk
  • fixed a bug in permutation MemPR when crossover doesn't assign an offspring
File size: 9.5 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.Data;
30using HeuristicLab.Encodings.BinaryVectorEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.MemPR.Binary {
37  [Item("MemPR (binary)", "MemPR implementation for binary vectors.")]
38  [StorableClass]
39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
40  public class BinaryMemPR : MemPRAlgorithm<ISingleObjectiveHeuristicOptimizationProblem, BinaryVector, BinaryMemPRPopulationContext, BinaryMemPRSolutionContext> {
41    [StorableConstructor]
42    protected BinaryMemPR(bool deserializing) : base(deserializing) { }
43    protected BinaryMemPR(BinaryMemPR original, Cloner cloner) : base(original, cloner) { }
44    public BinaryMemPR() {
45      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<BinaryMemPRPopulationContext>>())
46        SolutionModelTrainerParameter.ValidValues.Add(trainer);
47     
48      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<BinaryMemPRSolutionContext>>()) {
49        LocalSearchParameter.ValidValues.Add(localSearch);
50      }
51    }
52
53    public override IDeepCloneable Clone(Cloner cloner) {
54      return new BinaryMemPR(this, cloner);
55    }
56
57    protected override bool Eq(BinaryVector a, BinaryVector b) {
58      var len = a.Length;
59      for (var i = 0; i < len; i++)
60        if (a[i] != b[i]) return false;
61      return true;
62    }
63
64    protected override double Dist(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b) {
65      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a.Solution, b.Solution);
66    }
67
68    protected override ISolutionSubspace<BinaryVector> CalculateSubspace(IEnumerable<BinaryVector> solutions, bool inverse = false) {
69      var pop = solutions.ToList();
70      var N = pop[0].Length;
71      var subspace = new bool[N];
72      for (var i = 0; i < N; i++) {
73        var val = pop[0][i];
74        if (inverse) subspace[i] = true;
75        for (var p = 1; p < pop.Count; p++) {
76          if (pop[p][i] != val) subspace[i] = !inverse;
77        }
78      }
79      return new BinarySolutionSubspace(subspace);
80    }
81
82    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<BinaryVector> scope, int maxEvals, CancellationToken token, ISolutionSubspace<BinaryVector> subspace = null) {
83      var evaluations = 0;
84      var subset = subspace != null ? ((BinarySolutionSubspace)subspace).Subspace : null;
85      if (double.IsNaN(scope.Fitness)) {
86        Context.Evaluate(scope, token);
87        evaluations++;
88      }
89      SingleObjectiveSolutionScope<BinaryVector> bestOfTheWalk = null;
90      var currentScope = (SingleObjectiveSolutionScope<BinaryVector>)scope.Clone();
91      var current = currentScope.Solution;
92      var N = current.Length;
93
94      var subN = subset != null ? subset.Count(x => x) : N;
95      if (subN == 0) return;
96      var order = Enumerable.Range(0, N).Where(x => subset == null || subset[x]).Shuffle(Context.Random).ToArray();
97
98      var bound = Context.Maximization ? Context.Population.Max(x => x.Fitness) : Context.Population.Min(x => x.Fitness);
99      var range = Math.Abs(bound - Context.LocalOptimaLevel);
100      if (range.IsAlmost(0)) range = Math.Abs(bound * 0.05);
101      if (range.IsAlmost(0)) { // because bound = localoptimalevel = 0
102        Context.IncrementEvaluatedSolutions(evaluations);
103        return;
104      }
105     
106      var temp = -range / Math.Log(1.0 / maxEvals);
107      var endtemp = -range / Math.Log(0.1 / maxEvals);
108      var annealFactor = Math.Pow(endtemp / temp, 1.0 / maxEvals);
109      for (var iter = 0; iter < int.MaxValue; iter++) {
110        var moved = false;
111
112        for (var i = 0; i < subN; i++) {
113          var idx = order[i];
114          var before = currentScope.Fitness;
115          current[idx] = !current[idx];
116          Context.Evaluate(currentScope, token);
117          evaluations++;
118          var after = currentScope.Fitness;
119
120          if (Context.IsBetter(after, before) && (bestOfTheWalk == null || Context.IsBetter(after, bestOfTheWalk.Fitness))) {
121            bestOfTheWalk = (SingleObjectiveSolutionScope<BinaryVector>)currentScope.Clone();
122            if (Context.IsBetter(bestOfTheWalk, scope)) {
123              moved = false;
124              break;
125            }
126          }
127          var diff = Context.Maximization ? after - before : before - after;
128          if (diff > 0) moved = true;
129          else {
130            var prob = Math.Exp(diff / temp);
131            if (Context.Random.NextDouble() >= prob) {
132              // the move is not good enough -> undo the move
133              current[idx] = !current[idx];
134              currentScope.Fitness = before;
135            }
136          }
137          temp *= annealFactor;
138          if (evaluations >= maxEvals) break;
139        }
140        if (!moved) break;
141        if (evaluations >= maxEvals) break;
142      }
143
144      Context.IncrementEvaluatedSolutions(evaluations);
145      scope.Adopt(bestOfTheWalk ?? currentScope);
146    }
147
148    protected override ISingleObjectiveSolutionScope<BinaryVector> Breed(ISingleObjectiveSolutionScope<BinaryVector> p1, ISingleObjectiveSolutionScope<BinaryVector> p2, CancellationToken token) {
149      var evaluations = 0;
150      var N = p1.Solution.Length;
151
152      var probe = Context.ToScope((BinaryVector)p1.Solution.Clone());
153
154      var cache = new HashSet<BinaryVector>(new BinaryVectorEqualityComparer());
155      cache.Add(p1.Solution);
156      cache.Add(p2.Solution);
157
158      var cacheHits = 0;
159      ISingleObjectiveSolutionScope<BinaryVector> offspring = null;
160      while (evaluations < N) {
161        BinaryVector c = null;
162        var xochoice = Context.Random.Next(3);
163        switch (xochoice) {
164          case 0: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(1)); break;
165          case 1: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(2)); break;
166          case 2: c = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
167        }
168        if (cache.Contains(c)) {
169          cacheHits++;
170          if (cacheHits > 10) break;
171          continue;
172        }
173        Context.Evaluate(probe, token);
174        evaluations++;
175        cache.Add(c);
176        if (offspring == null || Context.IsBetter(probe, offspring)) {
177          offspring = probe;
178          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
179            break;
180        }
181      }
182      Context.IncrementEvaluatedSolutions(evaluations);
183      return offspring ?? probe;
184    }
185
186    protected override ISingleObjectiveSolutionScope<BinaryVector> Link(ISingleObjectiveSolutionScope<BinaryVector> a, ISingleObjectiveSolutionScope<BinaryVector> b, CancellationToken token, bool delink = false) {
187      var evaluations = 0;
188      var childScope = (ISingleObjectiveSolutionScope<BinaryVector>)a.Clone();
189      var child = childScope.Solution;
190      ISingleObjectiveSolutionScope<BinaryVector> best = null;
191      var cF = a.Fitness;
192      var bF = double.NaN;
193      var order = Enumerable.Range(0, child.Length)
194        .Where(x => !delink && child[x] != b.Solution[x] || delink && child[x] == b.Solution[x])
195        .Shuffle(Context.Random).ToList();
196      if (order.Count == 0) return childScope;
197
198      while (true) {
199        var bestS = double.NaN;
200        var bestI = -1;
201        for (var i = 0; i < order.Count; i++) {
202          var idx = order[i];
203          child[idx] = !child[idx]; // move
204          Context.Evaluate(childScope, token);
205          evaluations++;
206          var s = childScope.Fitness;
207          childScope.Fitness = cF;
208          child[idx] = !child[idx]; // undo move
209          if (Context.IsBetter(s, cF)) {
210            bestS = s;
211            bestI = i;
212            break; // first-improvement
213          }
214          if (Context.IsBetter(s, bestS)) {
215            // least-degrading
216            bestS = s;
217            bestI = i;
218          }
219        }
220        child[order[bestI]] = !child[order[bestI]];
221        order.RemoveAt(bestI);
222        cF = bestS;
223        childScope.Fitness = cF;
224        if (Context.IsBetter(cF, bF)) {
225          bF = cF;
226          best = (ISingleObjectiveSolutionScope<BinaryVector>)childScope.Clone();
227        }
228        if (order.Count == 0) break;
229      }
230      Context.IncrementEvaluatedSolutions(evaluations);
231      return best ?? childScope;
232    }
233  }
234}
Note: See TracBrowser for help on using the repository browser.