source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.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: 36.4 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.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.MemPR.Permutation {
37  [Item("MemPR (permutation)", "MemPR implementation for permutations.")]
38  [StorableClass]
39  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
40  public class PermutationMemPR : MemPRAlgorithm<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
41#if DEBUG
42    private const bool VALIDATE = true;
43#else
44    private const bool VALIDATE = false;
45#endif
46
47    [StorableConstructor]
48    protected PermutationMemPR(bool deserializing) : base(deserializing) { }
49    protected PermutationMemPR(PermutationMemPR original, Cloner cloner) : base(original, cloner) { }
50    public PermutationMemPR() {
51      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<PermutationMemPRPopulationContext>>())
52        SolutionModelTrainerParameter.ValidValues.Add(trainer);
53     
54      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<PermutationMemPRSolutionContext>>()) {
55        LocalSearchParameter.ValidValues.Add(localSearch);
56      }
57    }
58
59    public override IDeepCloneable Clone(Cloner cloner) {
60      return new PermutationMemPR(this, cloner);
61    }
62
63    protected override bool Eq(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
64      return new PermutationEqualityComparer().Equals(a.Solution, b.Solution);
65    }
66
67    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
68      return Dist(a.Solution, b.Solution);
69    }
70
71    private static double Dist(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
72      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
73    }
74
75    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> ToScope(Encodings.PermutationEncoding.Permutation code, double fitness = double.NaN) {
76      var creator = Problem.SolutionCreator as IPermutationCreator;
77      if (creator == null) throw new InvalidOperationException("Can only solve binary encoded problems with MemPR (binary)");
78      return new SingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation>(code, creator.PermutationParameter.ActualName, fitness, Problem.Evaluator.QualityParameter.ActualName) {
79        Parent = Context.Scope
80      };
81    }
82
83    protected override ISolutionSubspace<Encodings.PermutationEncoding.Permutation> CalculateSubspace(IEnumerable<Encodings.PermutationEncoding.Permutation> solutions, bool inverse = false) {
84      var subspace = new bool[Problem.Encoding.Length, Problem.Encoding.PermutationTypeParameter.Value.Value == PermutationTypes.Absolute ? 1 : Problem.Encoding.Length];
85
86      switch (Problem.Encoding.PermutationTypeParameter.Value.Value) {
87        case PermutationTypes.Absolute: {
88            if (inverse) {
89              for (var i = 0; i < subspace.GetLength(0); i++)
90                subspace[i, 0] = true;
91            }
92            var first = solutions.First();
93            foreach (var s in solutions.Skip(1)) {
94              for (var i = 0; i < s.Length; i++) {
95                if (first[i] != s[i]) subspace[i, 0] = !inverse;
96              }
97            }
98          }
99          break;
100        case PermutationTypes.RelativeDirected: {
101            if (inverse) {
102              for (var i = 0; i < subspace.GetLength(0); i++)
103                for (var j = 0; j < subspace.GetLength(1); j++)
104                  subspace[i, j] = true;
105            }
106            var first = solutions.First();
107            var placedFirst = new int[first.Length];
108            for (var i = 0; i < first.Length; i++) {
109              placedFirst[first[i]] = i;
110            }
111            foreach (var s in solutions.Skip(1)) {
112              for (var i = 0; i < s.Length; i++) {
113                if (placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)] != -1)
114                  subspace[i, 0] = !inverse;
115              }
116            }
117          }
118          break;
119        case PermutationTypes.RelativeUndirected: {
120            if (inverse) {
121              for (var i = 0; i < subspace.GetLength(0); i++)
122                for (var j = 0; j < subspace.GetLength(1); j++)
123                  subspace[i, j] = true;
124            }
125            var first = solutions.First();
126            var placedFirst = new int[first.Length];
127            for (var i = 0; i < first.Length; i++) {
128              placedFirst[first[i]] = i;
129            }
130            foreach (var s in solutions.Skip(1)) {
131              for (var i = 0; i < s.Length; i++) {
132                if (Math.Abs(placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)]) != 1)
133                  subspace[i, 0] = !inverse;
134              }
135            }
136          }
137          break;
138        default:
139          throw new ArgumentException(string.Format("Unknown permutation type {0}", Problem.Encoding.PermutationTypeParameter.Value.Value));
140      }
141      return new PermutationSolutionSubspace(subspace);
142    }
143
144    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
145      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Context.Problem, scope);
146      var quality = scope.Fitness;
147      try {
148        TabuWalk(Context.Random, scope.Solution, wrapper.Evaluate, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
149      } finally {
150        scope.Fitness = quality;
151      }
152    }
153
154    public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
155      switch (perm.PermutationType) {
156        case PermutationTypes.Absolute:
157          TabuWalkSwap(random, perm, eval, ref quality, maxEvals, subspace);
158          break;
159        case PermutationTypes.RelativeDirected:
160          TabuWalkShift(random, perm, eval, ref quality, maxEvals, subspace);
161          break;
162        case PermutationTypes.RelativeUndirected:
163          TabuWalkOpt(random, perm, eval, ref quality, maxEvals, subspace);
164          break;
165        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
166      }
167      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
168    }
169
170    public int TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
171      var evaluations = 0;
172      var maximization = Context.Problem.Maximization;
173      if (double.IsNaN(quality)) {
174        quality = eval(perm, random);
175        evaluations++;
176      }
177      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
178      double bestOfTheWalkF = double.NaN;
179      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
180      var currentF = quality;
181      var overallImprovement = false;
182      var tabu = new double[current.Length, current.Length];
183      for (var i = 0; i < current.Length; i++) {
184        for (var j = i; j < current.Length; j++) {
185          tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
186        }
187        tabu[i, current[i]] = currentF;
188      }
189
190      var steps = 0;
191      var stepsUntilBestOfWalk = 0;
192      for (var iter = 0; iter < int.MaxValue; iter++) {
193        var allTabu = true;
194        var bestOfTheRestF = double.NaN;
195        Swap2Move bestOfTheRest = null;
196        var improved = false;
197        foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
198          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
199            continue;
200
201          var h = current[swap.Index1];
202          current[swap.Index1] = current[swap.Index2];
203          current[swap.Index2] = h;
204          var q = eval(current, random);
205          evaluations++;
206          if (FitnessComparer.IsBetter(maximization, q, quality)) {
207            overallImprovement = true;
208            quality = q;
209            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
210          }
211          // check if it would not be an improvement to swap these into their positions
212          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
213                    && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
214          if (!isTabu) allTabu = false;
215          if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
216            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
217              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
218              bestOfTheWalkF = q;
219              stepsUntilBestOfWalk = steps;
220            }
221            steps++;
222            improved = true;
223            // perform the move
224            currentF = q;
225            // mark that to move them to their previous position requires to make an improvement
226            tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
227                                                                   : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
228            tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
229                                                                   : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
230          } else { // undo the move
231            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
232              bestOfTheRest = swap;
233              bestOfTheRestF = q;
234            }
235            current[swap.Index2] = current[swap.Index1];
236            current[swap.Index1] = h;
237          }
238          if (evaluations >= maxEvals) break;
239        }
240        if (!allTabu && !improved && bestOfTheRest != null) {
241          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
242                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
243          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
244                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
245
246          var h = current[bestOfTheRest.Index1];
247          current[bestOfTheRest.Index1] = current[bestOfTheRest.Index2];
248          current[bestOfTheRest.Index2] = h;
249
250          currentF = bestOfTheRestF;
251          steps++;
252        } else if (allTabu) break;
253        if (evaluations >= maxEvals) break;
254      }
255      Context.IncrementEvaluatedSolutions(evaluations);
256      if (!overallImprovement && bestOfTheWalk != null) {
257        quality = bestOfTheWalkF;
258        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
259      }
260      return stepsUntilBestOfWalk;
261    }
262
263    public int TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
264      return 0;
265    }
266
267    public int TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
268      var maximization = Context.Problem.Maximization;
269      var evaluations = 0;
270      if (double.IsNaN(quality)) {
271        quality = eval(perm, random);
272        evaluations++;
273      }
274      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
275      var bestOfTheWalkF = double.NaN;
276      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
277      var currentF = quality;
278      var overallImprovement = false;
279      var tabu = new double[current.Length, current.Length];
280      for (var i = 0; i < current.Length; i++) {
281        for (var j = i; j < current.Length; j++) {
282          tabu[i, j] = tabu[j, i] = double.MaxValue;
283        }
284        tabu[current[i], current.GetCircular(i + 1)] = currentF;
285        tabu[current.GetCircular(i + 1), current[i]] = currentF;
286      }
287
288      var steps = 0;
289      var stepsUntilBestOfWalk = 0;
290      for (var iter = 0; iter < int.MaxValue; iter++) {
291        var allTabu = true;
292        var bestOfTheRestF = double.NaN;
293        InversionMove bestOfTheRest = null;
294        var improved = false;
295
296        foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random)) {
297          var prev = opt.Index1 - 1;
298          var next = (opt.Index2 + 1) % current.Length;
299          if (prev < 0) prev += current.Length;
300          if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
301            continue;
302
303          InversionManipulator.Apply(current, opt.Index1, opt.Index2);
304
305          var q = eval(current, random);
306          evaluations++;
307          if (FitnessComparer.IsBetter(maximization, q, quality)) {
308            overallImprovement = true;
309            quality = q;
310            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
311          }
312          // check if it would not be an improvement to opt these into their positions
313          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[current[prev], current[opt.Index1]])
314                    && !FitnessComparer.IsBetter(maximization, q, tabu[current[opt.Index2], current[next]]);
315          if (!isTabu) allTabu = false;
316          if (!isTabu && FitnessComparer.IsBetter(maximization, q, currentF)) {
317            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
318              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
319              bestOfTheWalkF = q;
320              stepsUntilBestOfWalk = steps;
321            }
322
323            steps++;
324            improved = true;
325            // perform the move
326            currentF = q;
327            // mark that to move them to their previous position requires to make an improvement
328            if (maximization) {
329              tabu[current[prev], current[opt.Index2]] = Math.Max(q, tabu[current[prev], current[opt.Index2]]);
330              tabu[current[opt.Index2], current[prev]] = Math.Max(q, tabu[current[opt.Index2], current[prev]]);
331              tabu[current[opt.Index1], current[next]] = Math.Max(q, tabu[current[opt.Index1], current[next]]);
332              tabu[current[next], current[opt.Index1]] = Math.Max(q, tabu[current[next], current[opt.Index1]]);
333            } else {
334              tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
335              tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
336              tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
337              tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
338            }
339          } else { // undo the move
340            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
341              bestOfTheRest = opt;
342              bestOfTheRestF = q;
343            }
344
345            InversionManipulator.Apply(current, opt.Index1, opt.Index2);
346          }
347          if (evaluations >= maxEvals) break;
348        }
349        if (!allTabu && !improved && bestOfTheRest != null) {
350          var prev = bestOfTheRest.Index1 - 1;
351          var next = (bestOfTheRest.Index2 + 1) % current.Length;
352          if (prev < 0) prev += current.Length;
353
354          if (maximization) {
355            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Max(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
356            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
357            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
358            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Max(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
359          } else {
360            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
361            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
362            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
363            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
364          }
365          InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
366
367          currentF = bestOfTheRestF;
368          steps++;
369        } else if (allTabu) break;
370        if (evaluations >= maxEvals) break;
371      }
372      Context.IncrementEvaluatedSolutions(evaluations);
373      if (!overallImprovement && bestOfTheWalk != null) {
374        quality = bestOfTheWalkF;
375        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
376      }
377      return stepsUntilBestOfWalk;
378    }
379
380    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Breed(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
381      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> child = null;
382
383      if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
384        child = CrossAbsolute(p1, p2, token);
385      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
386        child = CrossRelativeDirected(p1, p2, token);
387      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
388        child = CrossRelativeUndirected(p1, p2, token);
389      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
390
391      if (VALIDATE && !child.Solution.Validate()) throw new ArgumentException("Cross produced invalid child");
392      return child;
393    }
394
395    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
396      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
397      var cacheHits = 0;
398      var evaluations = 1;
399      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
400      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
401        var c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution);
402        if (cache.Contains(c)) {
403          cacheHits++;
404          if (cacheHits > 10) break;
405          continue;
406        }
407        var probe = ToScope(c);
408        Evaluate(probe, token);
409        cache.Add(c);
410        if (offspring == null || Context.IsBetter(probe, offspring)) {
411          offspring = probe;
412          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
413            break;
414        }
415      }
416      Context.IncrementEvaluatedSolutions(evaluations-1);
417      return offspring;
418    }
419
420    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
421      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
422      var cacheHits = 0;
423      var evaluations = 1;
424      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
425      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
426        var c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
427        if (cache.Contains(c)) {
428          cacheHits++;
429          if (cacheHits > 10) break;
430          continue;
431        }
432        var probe = ToScope(c);
433        Evaluate(probe, token);
434        cache.Add(c);
435        if (offspring == null || Context.IsBetter(probe, offspring)) {
436          offspring = probe;
437          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
438            break;
439        }
440      }
441      Context.IncrementEvaluatedSolutions(evaluations-1);
442      return offspring;
443    }
444
445    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
446      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
447      var cacheHits = 0;
448      var evaluations = 1;
449      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
450      for (; evaluations <= Context.LocalSearchEvaluations; evaluations++) {
451        var c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
452        if (cache.Contains(c)) {
453          cacheHits++;
454          if (cacheHits > 10) break;
455          continue;
456        }
457        var probe = ToScope(c);
458        Evaluate(probe, token);
459        cache.Add(c);
460        if (offspring == null || Context.IsBetter(probe, offspring)) {
461          offspring = probe;
462          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
463            break;
464        }
465      }
466      Context.IncrementEvaluatedSolutions(evaluations-1);
467      return offspring;
468    }
469
470    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
471      if (double.IsNaN(a.Fitness)) Evaluate(a, token);
472      if (double.IsNaN(b.Fitness)) Evaluate(b, token);
473      if (Context.Random.NextDouble() < 0.5)
474        return Context.IsBetter(a, b) ? Relink(a, b, token) : Relink(b, a, token);
475      else return Context.IsBetter(a, b) ? Relink(b, a, token) : Relink(a, b, token);
476    }
477
478    protected virtual ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Relink(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> betterScope, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> worseScope, CancellationToken token) {
479      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, betterScope);
480      double quality;
481      return ToScope(Relink(Context.Random, betterScope.Solution, worseScope.Solution, wrapper.Evaluate, out quality));
482    }
483
484    public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
485      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
486      switch (p1.PermutationType) {
487        case PermutationTypes.Absolute:
488          return RelinkSwap(random, p1, p2, eval, out best);
489        case PermutationTypes.RelativeDirected:
490          return RelinkShift(random, p1, p2, eval, out best);
491        case PermutationTypes.RelativeUndirected:
492          return RelinkOpt(random, p1, p2, eval, out best);
493        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
494      }
495    }
496
497    public Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
498      var maximization = Context.Problem.Maximization;
499      var evaluations = 0;
500      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
501
502      best = double.NaN;
503      Encodings.PermutationEncoding.Permutation bestChild = null;
504
505      var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
506      var invChild = new int[child.Length];
507      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
508
509      //Log(string.Join(", ", child));
510      while (options.Count > 0) {
511        int bestOption = -1;
512        var bestChange = double.NaN;
513        for (var j = 0; j < options.Count; j++) {
514          var idx = options[j];
515          if (child[idx] == p2[idx]) {
516            options.RemoveAt(j);
517            j--;
518            continue;
519          }
520          Swap(child, invChild[p2[idx]], idx);
521          var moveF = eval(child, random);
522          evaluations++;
523          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
524            bestChange = moveF;
525            bestOption = j;
526          }
527          // undo
528          Swap(child, invChild[p2[idx]], idx);
529        }
530        if (!double.IsNaN(bestChange)) {
531          var idx1 = options[bestOption];
532          var idx2 = invChild[p2[idx1]];
533          Swap(child, idx1, idx2);
534          invChild[child[idx1]] = idx1;
535          invChild[child[idx2]] = idx2;
536          //Log(string.Join(", ", child));
537          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
538            if (Dist(child, p2) > 0) {
539              best = bestChange;
540              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
541            }
542          }
543          options.RemoveAt(bestOption);
544        }
545      }
546      if (bestChild == null) {
547        best = eval(child, random);
548        evaluations++;
549      }
550      Context.IncrementEvaluatedSolutions(evaluations);
551
552      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
553      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
554
555      return bestChild ?? child;
556    }
557
558    public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
559      var maximization = Context.Problem.Maximization;
560      var evaluations = 0;
561      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
562
563      best = double.NaN;
564      Encodings.PermutationEncoding.Permutation bestChild = null;
565
566      var invChild = new int[child.Length];
567      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
568
569      var bestChange = double.NaN;
570      do {
571        int bestFrom = -1, bestTo = -1;
572        bestChange = double.NaN;
573        for (var j = 0; j < child.Length; j++) {
574          var c = invChild[p2[j]];
575          var n = invChild[p2.GetCircular(j + 1)];
576          if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
577
578          if (c < n) Shift(child, from: n, to: c + 1);
579          else Shift(child, from: c, to: n);
580          var moveF = eval(child, random);
581          evaluations++;
582          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
583            bestChange = moveF;
584            bestFrom = c < n ? n : c;
585            bestTo = c < n ? c + 1 : n;
586          }
587          // undo
588          if (c < n) Shift(child, from: c + 1, to: n);
589          else Shift(child, from: n, to: c);
590        }
591        if (!double.IsNaN(bestChange)) {
592          Shift(child, bestFrom, bestTo);
593          for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
594          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
595            best = bestChange;
596            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
597          }
598        }
599      } while (!double.IsNaN(bestChange));
600
601      if (bestChild == null) {
602        best = eval(child, random);
603        evaluations++;
604      }
605      Context.IncrementEvaluatedSolutions(evaluations);
606
607      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
608      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
609
610      return bestChild ?? child;
611    }
612
613    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
614      var maximization = Context.Problem.Maximization;
615      var evaluations = 0;
616      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
617
618      best = double.NaN;
619      Encodings.PermutationEncoding.Permutation bestChild = null;
620
621      var invChild = new int[child.Length];
622      var invP2 = new int[child.Length];
623      for (var i = 0; i < child.Length; i++) {
624        invChild[child[i]] = i;
625        invP2[p2[i]] = i;
626      }
627
628      var bestChange = double.NaN;
629      var moveQueue = new Queue<Tuple<int, int>>();
630      var undoStack = new Stack<Tuple<int, int>>();
631      do {
632        Queue<Tuple<int, int>> bestQueue = null;
633        bestChange = double.NaN;
634        for (var j = 0; j < p2.Length; j++) {
635          if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
636
637          var a = invChild[p2[j]];
638          var b = invChild[p2.GetCircular(j + 1)];
639          if (a > b) { var h = a; a = b; b = h; }
640          var aprev = a - 1;
641          var bprev = b - 1;
642          while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
643            aprev--;
644          }
645          while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
646            bprev--;
647          }
648          var bnext = b + 1;
649          var anext = a + 1;
650          while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
651            bnext++;
652          }
653          while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
654            anext++;
655          }
656          aprev++; bprev++; anext--; bnext--;
657
658          if (aprev < a && bnext > b) {
659            if (aprev < 0) {
660              moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
661              moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
662            } else {
663              moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
664              moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
665            }
666          } else if (aprev < a && bnext == b && bprev == b) {
667            moveQueue.Enqueue(Tuple.Create(a + 1, b));
668          } else if (aprev < a && bprev < b) {
669            moveQueue.Enqueue(Tuple.Create(a + 1, b));
670          } else if (aprev == a && anext == a && bnext > b) {
671            moveQueue.Enqueue(Tuple.Create(a, b - 1));
672          } else if (aprev == a && anext == a && bnext == b && bprev == b) {
673            moveQueue.Enqueue(Tuple.Create(a, b - 1));
674          } else if (aprev == a && anext == a && bprev < b) {
675            moveQueue.Enqueue(Tuple.Create(a + 1, b));
676          } else if (anext > a && bnext > b) {
677            moveQueue.Enqueue(Tuple.Create(a, b - 1));
678          } else if (anext > a && bnext == b && bprev == b) {
679            moveQueue.Enqueue(Tuple.Create(a, b - 1));
680          } else /*if (anext > a && bprev < b)*/ {
681            moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
682            moveQueue.Enqueue(Tuple.Create(bprev, b));
683          }
684
685          while (moveQueue.Count > 0) {
686            var m = moveQueue.Dequeue();
687            Opt(child, m.Item1, m.Item2);
688            undoStack.Push(m);
689          }
690          var moveF = eval(child, random);
691          evaluations++;
692          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
693            bestChange = moveF;
694            bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
695          }
696          // undo
697          while (undoStack.Count > 0) {
698            var m = undoStack.Pop();
699            Opt(child, m.Item1, m.Item2);
700          }
701        }
702        if (!double.IsNaN(bestChange)) {
703          while (bestQueue.Count > 0) {
704            var m = bestQueue.Dequeue();
705            Opt(child, m.Item1, m.Item2);
706          }
707          for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
708          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
709            best = bestChange;
710            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
711          }
712        }
713      } while (!double.IsNaN(bestChange));
714
715      if (bestChild == null) {
716        best = eval(child, random);
717        evaluations++;
718      }
719      Context.IncrementEvaluatedSolutions(evaluations);
720     
721      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
722      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
723      return bestChild ?? child;
724    }
725
726    private static bool IsUndirectedEdge(int[] invP, int a, int b) {
727      var d = Math.Abs(invP[a] - invP[b]);
728      return d == 1 || d == invP.Length - 1;
729    }
730
731    private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
732      Swap2Manipulator.Apply(child, from, to);
733    }
734
735    private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
736      TranslocationManipulator.Apply(child, from, from, to);
737    }
738
739    private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
740      if (from > to) {
741        var h = from;
742        from = to;
743        to = h;
744      }
745      InversionManipulator.Apply(child, from, to);
746    }
747  }
748}
Note: See TracBrowser for help on using the repository browser.