Changeset 13470 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPAnalyticalTwoPointFiveLocalImprovement.cs

Timestamp:

12/15/15 16:38:08 (9 years ago)

Author:

abeham

Message:

#2221:

• implemented review comments
  • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
  • added missing probabilities
  • base class for instance providers
  • prebuild event events
  • build platforms
  • unit test will be removed on trunk integration
  • corrected assembly file version
  • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
  • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
• added moves (full evaluation) for analytical tsp
• added local improvement operators for analytical ptsp
• added recalculation of distance matrix when parameters change
• still lots of other changes

File:

• branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPAnalyticalTwoPointFiveLocalImprovement.cs (copied) (copied from branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPExhaustiveInversionLocalImprovement.cs) (6 diffs)

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

@@ -38 +38 @@
   /// The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.
   /// </remarks>
-  [Item("PTSPExhaustiveInversionLocalImprovement", "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.")]
+  [Item("PTSP Analytical 2.5 Local Improvement", "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 PTSPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
+  public sealed class PTSPAnalyticalTwoPointFiveLocalImprovement : SingleSuccessorOperator, IAnalyticalPTSPOperator, ILocalImprovementOperator {
 
     public ILookupParameter<IntValue> LocalIterationsParameter {
@@ -74 +74 @@
     }
 
-    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
-      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
+    public ILookupParameter<DoubleArray> ProbabilitiesParameter {
+      get { return (ILookupParameter<DoubleArray>)Parameters["Probabilities"]; }
     }
 
     [StorableConstructor]
-    private PTSPExhaustiveInversionLocalImprovement(bool deserializing) : base(deserializing) { }
-    private PTSPExhaustiveInversionLocalImprovement(PTSPExhaustiveInversionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
-    public PTSPExhaustiveInversionLocalImprovement()
+    private PTSPAnalyticalTwoPointFiveLocalImprovement(bool deserializing) : base(deserializing) { }
+    private PTSPAnalyticalTwoPointFiveLocalImprovement(PTSPAnalyticalTwoPointFiveLocalImprovement original, Cloner cloner) : base(original, cloner) { }
+    public PTSPAnalyticalTwoPointFiveLocalImprovement()
       : base() {
       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
@@ -91 +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 LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
+      Parameters.Add(new LookupParameter<DoubleArray>("Probabilities", "The list of probabilities of the cities to appear."));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new PTSPExhaustiveInversionLocalImprovement(this, cloner);
+      return new PTSPAnalyticalTwoPointFiveLocalImprovement(this, cloner);
     }
 
-    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
+    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, DoubleArray probabilities, CancellationToken cancellation) {
       var distanceM = (DistanceMatrix)distances;
+      Func<int, int, double> distance = (a, b) => distanceM[a, b];
       for (var i = localIterations.Value; i < maxIterations; i++) {
-        InversionMove bestMove = null;
-        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
-        double evaluations = 0.0;
-        foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) {
-          double moveQuality = PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
-          evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length;
+        TwoPointFiveMove bestMove = null;
+        var bestQuality = quality.Value; // we have to make an improvement, so current quality is the baseline
+        var evaluations = 0.0;
+        foreach (var move in ExhaustiveTwoPointFiveMoveGenerator.Generate(assignment)) {
+          var moveQuality = PTSPAnalyticalTwoPointFiveMoveEvaluator.EvaluateMove(assignment, move, distance, probabilities);
+          evaluations++;
           if (maximization && moveQuality > bestQuality
             || !maximization && moveQuality < bestQuality) {
@@ -115 +116 @@
         evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
         if (bestMove == null) break;
-        InversionManipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
-        quality.Value += bestQuality;
+        TwoPointFiveMoveMaker.Apply(assignment, bestMove);
+        quality.Value = bestQuality;
         localIterations.Value++;
         cancellation.ThrowIfCancellationRequested();
@@ -130 +131 @@
       var localIterations = LocalIterationsParameter.ActualValue;
       var evaluations = EvaluatedSolutionsParameter.ActualValue;
-      var realizations = RealizationsParameter.ActualValue;
+      var probabilities = ProbabilitiesParameter.ActualValue;
       if (localIterations == null) {
         localIterations = new IntValue(0);
@@ -136 +137 @@
       }
 
-      Improve(assignment, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken, realizations);
+      Improve(assignment, distances, quality, localIterations, evaluations, maximization, maxIterations, probabilities, CancellationToken);
 
       localIterations.Value = 0;