Changeset 6593 for branches/QAPAlgorithms

Timestamp:

07/25/11 18:28:10 (13 years ago)

Author:

abeham

Message:

#1541

• Changed aspiration criterion after contacting Taillard, added option to choose between old or new adaption scheme

Location:

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3

Files:

• RobustTabooSeachOperator.cs (modified) (6 diffs)
• RobustTabooSearch.cs (modified) (8 diffs)

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSeachOperator.cs

@@ -37 +37 @@
       get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
     }
+    public ILookupParameter<IRandom> RandomParameter {
+      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
+    }
     public ILookupParameter<Permutation> PermutationParameter {
       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
@@ -61 +64 @@
       get { return (ILookupParameter<Swap2Move>)Parameters["LastMove"]; }
     }
+    public ILookupParameter<BoolValue> UseNewTabuTenureAdaptionSchemeParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["UseNewTabuTenureAdaptionScheme"]; }
+    }
     public ILookupParameter<ResultCollection> ResultsParameter {
       get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
     }
 
-    public ILookupParameter<IRandom> RandomParameter {
-      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
-    }
     public IValueLookupParameter<IntValue> MaximumIterationsParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
@@ -101 +104 @@
       Parameters.Add(new LookupParameter<DoubleValue>("BestQuality", "The best quality value."));
       Parameters.Add(new LookupParameter<Swap2Move>("LastMove", "The last move that was applied."));
+      Parameters.Add(new LookupParameter<BoolValue>("UseNewTabuTenureAdaptionScheme", "True if the new tabu tenure adaption should be used or false otherwise."));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "Collection that houses the results of the algorithm."));
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run."));
@@ -151 +155 @@
                       || shortTermMemory[move.Index2, solution[move.Index1]] < iteration;
 
-        bool aspired = shortTermMemory[move.Index1, solution[move.Index2]] < iteration - alternativeAspirationTenure
-                    || shortTermMemory[move.Index2, solution[move.Index1]] < iteration - alternativeAspirationTenure
-                    || quality.Value + moveQuality < bestQuality.Value;
+        bool aspired = (shortTermMemory[move.Index1, solution[move.Index2]] < iteration - alternativeAspirationTenure
+                     && shortTermMemory[move.Index2, solution[move.Index1]] < iteration - alternativeAspirationTenure)
+                  || quality.Value + moveQuality < bestQuality.Value;
 
         if ((aspired && !already_aspired) // the first alternative move is aspired
@@ -169 +173 @@
         if (!results.ContainsKey("AspiredMoves")) {
           aspiredMoves = new IntValue(already_aspired ? 1 : 0);
-          results.Add(new Result("AspiredMoves", aspiredMoves));
+          results.Add(new Result("AspiredMoves", "Counts the number of moves that were selected because of the aspiration criteria.", aspiredMoves));
         } else if (already_aspired) {
           aspiredMoves = (IntValue)results["AspiredMoves"].Value;
@@ -180 +184 @@
       if (bestMove == null) return base.Apply();
 
-      shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = iteration + random.Next(minTenure, maxTenure);
-      shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = iteration + random.Next(minTenure, maxTenure);
+      bool useNewAdaptionScheme = UseNewTabuTenureAdaptionSchemeParameter.ActualValue.Value;
+      if (useNewAdaptionScheme) {
+        double r = random.NextDouble();
+        shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = (int)(iteration + r * r * r * maxTenure);
+        r = random.NextDouble();
+        shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = (int)(iteration + r * r * r * maxTenure);
+      } else {
+        shortTermMemory[bestMove.Index1, solution[bestMove.Index1]] = iteration + random.Next(minTenure, maxTenure);
+        shortTermMemory[bestMove.Index2, solution[bestMove.Index2]] = iteration + random.Next(minTenure, maxTenure);
+      }
       Swap2Manipulator.Apply(solution, bestMove.Index1, bestMove.Index2);
       quality.Value += bestMoveQuality;

branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs

@@ -75 +75 @@
       get { return (FixedValueParameter<IntValue>)Parameters["AlternativeAspirationTenure"]; }
     }
+    private FixedValueParameter<BoolValue> UseNewTabuTenureAdaptionSchemeParameter {
+      get { return (FixedValueParameter<BoolValue>)Parameters["UseNewTabuTenureAdaptionScheme"]; }
+    }
     #endregion
 
@@ -105 +108 @@
       get { return AlternativeAspirationTenureParameter.Value.Value; }
       set { AlternativeAspirationTenureParameter.Value.Value = value; }
+    }
+    public bool UseNewTabuTenureAdaptionScheme {
+      get { return UseNewTabuTenureAdaptionSchemeParameter.Value.Value; }
+      set { UseNewTabuTenureAdaptionSchemeParameter.Value.Value = value; }
     }
     #endregion
@@ -129 +136 @@
       Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "True whether the seed should be set randomly for each run, false if it should be fixed.", new BoolValue(true)));
       Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(10000)));
-      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(20)));
-      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(10)));
+      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(20)));
       Parameters.Add(new FixedValueParameter<BoolValue>("UseAlternativeAspiration", "True if the alternative aspiration condition should be used that takes moves that have not been made for some time above others.", new BoolValue(false)));
       Parameters.Add(new FixedValueParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.", new IntValue(10000)));
       Parameters.Add(new FixedValueParameter<BoolValue>("TerminateOnOptimalSolution", "True when the algorithm should stop if it reached a quality equal or smaller to the BestKnownQuality.", new BoolValue(true)));
+      Parameters.Add(new FixedValueParameter<BoolValue>("UseNewTabuTenureAdaptionScheme", @"In an updated version of his implementation, Eric Taillard introduced a different way to change the tabu tenure.
+Instead of setting it uniformly between min and max, it will be set between 0 and max according to a right-skewed distribution.
+Set this option to false if you want to optimize using the earlier 1991 version, and set to true if you want to optimize using the newer version.
+Please note that the MinimumTabuTenure parameter has no effect in the new version.", new BoolValue(true)));
 
       qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
@@ -230 +241 @@
     }
 
+    #region Event Handlers
     protected override void OnProblemChanged() {
       base.OnProblemChanged();
@@ -264 +276 @@
 
     private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) {
-      if (AlternativeAspirationTenure < MaximumIterations
-        && !UseAlternativeAspiration) {
-        UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
-        UseAlternativeAspiration = true;
-        UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
-      } else if (AlternativeAspirationTenure >= MaximumIterations
-        && UseAlternativeAspiration) {
-        UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
-        UseAlternativeAspiration = false;
-        UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
-      }
-    }
+      if (AlternativeAspirationTenure < MaximumIterations && !UseAlternativeAspiration) {
+        SetSilentlyUseAlternativeAspirationParameter(true);
+      } else if (AlternativeAspirationTenure >= MaximumIterations && UseAlternativeAspiration) {
+        SetSilentlyUseAlternativeAspirationParameter(false);
+      }
+    }
+
+    private void MaximumIterationsParameter_ValueChanged(object sender, EventArgs e) {
+      if (MaximumIterations >= AlternativeAspirationTenure && UseAlternativeAspiration) {
+        SetSilentlyUseAlternativeAspirationParameter(false);
+      } else if (MaximumIterations < AlternativeAspirationTenure && !UseAlternativeAspiration) {
+        SetSilentlyUseAlternativeAspirationParameter(true);
+      }
+    }
+
+    private void UseNewTabuTenureAdaptionSchemeParameter_ValueChanged(object sender, EventArgs e) {
+      UpdateProblemSpecificParameters();
+    }
+    #endregion
 
     [StorableHook(HookType.AfterDeserialization)]
@@ -285 +304 @@
       UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
       AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged);
+      MaximumIterationsParameter.Value.ValueChanged += new EventHandler(MaximumIterationsParameter_ValueChanged);
+      UseNewTabuTenureAdaptionSchemeParameter.Value.ValueChanged += new EventHandler(UseNewTabuTenureAdaptionSchemeParameter_ValueChanged);
     }
 
@@ -313 +334 @@
 
     private void UpdateProblemSpecificParameters() {
-      MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
-      MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
+      UpdateTabuTenure();
       UpdateAlternativeAspirationTenure();
+    }
+
+    private void UpdateTabuTenure() {
+      if (UseNewTabuTenureAdaptionScheme) {
+        MinimumTabuTenure = 0;
+        MaximumTabuTenure = 8 * Problem.Weights.Rows;
+      } else {
+        MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
+        MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
+      }
     }
 
     private void UpdateAlternativeAspirationTenure() {
       if (UseAlternativeAspiration) {
-        AlternativeAspirationTenure = Problem.Weights.Rows * Problem.Weights.Rows / 2;
+        int n = Problem.Weights.Rows;
+        // Taillard has given two formulas for calculating default values: n^2 / 2 and later n^2 * 5
+        // However these do not really model the values he used in his original publication though
+        // The following formula is a linear regression model on the problem size and parameters
+        // given in Table 3 in Taillard1991 and was lower-bounded artificially by 100
+        AlternativeAspirationTenure = Math.Max(203 * n - 2274, 100);
       } else {
         AlternativeAspirationTenure = int.MaxValue;
@@ -351 +386 @@
       }
     }
+
+    private void SetSilentlyUseAlternativeAspirationParameter(bool value) {
+      UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
+      UseAlternativeAspiration = value;
+      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
+    }
   }
 }