Changeset 2997 for trunk/sources/HeuristicLab.Algorithms.TS

Timestamp:

03/11/10 02:23:25 (14 years ago)

Author:

abeham

Message:

Updated tabu search and added an engine for the berlin52 TSP #840
Also added a BestQualityMemorizer operator in HeuristicLab.Analysis-3.3

Location:

trunk/sources/HeuristicLab.Algorithms.TS/3.3

Files:

• HeuristicLab.Algorithms.TS-3.3.csproj (modified) (1 diff)
• TSOperator.cs (modified) (8 diffs)
• Tabu Search.hl (added)
• TabuListCreator.cs (added)
• TabuSelector.cs (modified) (6 diffs)

trunk/sources/HeuristicLab.Algorithms.TS/3.3/HeuristicLab.Algorithms.TS-3.3.csproj

@@ -83 +83 @@
     <Compile Include="HeuristicLabAlgorithmsTSPlugin.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />
-    <Compile Include="TabuSelector.cs" />
-    <Compile Include="TSOperator.cs" />
+    <Compile Include="TabuListCreator.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="TabuSelector.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="TSOperator.cs">
+      <SubType>Code</SubType>
+    </Compile>
   </ItemGroup>
   <ItemGroup>

trunk/sources/HeuristicLab.Algorithms.TS/3.3/TSOperator.cs

@@ -25 +25 @@
 using HeuristicLab.Operators;
 using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Selection;
 
 namespace HeuristicLab.Algorithms.TS {
@@ -31 +33 @@
   /// </summary>
   [Item("TSOperator", "An operator which represents a Tabu Search.")]
+  [StorableClass(StorableClassType.Empty)]
   public class TSOperator : AlgorithmOperator {
     #region Parameter properties
@@ -51 +54 @@
       get { return (ValueLookupParameter<VariableCollection>)Parameters["Results"]; }
     }
+    public ValueLookupParameter<IOperator> MoveGeneratorParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["MoveGenerator"]; }
+    }
+    public ValueLookupParameter<IOperator> MoveQualityEvaluatorParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["MoveQualityEvaluator"]; }
+    }
+    public ValueLookupParameter<IOperator> MoveTabuEvaluatorParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["MoveTabuEvaluator"]; }
+    }
+    public ValueLookupParameter<IOperator> TabuSelectorParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["TabuSelector"]; }
+    }
+    public ValueLookupParameter<IOperator> MoveTabuMakerParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["MoveTabuMaker"]; }
+    }
+    public ValueLookupParameter<IOperator> MoveMakerParameter {
+      get { return (ValueLookupParameter<IOperator>)Parameters["MoveMaker"]; }
+    }
+
     private ScopeParameter CurrentScopeParameter {
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     }
-
     public IScope CurrentScope {
       get { return CurrentScopeParameter.ActualValue; }
@@ -69 +90 @@
       Parameters.Add(new ValueLookupParameter<IntData>("TabuTenure", "The length of the tabu list, and also means the number of iterations a move is kept tabu"));
       Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
+
+      Parameters.Add(new ValueLookupParameter<IOperator>("MoveGenerator", "The operator that generates the moves."));
+      Parameters.Add(new ValueLookupParameter<IOperator>("MoveQualityEvaluator", "The operator that evaluates the quality of a move."));
+      Parameters.Add(new ValueLookupParameter<IOperator>("MoveTabuEvaluator", "The operator that evaluates whether a move is tabu."));
+      TabuSelector tabuSelectorOp = new TabuSelector();
+      tabuSelectorOp.NumberOfSelectedSubScopes = new IntData(1);
+      Parameters.Add(new ValueLookupParameter<IOperator>("TabuSelector", "The operator that selects among the moves the next best.", tabuSelectorOp));
+      Parameters.Add(new ValueLookupParameter<IOperator>("MoveTabuMaker", "The operator that declares a move tabu."));
+      Parameters.Add(new ValueLookupParameter<IOperator>("MoveMaker", "The operator that performs a move and updates the quality."));
+
       Parameters.Add(new ScopeParameter("CurrentScope", "The current scope which represents a population of solutions on which the TS should be applied."));
       #endregion
 
       #region Create operators
+      TabuListCreator tabuListCreator = new TabuListCreator();
       VariableCreator variableCreator = new VariableCreator();
+      BestQualityMemorizer bestQualityMemorizer = new BestQualityMemorizer();
       ResultsCollector resultsCollector = new ResultsCollector();
+      UniformSequentialSubScopesProcessor mainProcessor = new UniformSequentialSubScopesProcessor();
       Placeholder moveGenerator = new Placeholder();
       UniformSequentialSubScopesProcessor moveEvaluationProcessor = new UniformSequentialSubScopesProcessor();
@@ -80 +114 @@
       Placeholder moveTabuEvaluator = new Placeholder();
       SubScopesSorter moveQualitySorter = new SubScopesSorter();
+      BestAverageWorstQualityCalculator bestAverageWorstMoveQualityCalculator = new BestAverageWorstQualityCalculator();
       Placeholder tabuSelector = new Placeholder();
-      SequentialSubScopesProcessor moveMakingProcessor = new SequentialSubScopesProcessor();
-      EmptyOperator emptyOp = new EmptyOperator();
-      UniformSequentialSubScopesProcessor actualMoveMakingProcessor = new UniformSequentialSubScopesProcessor();
+      RightReducer rightReducer = new RightReducer();
+      UniformSequentialSubScopesProcessor moveMakingProcessor = new UniformSequentialSubScopesProcessor();
+      Placeholder moveTabuMaker = new Placeholder();
       Placeholder moveMaker = new Placeholder();
-      Placeholder moveTabuMaker = new Placeholder();
+      DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
       SubScopesRemover subScopesRemover = new SubScopesRemover();
       IntCounter iterationsCounter = new IntCounter();
@@ -93 +128 @@
 
       variableCreator.CollectedValues.Add(new ValueParameter<IntData>("Iterations", new IntData(0)));
-      variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Best Quality", new DoubleData(0)));
       variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Best Move Quality", new DoubleData(0)));
       variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Average Move Quality", new DoubleData(0)));
       variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Worst Move Quality", new DoubleData(0)));
-      variableCreator.CollectedValues.Add(new ValueParameter<DataTable>("Qualities", new DataTable("Qualities")));
       variableCreator.CollectedValues.Add(new ValueParameter<DataTable>("MoveQualities", new DataTable("MoveQualities")));
 
       resultsCollector.CollectedValues.Add(new LookupParameter<IntData>("Iterations"));
-      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Quality"));
+      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Quality") { ActualName = "BestQuality" });
       resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Move Quality"));
       resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Average Move Quality"));
       resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Worst Move Quality"));
-      resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("Qualities"));
       resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("MoveQualities"));
       resultsCollector.ResultsParameter.ActualName = "Results";
 
+      mainProcessor.Name = "Solution processor (UniformSequentialSubScopesProcessor)";
+
       moveGenerator.Name = "MoveGenerator (placeholder)";
       moveGenerator.OperatorParameter.ActualName = "MoveGenerator";
@@ -121 +155 @@
       moveQualitySorter.ValueParameter.ActualName = "MoveQuality";
 
+      bestAverageWorstMoveQualityCalculator.AverageQualityParameter.ActualName = "Average Move Quality";
+      bestAverageWorstMoveQualityCalculator.BestQualityParameter.ActualName = "Best Move Quality";
+      bestAverageWorstMoveQualityCalculator.MaximizationParameter.ActualName = "Maximization";
+      bestAverageWorstMoveQualityCalculator.QualityParameter.ActualName = "MoveQuality";
+      bestAverageWorstMoveQualityCalculator.WorstQualityParameter.ActualName = "Worst Move Quality";
+
       tabuSelector.Name = "TabuSelector (placeholder)";
       tabuSelector.OperatorParameter.ActualName = "TabuSelector";
 
+      moveMakingProcessor.Name = "MoveMaking processor (UniformSequentialSubScopesProcessor)";
+
+      moveTabuMaker.Name = "MoveTabuMaker (placeholder)";
+      moveTabuMaker.OperatorParameter.ActualName = "MoveTabuMaker";
+
       moveMaker.Name = "MoveMaker (placeholder)";
       moveMaker.OperatorParameter.ActualName = "MoveMaker";
 
-      moveTabuMaker.Name = "MoveTabuMaker (placeholder)";
-      moveTabuMaker.OperatorParameter.ActualName = "MoveTabuMaker";
+      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Move Quality"));
+      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Average Move Quality"));
+      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Worst Move Quality"));
+      valuesCollector.DataTableParameter.ActualName = "MoveQualities";
 
       subScopesRemover.RemoveAllSubScopes = true;
 
+      iterationsCounter.Name = "Iterations Counter";
       iterationsCounter.Increment = new IntData(1);
-      iterationsCounter.IncrementParameter.ActualName = "Iterations";
-
+      iterationsCounter.ValueParameter.ActualName = "Iterations";
+
+      iterationsComparator.Name = "Iterations Comparator";
       iterationsComparator.Comparison = new ComparisonData(Comparison.Less);
       iterationsComparator.LeftSideParameter.ActualName = "Iterations";
@@ -140 +189 @@
       iterationsComparator.ResultParameter.ActualName = "IterationsCondition";
 
+      iterationsTermination.Name = "Iterations Termination Condition";
       iterationsTermination.ConditionParameter.ActualName = "IterationsCondition";
       #endregion
 
       #region Create operator graph
-      OperatorGraph.InitialOperator = variableCreator;
-      variableCreator.Successor = resultsCollector;
-      resultsCollector.Successor = moveGenerator;
+      OperatorGraph.InitialOperator = tabuListCreator;
+      tabuListCreator.Successor = variableCreator;
+      variableCreator.Successor = bestQualityMemorizer;
+      bestQualityMemorizer.Successor = resultsCollector;
+      resultsCollector.Successor = mainProcessor;
+      mainProcessor.Operator = moveGenerator;
+      mainProcessor.Successor = valuesCollector;
       moveGenerator.Successor = moveEvaluationProcessor;
       moveEvaluationProcessor.Operator = moveQualityEvaluator;
+      moveEvaluationProcessor.Successor = moveQualitySorter;
       moveQualityEvaluator.Successor = moveTabuEvaluator;
-      moveEvaluationProcessor.Successor = moveQualitySorter;
-      moveQualitySorter.Successor = tabuSelector;
-      tabuSelector.Successor = moveMakingProcessor;
-      moveMakingProcessor.Operators.AddRange(new Operator[] { emptyOp, actualMoveMakingProcessor });
-      actualMoveMakingProcessor.Operator = moveTabuMaker;
+      moveQualitySorter.Successor = bestAverageWorstMoveQualityCalculator;
+      bestAverageWorstMoveQualityCalculator.Successor = tabuSelector;
+      tabuSelector.Successor = rightReducer;
+      rightReducer.Successor = moveMakingProcessor;
+      moveMakingProcessor.Operator = moveTabuMaker;
+      moveMakingProcessor.Successor = subScopesRemover;
       moveTabuMaker.Successor = moveMaker;
-      moveMakingProcessor.Successor = subScopesRemover;
-      subScopesRemover.Successor = iterationsCounter;
+      valuesCollector.Successor = iterationsCounter;
       iterationsCounter.Successor = iterationsComparator;
       iterationsComparator.Successor = iterationsTermination;
-      iterationsTermination.TrueBranch = resultsCollector;
+      iterationsTermination.TrueBranch = bestQualityMemorizer;
       iterationsTermination.FalseBranch = finished;
       #endregion

trunk/sources/HeuristicLab.Algorithms.TS/3.3/TabuSelector.cs

@@ -40 +40 @@
   public class TabuSelector : Selector {
     /// <summary>
-    /// The quality of the current solution.
-    /// </summary>
-    public LookupParameter<DoubleData> QualityParameter {
-      get { return (LookupParameter<DoubleData>)Parameters["Quality"]; }
-    }
-    /// <summary>
     /// The best found quality so far.
     /// </summary>
@@ -76 +70 @@
     }
 
+    public IntData NumberOfSelectedSubScopes {
+      set { NumberOfSelectedSubScopesParameter.Value = value; }
+    }
+
     /// <summary>
     /// Initializes a new intsance with 6 parameters (<c>Quality</c>, <c>BestQuality</c>,
@@ -82 +80 @@
     public TabuSelector()
       : base() {
-      Parameters.Add(new LookupParameter<DoubleData>("Quality", "The quality of the current solution."));
       Parameters.Add(new LookupParameter<DoubleData>("BestQuality", "The best found quality so far."));
       Parameters.Add(new ValueLookupParameter<BoolData>("Aspiration", "Whether the default aspiration criterion should be used or not. The default aspiration criterion accepts a tabu move if it results in a better solution than the best solution found so far.", new BoolData(true)));
@@ -101 +98 @@
       bool maximization = MaximizationParameter.ActualValue.Value;
       double bestQuality = BestQualityParameter.ActualValue.Value;
-      double quality = QualityParameter.ActualValue.Value;
       ItemArray<DoubleData> moveQualities = MoveQualityParameter.ActualValue;
       ItemArray<BoolData> moveTabus = MoveTabuParameter.ActualValue;
@@ -110 +106 @@
       List<int> scopesToRemove = new List<int>();
       for (int i = 0; i < scopes.Count; i++) {
-        if (count > 0 && (!moveTabus[i].Value || aspiration &&
-          (maximization && moveQualities[i].Value + quality > bestQuality
-          || !maximization && moveQualities[i].Value + quality < bestQuality))) {
+        if (count > 0 && (!moveTabus[i].Value
+          || aspiration && IsBetter(maximization, moveQualities[i].Value, bestQuality))) {
           scopesToRemove.Add(i);
           if (copy) selected[selected.Length - count] = (IScope)scopes[i].Clone();
@@ -133 +128 @@
       return selected;
     }
+
+    private bool IsBetter(bool maximization, double moveQuality, double bestQuality) {
+      return (maximization && moveQuality > bestQuality || !maximization && moveQuality < bestQuality);
+    }
   }
 }