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

Last change on this file since 14477 was 14477, checked in by abeham, 3 years ago

#2701:

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