Changeset 2997

Timestamp:

03/11/10 02:23:25 (15 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

Files:

• HeuristicLab 3.3/Files.txt (modified) (1 diff)
• HeuristicLab.Algorithms.TS/3.3/HeuristicLab.Algorithms.TS-3.3.csproj (modified) (1 diff)
• HeuristicLab.Algorithms.TS/3.3/TSOperator.cs (modified) (8 diffs)
• HeuristicLab.Algorithms.TS/3.3/Tabu Search.hl (added)
• HeuristicLab.Algorithms.TS/3.3/TabuListCreator.cs (added)
• HeuristicLab.Algorithms.TS/3.3/TabuSelector.cs (modified) (6 diffs)
• HeuristicLab.Analysis/3.3/BestQualityMemorizer.cs (added)
• HeuristicLab.Analysis/3.3/HeuristicLab.Analysis-3.3.csproj (modified) (1 diff)
• HeuristicLab.Encodings.Permutation/3.3/HeuristicLab.Encodings.Permutation-3.3.csproj (modified) (2 diffs)
• HeuristicLab.Encodings.Permutation/3.3/Interfaces/IPermutationMoveGenerator.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Manipulators/InversionManipulator.cs (modified) (1 diff)
• HeuristicLab.Encodings.Permutation/3.3/Moves/ExhaustiveTwoOptMoveGenerator.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/Permutation2IndexMove.cs (deleted)
• HeuristicLab.Encodings.Permutation/3.3/Moves/Permutation2OptExhaustiveMoveGenerator.cs (deleted)
• HeuristicLab.Encodings.Permutation/3.3/Moves/Permutation2OptMove.cs (deleted)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoIndexMove.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoOptMove.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoOptMoveMaker.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoOptMoveTabuAttribute.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoOptMoveTabuEvaluator.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Moves/TwoOptMoveTabuMaker.cs (added)
• HeuristicLab.Encodings.Permutation/3.3/Permutation.cs (modified) (1 diff)
• HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj (modified) (1 diff)
• HeuristicLab.Optimization/3.3/Interfaces/IMoveGenerator.cs (added)
• HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.TSP/3.3/MoveEvaluators (added)
• HeuristicLab.Problems.TSP/3.3/MoveEvaluators/TwoOptMoveTSPEvaluator.cs (added)

trunk/sources/HeuristicLab 3.3/Files.txt

@@ -6 +6 @@
 HeuristicLab.Algorithms.SGA\3.3:HeuristicLab.Algorithms.SGA-3.3.dll
 HeuristicLab.Algorithms.SGA.Views\3.3:HeuristicLab.Algorithms.SGA.Views-3.3.dll
+HeuristicLab.Algorithms.TS\3.3:HeuristicLab.Algorithms.TS-3.3.dll
 HeuristicLab.Analysis\3.3:HeuristicLab.Analysis-3.3.dll
 HeuristicLab.Analysis.Views\3.3:HeuristicLab.Analysis.Views-3.3.dll

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);
+    }
   }
 }

trunk/sources/HeuristicLab.Analysis/3.3/HeuristicLab.Analysis-3.3.csproj

@@ -85 +85 @@
     <None Include="HeuristicLabAnalysisPlugin.cs.frame" />
     <Compile Include="BestAverageWorstQualityCalculator.cs" />
+    <Compile Include="BestQualityMemorizer.cs" />
     <Compile Include="DataRow.cs" />
     <Compile Include="HeuristicLabAnalysisPlugin.cs" />

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

@@ -96 +96 @@
     <Compile Include="Interfaces\IPermutationCrossover.cs" />
     <Compile Include="Interfaces\IPermutationManipulator.cs" />
+    <Compile Include="Interfaces\IPermutationMoveGenerator.cs" />
     <Compile Include="Interfaces\IPermutationOperator.cs" />
     <Compile Include="Manipulators\InsertionManipulator.cs" />
@@ -104 +105 @@
     <Compile Include="Manipulators\TranslocationInversionManipulator.cs" />
     <Compile Include="Manipulators\TranslocationManipulator.cs" />
-    <Compile Include="Moves\Permutation2IndexMove.cs" />
-    <Compile Include="Moves\Permutation2OptExhaustiveMoveGenerator.cs" />
-    <Compile Include="Moves\Permutation2OptMove.cs" />
+    <Compile Include="Moves\ExhaustiveTwoOptMoveGenerator.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoIndexMove.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoOptMove.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoOptMoveMaker.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoOptMoveTabuAttribute.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoOptMoveTabuEvaluator.cs">
+      <SubType>Code</SubType>
+    </Compile>
+    <Compile Include="Moves\TwoOptMoveTabuMaker.cs">
+      <SubType>Code</SubType>
+    </Compile>
     <Compile Include="PermutationManipulator.cs" />
     <Compile Include="PermutationCrossover.cs" />

trunk/sources/HeuristicLab.Encodings.Permutation/3.3/Manipulators/InversionManipulator.cs

@@ -47 +47 @@
       } while (breakPoint2 == breakPoint1);
       if (breakPoint2 < breakPoint1) { int h = breakPoint1; breakPoint1 = breakPoint2; breakPoint2 = h; }
+      Apply(permutation, breakPoint1, breakPoint2);
+    }
 
+    public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2) {
       for (int i = 0; i <= (breakPoint2 - breakPoint1) / 2; i++) {  // invert permutation between breakpoints
         int temp = permutation[breakPoint1 + i];

trunk/sources/HeuristicLab.Encodings.Permutation/3.3/Permutation.cs

@@ -85 +85 @@
     }
 
+    public int GetCircular(int position) {
+      if (position >= Length) position = position % Length;
+      while (position < 0) position += Length;
+      return this[position];
+    }
+
     #region IStringConvertibleArrayData Members
     int IStringConvertibleArrayData.Length {

trunk/sources/HeuristicLab.Optimization/3.3/HeuristicLab.Optimization-3.3.csproj

@@ -86 +86 @@
     <None Include="HeuristicLabOptimizationPlugin.cs.frame" />
     <Compile Include="Algorithm.cs" />
+    <Compile Include="Interfaces\IMoveGenerator.cs" />
     <Compile Include="Interfaces\IMultiObjectiveSelector.cs" />
     <Compile Include="Interfaces\ISingleObjectiveSelector.cs" />

trunk/sources/HeuristicLab.Problems.TSP/3.3/HeuristicLab.Problems.TSP-3.3.csproj

@@ -93 +93 @@
     <Compile Include="Interfaces\ITSPPathEvaluator.cs" />
     <Compile Include="HeuristicLabProblemsTSPPlugin.cs" />
+    <Compile Include="MoveEvaluators\TwoOptMoveTSPEvaluator.cs">
+      <SubType>Code</SubType>
+    </Compile>
     <Compile Include="TSPLIBParser.cs" />
     <Compile Include="TSP.cs" />