Changeset 3221 for trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt

Timestamp:

03/26/10 00:04:24 (15 years ago)

Author:

abeham

Message:

updated permutation moves, fixed 3-opt #889

Location:

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt

Files:

• ExhaustiveTwoOptMoveGenerator.cs (modified) (2 diffs)
• PreventDeleteTwoOptTabuMoveEvaluator.cs (added)
• PreventReaddDeleteTwoOptTabuMoveEvaluator.cs (modified) (3 diffs)
• PreventReaddTwoOptTabuMoveEvaluator.cs (modified) (3 diffs)
• StochasticTwoOptMultiMoveGenerator.cs (modified) (3 diffs)
• StochasticTwoOptSingleMoveGenerator.cs (modified) (2 diffs)
• TwoOptMoveGenerator.cs (modified) (2 diffs)
• TwoOptMoveMaker.cs (modified) (2 diffs)
• TwoOptTabuMoveMaker.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/ExhaustiveTwoOptMoveGenerator.cs

@@ -26 +26 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("ExhaustiveTwoOptMoveGenerator", "Generates all possible 2-opt moves from a given permutation.")]
+  [Item("ExhaustiveTwoOptMoveGenerator", "Generates all possible 2-opt moves (inversion) from a given permutation.")]
   [StorableClass]
   public class ExhaustiveTwoOptMoveGenerator : TwoOptMoveGenerator, IExhaustiveMoveGenerator {
     public static TwoOptMove[] Apply(Permutation permutation) {
       int length = permutation.Length;
-      int totalMoves = (length) * (length - 1) / 2 - 3;
+      int totalMoves = (length) * (length - 1) / 2; // - 3;
       TwoOptMove[] moves = new TwoOptMove[totalMoves];
       int count = 0;
@@ -37 +37 @@
         for (int j = i + 1; j < length; j++) {
           // doesn't make sense to inverse the whole permutation or the whole but one
-          if (i == 0 && j >= length - 2) continue;
-          else if (i == 1 && j >= length - 1) continue;
+          /*if (i == 0 && j >= length - 2) continue;
+          else if (i == 1 && j >= length - 1) continue;*/
           moves[count++] = new TwoOptMove(i, j);
         }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddDeleteTwoOptTabuMoveEvaluator.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventReaddDeleteTwoOptTabuMoveEvaluator", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
+  [Item("TwoOptPreventEdgeRemovalAndReadding", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
   [StorableClass]
   public class PreventReaddDeleteTwoOptTabuMoveEvaluator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, ITabuMoveEvaluator {
+    public override bool CanChangeName {
+      get { return false; }
+    }
     public ILookupParameter<TwoOptMove> TwoOptMoveParameter {
       get { return (LookupParameter<TwoOptMove>)Parameters["TwoOptMove"]; }
@@ -66 +69 @@
       int E2S = permutation[move.Index2];
       int E2T = permutation.GetCircular(move.Index2 + 1);
-      bool isTabu = false;
-      foreach (IItem tabuMove in tabuList) {
-        TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
-        if (attribute != null) {
-          // if previously deleted Edge1Source-Target is readded
-          if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
-            || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
-            // if previously deleted Edge2Source-Target is readded
-            || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
-            || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S
-            // if previously added Edge1Source-Edge2Source is deleted
-            || attribute.Edge1Source == E1S && attribute.Edge2Source == E1T || attribute.Edge1Source == E1T && attribute.Edge2Source == E1S
-            || attribute.Edge1Source == E2S && attribute.Edge2Source == E2T || attribute.Edge1Source == E2T && attribute.Edge2Source == E2S
-            // if previously added Edge1Target-Edge2Target is deleted
-            || attribute.Edge1Target == E2S && attribute.Edge2Target == E2T || attribute.Edge1Target == E2T && attribute.Edge2Target == E2S
-            || attribute.Edge1Target == E1S && attribute.Edge2Target == E1T || attribute.Edge1Target == E1T && attribute.Edge2Target == E1S) {
-            isTabu = true;
-            break;
+      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
+      if (!isTabu) {
+        foreach (IItem tabuMove in tabuList) {
+          TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
+          if (attribute != null) {
+            // if previously deleted Edge1Source-Target is readded
+            if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
+              || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
+              // if previously deleted Edge2Source-Target is readded
+              || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
+              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S
+              // if previously added Edge1Source-Edge2Source is deleted
+              || attribute.Edge1Source == E1S && attribute.Edge2Source == E1T || attribute.Edge1Source == E1T && attribute.Edge2Source == E1S
+              || attribute.Edge1Source == E2S && attribute.Edge2Source == E2T || attribute.Edge1Source == E2T && attribute.Edge2Source == E2S
+              // if previously added Edge1Target-Edge2Target is deleted
+              || attribute.Edge1Target == E2S && attribute.Edge2Target == E2T || attribute.Edge1Target == E2T && attribute.Edge2Target == E2S
+              || attribute.Edge1Target == E1S && attribute.Edge2Target == E1T || attribute.Edge1Target == E1T && attribute.Edge2Target == E1S) {
+              isTabu = true;
+              break;
+            }
           }
         }
@@ -90 +95 @@
       return base.Apply();
     }
-
-    public override bool CanChangeName {
-      get { return false; }
-    }
   }
 }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddTwoOptTabuMoveEvaluator.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventReaddTwoOptTabuMoveEvaluator", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
+  [Item("TwoOptPreventEdgeReadding", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
   [StorableClass]
   public class PreventReaddTwoOptTabuMoveEvaluator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, ITabuMoveEvaluator {
+    public override bool CanChangeName {
+      get { return false; }
+    }
     public ILookupParameter<TwoOptMove> TwoOptMoveParameter {
       get { return (LookupParameter<TwoOptMove>)Parameters["TwoOptMove"]; }
@@ -66 +69 @@
       int E2S = permutation[move.Index2];
       int E2T = permutation.GetCircular(move.Index2 + 1);
-      bool isTabu = false;
-      foreach (IItem tabuMove in tabuList) {
-        TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
-        if (attribute != null) {
-          // if previously deleted Edge1Source-Target is readded
-          if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
-            || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
-            // if previously deleted Edge2Source-Target is readded
-            || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
-            || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S) {
-            isTabu = true;
-            break;
+      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
+      if (!isTabu) {
+        foreach (IItem tabuMove in tabuList) {
+          TwoOptTabuMoveAttribute attribute = (tabuMove as TwoOptTabuMoveAttribute);
+          if (attribute != null) {
+            // if previously deleted Edge1Source-Target is readded
+            if (attribute.Edge1Source == E1S && attribute.Edge1Target == E2S || attribute.Edge1Source == E2S && attribute.Edge1Target == E1S
+              || attribute.Edge1Source == E1T && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1T
+              // if previously deleted Edge2Source-Target is readded
+              || attribute.Edge2Source == E1T && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1T
+              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2S || attribute.Edge2Source == E2S && attribute.Edge2Target == E1S) {
+              isTabu = true;
+              break;
+            }
           }
         }
@@ -84 +89 @@
       return base.Apply();
     }
-
-    public override bool CanChangeName {
-      get { return false; }
-    }
   }
 }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptMultiMoveGenerator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("StochasticTwoOptMultiMoveGenerator", "Randomly samples n from all possible 2-opt moves from a given permutation.")]
+  [Item("StochasticTwoOptMultiMoveGenerator", "Randomly samples n from all possible 2-opt moves (inversion) from a given permutation.")]
   [StorableClass]
-  public class StochasticTwoOptMultiMoveGenerator : StochasticTwoOptSingleMoveGenerator, IMultiMoveGenerator {
+  public class StochasticTwoOptMultiMoveGenerator : TwoOptMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
     public IValueLookupParameter<IntValue> SampleSizeParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
@@ -42 +45 @@
     public StochasticTwoOptMultiMoveGenerator()
       : base() {
+      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
       Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "The number of moves to generate."));
     }
@@ -49 +53 @@
       TwoOptMove[] moves = new TwoOptMove[sampleSize];
       for (int i = 0; i < sampleSize; i++) {
-        moves[i] = Apply(permutation, random);
+        moves[i] = StochasticTwoOptSingleMoveGenerator.Apply(permutation, random);
       }
       return moves;

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/StochasticTwoOptSingleMoveGenerator.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("StochasticTwoOptSingleMoveGenerator", "Randomly samples a single from all possible 2-opt moves from a given permutation.")]
+  [Item("StochasticTwoOptSingleMoveGenerator", "Randomly samples a single from all possible 2-opt moves (inversion) from a given permutation.")]
   [StorableClass]
   public class StochasticTwoOptSingleMoveGenerator : TwoOptMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
@@ -42 +42 @@
     public static TwoOptMove Apply(Permutation permutation, IRandom random) {
       int length = permutation.Length;
-      int index1 = random.Next(length - 1), index2;
-      if (index1 >= 2)
-        index2 = random.Next(index1 + 1, length);
-      else index2 = random.Next(index1 + 1, length - (2 - index1));
+      int index1 = random.Next(length - 1);
+      int index2 = random.Next(index1 + 1, length);
       return new TwoOptMove(index1, index2);;
     }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptMoveGenerator.cs

@@ -31 +31 @@
   [StorableClass]
   public abstract class TwoOptMoveGenerator : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, IMoveGenerator {
+    public override bool CanChangeName {
+      get { return false; }
+    }
     public ILookupParameter<Permutation> PermutationParameter {
       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
@@ -61 +64 @@
 
     protected abstract TwoOptMove[] GenerateMoves(Permutation permutation);
-
-    public override bool CanChangeName {
-      get { return false; }
-    }
   }
 }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptMoveMaker.cs

@@ -32 +32 @@
   [StorableClass]
   public class TwoOptMoveMaker : SingleSuccessorOperator, ITwoOptPermutationMoveOperator, IMoveMaker {
+    public override bool CanChangeName {
+      get { return false; }
+    }
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
@@ -64 +67 @@
       return base.Apply();
     }
-
-    public override bool CanChangeName {
-      get { return false; }
-    }
   }
 }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/TwoOptTabuMoveMaker.cs

@@ -32 +32 @@
   [StorableClass]
   public class TwoOptTabuMoveMaker : TabuMoveMaker, ITwoOptPermutationMoveOperator {
+    public override bool CanChangeName {
+      get { return false; }
+    }
     public ILookupParameter<Permutation> PermutationParameter {
       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
@@ -53 +56 @@
         permutation.GetCircular(move.Index2 + 1));
     }
-
-    public override bool CanChangeName {
-      get { return false; }
-    }
   }
 }