Changeset 14556

Timestamp:

01/11/17 01:53:44 (7 years ago)

Author:

abeham

Message:

#2701:

• fixed bug with breeding
• fixed permutation sub-space hillclimber
• improved speed of inversion by calling Array.Reverse(int, int) instead of using a for-loop
• added delinking for relative-undirected permutations

Location:

branches/MemPRAlgorithm

Files:

• HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs (modified) (1 diff)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs (modified) (15 diffs)
• HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InversionManipulator.cs (modified) (1 diff)
• HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs (modified) (1 diff)

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Binary/BinaryMemPR.cs

@@ -160 +160 @@
       while (evaluations < N) {
         BinaryVector c = null;
-        var xochoice = Context.Random.Next(3);
-        switch (xochoice) {
-          case 0: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(1)); break;
-          case 1: c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(2)); break;
-          case 2: c = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution); break;
-        }
+        var xochoice = Context.Random.NextDouble();
+        if (xochoice < 0.2)
+          c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(1));
+        else if (xochoice < 0.5)
+          c = NPointCrossover.Apply(Context.Random, p1.Solution, p2.Solution, new IntValue(2));
+        else c = UniformCrossover.Apply(Context.Random, p1.Solution, p2.Solution);
         if (cache.Contains(c)) {
           cacheHits++;
-          if (cacheHits > 10) break;
+          if (cacheHits > 20) break;
           continue;
         }
+        probe.Solution = c;
         Context.Evaluate(probe, token);
         evaluations++;

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/LinearLinkage/LinearLinkageMemPR.cs

@@ -260 +260 @@
           continue;
         }
+        probe.Solution = c;
         Context.Evaluate(probe, token);
         evaluations++;

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/MemPRAlgorithm.cs

@@ -43 +43 @@
       where TPopulationContext : MemPRPopulationContext<TProblem, TSolution, TPopulationContext, TSolutionContext>, new()
       where TSolutionContext : MemPRSolutionContext<TProblem, TSolution, TPopulationContext, TSolutionContext> {
-    private const double MutationProbabilityMagicConst = 0.1;
 
     public override Type ProblemType {

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/ExhaustiveHillClimbSubspace.cs

@@ -33 +33 @@
   [StorableClass]
   public class ExhaustiveHillClimbSubspace<TContext> : NamedItem, ILocalSearch<TContext>
-      where TContext : ISingleSolutionHeuristicAlgorithmContext<SingleObjectiveBasicProblem<PermutationEncoding>, Encodings.PermutationEncoding.Permutation>,
+      where TContext : ISingleSolutionHeuristicAlgorithmContext<ISingleObjectiveHeuristicOptimizationProblem, Encodings.PermutationEncoding.Permutation>,
                        IPermutationSubspaceContext, IEvaluationServiceContext<Encodings.PermutationEncoding.Permutation> {
 
@@ -52 +52 @@
       try {
         var result = Exhaustive.HillClimb(context.Random, context.Solution.Solution, ref quality,
-          context.Problem.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace);
+          context.Maximization, context.Evaluate, CancellationToken.None, context.Subspace.Subspace);
         context.IncrementEvaluatedSolutions(result.Item1);
         context.Iterations = result.Item2;

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/LocalSearch/StaticAPI/Exhaustive2Opt.cs

@@ -55 +55 @@
             continue;
 
-          InversionManipulator.Apply(current, opt.Index1, opt.Index2);
+          current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
           var q = eval(current, token);
           evaluations++;
@@ -62 +62 @@
             quality = q;
             lastSuccessMove = opt;
-          } else InversionManipulator.Apply(current, opt.Index1, opt.Index2);
+          } else current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
 
           if (token.IsCancellationRequested) {

branches/MemPRAlgorithm/HeuristicLab.Algorithms.MemPR/3.3/Permutation/PermutationMemPR.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Runtime.CompilerServices;
 using System.Threading;
 using HeuristicLab.Algorithms.MemPR.Interfaces;
@@ -297 +298 @@
             continue;
 
-          InversionManipulator.Apply(current, opt.Index1, opt.Index2);
+          current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
 
           var q = eval(current, token);
@@ -338 +339 @@
               bestOfTheRestF = q;
             }
-
-            InversionManipulator.Apply(current, opt.Index1, opt.Index2);
+            
+            current.Reverse(opt.Index1, opt.Index2 - opt.Index1 + 1);
           }
           if (evaluations >= maxEvals) break;
@@ -359 +360 @@
             tabu[current[next], current[bestOfTheRest.Index2]] = Math.Min(currentF, tabu[current[next], current[bestOfTheRest.Index2]]);
           }
-          InversionManipulator.Apply(current, bestOfTheRest.Index1, bestOfTheRest.Index2);
+          current.Reverse(bestOfTheRest.Index1, bestOfTheRest.Index2 - bestOfTheRest.Index1 + 1);
 
           currentF = bestOfTheRestF;
@@ -397 +398 @@
       var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
+      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
       while (evaluations < p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
@@ -410 +412 @@
           continue;
         }
-        var probe = Context.ToScope(c);
+        probe.Solution = c;
         Context.Evaluate(probe, token);
         evaluations++;
@@ -432 +434 @@
       var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
-      while(evaluations < p1.Solution.Length) {
+      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
+      while (evaluations < p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
         var xochoice = Context.Random.Next(3);
@@ -445 +448 @@
           continue;
         }
-        var probe = Context.ToScope(c);
+        probe.Solution = c;
         Context.Evaluate(probe, token);
         evaluations++;
@@ -467 +470 @@
       var evaluations = 0;
       ISingleObjectiveSolutionScope<Encodings.PermutationEncoding.Permutation> offspring = null;
-      while(evaluations <= p1.Solution.Length) {
+      var probe = Context.ToScope((Encodings.PermutationEncoding.Permutation)p1.Solution.Clone());
+      while (evaluations <= p1.Solution.Length) {
         Encodings.PermutationEncoding.Permutation c = null;
         var xochoice = Context.Random.Next(3);
@@ -480 +484 @@
           continue;
         }
-        var probe = Context.ToScope(c);
+        probe.Solution = c;
         Context.Evaluate(probe, token);
         evaluations++;
@@ -507 +511 @@
           return RelinkShift(random, p1, p2, eval, token, delink, out best);
         case PermutationTypes.RelativeUndirected:
-          return RelinkOpt(random, p1, p2, eval, token, delink, out best);
+          return delink ? DelinkOpt(random, p1, p2, eval, token, out best) : RelinkOpt(random, p1, p2, eval, token, out best);
         default: throw new ArgumentException(string.Format("Unknown permutation type {0}", p1.PermutationType));
       }
@@ -684 +688 @@
     }
 
-    public Encodings.PermutationEncoding.Permutation RelinkOpt(IRandom random, Encodings.PermutationEncoding.Permutation p1, Encodings.PermutationEncoding.Permutation p2, Func<Encodings.PermutationEncoding.Permutation, CancellationToken, double> eval, CancellationToken token, bool delink, out double best) {
+    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) {
       var maximization = Context.Maximization;
       var evaluations = 0;
@@ -777 +781 @@
             var m = bestQueue.Dequeue();
             Opt(child, m.Item1, m.Item2);
-          }
-          for (var i = 0; i < child.Length; i++) invChild[child[i]] = i;
+            for (var i = m.Item1; i <= m.Item2; i++) invChild[child[i]] = i;
+          }
           if (FitnessComparer.IsBetter(maximization, bestChange, best)) {
             best = bestChange;
@@ -797 +801 @@
     }
 
+    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) {
+      var evaluations = 0;
+      var child = (Encodings.PermutationEncoding.Permutation)p1.Clone();
+
+      best = double.NaN;
+      Encodings.PermutationEncoding.Permutation bestChild = null;
+
+      var invChild = new int[child.Length];
+      var invP2 = new int[child.Length];
+      for (var i = 0; i < child.Length; i++) {
+        invChild[child[i]] = i;
+        invP2[p2[i]] = i;
+      }
+
+      var order = Enumerable.Range(0, p2.Length).Where(x => IsUndirectedEdge(invP2, child[x], child.GetCircular(x + 1))).Shuffle(Context.Random).ToList();
+      while (order.Count > 0) {
+        var idx = order.First();
+        var bestChange = double.NaN;
+        var bestIdx = -1;
+        for (var m = 0; m < p2.Length; m++) {
+          if (Math.Abs(m - idx) <= 1 || Math.Abs(m - idx) >= p2.Length - 2) continue;
+          if (m < idx) {
+            if (IsUndirectedEdge(invP2, child.GetCircular(m - 1), child[idx])
+              || IsUndirectedEdge(invP2, child[m], child.GetCircular(idx + 1))) continue;
+            Opt(child, m, idx);
+            var moveF = eval(child, token);
+            evaluations++;
+            if (Context.IsBetter(moveF, bestChange)) {
+              bestChange = moveF;
+              bestIdx = m;
+            }
+            // undo
+            Opt(child, m, idx);
+          } else {
+            if (IsUndirectedEdge(invP2, child[idx], child[m])
+              || IsUndirectedEdge(invP2, child.GetCircular(idx + 1), child.GetCircular(m + 1))) continue;
+            Opt(child, idx + 1, m);
+            var moveF = eval(child, token);
+            evaluations++;
+            if (Context.IsBetter(moveF, bestChange)) {
+              bestChange = moveF;
+              bestIdx = m;
+            }
+            // undo
+            Opt(child, idx + 1, m);
+          }
+        }
+        if (bestIdx >= 0) {
+          if (bestIdx > idx)
+            Opt(child, idx + 1, bestIdx);
+          else Opt(child, bestIdx, idx);
+          for (var i = Math.Min(idx, bestIdx); i <= Math.Max(idx, bestIdx); i++)
+            invChild[child[i]] = i;
+
+          order = Enumerable.Range(0, p2.Length).Where(x => IsUndirectedEdge(invP2, child[x], child.GetCircular(x + 1))).Shuffle(Context.Random).ToList();
+          if (Context.IsBetter(bestChange, best)) {
+            best = bestChange;
+            bestChild = (Encodings.PermutationEncoding.Permutation)child.Clone();
+          }
+        }
+      }
+
+      if (bestChild == null) {
+        best = eval(child, token);
+        evaluations++;
+      }
+      Context.IncrementEvaluatedSolutions(evaluations);
+
+      if (VALIDATE && bestChild != null && !bestChild.Validate()) throw new ArgumentException("Delinking produced invalid child");
+      if (VALIDATE && Dist(child, p2) < 1) throw new InvalidOperationException("Child is not different from p2 after delinking");
+      return bestChild ?? child;
+    }
+
     private static bool IsUndirectedEdge(int[] invP, int a, int b) {
       var d = Math.Abs(invP[a] - invP[b]);
@@ -810 +887 @@
     }
 
+    [MethodImpl(MethodImplOptions.AggressiveInlining)]
     private static void Opt(Encodings.PermutationEncoding.Permutation child, int from, int to) {
-      if (from > to) {
-        var h = from;
-        from = to;
-        to = h;
-      }
-      InversionManipulator.Apply(child, from, to);
+      if (from > to) child.Reverse(to, from - to + 1);
+      else child.Reverse(from, to - from + 1);
     }
   }

branches/MemPRAlgorithm/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InversionManipulator.cs

@@ -60 +60 @@
 
     public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2) {
-      for (int i = 0; i <= (breakPoint2 - breakPoint1) / 2; i++) {  // invert permutation between breakpoints
-        int temp = permutation[breakPoint1 + i];
-        permutation[breakPoint1 + i] = permutation[breakPoint2 - i];
-        permutation[breakPoint2 - i] = temp;
-      }
+      permutation.Reverse(breakPoint1, breakPoint2 - breakPoint1 + 1);
     }
 

branches/MemPRAlgorithm/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs

@@ -121 +121 @@
     }
 
+    public virtual void Reverse(int startIndex, int length) {
+      Array.Reverse(array, startIndex, length);
+    }
+
     public event EventHandler PermutationTypeChanged;