source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs @ 14492

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

#2701:

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