Changeset 3340 for trunk/sources/HeuristicLab.Encodings.BinaryVectorEncoding/3.3

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.BinaryVectorEncoding/3.3

Files:

• HeuristicLab.Encodings.BinaryVectorEncoding-3.3.csproj (modified) (1 diff)
• Moves/OneBitflipMove/OneBitflipMoveAttribute.cs (added)
• Moves/OneBitflipMove/OneBitflipMoveTabuChecker.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Moves/OneBitflipMove/PreventOneBitflipTabuMoveEvaluator.cs) (4 diffs)
• Moves/OneBitflipMove/OneBitflipMoveTabuMaker.cs (moved) (moved from trunk/sources/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Moves/OneBitflipMove/OneBitflipTabuMoveMaker.cs) (3 diffs)

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

@@ -106 +106 @@
     <Compile Include="Moves\OneBitflipMove\OneBitflipMoveGenerator.cs" />
     <Compile Include="Moves\OneBitflipMove\OneBitflipMoveMaker.cs" />
-    <Compile Include="Moves\OneBitflipMove\OneBitflipTabuMoveMaker.cs" />
-    <Compile Include="Moves\OneBitflipMove\PreventOneBitflipTabuMoveEvaluator.cs" />
+    <Compile Include="Moves\OneBitflipMove\OneBitflipMoveTabuChecker.cs" />
+    <Compile Include="Moves\OneBitflipMove\OneBitflipMoveTabuMaker.cs" />
+    <Compile Include="Moves\OneBitflipMove\OneBitflipMoveAttribute.cs" />
     <Compile Include="Moves\OneBitflipMove\StochasticOneBitflipMultiMoveGenerator.cs" />
     <Compile Include="Moves\OneBitflipMove\StochasticOneBitflipSingleMoveGenerator.cs" />

trunk/sources/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Moves/OneBitflipMove/OneBitflipMoveTabuChecker.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.BinaryVectorEncoding {
-  [Item("PreventOneBitflipTabuMoveEvaluator", "Prevents peforming a one bitflip move again.")]
+  [Item("OneBitflipMoveTabuChecker", "Prevents peforming a one bitflip move again.")]
   [StorableClass]
-  public class PreventOneBitflipTabuMoveEvaluator : SingleSuccessorOperator, IOneBitflipMoveOperator, ITabuChecker {
+  public class OneBitflipMoveTabuChecker : SingleSuccessorOperator, IOneBitflipMoveOperator, ITabuChecker {
     public ILookupParameter<OneBitflipMove> OneBitflipMoveParameter {
       get { return (LookupParameter<OneBitflipMove>)Parameters["OneBitflipMove"]; }
@@ -44 +44 @@
       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 PreventOneBitflipTabuMoveEvaluator()
+    public BoolValue UseAspirationCriterion {
+      get { return UseAspirationCriterionParameter.Value; }
+      set { UseAspirationCriterionParameter.Value = value; }
+    }
+
+    public OneBitflipMoveTabuChecker()
       : base() {
       Parameters.Add(new LookupParameter<OneBitflipMove>("OneBitflipMove", "The move to evaluate."));
@@ -54 +65 @@
       Parameters.Add(new LookupParameter<BinaryVector>("BinaryVector", "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."));
     }
 
@@ -60 +73 @@
       ItemList<IItem> tabuList = TabuListParameter.ActualValue;
       OneBitflipMove move = OneBitflipMoveParameter.ActualValue;
+      double moveQuality = MoveQualityParameter.ActualValue.Value;
+      bool maximization = MaximizationParameter.ActualValue.Value;
+      bool useAspiration = UseAspirationCriterion.Value;
       bool isTabu = false;
       foreach (IItem tabuMove in tabuList) {
-        OneBitflipMove attribute = (tabuMove as OneBitflipMove);
+        OneBitflipMoveAttribute attribute = (tabuMove as OneBitflipMoveAttribute);
         if (attribute != null) {
-          if (attribute.Index == move.Index) {
-            isTabu = true;
-            break;
+          if (!useAspiration
+            || maximization && moveQuality <= attribute.MoveQuality
+            || !maximization && moveQuality >= attribute.MoveQuality) {
+            if (attribute.Index == move.Index) {
+              isTabu = true;
+              break;
+            }
           }
         }

trunk/sources/HeuristicLab.Encodings.BinaryVectorEncoding/3.3/Moves/OneBitflipMove/OneBitflipMoveTabuMaker.cs

@@ -29 +29 @@
 
 namespace HeuristicLab.Encodings.BinaryVectorEncoding {
-  [Item("OneBitflipTabuMoveMaker", "Declares a given one bitflip move as tabu, by adding its attributes to the tabu list. It also removes the oldest entry in the tabu list when its size is greater than tenure.")]
+  [Item("OneBitflipMoveTabuMaker", "Declares a given one bitflip move as tabu, by adding its attributes to the tabu list. It also removes the oldest entry in the tabu list when its size is greater than tenure.")]
   [StorableClass]
-  public class OneBitflipTabuMoveMaker : TabuMaker, IOneBitflipMoveOperator {
+  public class OneBitflipMoveTabuMaker : TabuMaker, IOneBitflipMoveOperator {
     public ILookupParameter<BinaryVector> BinaryVectorParameter {
       get { return (ILookupParameter<BinaryVector>)Parameters["BinaryVector"]; }
@@ -39 +39 @@
     }
 
-    public OneBitflipTabuMoveMaker()
+    public OneBitflipMoveTabuMaker()
       : base() {
       Parameters.Add(new LookupParameter<BinaryVector>("BinaryVector", "The solution as BinaryVector."));
@@ -45 +45 @@
     }
 
-    protected override IItem GetTabuAttribute() {
-      return OneBitflipMoveParameter.ActualValue;
+    protected override IItem GetTabuAttribute(bool maximization, double quality, double moveQuality) {
+      double baseQuality = moveQuality;
+      if (maximization && quality > moveQuality || !maximization && quality < moveQuality) baseQuality = quality;
+      return new OneBitflipMoveAttribute(OneBitflipMoveParameter.ActualValue.Index, baseQuality);
     }