Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs

Timestamp:

11/28/15 23:38:51 (8 years ago)

Author:

abeham

Message:

#2221:

• Completely refactored PTSP branch
  • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
  • Implemented missing EvaluateByCoordinates for 1-shift moves
  • Made it clear that move evaluators are for estimated PTSP only
  • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
  • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
  • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
  • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types

File:

• branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs (modified) (7 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInsertionLocalImprovement.cs

@@ -21 +21 @@
 
 using System;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -29 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using System.Threading;
 
 namespace HeuristicLab.Problems.PTSP {
@@ -36 +36 @@
   /// </summary>
   /// <remarks>
-  /// The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.
+  /// The operator tries to improve the probabilistic traveling salesman solution by inserting a city in the tour between two other cities for a certain number of times.
   /// </remarks>
   [Item("PTSPExhaustiveInsertionLocalImprovement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
   [StorableClass]
-  public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator {
-  
+  public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
+
     public ILookupParameter<IntValue> LocalIterationsParameter {
       get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
@@ -74 +74 @@
     }
 
-    public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
-      get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
+    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
+      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
     }
 
     [StorableConstructor]
-    protected PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
-    protected PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner)
-      : base(original, cloner) {
-    }
+    private PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
+    private PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
     public PTSPExhaustiveInsertionLocalImprovement()
       : base() {
@@ -93 +91 @@
       Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
       Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
-      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
+      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
     }
 
@@ -100 +98 @@
     }
 
-    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<ItemList<IntValue>> realizations) {
-      DistanceMatrix distanceM = (DistanceMatrix)distances;
-      for (int i = localIterations.Value; i < maxIterations; i++) {
+    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
+      var distanceM = (DistanceMatrix)distances;
+      for (var i = localIterations.Value; i < maxIterations; i++) {
         TranslocationMove bestMove = null;
         double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
         double evaluations = 0.0;
         foreach (var move in ExhaustiveInsertionMoveGenerator.Generate(assignment)) {
-          double moveQuality = PTSPEstimatedInsertionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
+          double moveQuality = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
           int min = Math.Min(move.Index1, move.Index3);
           int max = Math.Max(move.Index2, move.Index3 + (move.Index2 - move.Index1));
@@ -135 +133 @@
       var localIterations = LocalIterationsParameter.ActualValue;
       var evaluations = EvaluatedSolutionsParameter.ActualValue;
-      var realizations = RealizationsParameter.Value;
+      var realizations = RealizationsParameter.ActualValue;
       if (localIterations == null) {
         localIterations = new IntValue(0);