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

Timestamp:

04/14/10 03:52:07 (15 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

File:

• trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/InversionMoveHardTabuCriterion.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Moves/TwoOpt/PreventRemovalInversionMoveTabuChecker.cs) (4 diffs)

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;