Changeset 3233

Timestamp:

03/30/10 14:52:30 (15 years ago)

Author:

abeham

Message:

Updated inversion moves to respect different types of permutation #889

Location:

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3

Files:

• HeuristicLab.Encodings.PermutationEncoding-3.3.csproj (modified) (1 diff)
• Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs (modified) (1 diff)
• Moves/TwoOpt/InversionMoveAbsoluteAttribute.cs (added)
• Moves/TwoOpt/InversionMoveAttribute.cs (deleted)
• Moves/TwoOpt/InversionMoveRelativeAttribute.cs (added)
• Moves/TwoOpt/InversionMoveTabuMaker.cs (modified) (1 diff)
• Moves/TwoOpt/PreventReaddAndRemovalInversionMoveTabuChecker.cs (modified) (1 diff)
• Moves/TwoOpt/PreventReaddInversionMoveTabuChecker.cs (modified) (1 diff)
• Moves/TwoOpt/PreventRemovalInversionMoveTabuChecker.cs (modified) (1 diff)
• Moves/TwoOpt/StochasticInversionSingleMoveGenerator.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/HeuristicLab.Encodings.PermutationEncoding-3.3.csproj

@@ -124 +124 @@
       <SubType>Code</SubType>
     </Compile>
+    <Compile Include="Moves\TwoOpt\InversionMoveAbsoluteAttribute.cs" />
     <Compile Include="Moves\TwoOpt\ExhaustiveInversionMoveGenerator.cs" />
     <Compile Include="Moves\TwoOpt\InversionMove.cs" />
-    <Compile Include="Moves\TwoOpt\InversionMoveAttribute.cs" />
+    <Compile Include="Moves\TwoOpt\InversionMoveRelativeAttribute.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveGenerator.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveMaker.cs" />

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

@@ -34 +34 @@
       InversionMove[] moves = new InversionMove[totalMoves];
       int count = 0;
-      for (int i = 0; i < length - 1; i++)
-        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;*/
-          moves[count++] = new InversionMove(i, j);
+
+      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
+        for (int i = 0; i < length - 1; i++) {
+          for (int j = i + 1; j < length; j++) {
+            // doesn't make sense to inverse the whole permutation or the whole but one in case of relative undirected permutations
+            if (j - i >= length - 2) continue;
+            moves[count++] = new InversionMove(i, j);
+          }
         }
+      } else {
+          for (int i = 0; i < length - 1; i++)
+            for (int j = i + 1; j < length; j++) {
+              moves[count++] = new InversionMove(i, j);
+            }
+      }
       return moves;
     }

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

@@ -51 +51 @@
       InversionMove move = InversionMoveParameter.ActualValue;
       Permutation permutation = PermutationParameter.ActualValue;
-      return new InversionMoveAttribute( permutation.GetCircular(move.Index1 - 1),
-        permutation[move.Index1],
-        permutation[move.Index2],
-        permutation.GetCircular(move.Index2 + 1));
+      if (permutation.PermutationType == PermutationTypes.Absolute)
+        return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2]);
+      else
+        return new InversionMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
+          permutation[move.Index1],
+          permutation[move.Index2],
+          permutation.GetCircular(move.Index2 + 1));
     }
   }

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

@@ -65 +65 @@
       Permutation permutation = PermutationParameter.ActualValue;
       int length = permutation.Length;
-      int E1S = permutation.GetCircular(move.Index1 - 1);
-      int E1T = permutation[move.Index1];
-      int E2S = permutation[move.Index2];
-      int E2T = permutation.GetCircular(move.Index2 + 1);
-      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
-      if (!isTabu) {
-        foreach (IItem tabuMove in tabuList) {
-          InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
-          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 = false;
+      foreach (IItem tabuMove in tabuList) {
+        switch (permutation.PermutationType) {
+          case PermutationTypes.RelativeUndirected: {
+            int E1S = permutation.GetCircular(move.Index1 - 1);
+            int E1T = permutation[move.Index1];
+            int E2S = permutation[move.Index2];
+            int E2T = permutation.GetCircular(move.Index2 + 1);
+            InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+            if (relAttrib != null) {
+              // if previously deleted Edge1Source-Target is readded
+              if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S || relAttrib.Edge1Source == E2S && relAttrib.Edge1Target == E1S
+                || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge1Target == E1T
+                // if previously deleted Edge2Source-Target is readded
+                || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T || relAttrib.Edge2Source == E2T && relAttrib.Edge2Target == E1T
+                || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S || relAttrib.Edge2Source == E2S && relAttrib.Edge2Target == E1S
+                // if previously added Edge1Source-Edge2Source is deleted
+                || relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T || relAttrib.Edge1Source == E1T && relAttrib.Edge2Source == E1S
+                || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge2Source == E2S
+                // if previously added Edge1Target-Edge2Target is deleted
+                || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T || relAttrib.Edge1Target == E2T && relAttrib.Edge2Target == E2S
+                || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T || relAttrib.Edge1Target == E1T && relAttrib.Edge2Target == E1S) {
+                isTabu = true;
+              }
             }
           }
+          break;
+          case PermutationTypes.RelativeDirected: {
+            int E1S = permutation.GetCircular(move.Index1 - 1);
+            int E1T = permutation[move.Index1];
+            int E2S = permutation[move.Index2];
+            int E2T = permutation.GetCircular(move.Index2 + 1);
+            InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+            if (relAttrib != null) {
+              if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S
+                || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T
+                // if previously deleted Edge2Source-Target is readded
+                || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T
+                || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S
+                // if previously added Edge1Source-Edge2Source is deleted
+                || relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T
+                || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T
+                // if previously added Edge1Target-Edge2Target is deleted
+                || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T
+                || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T) {
+                isTabu = true;
+              }
+            }
+          }
+          break;
+          case PermutationTypes.Absolute: {
+            int i1 = move.Index1;
+            int n1 = permutation[move.Index1];
+            int i2 = move.Index2;
+            int n2 = permutation[move.Index2];
+            InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
+            if (absAttrib != null) {
+              if (absAttrib.Number1 == n1 || absAttrib.Number1 == n2
+                || absAttrib.Number2 == n2 || absAttrib.Number2 == n1)
+                isTabu = true;
+              
+            }
+          }
+          break;
+          default: {
+            throw new InvalidOperationException(Name + ": Unknown permutation type.");
+          }
         }
+        if (isTabu) break;
       }
       MoveTabuParameter.ActualValue = new BoolValue(isTabu);

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

@@ -65 +65 @@
       Permutation permutation = PermutationParameter.ActualValue;
       int length = permutation.Length;
-      int E1S = permutation.GetCircular(move.Index1 - 1);
-      int E1T = permutation[move.Index1];
-      int E2S = permutation[move.Index2];
-      int E2T = permutation.GetCircular(move.Index2 + 1);
-      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution;
-      if (!isTabu) {
-        foreach (IItem tabuMove in tabuList) {
-          InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
-          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 = false;
+      foreach (IItem tabuMove in tabuList) {
+        switch (permutation.PermutationType) {
+          case PermutationTypes.RelativeUndirected: {
+              int E1S = permutation.GetCircular(move.Index1 - 1);
+              int E1T = permutation[move.Index1];
+              int E2S = permutation[move.Index2];
+              int E2T = permutation.GetCircular(move.Index2 + 1);
+              InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+              if (relAttrib != null) {
+                // if previously deleted Edge1Source-Target is readded
+                if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S || relAttrib.Edge1Source == E2S && relAttrib.Edge1Target == E1S
+                  || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge1Target == E1T
+                  // if previously deleted Edge2Source-Target is readded
+                  || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T || relAttrib.Edge2Source == E2T && relAttrib.Edge2Target == E1T
+                  || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S || relAttrib.Edge2Source == E2S && relAttrib.Edge2Target == E1S) {
+                  isTabu = true;
+                }
+              }
             }
-          }
+            break;
+          case PermutationTypes.RelativeDirected: {
+              int E1S = permutation.GetCircular(move.Index1 - 1);
+              int E1T = permutation[move.Index1];
+              int E2S = permutation[move.Index2];
+              int E2T = permutation.GetCircular(move.Index2 + 1);
+              InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+              if (relAttrib != null) {
+                if (relAttrib.Edge1Source == E1S && relAttrib.Edge1Target == E2S
+                  || relAttrib.Edge1Source == E1T && relAttrib.Edge1Target == E2T
+                  // if previously deleted Edge2Source-Target is readded
+                  || relAttrib.Edge2Source == E1T && relAttrib.Edge2Target == E2T
+                  || relAttrib.Edge2Source == E1S && relAttrib.Edge2Target == E2S) {
+                  isTabu = true;
+                }
+              }
+            }
+            break;
+          case PermutationTypes.Absolute: {
+              int i1 = move.Index1;
+              int n1 = permutation[move.Index1];
+              int i2 = move.Index2;
+              int n2 = permutation[move.Index2];
+              InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
+              if (absAttrib != null) {
+                if ((absAttrib.Index1 == i1 || absAttrib.Index1 == i2) && (absAttrib.Number1 == n1 || absAttrib.Number1 == n2)
+                  || (absAttrib.Index2 == i2 || absAttrib.Index2 == i1) && (absAttrib.Number2 == n2 || absAttrib.Number2 == n1))
+                  isTabu = true;
+
+              }
+            }
+            break;
+          default: {
+              throw new InvalidOperationException(Name + ": Unknown permutation type.");
+            }
         }
+        if (isTabu) break;
       }
       MoveTabuParameter.ActualValue = new BoolValue(isTabu);

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

@@ -65 +65 @@
       Permutation permutation = PermutationParameter.ActualValue;
       int length = permutation.Length;
-      int E1S = permutation.GetCircular(move.Index1 - 1);
-      int E1T = permutation[move.Index1];
-      int E2S = permutation[move.Index2];
-      int E2T = permutation.GetCircular(move.Index2 + 1);
-      bool isTabu = (move.Index2 - move.Index1 >= length - 2); // doesn't change the solution
-      if (!isTabu) {
-        foreach (IItem tabuMove in tabuList) {
-          InversionMoveAttribute attribute = (tabuMove as InversionMoveAttribute);
-          if (attribute != null) {
-            // if previously added Edge1Source-Edge2Source is deleted
-            if (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 = false;
+      foreach (IItem tabuMove in tabuList) {
+        switch (permutation.PermutationType) {
+          case PermutationTypes.RelativeUndirected: {
+              int E1S = permutation.GetCircular(move.Index1 - 1);
+              int E1T = permutation[move.Index1];
+              int E2S = permutation[move.Index2];
+              int E2T = permutation.GetCircular(move.Index2 + 1);
+              InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+              if (relAttrib != null) {
+                if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T || relAttrib.Edge1Source == E1T && relAttrib.Edge2Source == E1S
+                  || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T || relAttrib.Edge1Source == E2T && relAttrib.Edge2Source == E2S
+                  // if previously added Edge1Target-Edge2Target is deleted
+                  || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T || relAttrib.Edge1Target == E2T && relAttrib.Edge2Target == E2S
+                  || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T || relAttrib.Edge1Target == E1T && relAttrib.Edge2Target == E1S) {
+                  isTabu = true;
+                }
+              }
             }
-          }
+            break;
+          case PermutationTypes.RelativeDirected: {
+              int E1S = permutation.GetCircular(move.Index1 - 1);
+              int E1T = permutation[move.Index1];
+              int E2S = permutation[move.Index2];
+              int E2T = permutation.GetCircular(move.Index2 + 1);
+              InversionMoveRelativeAttribute relAttrib = (tabuMove as InversionMoveRelativeAttribute);
+              if (relAttrib != null) {
+                if (relAttrib.Edge1Source == E1S && relAttrib.Edge2Source == E1T
+                  || relAttrib.Edge1Source == E2S && relAttrib.Edge2Source == E2T
+                  // if previously added Edge1Target-Edge2Target is deleted
+                  || relAttrib.Edge1Target == E2S && relAttrib.Edge2Target == E2T
+                  || relAttrib.Edge1Target == E1S && relAttrib.Edge2Target == E1T) {
+                  isTabu = true;
+                }
+              }
+            }
+            break;
+          case PermutationTypes.Absolute: {
+              int i1 = move.Index1;
+              int n1 = permutation[move.Index1];
+              int i2 = move.Index2;
+              int n2 = permutation[move.Index2];
+              InversionMoveAbsoluteAttribute absAttrib = (tabuMove as InversionMoveAbsoluteAttribute);
+              if (absAttrib != null) {
+                if (absAttrib.Number1 == n1 || absAttrib.Number1 == n2
+                  || absAttrib.Number2 == n2 || absAttrib.Number2 == n1)
+                  isTabu = true;
+
+              }
+            }
+            break;
+          default: {
+              throw new InvalidOperationException(Name + ": Unknown permutation type.");
+            }
         }
+        if (isTabu) break;
       }
       MoveTabuParameter.ActualValue = new BoolValue(isTabu);

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

@@ -44 +44 @@
       int index1 = random.Next(length - 1);
       int index2 = random.Next(index1 + 1, length);
-      return new InversionMove(index1, index2);;
+      if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
+        while (index2 - index1 >= length - 2)
+          index2 = random.Next(index1 + 1, length);
+      }
+      return new InversionMove(index1, index2);
     }