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