source: branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs @ 14550

Last change on this file since 14550 was 14550, checked in by abeham, 5 years ago

#2701:

  • Added BinaryVectorEqualityComparer (identical to the one in the P3 plugin) to binaryvector plugin
  • Added delinking for absolute coded permutations
  • Some tweaks
File size: 39.3 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(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
64      return new PermutationEqualityComparer().Equals(a, b);
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 <= p1.Solution.Length; evaluations++) {
401        Encodings.PermutationEncoding.Permutation c = null;
402        var xochoice = Context.Random.Next(3);
403        switch (xochoice) {
404          case 0: c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
405          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
406          case 2: c = UniformLikeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
407        }
408        if (cache.Contains(c)) {
409          cacheHits++;
410          if (cacheHits > 10) break;
411          continue;
412        }
413        var probe = ToScope(c);
414        Evaluate(probe, token);
415        cache.Add(c);
416        if (offspring == null || Context.IsBetter(probe, offspring)) {
417          offspring = probe;
418          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
419            break;
420        }
421      }
422      Context.IncrementEvaluatedSolutions(evaluations-1);
423      return offspring;
424    }
425
426    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
427      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
428      var cacheHits = 0;
429      var evaluations = 1;
430      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
431      for (; evaluations <= p1.Solution.Length; evaluations++) {
432        Encodings.PermutationEncoding.Permutation c = null;
433        var xochoice = Context.Random.Next(3);
434        switch (xochoice) {
435          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
436          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
437          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
438        }
439        if (cache.Contains(c)) {
440          cacheHits++;
441          if (cacheHits > 10) break;
442          continue;
443        }
444        var probe = ToScope(c);
445        Evaluate(probe, token);
446        cache.Add(c);
447        if (offspring == null || Context.IsBetter(probe, offspring)) {
448          offspring = probe;
449          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
450            break;
451        }
452      }
453      Context.IncrementEvaluatedSolutions(evaluations-1);
454      return offspring;
455    }
456
457    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
458      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
459      var cacheHits = 0;
460      var evaluations = 1;
461      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
462      for (; evaluations <= p1.Solution.Length; evaluations++) {
463        Encodings.PermutationEncoding.Permutation c = null;
464        var xochoice = Context.Random.Next(3);
465        switch (xochoice) {
466          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
467          case 1: c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
468          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
469        }
470        if (cache.Contains(c)) {
471          cacheHits++;
472          if (cacheHits > 10) break;
473          continue;
474        }
475        var probe = ToScope(c);
476        Evaluate(probe, token);
477        cache.Add(c);
478        if (offspring == null || Context.IsBetter(probe, offspring)) {
479          offspring = probe;
480          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
481            break;
482        }
483      }
484      Context.IncrementEvaluatedSolutions(evaluations-1);
485      return offspring;
486    }
487
488    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
489      if (double.IsNaN(a.Fitness)) {
490        Evaluate(a, token);
491        Context.IncrementEvaluatedSolutions(1);
492      }
493      if (double.IsNaN(b.Fitness)) {
494        Evaluate(b, token);
495        Context.IncrementEvaluatedSolutions(1);
496      }
497
498      var wrapper = new EvaluationWrapper<Encodings.PermutationEncoding.Permutation>(Problem, ToScope(null));
499      double quality;
500      return ToScope(Relink(Context.Random, a.Solution, b.Solution, wrapper.Evaluate, delink, out quality));
501    }
502
503    public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
504      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
505      switch (p1.PermutationType) {
506        case PermutationTypes.Absolute:
507          return delink ? DelinkSwap(random, p1, p2, eval, out best) : RelinkSwap(random, p1, p2, eval, out best);
508        case PermutationTypes.RelativeDirected:
509          return RelinkShift(random, p1, p2, eval, delink, out best);
510        case PermutationTypes.RelativeUndirected:
511          return RelinkOpt(random, p1, p2, eval, delink, out best);
512        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
513      }
514    }
515
516    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) {
517      var maximization = Context.Problem.Maximization;
518      var evaluations = 0;
519      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
520
521      best = double.NaN;
522      Encodings.PermutationEncoding.Permutation bestChild = null;
523
524      var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
525      var invChild = new int[child.Length];
526      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
527     
528      while (options.Count > 0) {
529        int bestOption = -1;
530        var bestChange = double.NaN;
531        for (var j = 0; j < options.Count; j++) {
532          var idx = options[j];
533          if (child[idx] == p2[idx]) {
534            options.RemoveAt(j);
535            j--;
536            continue;
537          }
538          Swap(child, invChild[p2[idx]], idx);
539          var moveF = eval(child, random);
540          evaluations++;
541          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
542            bestChange = moveF;
543            bestOption = j;
544          }
545          // undo
546          Swap(child, invChild[p2[idx]], idx);
547        }
548        if (!double.IsNaN(bestChange)) {
549          var idx1 = options[bestOption];
550          var idx2 = invChild[p2[idx1]];
551          Swap(child, idx1, idx2);
552          invChild[child[idx1]] = idx1;
553          invChild[child[idx2]] = idx2;
554          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
555            if (Dist(child, p2) > 0) {
556              best = bestChange;
557              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
558            }
559          }
560          options.RemoveAt(bestOption);
561        }
562      }
563      if (bestChild == null) {
564        best = eval(child, random);
565        evaluations++;
566      }
567      Context.IncrementEvaluatedSolutions(evaluations);
568
569      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
570      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
571
572      return bestChild ?? child;
573    }
574
575    public Encodings.PermutationEncoding.Permutation DelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, out double best) {
576      var maximization = Context.Problem.Maximization;
577      var evaluations = 0;
578      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
579
580      best = double.NaN;
581      Encodings.PermutationEncoding.Permutation bestChild = null;
582
583      var options = Enumerable.Range(0, child.Length).Where(x => child[x] == p2[x]).ToList();
584     
585      while (options.Count > 0) {
586        int bestOption = -1;
587        int bestCompanion = -1;
588        var bestChange = double.NaN;
589        for (var j = 0; j < options.Count; j++) {
590          var idx = options[j];
591          if (child[idx] != p2[idx]) {
592            options.RemoveAt(j);
593            j--;
594            continue;
595          }
596          for (var k = 0; k < child.Length; k++) {
597            if (k == idx) continue;
598            Swap(child, k, idx);
599            var moveF = eval(child, random);
600            evaluations++;
601            if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
602              bestChange = moveF;
603              bestOption = j;
604              bestCompanion = k;
605            }
606            // undo
607            Swap(child, k, idx);
608          }
609        }
610        if (!double.IsNaN(bestChange)) {
611          var idx1 = options[bestOption];
612          Swap(child, idx1, bestCompanion);
613          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
614            if (!Eq(child, p2)) {
615              best = bestChange;
616              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
617            }
618          }
619          options.RemoveAt(bestOption);
620        }
621      }
622      if (bestChild == null) {
623        best = eval(child, random);
624        evaluations++;
625      }
626      Context.IncrementEvaluatedSolutions(evaluations);
627
628      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
629      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
630
631      return bestChild ?? child;
632    }
633
634    public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
635      var maximization = Context.Problem.Maximization;
636      var evaluations = 0;
637      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
638
639      best = double.NaN;
640      Encodings.PermutationEncoding.Permutation bestChild = null;
641
642      var invChild = new int[child.Length];
643      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
644
645      var bestChange = double.NaN;
646      do {
647        int bestFrom = -1, bestTo = -1;
648        bestChange = double.NaN;
649        for (var j = 0; j < child.Length; j++) {
650          var c = invChild[p2[j]];
651          var n = invChild[p2.GetCircular(j + 1)];
652          if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
653
654          if (c < n) Shift(child, from: n, to: c + 1);
655          else Shift(child, from: c, to: n);
656          var moveF = eval(child, random);
657          evaluations++;
658          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
659            bestChange = moveF;
660            bestFrom = c < n ? n : c;
661            bestTo = c < n ? c + 1 : n;
662          }
663          // undo
664          if (c < n) Shift(child, from: c + 1, to: n);
665          else Shift(child, from: n, to: c);
666        }
667        if (!double.IsNaN(bestChange)) {
668          Shift(child, bestFrom, bestTo);
669          for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
670          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
671            best = bestChange;
672            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
673          }
674        }
675      } while (!double.IsNaN(bestChange));
676
677      if (bestChild == null) {
678        best = eval(child, random);
679        evaluations++;
680      }
681      Context.IncrementEvaluatedSolutions(evaluations);
682
683      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
684      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
685
686      return bestChild ?? child;
687    }
688
689    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, IRandom, double> eval, bool delink, out double best) {
690      var maximization = Context.Problem.Maximization;
691      var evaluations = 0;
692      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
693
694      best = double.NaN;
695      Encodings.PermutationEncoding.Permutation bestChild = null;
696
697      var invChild = new int[child.Length];
698      var invP2 = new int[child.Length];
699      for (var i = 0; i < child.Length; i++) {
700        invChild[child[i]] = i;
701        invP2[p2[i]] = i;
702      }
703
704      var bestChange = double.NaN;
705      var moveQueue = new Queue<Tuple<int, int>>();
706      var undoStack = new Stack<Tuple<int, int>>();
707      do {
708        Queue<Tuple<int, int>> bestQueue = null;
709        bestChange = double.NaN;
710        for (var j = 0; j < p2.Length; j++) {
711          if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
712
713          var a = invChild[p2[j]];
714          var b = invChild[p2.GetCircular(j + 1)];
715          if (a > b) { var h = a; a = b; b = h; }
716          var aprev = a - 1;
717          var bprev = b - 1;
718          while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
719            aprev--;
720          }
721          while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
722            bprev--;
723          }
724          var bnext = b + 1;
725          var anext = a + 1;
726          while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
727            bnext++;
728          }
729          while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
730            anext++;
731          }
732          aprev++; bprev++; anext--; bnext--;
733
734          if (aprev < a && bnext > b) {
735            if (aprev < 0) {
736              moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
737              moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
738            } else {
739              moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
740              moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
741            }
742          } else if (aprev < a && bnext == b && bprev == b) {
743            moveQueue.Enqueue(Tuple.Create(a + 1, b));
744          } else if (aprev < a && bprev < b) {
745            moveQueue.Enqueue(Tuple.Create(a + 1, b));
746          } else if (aprev == a && anext == a && bnext > b) {
747            moveQueue.Enqueue(Tuple.Create(a, b - 1));
748          } else if (aprev == a && anext == a && bnext == b && bprev == b) {
749            moveQueue.Enqueue(Tuple.Create(a, b - 1));
750          } else if (aprev == a && anext == a && bprev < b) {
751            moveQueue.Enqueue(Tuple.Create(a + 1, b));
752          } else if (anext > a && bnext > b) {
753            moveQueue.Enqueue(Tuple.Create(a, b - 1));
754          } else if (anext > a && bnext == b && bprev == b) {
755            moveQueue.Enqueue(Tuple.Create(a, b - 1));
756          } else /*if (anext > a && bprev < b)*/ {
757            moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
758            moveQueue.Enqueue(Tuple.Create(bprev, b));
759          }
760
761          while (moveQueue.Count > 0) {
762            var m = moveQueue.Dequeue();
763            Opt(child, m.Item1, m.Item2);
764            undoStack.Push(m);
765          }
766          var moveF = eval(child, random);
767          evaluations++;
768          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
769            bestChange = moveF;
770            bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
771          }
772          // undo
773          while (undoStack.Count > 0) {
774            var m = undoStack.Pop();
775            Opt(child, m.Item1, m.Item2);
776          }
777        }
778        if (!double.IsNaN(bestChange)) {
779          while (bestQueue.Count > 0) {
780            var m = bestQueue.Dequeue();
781            Opt(child, m.Item1, m.Item2);
782          }
783          for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
784          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
785            best = bestChange;
786            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
787          }
788        }
789      } while (!double.IsNaN(bestChange));
790
791      if (bestChild == null) {
792        best = eval(child, random);
793        evaluations++;
794      }
795      Context.IncrementEvaluatedSolutions(evaluations);
796     
797      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
798      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
799      return bestChild ?? child;
800    }
801
802    private static bool IsUndirectedEdge(int[] invP, int a, int b) {
803      var d = Math.Abs(invP[a] - invP[b]);
804      return d == 1 || d == invP.Length - 1;
805    }
806
807    private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
808      Swap2Manipulator.Apply(child, from, to);
809    }
810
811    private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
812      TranslocationManipulator.Apply(child, from, from, to);
813    }
814
815    private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
816      if (from > to) {
817        var h = from;
818        from = to;
819        to = h;
820      }
821      InversionManipulator.Apply(child, from, to);
822    }
823  }
824}
Note: See TracBrowser for help on using the repository browser.