source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.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: 13.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.Algorithms.MemPR.Util;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Encodings.LinearLinkageEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.MemPR.Grouping {
37  [Item("MemPR (linear linkage)", "MemPR implementation for linear linkage vectors.")]
38  [StorableClass]
39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
40  public class LinearLinkageMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<LinearLinkageEncoding>, LinearLinkage, LinearLinkageMemPRPopulationContext, LinearLinkageMemPRSolutionContext> {
41    [StorableConstructor]
42    protected LinearLinkageMemPR(bool deserializing) : base(deserializing) { }
43    protected LinearLinkageMemPR(LinearLinkageMemPR original, Cloner cloner) : base(original, cloner) { }
44    public LinearLinkageMemPR() {
45      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<LinearLinkageMemPRPopulationContext>>())
46        SolutionModelTrainerParameter.ValidValues.Add(trainer);
47     
48      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<LinearLinkageMemPRSolutionContext>>()) {
49        LocalSearchParameter.ValidValues.Add(localSearch);
50      }
51    }
52
53    public override IDeepCloneable Clone(Cloner cloner) {
54      return new LinearLinkageMemPR(this, cloner);
55    }
56
57    protected override bool Eq(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
58      var s1 = a.Solution;
59      var s2 = b.Solution;
60      if (s1.Length != s2.Length) return false;
61      for (var i = 0; i < s1.Length; i++)
62        if (s1[i] != s2[i]) return false;
63      return true;
64    }
65
66    protected override double Dist(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b) {
67      return Dist(a.Solution, b.Solution);
68    }
69
70    private double Dist(LinearLinkage a, LinearLinkage b) {
71      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
72    }
73
74    protected override ISingleObjectiveSolutionScope<LinearLinkage> ToScope(LinearLinkage code, double fitness = double.NaN) {
75      var creator = Problem.SolutionCreator as ILinearLinkageCreator;
76      if (creator == null) throw new InvalidOperationException("Can only solve linear linkage encoded problems with MemPR (linear linkage)");
77      return new SingleObjectiveSolutionScope<LinearLinkage>(code, creator.LLEParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
78        Parent = Context.Scope
79      };
80    }
81
82    protected override ISolutionSubspace<LinearLinkage> CalculateSubspace(IEnumerable<LinearLinkage> solutions, bool inverse = false) {
83      var pop = solutions.ToList();
84      var N = pop[0].Length;
85      var subspace = new bool[N];
86      for (var i = 0; i < N; i++) {
87        var val = pop[0][i];
88        if (inverse) subspace[i] = true;
89        for (var p = 1; p < pop.Count; p++) {
90          if (pop[p][i] != val) subspace[i] = !inverse;
91        }
92      }
93      return new LinearLinkageSolutionSubspace(subspace);
94    }
95
96    protected override void AdaptiveWalk(
97        ISingleObjectiveSolutionScope<LinearLinkage> scope,
98        int maxEvals, CancellationToken token,
99        ISolutionSubspace<LinearLinkage> sub_space = null) {
100      var maximization = Context.Problem.Maximization;
101      var subspace = sub_space is LinearLinkageSolutionSubspace ? ((LinearLinkageSolutionSubspace)sub_space).Subspace : null;
102      var evaluations = 0;
103      var quality = scope.Fitness;
104      if (double.IsNaN(quality)) {
105        Evaluate(scope, token);
106        quality = scope.Fitness;
107        evaluations++;
108        if (evaluations >= maxEvals) return;
109      }
110      var bestQuality = quality;
111      var currentScope = (ISingleObjectiveSolutionScope<LinearLinkage>)scope.Clone();
112      var current = currentScope.Solution;
113      LinearLinkage bestOfTheWalk = null;
114      var bestOfTheWalkF = double.NaN;
115
116      var tabu = new double[current.Length, current.Length];
117      for (var i = 0; i < current.Length; i++) {
118        for (var j = i; j < current.Length; j++) {
119          tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
120        }
121        tabu[i, current[i]] = quality;
122      }
123
124      // this dictionary holds the last relevant links
125      var groupItems = new List<int>();
126      var lleb = current.ToBackLinks();
127      Move bestOfTheRest = null;
128      var bestOfTheRestF = double.NaN;
129      var lastAppliedMove = -1;
130      for (var iter = 0; iter < int.MaxValue; iter++) {
131        // clear the dictionary before a new pass through the array is made
132        groupItems.Clear();
133        for (var i = 0; i < current.Length; i++) {
134          if (subspace != null && !subspace[i]) {
135            if (lleb[i] != i)
136              groupItems.Remove(lleb[i]);
137            groupItems.Add(i);
138            continue;
139          }
140
141          var next = current[i];
142
143          if (lastAppliedMove == i) {
144            if (bestOfTheRest != null) {
145              bestOfTheRest.Apply(current);
146              bestOfTheRest.ApplyToLLEb(lleb);
147              currentScope.Fitness = bestOfTheRestF;
148              quality = bestOfTheRestF;
149              if (maximization) {
150                tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
151                tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
152              } else {
153                tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
154                tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
155              }
156              if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
157                bestOfTheWalk = (LinearLinkage)current.Clone();
158                bestOfTheWalkF = bestOfTheRestF;
159              }
160              bestOfTheRest = null;
161              bestOfTheRestF = double.NaN;
162              lastAppliedMove = i;
163            } else {
164              lastAppliedMove = -1;
165            }
166            break;
167          } else {
168            foreach (var move in MoveGenerator.GenerateForItem(i, groupItems, current, lleb)) {
169              // we intend to break link i -> next
170              var qualityToBreak = tabu[i, next];
171              move.Apply(current);
172              var qualityToRestore = tabu[i, current[i]]; // current[i] is new next
173              Evaluate(currentScope, token);
174              evaluations++;
175              var moveF = currentScope.Fitness;
176              var isNotTabu = FitnessComparer.IsBetter(maximization, moveF, qualityToBreak)
177                              && FitnessComparer.IsBetter(maximization, moveF, qualityToRestore);
178              var isImprovement = FitnessComparer.IsBetter(maximization, moveF, quality);
179              var isAspired = FitnessComparer.IsBetter(maximization, moveF, bestQuality);
180              if ((isNotTabu && isImprovement) || isAspired) {
181                if (maximization) {
182                  tabu[i, next] = Math.Max(tabu[i, next], moveF);
183                  tabu[i, current[i]] = Math.Max(tabu[i, current[i]], moveF);
184                } else {
185                  tabu[i, next] = Math.Min(tabu[i, next], moveF);
186                  tabu[i, current[i]] = Math.Min(tabu[i, current[i]], moveF);
187                }
188                quality = moveF;
189                if (isAspired) bestQuality = quality;
190
191                move.ApplyToLLEb(lleb);
192
193                if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheWalkF)) {
194                  bestOfTheWalk = (LinearLinkage)current.Clone();
195                  bestOfTheWalkF = moveF;
196                }
197
198                bestOfTheRest = null;
199                bestOfTheRestF = double.NaN;
200                lastAppliedMove = i;
201                break;
202              } else {
203                if (isNotTabu) {
204                  if (FitnessComparer.IsBetter(maximization, moveF, bestOfTheRestF)) {
205                    bestOfTheRest = move;
206                    bestOfTheRestF = moveF;
207                  }
208                }
209                move.Undo(current);
210                currentScope.Fitness = quality;
211              }
212              if (evaluations >= maxEvals) break;
213            }
214          }
215          if (lleb[i] != i)
216            groupItems.Remove(lleb[i]);
217          groupItems.Add(i);
218          if (evaluations >= maxEvals) break;
219          if (token.IsCancellationRequested) break;
220        }
221        if (lastAppliedMove == -1) { // no move has been applied
222          if (bestOfTheRest != null) {
223            var i = bestOfTheRest.Item;
224            var next = current[i];
225            bestOfTheRest.Apply(current);
226            currentScope.Fitness = bestOfTheRestF;
227            quality = bestOfTheRestF;
228            if (maximization) {
229              tabu[i, next] = Math.Max(tabu[i, next], bestOfTheRestF);
230              tabu[i, current[i]] = Math.Max(tabu[i, current[i]], bestOfTheRestF);
231            } else {
232              tabu[i, next] = Math.Min(tabu[i, next], bestOfTheRestF);
233              tabu[i, current[i]] = Math.Min(tabu[i, current[i]], bestOfTheRestF);
234            }
235            if (FitnessComparer.IsBetter(maximization, bestOfTheRestF, bestOfTheWalkF)) {
236              bestOfTheWalk = (LinearLinkage)current.Clone();
237              bestOfTheWalkF = bestOfTheRestF;
238            }
239
240            bestOfTheRest = null;
241            bestOfTheRestF = double.NaN;
242          } else break;
243        }
244        if (evaluations >= maxEvals) break;
245        if (token.IsCancellationRequested) break;
246      }
247      if (bestOfTheWalk != null) {
248        scope.Solution = bestOfTheWalk;
249        scope.Fitness = bestOfTheWalkF;
250      }
251    }
252
253    protected override ISingleObjectiveSolutionScope<LinearLinkage> Breed(ISingleObjectiveSolutionScope<LinearLinkage> p1Scope, ISingleObjectiveSolutionScope<LinearLinkage> p2Scope, CancellationToken token) {
254      var cache = new HashSet<LinearLinkage>(new LinearLinkageEqualityComparer());
255      var cachehits = 0;
256      var evaluations = 1;
257      ISingleObjectiveSolutionScope<LinearLinkage> offspring = null;
258      for (; evaluations < Context.LocalSearchEvaluations; evaluations++) {
259        var code = GroupCrossover.Apply(Context.Random, p1Scope.Solution, p2Scope.Solution);
260        if (cache.Contains(code)) {
261          cachehits++;
262          if (cachehits > 10) break;
263          continue;
264        }
265        var probe = ToScope(code);
266        Evaluate(probe, token);
267        cache.Add(code);
268        if (offspring == null || Context.IsBetter(probe, offspring)) {
269          offspring = probe;
270          if (Context.IsBetter(offspring, p1Scope) && Context.IsBetter(offspring, p2Scope))
271            break;
272        }
273      }
274      Context.IncrementEvaluatedSolutions(evaluations-1);
275      return offspring;
276    }
277
278    protected override ISingleObjectiveSolutionScope<LinearLinkage> Link(ISingleObjectiveSolutionScope<LinearLinkage> a, ISingleObjectiveSolutionScope<LinearLinkage> b, CancellationToken token, bool delink = false) {
279      var evaluations = 0;
280      if (double.IsNaN(a.Fitness)) {
281        Evaluate(a, token);
282        evaluations++;
283      }
284      if (double.IsNaN(b.Fitness)) {
285        Evaluate(b, token);
286        evaluations++;
287      }
288
289      var probe = (ISingleObjectiveSolutionScope<LinearLinkage>)a.Clone();
290      ISingleObjectiveSolutionScope<LinearLinkage> best = null;
291      while (true) {
292        Move bestMove = null;
293        var bestMoveQ = double.NaN;
294        // this approach may not fully relink the two solutions
295        foreach (var m in MoveGenerator.Generate(probe.Solution)) {
296          var distBefore = Dist(probe, b);
297          m.Apply(probe.Solution);
298          var distAfter = Dist(probe, b);
299          if (delink && distAfter > distBefore || !delink && distAfter < distBefore) {
300            var beforeQ = probe.Fitness;
301            Evaluate(probe, token);
302            evaluations++;
303            var q = probe.Fitness;
304            m.Undo(probe.Solution);
305            probe.Fitness = beforeQ;
306
307            if (Context.IsBetter(q, bestMoveQ)) {
308              bestMove = m;
309              bestMoveQ = q;
310            }
311            if (Context.IsBetter(q, beforeQ)) break;
312          } else m.Undo(probe.Solution);
313        }
314        if (bestMove == null) break;
315        bestMove.Apply(probe.Solution);
316        probe.Fitness = bestMoveQ;
317        if (best == null || Context.IsBetter(probe, best))
318          best = (ISingleObjectiveSolutionScope<LinearLinkage>)probe.Clone();
319      }
320      Context.IncrementEvaluatedSolutions(evaluations);
321
322      return best ?? probe;
323    }
324  }
325}
Note: See TracBrowser for help on using the repository browser.