source: branches/PerformanceComparison/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs @ 14678

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

#2457: worked on problem instance detection

File size: 43.8 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.Runtime.CompilerServices;
26using System.Threading;
27using HeuristicLab.Algorithms.MemPR.Interfaces;
28using HeuristicLab.Algorithms.MemPR.Util;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Encodings.PermutationEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.MemPR.Permutation {
38  [Item("MemPR (permutation)", "MemPR implementation for permutations.")]
39  [StorableClass]
40  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms, Priority = 999)]
41  public class PermutationMemPR : MemPRAlgorithm<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation, PermutationMemPRPopulationContext, PermutationMemPRSolutionContext> {
42#if DEBUG
43    private const bool VALIDATE = true;
44#else
45    private const bool VALIDATE = false;
46#endif
47
48    [StorableConstructor]
49    protected PermutationMemPR(bool deserializing) : base(deserializing) { }
50    protected PermutationMemPR(PermutationMemPR original, Cloner cloner) : base(original, cloner) { }
51    public PermutationMemPR() {
52      foreach (var trainer in ApplicationManager.Manager.GetInstances<ISolutionModelTrainer<PermutationMemPRPopulationContext>>())
53        SolutionModelTrainerParameter.ValidValues.Add(trainer);
54
55      if (SolutionModelTrainerParameter.ValidValues.Count > 0) {
56        var unbiased = SolutionModelTrainerParameter.ValidValues.FirstOrDefault(x => !x.Bias);
57        if (unbiased != null) SolutionModelTrainerParameter.Value = unbiased;
58      }
59
60      foreach (var localSearch in ApplicationManager.Manager.GetInstances<ILocalSearch<PermutationMemPRSolutionContext>>()) {
61        LocalSearchParameter.ValidValues.Add(localSearch);
62      }
63    }
64
65    public override IDeepCloneable Clone(Cloner cloner) {
66      return new PermutationMemPR(this, cloner);
67    }
68
69    protected override bool Eq(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
70      return new PermutationEqualityComparer().Equals(a, b);
71    }
72
73    protected override double Dist(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b) {
74      return Dist(a.Solution, b.Solution);
75    }
76
77    private static double Dist(Encodings.PermutationEncoding.Permutation a, Encodings.PermutationEncoding.Permutation b) {
78      return 1.0 - HammingSimilarityCalculator.CalculateSimilarity(a, b);
79    }
80
81    protected override ISolutionSubspace<Encodings.PermutationEncoding.Permutation> CalculateSubspace(IEnumerable<Encodings.PermutationEncoding.Permutation> solutions, bool inverse = false) {
82      var solutionsIter = solutions.GetEnumerator();
83      if (!solutionsIter.MoveNext()) throw new ArgumentException("Cannot calculate sub-space when no solutions are given.");
84      var first = solutionsIter.Current;
85
86      var N = solutionsIter.Current.Length;
87      var type = solutionsIter.Current.PermutationType;
88      var subspace = new bool[N, type == PermutationTypes.Absolute ? 1 : N];
89      switch (type) {
90        case PermutationTypes.Absolute: {
91            if (inverse) {
92              for (var i = 0; i < subspace.GetLength(0); i++)
93                subspace[i, 0] = true;
94            }
95            while (solutionsIter.MoveNext()) {
96              var s = solutionsIter.Current;
97              for (var i = 0; i < s.Length; i++) {
98                if (first[i] != s[i]) subspace[i, 0] = !inverse;
99              }
100            }
101          }
102          break;
103        case PermutationTypes.RelativeDirected: {
104            if (inverse) {
105              for (var i = 0; i < subspace.GetLength(0); i++)
106                for (var j = 0; j < subspace.GetLength(1); j++)
107                  subspace[i, j] = true;
108            }
109            var placedFirst = new int[first.Length];
110            for (var i = 0; i < first.Length; i++) {
111              placedFirst[first[i]] = i;
112            }
113            while (solutionsIter.MoveNext()) {
114              var s = solutionsIter.Current;
115              for (var i = 0; i < s.Length; i++) {
116                if (placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)] != -1)
117                  subspace[i, 0] = !inverse;
118              }
119            }
120          }
121          break;
122        case PermutationTypes.RelativeUndirected: {
123            if (inverse) {
124              for (var i = 0; i < subspace.GetLength(0); i++)
125                for (var j = 0; j < subspace.GetLength(1); j++)
126                  subspace[i, j] = true;
127            }
128            var placedFirst = new int[first.Length];
129            for (var i = 0; i < first.Length; i++) {
130              placedFirst[first[i]] = i;
131            }
132            while (solutionsIter.MoveNext()) {
133              var s = solutionsIter.Current;
134              for (var i = 0; i < s.Length; i++) {
135                if (Math.Abs(placedFirst[s[i]] - placedFirst[s.GetCircular(i + 1)]) != 1)
136                  subspace[i, 0] = !inverse;
137              }
138            }
139          }
140          break;
141        default:
142          throw new ArgumentException(string.Format("Unknown permutation type {0}", type));
143      }
144      return new PermutationSolutionSubspace(subspace);
145    }
146
147    protected override void AdaptiveWalk(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> scope, int maxEvals, CancellationToken token, ISolutionSubspace<Encodings.PermutationEncoding.Permutation> subspace = null) {
148      var quality = scope.Fitness;
149      try {
150        TabuWalk(Context.Random, scope.Solution, Context.Evaluate, token, ref quality, maxEvals, subspace != null ? ((PermutationSolutionSubspace)subspace).Subspace : null);
151      } finally {
152        scope.Fitness = quality;
153      }
154    }
155
156    public void TabuWalk(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
157      switch (perm.PermutationType) {
158        case PermutationTypes.Absolute:
159          TabuWalkSwap(random, perm, eval, token, ref quality, maxEvals, subspace);
160          break;
161        case PermutationTypes.RelativeDirected:
162          TabuWalkShift(random, perm, eval, token, ref quality, maxEvals, subspace);
163          break;
164        case PermutationTypes.RelativeUndirected:
165          TabuWalkOpt(random, perm, eval, token, ref quality, maxEvals, subspace);
166          break;
167        default: throw new ArgumentException(string.Format("Permutation type {0} is not known", perm.PermutationType));
168      }
169      if (VALIDATE && !perm.Validate()) throw new ArgumentException("TabuWalk produced invalid child");
170    }
171
172    public int TabuWalkSwap(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
173      var evaluations = 0;
174      var maximization = Context.Maximization;
175      if (double.IsNaN(quality)) {
176        quality = eval(perm, token);
177        evaluations++;
178      }
179      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
180      double bestOfTheWalkF = double.NaN;
181      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
182      var currentF = quality;
183      var overallImprovement = false;
184      var tabu = new double[current.Length, current.Length];
185      for (var i = 0; i < current.Length; i++) {
186        for (var j = i; j < current.Length; j++) {
187          tabu[i, j] = tabu[j, i] = maximization ? double.MinValue : double.MaxValue;
188        }
189        tabu[i, current[i]] = currentF;
190      }
191
192      var steps = 0;
193      var stepsUntilBestOfWalk = 0;
194      for (var iter = 0; iter < int.MaxValue; iter++) {
195        var allTabu = true;
196        var bestOfTheRestF = double.NaN;
197        Swap2Move bestOfTheRest = null;
198        var improved = false;
199        foreach (var swap in ExhaustiveSwap2MoveGenerator.Generate(current).Shuffle(random)) {
200          if (subspace != null && !(subspace[swap.Index1, 0] && subspace[swap.Index2, 0]))
201            continue;
202
203          var h = current[swap.Index1];
204          current[swap.Index1] = current[swap.Index2];
205          current[swap.Index2] = h;
206          var q = eval(current, token);
207          evaluations++;
208          if (FitnessComparer.IsBetter(maximization, q, quality)) {
209            overallImprovement = true;
210            quality = q;
211            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
212          }
213          // check if it would not be an improvement to swap these into their positions
214          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index1, current[swap.Index1]])
215                    && !FitnessComparer.IsBetter(maximization, q, tabu[swap.Index2, current[swap.Index2]]);
216          if (!isTabu) allTabu = false;
217          if (FitnessComparer.IsBetter(maximization, q, currentF) && !isTabu) {
218            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
219              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
220              bestOfTheWalkF = q;
221              stepsUntilBestOfWalk = steps;
222            }
223            steps++;
224            improved = true;
225            // perform the move
226            currentF = q;
227            // mark that to move them to their previous position requires to make an improvement
228            tabu[swap.Index1, current[swap.Index2]] = maximization ? Math.Max(q, tabu[swap.Index1, current[swap.Index2]])
229                                                                   : Math.Min(q, tabu[swap.Index1, current[swap.Index2]]);
230            tabu[swap.Index2, current[swap.Index1]] = maximization ? Math.Max(q, tabu[swap.Index2, current[swap.Index1]])
231                                                                   : Math.Min(q, tabu[swap.Index2, current[swap.Index1]]);
232          } else { // undo the move
233            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
234              bestOfTheRest = swap;
235              bestOfTheRestF = q;
236            }
237            current[swap.Index2] = current[swap.Index1];
238            current[swap.Index1] = h;
239          }
240          if (evaluations >= maxEvals) break;
241        }
242        if (!allTabu && !improved && bestOfTheRest != null) {
243          tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]])
244                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index1, current[bestOfTheRest.Index1]]);
245          tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]] = maximization ? Math.Max(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]])
246                                                                                   : Math.Min(currentF, tabu[bestOfTheRest.Index2, current[bestOfTheRest.Index2]]);
247
248          var h = current[bestOfTheRest.Index1];
249          current[bestOfTheRest.Index1] = current[bestOfTheRest.Index2];
250          current[bestOfTheRest.Index2] = h;
251
252          currentF = bestOfTheRestF;
253          steps++;
254        } else if (allTabu) break;
255        if (evaluations >= maxEvals) break;
256      }
257      Context.IncrementEvaluatedSolutions(evaluations);
258      if (!overallImprovement && bestOfTheWalk != null) {
259        quality = bestOfTheWalkF;
260        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
261      }
262      return stepsUntilBestOfWalk;
263    }
264
265    public int TabuWalkShift(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
266      return 0;
267    }
268
269    public int TabuWalkOpt(IRandom random, Encodings.PermutationEncoding.Permutation perm, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, ref double quality, int maxEvals = int.MaxValue, bool[,] subspace = null) {
270      var maximization = Context.Maximization;
271      var evaluations = 0;
272      if (double.IsNaN(quality)) {
273        quality = eval(perm, token);
274        evaluations++;
275      }
276      Encodings.PermutationEncoding.Permutation bestOfTheWalk = null;
277      var bestOfTheWalkF = double.NaN;
278      var current = (Encodings.PermutationEncoding.Permutation)perm.Clone();
279      var currentF = quality;
280      var overallImprovement = false;
281      var tabu = new double[current.Length, current.Length];
282      for (var i = 0; i < current.Length; i++) {
283        for (var j = i; j < current.Length; j++) {
284          tabu[i, j] = tabu[j, i] = double.MaxValue;
285        }
286        tabu[current[i], current.GetCircular(i + 1)] = currentF;
287        tabu[current.GetCircular(i + 1), current[i]] = currentF;
288      }
289
290      var steps = 0;
291      var stepsUntilBestOfWalk = 0;
292      for (var iter = 0; iter < int.MaxValue; iter++) {
293        var allTabu = true;
294        var bestOfTheRestF = double.NaN;
295        InversionMove bestOfTheRest = null;
296        var improved = false;
297       
298        foreach (var opt in ExhaustiveInversionMoveGenerator.Generate(current).Shuffle(random)) {
299          var prev = opt.Index1 - 1;
300          var next = (opt.Index2 + 1) % current.Length;
301          if (prev < 0) prev += current.Length;
302          if (subspace != null && !(subspace[current[prev], current[opt.Index1]] && subspace[current[opt.Index2], current[next]]))
303            continue;
304
305          current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
306
307          var q = eval(current, token);
308          evaluations++;
309          if (FitnessComparer.IsBetter(maximization, q, quality)) {
310            overallImprovement = true;
311            quality = q;
312            for (var i = 0; i < current.Length; i++) perm[i] = current[i];
313          }
314          // check if it would not be an improvement to opt these into their positions
315          var isTabu = !FitnessComparer.IsBetter(maximization, q, tabu[current[prev], current[opt.Index1]])
316                    && !FitnessComparer.IsBetter(maximization, q, tabu[current[opt.Index2], current[next]]);
317          if (!isTabu) allTabu = false;
318          if (!isTabu && FitnessComparer.IsBetter(maximization, q, currentF)) {
319            if (FitnessComparer.IsBetter(maximization, q, bestOfTheWalkF)) {
320              bestOfTheWalk = (Encodings.PermutationEncoding.Permutation)current.Clone();
321              bestOfTheWalkF = q;
322              stepsUntilBestOfWalk = steps;
323            }
324
325            steps++;
326            improved = true;
327            // perform the move
328            currentF = q;
329            // mark that to move them to their previous position requires to make an improvement
330            if (maximization) {
331              tabu[current[prev], current[opt.Index2]] = Math.Max(q, tabu[current[prev], current[opt.Index2]]);
332              tabu[current[opt.Index2], current[prev]] = Math.Max(q, tabu[current[opt.Index2], current[prev]]);
333              tabu[current[opt.Index1], current[next]] = Math.Max(q, tabu[current[opt.Index1], current[next]]);
334              tabu[current[next], current[opt.Index1]] = Math.Max(q, tabu[current[next], current[opt.Index1]]);
335            } else {
336              tabu[current[prev], current[opt.Index2]] = Math.Min(q, tabu[current[prev], current[opt.Index2]]);
337              tabu[current[opt.Index2], current[prev]] = Math.Min(q, tabu[current[opt.Index2], current[prev]]);
338              tabu[current[opt.Index1], current[next]] = Math.Min(q, tabu[current[opt.Index1], current[next]]);
339              tabu[current[next], current[opt.Index1]] = Math.Min(q, tabu[current[next], current[opt.Index1]]);
340            }
341          } else { // undo the move
342            if (!isTabu && FitnessComparer.IsBetter(maximization, q, bestOfTheRestF)) {
343              bestOfTheRest = opt;
344              bestOfTheRestF = q;
345            }
346           
347            current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
348          }
349          if (evaluations >= maxEvals) break;
350        }
351        if (!allTabu && !improved && bestOfTheRest != null) {
352          var prev = bestOfTheRest.Index1 - 1;
353          var next = (bestOfTheRest.Index2 + 1) % current.Length;
354          if (prev < 0) prev += current.Length;
355
356          if (maximization) {
357            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Max(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
358            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
359            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Max(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
360            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Max(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
361          } else {
362            tabu[current[prev], current[bestOfTheRest.Index1]] = Math.Min(currentF, tabu[current[prev], current[bestOfTheRest.Index1]]);
363            tabu[current[bestOfTheRest.Index1], current[prev]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index1], current[prev]]);
364            tabu[current[bestOfTheRest.Index2], current[next]] = Math.Min(currentF, tabu[current[bestOfTheRest.Index2], current[next]]);
365            tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
366          }
367          current.Reverse(bestOfTheRest.Index1, bestOfTheRest.Index2 - bestOfTheRest.Index1 + 1);
368
369          currentF = bestOfTheRestF;
370          steps++;
371        } else if (allTabu) break;
372        if (evaluations >= maxEvals) break;
373      }
374      Context.IncrementEvaluatedSolutions(evaluations);
375      if (!overallImprovement && bestOfTheWalk != null) {
376        quality = bestOfTheWalkF;
377        for (var i = 0; i < current.Length; i++) perm[i] = bestOfTheWalk[i];
378      }
379      return stepsUntilBestOfWalk;
380    }
381
382    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Breed(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
383      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> child = null;
384
385      if (p1.Solution.PermutationType == PermutationTypes.Absolute) {
386        child = CrossAbsolute(p1, p2, token);
387      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeDirected) {
388        child = CrossRelativeDirected(p1, p2, token);
389      } else if (p1.Solution.PermutationType == PermutationTypes.RelativeUndirected) {
390        child = CrossRelativeUndirected(p1, p2, token);
391      } else throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.Solution.PermutationType));
392
393      if (VALIDATE && !child.Solution.Validate()) throw new ArgumentException("Cross produced invalid child");
394      return child;
395    }
396
397    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossAbsolute(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
398      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
399      cache.Add(p1.Solution);
400      cache.Add(p2.Solution);
401
402      var cacheHits = new Dictionary<int, int>() { { 0, 0 }, { 1, 0 }, { 2, 0 } };
403      var evaluations = 0;
404      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
405      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
406      while (evaluations < p1.Solution.Length) {
407        Encodings.PermutationEncoding.Permutation c = null;
408        var xochoice = cacheHits.SampleRandom(Context.Random).Key;
409        switch (xochoice) {
410          case 0: c = CyclicCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
411          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
412          case 2: c = UniformLikeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
413        }
414        if (cache.Contains(c)) {
415          cacheHits[xochoice]++;
416          if (cacheHits[xochoice] > 10) {
417            cacheHits.Remove(xochoice);
418            if (cacheHits.Count == 0) break;
419          }
420          continue;
421        }
422        probe.Solution = c;
423        Context.Evaluate(probe, token);
424        evaluations++;
425        cache.Add(c);
426        if (offspring == null || Context.IsBetter(probe, offspring)) {
427          offspring = probe;
428          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
429            break;
430        }
431      }
432      Context.IncrementEvaluatedSolutions(evaluations);
433      return offspring ?? p1;
434    }
435
436    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeDirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
437      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
438      cache.Add(p1.Solution);
439      cache.Add(p2.Solution);
440
441      var cacheHits = new Dictionary<int, int>() { { 0, 0 }, { 1, 0 }, { 2, 0 } };
442      var evaluations = 0;
443      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
444      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
445      while (evaluations < p1.Solution.Length) {
446        Encodings.PermutationEncoding.Permutation c = null;
447        var xochoice = cacheHits.SampleRandom(Context.Random).Key;
448        switch (xochoice) {
449          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
450          case 1: c = PartiallyMatchedCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
451          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
452        }
453        if (cache.Contains(c)) {
454          cacheHits[xochoice]++;
455          if (cacheHits[xochoice] > 10) {
456            cacheHits.Remove(xochoice);
457            if (cacheHits.Count == 0) break;
458          }
459          continue;
460        }
461        probe.Solution = c;
462        Context.Evaluate(probe, token);
463        evaluations++;
464        cache.Add(c);
465        if (offspring == null || Context.IsBetter(probe, offspring)) {
466          offspring = probe;
467          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
468            break;
469        }
470      }
471      Context.IncrementEvaluatedSolutions(evaluations);
472      return offspring ?? p1;
473    }
474
475    private ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> CrossRelativeUndirected(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p1, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> p2, CancellationToken token) {
476      var cache = new HashSet<Encodings.PermutationEncoding.Permutation>(new PermutationEqualityComparer());
477      cache.Add(p1.Solution);
478      cache.Add(p2.Solution);
479
480      var cacheHits = new Dictionary<int, int>() { { 0, 0 }, { 1, 0 }, { 2, 0 } };
481      var evaluations = 0;
482      ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
483      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
484      while (evaluations <= p1.Solution.Length) {
485        Encodings.PermutationEncoding.Permutation c = null;
486        var xochoice = cacheHits.SampleRandom(Context.Random).Key;
487        switch (xochoice) {
488          case 0: c = OrderCrossover2.Apply(Context.Random, p1.Solution, p2.Solution); break;
489          case 1: c = EdgeRecombinationCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
490          case 2: c = MaximalPreservativeCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
491        }
492        if (cache.Contains(c)) {
493          cacheHits[xochoice]++;
494          if (cacheHits[xochoice] > 10) {
495            cacheHits.Remove(xochoice);
496            if (cacheHits.Count == 0) break;
497          }
498          continue;
499        }
500        probe.Solution = c;
501        Context.Evaluate(probe, token);
502        evaluations++;
503        cache.Add(c);
504        if (offspring == null || Context.IsBetter(probe, offspring)) {
505          offspring = probe;
506          if (Context.IsBetter(offspring, p1) && Context.IsBetter(offspring, p2))
507            break;
508        }
509      }
510      Context.IncrementEvaluatedSolutions(evaluations);
511      return offspring ?? p1;
512    }
513
514    protected override ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> Link(ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> a, ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> b, CancellationToken token, bool delink = false) {
515      double quality;
516      return Context.ToScope(Relink(Context.Random, a.Solution, b.Solution, Context.Evaluate, token, delink, out quality));
517    }
518
519    public Encodings.PermutationEncoding.Permutation Relink(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, bool delink, out double best) {
520      if (p1.PermutationType != p2.PermutationType) throw new ArgumentException(string.Format("Unequal permutation types {0} and {1}", p1.PermutationType, p2.PermutationType));
521      switch (p1.PermutationType) {
522        case PermutationTypes.Absolute:
523          return delink ? DelinkSwap(random, p1, p2, eval, token, out best) : RelinkSwap(random, p1, p2, eval, token, out best);
524        case PermutationTypes.RelativeDirected:
525          return RelinkShift(random, p1, p2, eval, token, delink, out best);
526        case PermutationTypes.RelativeUndirected:
527          return delink ? DelinkOpt(random, p1, p2, eval, token, out best) : RelinkOpt(random, p1, p2, eval, token, out best);
528        default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
529      }
530    }
531
532    public Encodings.PermutationEncoding.Permutation RelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, out double best) {
533      var maximization = Context.Maximization;
534      var evaluations = 0;
535      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
536      var childF = eval(child, token);
537      evaluations++;
538
539      var thisPath = new List<Tuple<Encodings.PermutationEncoding.Permutation, double>>() {
540        Tuple.Create((Encodings.PermutationEncoding.Permutation)child.Clone(), (childF - Context.LowerBound) / (Context.AverageQuality - Context.LowerBound))
541      };
542      best = double.NaN;
543      Encodings.PermutationEncoding.Permutation bestChild = null;
544
545      var options = Enumerable.Range(0, child.Length).Where(x => child[x] != p2[x]).ToList();
546      var invChild = new int[child.Length];
547      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
548     
549      while (options.Count > 0) {
550        int bestOption = -1;
551        var bestChange = double.NaN;
552        for (var j = 0; j < options.Count; j++) {
553          var idx = options[j];
554          if (child[idx] == p2[idx]) {
555            options.RemoveAt(j);
556            j--;
557            continue;
558          }
559          Swap(child, invChild[p2[idx]], idx);
560          var moveF = eval(child, token);
561          evaluations++;
562          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
563            bestChange = moveF;
564            bestOption = j;
565          }
566          // undo
567          Swap(child, invChild[p2[idx]], idx);
568        }
569        if (!double.IsNaN(bestChange)) {
570          var idx1 = options[bestOption];
571          var idx2 = invChild[p2[idx1]];
572          Swap(child, idx1, idx2);
573          thisPath.Add(Tuple.Create((Encodings.PermutationEncoding.Permutation)child.Clone(), (bestChange - Context.LowerBound) / (Context.AverageQuality - Context.LowerBound)));
574          invChild[child[idx1]] = idx1;
575          invChild[child[idx2]] = idx2;
576          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
577            if (Dist(child, p2) > 0) {
578              best = bestChange;
579              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
580            }
581          }
582          options.RemoveAt(bestOption);
583        }
584      }
585      if (bestChild == null) {
586        best = eval(child, token);
587        evaluations++;
588      }
589      Context.IncrementEvaluatedSolutions(evaluations);
590      if (thisPath.Count > 5)
591        Context.RelinkedPaths.AddPath(thisPath);
592
593      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
594      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
595
596      return bestChild ?? child;
597    }
598
599    public Encodings.PermutationEncoding.Permutation DelinkSwap(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, out double best) {
600      var maximization = Context.Maximization;
601      var evaluations = 0;
602      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
603
604      best = double.NaN;
605      Encodings.PermutationEncoding.Permutation bestChild = null;
606
607      var options = Enumerable.Range(0, child.Length).Where(x => child[x] == p2[x]).ToList();
608     
609      while (options.Count > 0) {
610        int bestOption = -1;
611        int bestCompanion = -1;
612        var bestChange = double.NaN;
613        for (var j = 0; j < options.Count; j++) {
614          var idx = options[j];
615          if (child[idx] != p2[idx]) {
616            options.RemoveAt(j);
617            j--;
618            continue;
619          }
620          for (var k = 0; k < child.Length; k++) {
621            if (k == idx) continue;
622            Swap(child, k, idx);
623            var moveF = eval(child, token);
624            evaluations++;
625            if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
626              bestChange = moveF;
627              bestOption = j;
628              bestCompanion = k;
629            }
630            // undo
631            Swap(child, k, idx);
632          }
633        }
634        if (!double.IsNaN(bestChange)) {
635          var idx1 = options[bestOption];
636          Swap(child, idx1, bestCompanion);
637          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
638            if (!Eq(child, p2)) {
639              best = bestChange;
640              bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
641            }
642          }
643          options.RemoveAt(bestOption);
644        }
645      }
646      if (bestChild == null) {
647        best = eval(child, token);
648        evaluations++;
649      }
650      Context.IncrementEvaluatedSolutions(evaluations);
651
652      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Delinking produced invalid child");
653
654      return bestChild ?? child;
655    }
656
657    public Encodings.PermutationEncoding.Permutation RelinkShift(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, bool delink, out double best) {
658      var maximization = Context.Maximization;
659      var evaluations = 0;
660      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
661
662      best = double.NaN;
663      Encodings.PermutationEncoding.Permutation bestChild = null;
664
665      var invChild = new int[child.Length];
666      for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
667
668      var bestChange = double.NaN;
669      do {
670        int bestFrom = -1, bestTo = -1;
671        bestChange = double.NaN;
672        for (var j = 0; j < child.Length; j++) {
673          var c = invChild[p2[j]];
674          var n = invChild[p2.GetCircular(j + 1)];
675          if (n - c == 1 || c == child.Length - 1 && n == 0) continue;
676
677          if (c < n) Shift(child, from: n, to: c + 1);
678          else Shift(child, from: c, to: n);
679          var moveF = eval(child, token);
680          evaluations++;
681          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
682            bestChange = moveF;
683            bestFrom = c < n ? n : c;
684            bestTo = c < n ? c + 1 : n;
685          }
686          // undo
687          if (c < n) Shift(child, from: c + 1, to: n);
688          else Shift(child, from: n, to: c);
689        }
690        if (!double.IsNaN(bestChange)) {
691          Shift(child, bestFrom, bestTo);
692          for (var i = Math.Min(bestFrom, bestTo); i < Math.Max(bestFrom, bestTo); i++) invChild[child[i]] = i;
693          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
694            best = bestChange;
695            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
696          }
697        }
698      } while (!double.IsNaN(bestChange));
699
700      if (bestChild == null) {
701        best = eval(child, token);
702        evaluations++;
703      }
704      Context.IncrementEvaluatedSolutions(evaluations);
705
706      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
707      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
708
709      return bestChild ?? child;
710    }
711
712    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, out double best) {
713      var maximization = Context.Maximization;
714      var evaluations = 0;
715      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
716
717      best = double.NaN;
718      Encodings.PermutationEncoding.Permutation bestChild = null;
719
720      var invChild = new int[child.Length];
721      var invP2 = new int[child.Length];
722      for (var i = 0; i < child.Length; i++) {
723        invChild[child[i]] = i;
724        invP2[p2[i]] = i;
725      }
726
727      var bestChange = double.NaN;
728      var moveQueue = new Queue<Tuple<int, int>>();
729      var undoStack = new Stack<Tuple<int, int>>();
730      do {
731        Queue<Tuple<int, int>> bestQueue = null;
732        bestChange = double.NaN;
733        for (var j = 0; j < p2.Length; j++) {
734          if (IsUndirectedEdge(invChild, p2[j], p2.GetCircular(j + 1))) continue;
735
736          var a = invChild[p2[j]];
737          var b = invChild[p2.GetCircular(j + 1)];
738          if (a > b) { var h = a; a = b; b = h; }
739          var aprev = a - 1;
740          var bprev = b - 1;
741          while (IsUndirectedEdge(invP2, child.GetCircular(aprev), child.GetCircular(aprev + 1))) {
742            aprev--;
743          }
744          while (IsUndirectedEdge(invP2, child.GetCircular(bprev), child.GetCircular(bprev + 1))) {
745            bprev--;
746          }
747          var bnext = b + 1;
748          var anext = a + 1;
749          while (IsUndirectedEdge(invP2, child.GetCircular(bnext - 1), child.GetCircular(bnext))) {
750            bnext++;
751          }
752          while (IsUndirectedEdge(invP2, child.GetCircular(anext - 1), child.GetCircular(anext))) {
753            anext++;
754          }
755          aprev++; bprev++; anext--; bnext--;
756
757          if (aprev < a && bnext > b) {
758            if (aprev < 0) {
759              moveQueue.Enqueue(Tuple.Create(a + 1, bnext));
760              moveQueue.Enqueue(Tuple.Create(a + 1, a + 1 + (bnext - b)));
761            } else {
762              moveQueue.Enqueue(Tuple.Create(aprev, b - 1));
763              moveQueue.Enqueue(Tuple.Create(b - 1 - (a - aprev), b - 1));
764            }
765          } else if (aprev < a && bnext == b && bprev == b) {
766            moveQueue.Enqueue(Tuple.Create(a + 1, b));
767          } else if (aprev < a && bprev < b) {
768            moveQueue.Enqueue(Tuple.Create(a + 1, b));
769          } else if (aprev == a && anext == a && bnext > b) {
770            moveQueue.Enqueue(Tuple.Create(a, b - 1));
771          } else if (aprev == a && anext == a && bnext == b && bprev == b) {
772            moveQueue.Enqueue(Tuple.Create(a, b - 1));
773          } else if (aprev == a && anext == a && bprev < b) {
774            moveQueue.Enqueue(Tuple.Create(a + 1, b));
775          } else if (anext > a && bnext > b) {
776            moveQueue.Enqueue(Tuple.Create(a, b - 1));
777          } else if (anext > a && bnext == b && bprev == b) {
778            moveQueue.Enqueue(Tuple.Create(a, b - 1));
779          } else /*if (anext > a && bprev < b)*/ {
780            moveQueue.Enqueue(Tuple.Create(a, bprev - 1));
781            moveQueue.Enqueue(Tuple.Create(bprev, b));
782          }
783
784          while (moveQueue.Count > 0) {
785            var m = moveQueue.Dequeue();
786            Opt(child, m.Item1, m.Item2);
787            undoStack.Push(m);
788          }
789          var moveF = eval(child, token);
790          evaluations++;
791          if (FitnessComparer.IsBetter(maximization, moveF, bestChange)) {
792            bestChange = moveF;
793            bestQueue = new Queue<Tuple<int, int>>(undoStack.Reverse());
794          }
795          // undo
796          while (undoStack.Count > 0) {
797            var m = undoStack.Pop();
798            Opt(child, m.Item1, m.Item2);
799          }
800        }
801        if (!double.IsNaN(bestChange)) {
802          while (bestQueue.Count > 0) {
803            var m = bestQueue.Dequeue();
804            Opt(child, m.Item1, m.Item2);
805            for (var i = m.Item1; i <= m.Item2; i++) invChild[child[i]] = i;
806          }
807          if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
808            best = bestChange;
809            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
810          }
811        }
812      } while (!double.IsNaN(bestChange));
813
814      if (bestChild == null) {
815        best = eval(child, token);
816        evaluations++;
817      }
818      Context.IncrementEvaluatedSolutions(evaluations);
819     
820      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Relinking produced invalid child");
821      if (VALIDATE && Dist(child, p2) > 0) throw new InvalidOperationException("Child is not equal to p2 after relinking");
822      return bestChild ?? child;
823    }
824
825    public Encodings.PermutationEncoding.Permutation DelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, out double best) {
826      var evaluations = 0;
827      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
828
829      best = double.NaN;
830      Encodings.PermutationEncoding.Permutation bestChild = null;
831
832      var invChild = new int[child.Length];
833      var invP2 = new int[child.Length];
834      for (var i = 0; i < child.Length; i++) {
835        invChild[child[i]] = i;
836        invP2[p2[i]] = i;
837      }
838
839      var order = Enumerable.Range(0, p2.Length).Where(x => IsUndirectedEdge(invP2, child[x], child.GetCircular(x + 1))).Shuffle(Context.Random).ToList();
840      while (order.Count > 0) {
841        var idx = order.First();
842        var bestChange = double.NaN;
843        var bestIdx = -1;
844        for (var m = 0; m < p2.Length; m++) {
845          if (Math.Abs(m - idx) <= 1 || Math.Abs(m - idx) >= p2.Length - 2) continue;
846          if (m < idx) {
847            if (IsUndirectedEdge(invP2, child.GetCircular(m - 1), child[idx])
848              || IsUndirectedEdge(invP2, child[m], child.GetCircular(idx + 1))) continue;
849            Opt(child, m, idx);
850            var moveF = eval(child, token);
851            evaluations++;
852            if (Context.IsBetter(moveF, bestChange)) {
853              bestChange = moveF;
854              bestIdx = m;
855            }
856            // undo
857            Opt(child, m, idx);
858          } else {
859            if (IsUndirectedEdge(invP2, child[idx], child[m])
860              || IsUndirectedEdge(invP2, child.GetCircular(idx + 1), child.GetCircular(m + 1))) continue;
861            Opt(child, idx + 1, m);
862            var moveF = eval(child, token);
863            evaluations++;
864            if (Context.IsBetter(moveF, bestChange)) {
865              bestChange = moveF;
866              bestIdx = m;
867            }
868            // undo
869            Opt(child, idx + 1, m);
870          }
871        }
872        if (bestIdx >= 0) {
873          if (bestIdx > idx)
874            Opt(child, idx + 1, bestIdx);
875          else Opt(child, bestIdx, idx);
876          for (var i = Math.Min(idx, bestIdx); i <= Math.Max(idx, bestIdx); i++)
877            invChild[child[i]] = i;
878
879          order = Enumerable.Range(0, p2.Length).Where(x => IsUndirectedEdge(invP2, child[x], child.GetCircular(x + 1))).Shuffle(Context.Random).ToList();
880          if (Context.IsBetter(bestChange, best)) {
881            best = bestChange;
882            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
883          }
884        }
885      }
886
887      if (bestChild == null) {
888        best = eval(child, token);
889        evaluations++;
890      }
891      Context.IncrementEvaluatedSolutions(evaluations);
892
893      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Delinking produced invalid child");
894      if (VALIDATE && Dist(child, p2) < 1) throw new InvalidOperationException("Child is not different from p2 after delinking");
895      return bestChild ?? child;
896    }
897
898    private static bool IsUndirectedEdge(int[] invP, int a, int b) {
899      var d = Math.Abs(invP[a] - invP[b]);
900      return d == 1 || d == invP.Length - 1;
901    }
902
903    private static void Swap(Encodings.PermutationEncoding.Permutation child, int from, int to) {
904      Swap2Manipulator.Apply(child, from, to);
905    }
906
907    private static void Shift(Encodings.PermutationEncoding.Permutation child, int from, int to) {
908      TranslocationManipulator.Apply(child, from, from, to);
909    }
910
911    [MethodImpl(MethodImplOptions.AggressiveInlining)]
912    private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
913      if (from > to) child.Reverse(to, from - to + 1);
914      else child.Reverse(from, to - from + 1);
915    }
916  }
917}
Note: See TracBrowser for help on using the repository browser.