Changeset 3340 for trunk/sources/HeuristicLab.Encodings.PermutationEncoding

Timestamp:

04/14/10 03:52:07 (14 years ago)

Author:

abeham

Message:

Updated Tabu search, permutation move operators, real vector move operators, binary vector move operators #840
Added a Tabu Search TSP workbench

Location:

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3

Files:

• HeuristicLab.Encodings.PermutationEncoding-3.3.csproj (modified) (2 diffs)
• Manipulators/InsertionManipulator.cs (modified) (1 diff)
• Moves/PermutationMoveAttribute.cs (added)
• Moves/ThreeOpt/ExhaustiveInsertionMoveGenerator.cs (modified) (1 diff)
• Moves/ThreeOpt/PreventRemovalTranslocationMoveTabuChecker.cs (deleted)
• Moves/ThreeOpt/StochasticTranslocationSingleMoveGenerator.cs (modified) (1 diff)
• Moves/ThreeOpt/TranslocationMoveAbsoluteAttribute.cs (added)
• Moves/ThreeOpt/TranslocationMoveHardTabuCriterion.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/PreventReaddAndRemovalTranslocationMoveTabuChecker.cs) (4 diffs)
• Moves/ThreeOpt/TranslocationMoveRelativeAttribute.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveAttribute.cs) (3 diffs)
• Moves/ThreeOpt/TranslocationMoveSoftTabuCriterion.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/PreventReaddTranslocationMoveTabuChecker.cs) (4 diffs)
• Moves/ThreeOpt/TranslocationMoveTabuMaker.cs (modified) (1 diff)
• Moves/TwoOpt/ExhaustiveInversionMoveGenerator.cs (modified) (2 diffs)
• Moves/TwoOpt/InversionMoveAbsoluteAttribute.cs (modified) (2 diffs)
• Moves/TwoOpt/InversionMoveHardTabuCriterion.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventRemovalInversionMoveTabuChecker.cs) (4 diffs)
• Moves/TwoOpt/InversionMoveRelativeAttribute.cs (modified) (2 diffs)
• Moves/TwoOpt/InversionMoveSoftTabuCriterion.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventReaddInversionMoveTabuChecker.cs) (4 diffs)
• Moves/TwoOpt/InversionMoveTabuMaker.cs (modified) (2 diffs)
• Moves/TwoOpt/PreventReaddAndRemovalInversionMoveTabuChecker.cs (deleted)

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

@@ -107 +107 @@
     <Compile Include="Manipulators\TranslocationInversionManipulator.cs" />
     <Compile Include="Manipulators\TranslocationManipulator.cs" />
+    <Compile Include="Moves\PermutationMoveAttribute.cs" />
     <Compile Include="Moves\ThreeIndexMove.cs" />
+    <Compile Include="Moves\ThreeOpt\TranslocationMoveAbsoluteAttribute.cs" />
     <Compile Include="Moves\ThreeOpt\ExhaustiveInsertionMoveGenerator.cs">
       <SubType>Code</SubType>
     </Compile>
-    <Compile Include="Moves\ThreeOpt\PreventReaddAndRemovalTranslocationMoveTabuChecker.cs" />
-    <Compile Include="Moves\ThreeOpt\PreventReaddTranslocationMoveTabuChecker.cs" />
-    <Compile Include="Moves\ThreeOpt\PreventRemovalTranslocationMoveTabuChecker.cs" />
     <Compile Include="Moves\ThreeOpt\StochasticTranslocationMultiMoveGenerator.cs" />
     <Compile Include="Moves\ThreeOpt\StochasticTranslocationSingleMoveGenerator.cs" />
     <Compile Include="Moves\ThreeOpt\TranslocationMove.cs" />
-    <Compile Include="Moves\ThreeOpt\TranslocationMoveAttribute.cs" />
     <Compile Include="Moves\ThreeOpt\TranslocationMoveGenerator.cs" />
+    <Compile Include="Moves\ThreeOpt\TranslocationMoveHardTabuCriterion.cs" />
     <Compile Include="Moves\ThreeOpt\TranslocationMoveMaker.cs" />
+    <Compile Include="Moves\ThreeOpt\TranslocationMoveRelativeAttribute.cs" />
+    <Compile Include="Moves\ThreeOpt\TranslocationMoveSoftTabuCriterion.cs" />
     <Compile Include="Moves\ThreeOpt\TranslocationMoveTabuMaker.cs" />
     <Compile Include="Moves\TwoIndexMove.cs">
@@ -127 +128 @@
     <Compile Include="Moves\TwoOpt\ExhaustiveInversionMoveGenerator.cs" />
     <Compile Include="Moves\TwoOpt\InversionMove.cs" />
+    <Compile Include="Moves\TwoOpt\InversionMoveHardTabuCriterion.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveRelativeAttribute.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveGenerator.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveMaker.cs" />
+    <Compile Include="Moves\TwoOpt\InversionMoveSoftTabuCriterion.cs" />
     <Compile Include="Moves\TwoOpt\InversionMoveTabuMaker.cs" />
-    <Compile Include="Moves\TwoOpt\PreventReaddAndRemovalInversionMoveTabuChecker.cs" />
-    <Compile Include="Moves\TwoOpt\PreventReaddInversionMoveTabuChecker.cs" />
-    <Compile Include="Moves\TwoOpt\PreventRemovalInversionMoveTabuChecker.cs" />
     <Compile Include="Moves\TwoOpt\StochasticInversionMultiMoveGenerator.cs" />
     <Compile Include="Moves\TwoOpt\StochasticInversionSingleMoveGenerator.cs" />

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InsertionManipulator.cs

@@ -30 +30 @@
   /// It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.
   /// </remarks>
-  [Item("InsertionManipulator", "An operator which moves randomly one element to another position in the permutation. It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.")]
+  [Item("InsertionManipulator", "An operator which moves randomly one element to another position in the permutation (Insertion is a special case of Translocation). It is implemented as described in Fogel, D.B. (1988). An Evolutionary Approach to the Traveling Salesman Problem, Biological Cybernetics, 60, pp. 139-144.")]
   [StorableClass]
   public class InsertionManipulator : PermutationManipulator {

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/ExhaustiveInsertionMoveGenerator.cs

@@ -34 +34 @@
     public static TranslocationMove[] Apply(Permutation permutation) {
       int length = permutation.Length;
-      TranslocationMove[] moves = new TranslocationMove[length * (length - 1)];
+      TranslocationMove[] moves = null;
       int count = 0;
-      for (int i = 0; i < length; i++) {
-        for (int j = 1; j <= length - 1; j++) {
-          moves[count++] = new TranslocationMove(i, i, (i + j) % length);
+      if (permutation.PermutationType == PermutationTypes.Absolute) {
+        moves = new TranslocationMove[length * (length - 1)];
+        for (int i = 0; i < length; i++) {
+          for (int j = 1; j <= length - 1; j++) {
+            moves[count++] = new TranslocationMove(i, i, (i + j) % length);
+          }
+        }
+      } else {
+        moves = new TranslocationMove[length * (length - 1) - 2];
+        for (int i = 0; i < length; i++) {
+          for (int j = 1; j <= length - 1; j++) {
+            if (i == 0 && j == length - 1
+              || i == length - 1 && j == 1) continue;
+            moves[count++] = new TranslocationMove(i, i, (i + j) % length);
+          }
         }
       }
+      System.Diagnostics.Debug.Assert(count == moves.Length);
       return moves;
     }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/StochasticTranslocationSingleMoveGenerator.cs

@@ -43 +43 @@
       int length = permutation.Length;
       int index1, index2, index3;
-      index1 = random.Next(length - 1);
       do {
-        index2 = random.Next(index1, length);
-      } while (index2 - index1 >= length - 2);
-      do {
-        index3 = random.Next(length - index2 + index1);
-      } while (index3 == index1);
-      
+        index1 = random.Next(length);
+        do {
+          index2 = random.Next(index1, length);
+        } while (index2 - index1 >= length - 2);
+        do {
+          index3 = random.Next(length - index2 + index1);
+        } while (index3 == index1);
+      } while (permutation.PermutationType != PermutationTypes.Absolute && (index1 == 0 && index3 == length - 1 || index1 == length - 1 && index3 == 0));
       return new TranslocationMove(index1, index2, index3);
     }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveHardTabuCriterion.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventReaddAndRemovalTranslocationMoveTabuChecker", "Prevents readding of previously deleted edges as well as deleting previously added edges.")]
+  [Item("TranslocationMoveHardTabuCriterion", @"For relative postion encoded permutations it prevents readding of previously deleted edges as well as deleting previously added edges.
+  For absolute position encoded permutations it prevents moving a number if it was previously moved.
+
+If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
   [StorableClass]
-  public class PreventReaddAndRemovalTranslocationMoveTabuChecker : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
+  public class TranslocationMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
     public override bool CanChangeName {
       get { return false; }
@@ -47 +50 @@
       get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
     }
-    private ScopeParameter CurrentScopeParameter {
-      get { return (ScopeParameter)Parameters["CurrentScope"]; }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
+    public ILookupParameter<DoubleValue> MoveQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
+    }
+    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
     }
 
-    public PreventReaddAndRemovalTranslocationMoveTabuChecker()
+    public BoolValue UseAspirationCriterion {
+      get { return UseAspirationCriterionParameter.Value; }
+      set { UseAspirationCriterionParameter.Value = value; }
+    }
+
+    public TranslocationMoveHardTabuCriterion()
       : base() {
       Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
@@ -57 +71 @@
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
       Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
-      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
+      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
     }
 
@@ -65 +81 @@
       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);
-      int E3S, E3T;
-      if (move.Index3 > move.Index1) {
-        E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
-        E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
+      double moveQuality = MoveQualityParameter.ActualValue.Value;
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      bool useAspiration = UseAspirationCriterion.Value;
+      bool isTabu = false;
+
+      if (permutation.PermutationType == PermutationTypes.Absolute) {
+        int count = move.Index2 - move.Index1 + 1;
+        int[] numbers = new int[count];
+        for (int i = move.Index1; i <= move.Index2; i++)
+          numbers[i - move.Index1] = permutation[i];
+
+        foreach (IItem tabuMove in tabuList) {
+          TranslocationMoveAbsoluteAttribute attribute = (tabuMove as TranslocationMoveAbsoluteAttribute);
+          if (attribute != null) {
+            if (!useAspiration
+              || maximization && moveQuality <= attribute.MoveQuality
+              || !maximization && moveQuality >= attribute.MoveQuality) { // if the move quality is improving beyond what was recorded when the move in the tabu list was recorded the move is regarded as okay
+
+              for (int i = 0; i < count; i++) {
+                for (int j = 0; j < attribute.Number.Length; j++) {
+                  if (attribute.Number[j] == numbers[i]) {
+                    isTabu = true;
+                    break;
+                  }
+                }
+                if (isTabu) break;
+              }
+            }
+          }
+          if (isTabu) break;
+        }
       } else {
-        E3S = permutation.GetCircular(move.Index3 - 1);
-        E3T = permutation[move.Index3];
-      }
-      bool isTabu = (move.Index1 == move.Index3
-        || move.Index2 - move.Index1 >= permutation.Length - 2
-        || move.Index1 == permutation.Length - 1 && move.Index3 == 0
-        || move.Index3 == permutation.Length - 1 && move.Index1 == 0);
-      if (!isTabu) {
+        int E1S = permutation.GetCircular(move.Index1 - 1);
+        int E1T = permutation[move.Index1];
+        int E2S = permutation[move.Index2];
+        int E2T = permutation.GetCircular(move.Index2 + 1);
+        int E3S, E3T;
+        if (move.Index3 > move.Index1) {
+          E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
+          E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
+        } else {
+          E3S = permutation.GetCircular(move.Index3 - 1);
+          E3T = permutation[move.Index3];
+        }
         foreach (IItem tabuMove in tabuList) {
-          TranslocationMoveAttribute attribute = (tabuMove as TranslocationMoveAttribute);
+          TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute);
           if (attribute != null) {
-            // if previously deleted Edge1Source-Target is readded
-            if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
-              || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
-              || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
-              // if previously deleted Edge2Source-Target is readded
-              || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
-              || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
-              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
-              // if previously deleted Edge3Source-Target is readded
-              || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
-              || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
-              || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S
-              // if previously added Edge3Source-Edge1Target is deleted
-              || attribute.Edge3Source == E1S && attribute.Edge1Target == E1T || attribute.Edge3Source == E1T && attribute.Edge1Target == E1S
-              || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T || attribute.Edge3Source == E2T && attribute.Edge1Target == E2S
-              || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T || attribute.Edge3Source == E3T && attribute.Edge1Target == E3S
-              // if previously added Edge2Source-Edge3Target is deleted
-              || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T || attribute.Edge2Source == E1T && attribute.Edge3Target == E1S
-              || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T || attribute.Edge2Source == E2T && attribute.Edge3Target == E2S
-              || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T || attribute.Edge2Source == E3T && attribute.Edge3Target == E3S
-              // if previously added Edge1Source-Edge2Target is deleted
-              || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T || attribute.Edge1Source == E1T && attribute.Edge2Target == E1S
-              || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T || attribute.Edge1Source == E2T && attribute.Edge2Target == E2S
-              || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T || attribute.Edge1Source == E3T && attribute.Edge2Target == E3S) {
-              isTabu = true;
-              break;
+            if (!useAspiration
+              || maximization && moveQuality <= attribute.MoveQuality
+              || !maximization && moveQuality >= attribute.MoveQuality) {
+
+              if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
+                if (// if previously added Edge3Source-Edge1Target is deleted
+                  attribute.Edge3Source == E1S && attribute.Edge1Target == E1T || attribute.Edge3Source == E1T && attribute.Edge1Target == E1S
+                  || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T || attribute.Edge3Source == E2T && attribute.Edge1Target == E2S
+                  || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T || attribute.Edge3Source == E3T && attribute.Edge1Target == E3S
+                  // if previously added Edge2Source-Edge3Target is deleted
+                  || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T || attribute.Edge2Source == E1T && attribute.Edge3Target == E1S
+                  || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T || attribute.Edge2Source == E2T && attribute.Edge3Target == E2S
+                  || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T || attribute.Edge2Source == E3T && attribute.Edge3Target == E3S
+                  // if previously added Edge1Source-Edge2Target is deleted
+                  || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T || attribute.Edge1Source == E1T && attribute.Edge2Target == E1S
+                  || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T || attribute.Edge1Source == E2T && attribute.Edge2Target == E2S
+                  || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T || attribute.Edge1Source == E3T && attribute.Edge2Target == E3S) {
+                  isTabu = true;
+                  break;
+                }
+              } else {
+                if (// if previously added Edge3Source-Edge1Target is deleted
+                  attribute.Edge3Source == E1S && attribute.Edge1Target == E1T
+                  || attribute.Edge3Source == E2S && attribute.Edge1Target == E2T
+                  || attribute.Edge3Source == E3S && attribute.Edge1Target == E3T
+                  // if previously added Edge2Source-Edge3Target is deleted
+                  || attribute.Edge2Source == E1S && attribute.Edge3Target == E1T
+                  || attribute.Edge2Source == E2S && attribute.Edge3Target == E2T
+                  || attribute.Edge2Source == E3S && attribute.Edge3Target == E3T
+                  // if previously added Edge1Source-Edge2Target is deleted
+                  || attribute.Edge1Source == E1S && attribute.Edge2Target == E1T
+                  || attribute.Edge1Source == E2S && attribute.Edge2Target == E2T
+                  || attribute.Edge1Source == E3S && attribute.Edge2Target == E3T) {
+                  isTabu = true;
+                  break;
+                }
+              }
             }
           }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveRelativeAttribute.cs

@@ -24 +24 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("TranslocationMoveAttribute", "Specifies the tabu attributes for a translocation and insertion move (3-opt).")]
+  [Item("TranslocationMoveRelativeAttribute", "Specifies the tabu attributes for a translocation and insertion move (3-opt) on relative permutation encodings.")]
   [StorableClass]
-  public class TranslocationMoveAttribute : Item {
+  public class TranslocationMoveRelativeAttribute : PermutationMoveAttribute {
     [Storable]
     public int Edge1Source { get; private set; }
@@ -41 +41 @@
 
     [StorableConstructor]
-    private TranslocationMoveAttribute(bool deserializing)
+    private TranslocationMoveRelativeAttribute(bool deserializing)
       : base() {
     }
 
-    public TranslocationMoveAttribute()
-      : this(-1, -1, -1, -1, -1, -1) { }
+    public TranslocationMoveRelativeAttribute()
+      : this(-1, -1, -1, -1, -1, -1, -1) { }
 
-    public TranslocationMoveAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, int edge3Source, int edge3Target)
-      : base() {
+    public TranslocationMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, int edge3Source, int edge3Target, double moveQuality)
+      : base(moveQuality) {
       Edge1Source = edge1Source;
       Edge1Target = edge1Target;
@@ -59 +59 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      TranslocationMoveAttribute clone = (TranslocationMoveAttribute)base.Clone(cloner);
+      TranslocationMoveRelativeAttribute clone = (TranslocationMoveRelativeAttribute)base.Clone(cloner);
       clone.Edge1Source = Edge1Source;
       clone.Edge1Target = Edge1Target;

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveSoftTabuCriterion.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventReaddTranslocationMoveTabuChecker", "Prevents readding of previously deleted edges.")]
+  [Item("TranslocationMoveSoftTabuCriterion", @"For relative postion encoded permutations it just prevents readding of previously deleted edges, but allows deleting previously added edges.
+  For absolute position encoded permutations it prevents moving a number to a position it has previously occupied.
+
+If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
   [StorableClass]
-  public class PreventReaddTranslocationMoveTabuChecker : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
+  public class TranslocationMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationTranslocationMoveOperator, ITabuChecker {
     public override bool CanChangeName {
       get { return false; }
@@ -47 +50 @@
       get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
     }
-    private ScopeParameter CurrentScopeParameter {
-      get { return (ScopeParameter)Parameters["CurrentScope"]; }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
+    public ILookupParameter<DoubleValue> MoveQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
+    }
+    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
     }
 
-    public PreventReaddTranslocationMoveTabuChecker()
+    public BoolValue UseAspirationCriterion {
+      get { return UseAspirationCriterionParameter.Value; }
+      set { UseAspirationCriterionParameter.Value = value; }
+    }
+
+    public TranslocationMoveSoftTabuCriterion()
       : base() {
       Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
@@ -57 +71 @@
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
       Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
-      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
+      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
     }
 
@@ -65 +81 @@
       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);
-      int E3S, E3T;
-      if (move.Index3 > move.Index1) {
-        E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
-        E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
+      double moveQuality = MoveQualityParameter.ActualValue.Value;
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      bool useAspiration = UseAspirationCriterion.Value;
+      bool isTabu = false;
+
+      if (permutation.PermutationType == PermutationTypes.Absolute) {
+        int count = move.Index2 - move.Index1 + 1;
+        int[] numbers = new int[count];
+        for (int i = move.Index1; i <= move.Index2; i++)
+          numbers[i - move.Index1] = permutation[i];
+
+        foreach (IItem tabuMove in tabuList) {
+          TranslocationMoveAbsoluteAttribute attribute = (tabuMove as TranslocationMoveAbsoluteAttribute);
+          if (attribute != null) {
+            if (!useAspiration
+              || maximization && moveQuality <= attribute.MoveQuality
+              || !maximization && moveQuality >= attribute.MoveQuality) { // if the move quality is improving beyond what was recorded when the move in the tabu list was recorded the move is regarded as okay
+
+              for (int i = 0; i < count; i++) {
+                for (int j = 0; j < attribute.Number.Length; j++) {
+                  if (attribute.Number[j] == numbers[i] && attribute.OldPosition + j == move.Index3 + i) {
+                    isTabu = true;
+                    break;
+                  }
+                }
+                if (isTabu) break;
+              }
+            }
+          }
+          if (isTabu) break;
+        }
       } else {
-        E3S = permutation.GetCircular(move.Index3 - 1);
-        E3T = permutation[move.Index3];
-      }
-      bool isTabu = (move.Index1 == move.Index3
-        || move.Index2 - move.Index1 >= permutation.Length - 2
-        || move.Index1 == permutation.Length - 1 && move.Index3 == 0
-        || move.Index3 == permutation.Length - 1 && move.Index1 == 0);
-      if (!isTabu) {
+        int E1S = permutation.GetCircular(move.Index1 - 1);
+        int E1T = permutation[move.Index1];
+        int E2S = permutation[move.Index2];
+        int E2T = permutation.GetCircular(move.Index2 + 1);
+        int E3S, E3T;
+        if (move.Index3 > move.Index1) {
+          E3S = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
+          E3T = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
+        } else {
+          E3S = permutation.GetCircular(move.Index3 - 1);
+          E3T = permutation[move.Index3];
+        }
         foreach (IItem tabuMove in tabuList) {
-          TranslocationMoveAttribute attribute = (tabuMove as TranslocationMoveAttribute);
+          TranslocationMoveRelativeAttribute attribute = (tabuMove as TranslocationMoveRelativeAttribute);
           if (attribute != null) {
-            // if previously deleted Edge1Source-Target is readded
-            if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
-              || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
-              || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
-              // if previously deleted Edge2Source-Target is readded
-              || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
-              || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
-              || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
-              // if previously deleted Edge3Source-Target is readded
-              || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
-              || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
-              || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S) {
-              isTabu = true;
-              break;
+            if (!useAspiration
+              || maximization && moveQuality <= attribute.MoveQuality
+              || !maximization && moveQuality >= attribute.MoveQuality) {
+
+              // if previously deleted Edge1Source-Target is readded
+              if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
+                if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T || attribute.Edge1Source == E1T && attribute.Edge1Target == E3S
+                  || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T || attribute.Edge1Source == E3T && attribute.Edge1Target == E2S
+                  || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T || attribute.Edge1Source == E2T && attribute.Edge1Target == E1S
+                  // if previously deleted Edge2Source-Target is readded
+                  || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T || attribute.Edge2Source == E1T && attribute.Edge2Target == E3S
+                  || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T || attribute.Edge2Source == E3T && attribute.Edge2Target == E2S
+                  || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T || attribute.Edge2Source == E2T && attribute.Edge2Target == E1S
+                  // if previously deleted Edge3Source-Target is readded
+                  || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T || attribute.Edge3Source == E1T && attribute.Edge3Target == E3S
+                  || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T || attribute.Edge3Source == E3T && attribute.Edge3Target == E2S
+                  || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T || attribute.Edge3Source == E2T && attribute.Edge3Target == E1S) {
+                  isTabu = true;
+                  break;
+                }
+              } else {
+                if (attribute.Edge1Source == E3S && attribute.Edge1Target == E1T
+                  || attribute.Edge1Source == E2S && attribute.Edge1Target == E3T
+                  || attribute.Edge1Source == E1S && attribute.Edge1Target == E2T
+                  // if previously deleted Edge2Source-Target is readded
+                  || attribute.Edge2Source == E3S && attribute.Edge2Target == E1T
+                  || attribute.Edge2Source == E2S && attribute.Edge2Target == E3T
+                  || attribute.Edge2Source == E1S && attribute.Edge2Target == E2T
+                  // if previously deleted Edge3Source-Target is readded
+                  || attribute.Edge3Source == E3S && attribute.Edge3Target == E1T
+                  || attribute.Edge3Source == E2S && attribute.Edge3Target == E3T
+                  || attribute.Edge3Source == E1S && attribute.Edge3Target == E2T) {
+                  isTabu = true;
+                  break;
+                }
+              }
             }
           }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/ThreeOpt/TranslocationMoveTabuMaker.cs

@@ -48 +48 @@
     }
 
-    protected override IItem GetTabuAttribute() {
+    protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) {
       TranslocationMove move = TranslocationMoveParameter.ActualValue;
       Permutation permutation = PermutationParameter.ActualValue;
-      if (move.Index3 > move.Index1)
-        return new TranslocationMoveAttribute(permutation.GetCircular(move.Index1 - 1),
-        permutation[move.Index1],
-        permutation[move.Index2],
-        permutation.GetCircular(move.Index2 + 1),
-        permutation.GetCircular(move.Index3 + move.Index2 - move.Index1),
-        permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1));
-      else
-        return new TranslocationMoveAttribute(permutation.GetCircular(move.Index1 - 1),
-        permutation[move.Index1],
-        permutation[move.Index2],
-        permutation.GetCircular(move.Index2 + 1),
-        permutation.GetCircular(move.Index3 - 1),
-        permutation.GetCircular(move.Index3));
+      double baseQuality = moveQuality;
+      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
+      if (permutation.PermutationType == PermutationTypes.Absolute) {
+        int[] numbers = new int[move.Index2 - move.Index1 + 1];
+        for (int i = 0; i < numbers.Length; i++) {
+          numbers[i] = permutation[i + move.Index1];
+        }
+        return new TranslocationMoveAbsoluteAttribute(numbers, move.Index1, move.Index3, baseQuality); ;
+      } else {
+        if (move.Index3 > move.Index1)
+          return new TranslocationMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
+          permutation[move.Index1],
+          permutation[move.Index2],
+          permutation.GetCircular(move.Index2 + 1),
+          permutation.GetCircular(move.Index3 + move.Index2 - move.Index1),
+          permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1),
+          baseQuality);
+        else
+          return new TranslocationMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
+          permutation[move.Index1],
+          permutation[move.Index2],
+          permutation.GetCircular(move.Index2 + 1),
+          permutation.GetCircular(move.Index3 - 1),
+          permutation.GetCircular(move.Index3),
+          baseQuality);
+      }
     }
   }

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

@@ -31 +31 @@
     public static InversionMove[] Apply(Permutation permutation) {
       int length = permutation.Length;
-      int totalMoves = (length) * (length - 1) / 2; // - 3;
-      InversionMove[] moves = new InversionMove[totalMoves];
+      int totalMoves = (length) * (length - 1) / 2;
+      InversionMove[] moves = null;
       int count = 0;
 
       if (permutation.PermutationType == PermutationTypes.RelativeUndirected) {
+        moves = new InversionMove[totalMoves - 3];
         for (int i = 0; i < length - 1; i++) {
           for (int j = i + 1; j < length; j++) {
@@ -44 +45 @@
         }
       } else {
-          for (int i = 0; i < length - 1; i++)
-            for (int j = i + 1; j < length; j++) {
-              moves[count++] = new InversionMove(i, j);
-            }
+        moves = new InversionMove[totalMoves];
+        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/InversionMoveAbsoluteAttribute.cs

@@ -26 +26 @@
   [Item("InversionMoveAbsoluteAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on an absolute position permutation.")]
   [StorableClass]
-  public class InversionMoveAbsoluteAttribute : Item {
+  public class InversionMoveAbsoluteAttribute : PermutationMoveAttribute {
     [Storable]
     public int Index1 { get; private set; }
@@ -42 +42 @@
 
     public InversionMoveAbsoluteAttribute()
-      : this(-1, -1, -1, -1) { }
+      : this(-1, -1, -1, -1, -1) { }
 
-    public InversionMoveAbsoluteAttribute(int index1, int number1, int index2, int number2)
-      : base() {
+    public InversionMoveAbsoluteAttribute(int index1, int number1, int index2, int number2, double moveQuality)
+      : base(moveQuality) {
       Index1 = index1;
       Number1 = number1;

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

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventRemovalInversionMoveTabuChecker", "Prevents deleting of previously added edges.")]
+  [Item("InversionMoveHardTabuCriterion", @"For relative postion encoded permutations it prevents readding of previously deleted edges as well as deleting previously added edges.
+  For absolute position encoded permutations it prevents moving a number if it was previously moved.
+
+If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
   [StorableClass]
-  public class PreventRemovalInversionMoveTabuChecker : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
+  public class InversionMoveHardTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
     public override bool CanChangeName {
       get { return false; }
@@ -47 +50 @@
       get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
     }
-    private ScopeParameter CurrentScopeParameter {
-      get { return (ScopeParameter)Parameters["CurrentScope"]; }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
+    public ILookupParameter<DoubleValue> MoveQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
+    }
+    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
     }
 
-    public PreventRemovalInversionMoveTabuChecker()
+    public BoolValue UseAspirationCriterion {
+      get { return UseAspirationCriterionParameter.Value; }
+      set { UseAspirationCriterionParameter.Value = value; }
+    }
+
+    public InversionMoveHardTabuCriterion()
       : base() {
       Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
@@ -57 +71 @@
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
       Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
-      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
+      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
     }
 
@@ -65 +81 @@
       Permutation permutation = PermutationParameter.ActualValue;
       int length = permutation.Length;
+      double moveQuality = MoveQualityParameter.ActualValue.Value;
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      bool useAspiration = UseAspirationCriterion.Value;
       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;
+        PermutationMoveAttribute attrib = (tabuMove as PermutationMoveAttribute);
+        if (!useAspiration
+          || maximization && moveQuality <= attrib.MoveQuality
+          || !maximization && moveQuality >= attrib.MoveQuality) {
+          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 = (attrib 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.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 = (attrib 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;
+            case PermutationTypes.Absolute: {
+                int i1 = move.Index1;
+                int n1 = permutation[move.Index1];
+                int i2 = move.Index2;
+                int n2 = permutation[move.Index2];
+                InversionMoveAbsoluteAttribute absAttrib = (attrib 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.");
-            }
+              break;
+            default: {
+                throw new InvalidOperationException(Name + ": Unknown permutation type.");
+              }
+          }
         }
         if (isTabu) break;

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

@@ -26 +26 @@
   [Item("InversionMoveRelativeAttribute", "Specifies the tabu attributes for an inversion move (2-opt) on a relative position permutation.")]
   [StorableClass]
-  public class InversionMoveRelativeAttribute : Item {
+  public class InversionMoveRelativeAttribute : PermutationMoveAttribute {
     [Storable]
     public int Edge1Source { get; private set; }
@@ -42 +42 @@
 
     public InversionMoveRelativeAttribute()
-      : this(-1, -1, -1, -1) { }
+      : this(-1, -1, -1, -1, -1) { }
 
-    public InversionMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target)
-      : base() {
+    public InversionMoveRelativeAttribute(int edge1Source, int edge1Target, int edge2Source, int edge2Target, double moveQuality)
+      : base(moveQuality) {
       Edge1Source = edge1Source;
       Edge1Target = edge1Target;

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

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("PreventReaddInversionMoveTabuChecker", "Prevents readding of previously deleted edges, but allows deleting previously added edges.")]
+  [Item("InversionMoveSoftTabuCriterion", @"For relative postion encoded permutations it just prevents readding of previously deleted edges, but allows deleting previously added edges.
+  For absolute position encoded permutations it prevents moving a number to a position it has previously occupied.
+
+If the aspiration condition is activated, a move will not be considered tabu against a move in the tabu list if it leads to a better solution than the quality recorded with the move in the tabu list.")]
   [StorableClass]
-  public class PreventReaddInversionMoveTabuChecker : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
+  public class InversionMoveSoftTabuCriterion : SingleSuccessorOperator, IPermutationInversionMoveOperator, ITabuChecker {
     public override bool CanChangeName {
       get { return false; }
@@ -47 +50 @@
       get { return (ILookupParameter<BoolValue>)Parameters["MoveTabu"]; }
     }
-    private ScopeParameter CurrentScopeParameter {
-      get { return (ScopeParameter)Parameters["CurrentScope"]; }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
+    public ILookupParameter<DoubleValue> MoveQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
+    }
+    public ValueParameter<BoolValue> UseAspirationCriterionParameter {
+      get { return (ValueParameter<BoolValue>)Parameters["UseAspirationCriterion"]; }
     }
 
-    public PreventReaddInversionMoveTabuChecker()
+    public BoolValue UseAspirationCriterion {
+      get { return UseAspirationCriterionParameter.Value; }
+      set { UseAspirationCriterionParameter.Value = value; }
+    }
+
+    public InversionMoveSoftTabuCriterion()
       : base() {
       Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
@@ -57 +71 @@
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
       Parameters.Add(new LookupParameter<ItemList<IItem>>("TabuList", "The tabu list."));
-      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope."));
+      Parameters.Add(new ValueParameter<BoolValue>("UseAspirationCriterion", "Whether to use the aspiration criterion or not.", new BoolValue(true)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, else if it is a minimization problem."));
+      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the current move."));
     }
 
@@ -65 +81 @@
       Permutation permutation = PermutationParameter.ActualValue;
       int length = permutation.Length;
+      double moveQuality = MoveQualityParameter.ActualValue.Value;
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      bool useAspiration = UseAspirationCriterion.Value;
       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;
+        PermutationMoveAttribute attrib = (tabuMove as PermutationMoveAttribute);
+        if (!useAspiration
+          || maximization && moveQuality <= attrib.MoveQuality
+          || !maximization && moveQuality >= attrib.MoveQuality) {
+          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 = (attrib 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.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 = (attrib 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;
+            case PermutationTypes.Absolute: {
+                int i1 = move.Index1;
+                int n1 = permutation[move.Index1];
+                int i2 = move.Index2;
+                int n2 = permutation[move.Index2];
+                InversionMoveAbsoluteAttribute absAttrib = (attrib 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.");
-            }
+              break;
+            default: {
+                throw new InvalidOperationException(Name + ": Unknown permutation type.");
+              }
+          }
         }
         if (isTabu) break;

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

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
-  [Item("InversionMoveTabuMaker", "Declares a given inversion move (2-opt) as tabu, by adding its attributes to the tabu list.")]
+  [Item("InversionMoveTabuMaker", "Declares a given inversion move (2-opt) as tabu, by adding its attributes to the tabu list and also store the solution quality or the move quality (whichever is better).")]
   [StorableClass]
   public class InversionMoveTabuMaker : TabuMaker, IPermutationInversionMoveOperator {
@@ -48 +48 @@
     }
 
-    protected override IItem GetTabuAttribute() {
+    protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) {
       InversionMove move = InversionMoveParameter.ActualValue;
       Permutation permutation = PermutationParameter.ActualValue;
+      double baseQuality = moveQuality;
+      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality; // we make an uphill move, the lower bound is the solution quality
       if (permutation.PermutationType == PermutationTypes.Absolute)
-        return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2]);
+        return new InversionMoveAbsoluteAttribute(move.Index1, permutation[move.Index1], move.Index2, permutation[move.Index2], baseQuality);
       else
         return new InversionMoveRelativeAttribute(permutation.GetCircular(move.Index1 - 1),
           permutation[move.Index1],
           permutation[move.Index2],
-          permutation.GetCircular(move.Index2 + 1));
+          permutation.GetCircular(move.Index2 + 1),
+          baseQuality);
     }
   }