Changeset 13412 for branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.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/EstimatedPTSP.cs (modified) (4 diffs)

branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs

@@ -1 @@
-using System.Text;
-using System.Threading.Tasks;
-using HeuristicLab.Optimization;
-using HeuristicLab.PluginInfrastructure;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
+using System.Linq;
+using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.Instances;
-using HeuristicLab.Encodings.PermutationEncoding;
-using HeuristicLab.Common;
-using HeuristicLab.Parameters;
-using HeuristicLab.Data;
 using HeuristicLab.Random;
-using System;
-using System.Linq;
 
 namespace HeuristicLab.Problems.PTSP {
-  [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
-  [Creatable("Problems")]
+  [Item("Estimated Probabilistic Traveling Salesman Problem (PTSP)", "Represents a probabilistic traveling salesman problem where the expected tour length is estimated by averaging over the length of tours on a number of, so called, realizations.")]
+  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
   [StorableClass]
-  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
-  IProblemInstanceConsumer<PTSPData> {
-
+  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem {
 
     #region Parameter Properties
-    public ValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
-      get { return (ValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
-    }
-    public ValueParameter<IntValue> RealizationsSizeParameter {
-      get { return (ValueParameter<IntValue>)Parameters["RealizationsSize"]; }
-    }
-
+    public IValueParameter<ItemList<BoolArray>> RealizationsParameter {
+      get { return (IValueParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
+    }
+    public IFixedValueParameter<IntValue> RealizationsSizeParameter {
+      get { return (IFixedValueParameter<IntValue>)Parameters["RealizationsSize"]; }
+    }
     #endregion
 
     #region Properties
-    public ItemList<ItemList<IntValue>> Realizations {
+    public ItemList<BoolArray> Realizations {
       get { return RealizationsParameter.Value; }
       set { RealizationsParameter.Value = value; }
     }
 
-    public IntValue RealizationsSize {
-      get { return RealizationsSizeParameter.Value; }
-      set { RealizationsSizeParameter.Value = value; }
+    public int RealizationsSize {
+      get { return RealizationsSizeParameter.Value.Value; }
+      set { RealizationsSizeParameter.Value.Value = value; }
     }
     #endregion
@@ -51 +65 @@
     }
     public EstimatedProbabilisticTravelingSalesmanProblem() {
-      Parameters.Add(new ValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation"));
-      Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
-
-      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
-      Operators.RemoveAll(x => x is IMoveGenerator);
-      Operators.RemoveAll(x => x is IMoveMaker);
+      Parameters.Add(new FixedValueParameter<IntValue>("RealizationsSize", "Size of the sample for the estimation-based evaluation", new IntValue(100)));
+      Parameters.Add(new ValueParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances.", new ItemList<BoolArray>()));
 
       Operators.Add(new BestPTSPSolutionAnalyzer());
 
-      Operators.Add(new PTSPEstimatedInversionEvaluator());
-      Operators.Add(new PTSPEstimatedInsertionEvaluator());
+      Operators.Add(new PTSPEstimatedInversionMoveEvaluator());
+      Operators.Add(new PTSPEstimatedInsertionMoveEvaluator());
       Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
       Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
 
-      Operators.Add(new Exhaustive25MoveGenerator());
-      Operators.Add(new Stochastic25MultiMoveGenerator());
-      Operators.Add(new Stochastic25SingleMoveGenerator());
+      Operators.Add(new ExhaustiveTwoPointFiveMoveGenerator());
+      Operators.Add(new StochasticTwoPointFiveMultiMoveGenerator());
+      Operators.Add(new StochasticTwoPointFiveSingleMoveGenerator());
       Operators.Add(new TwoPointFiveMoveMaker());
-      Operators.Add(new PTSP25MoveEvaluator());
+      Operators.Add(new PTSPTwoPointFiveMoveEvaluator());
 
       Encoding.ConfigureOperators(Operators.OfType<IOperator>());
-      foreach (var twopointfiveMoveOperator in Operators.OfType<I25MoveOperator>()) {
+      foreach (var twopointfiveMoveOperator in Operators.OfType<ITwoPointFiveMoveOperator>()) {
         twopointfiveMoveOperator.TwoPointFiveMoveParameter.ActualName = "Permutation.TwoPointFiveMove";
       }
-      RealizationsSize = new IntValue(100);
+
       RegisterEventHandlers();
     }
@@ -83 +93 @@
     }
 
-    public override double Evaluate(Individual individual, IRandom random) {
-      Permutation p = individual.Permutation();
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      RegisterEventHandlers();
+    }
+
+    private void RegisterEventHandlers() {
+      RealizationsSizeParameter.Value.ValueChanged += RealizationsSizeParameter_ValueChanged;
+    }
+
+    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
+      UpdateRealizations();
+    }
+
+    public override double Evaluate(Permutation tour, IRandom random) {
       // Estimation-based evaluation
-      MersenneTwister r = new MersenneTwister();
-      double estimatedSum = 0;
-      for (int i = 0; i < Realizations.Count; i++) {
+      var estimatedSum = 0.0;
+      for (var i = 0; i < Realizations.Count; i++) {
         int singleRealization = -1, firstNode = -1;
-        for (int j = 0; j < Realizations[i].Count; j++) {
-          if (Realizations[i][p[j]].Value == 1) {
+        for (var j = 0; j < Realizations[i].Length; j++) {
+          if (Realizations[i][tour[j]]) {
             if (singleRealization != -1) {
-              estimatedSum += DistanceMatrix[singleRealization, p[j]];
+              estimatedSum += GetDistance(singleRealization, tour[j]);
             } else {
-              firstNode = p[j];
+              firstNode = tour[j];
             }
-            singleRealization = p[j];
+            singleRealization = tour[j];
           }
         }
         if (singleRealization != -1) {
-          estimatedSum += DistanceMatrix[singleRealization, firstNode];
-        }
-      }
-      return estimatedSum / RealizationsSize.Value;
-    }
-
-    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
+          estimatedSum += GetDistance(singleRealization, firstNode);
+        }
+      }
+      return estimatedSum / RealizationsSize;
+    }
+
+    /// <summary>
+    /// An evaluate method that can be used if mean as well as variance should be calculated
+    /// </summary>
+    /// <param name="tour">The tour between all cities.</param>
+    /// <param name="distanceMatrix">The distances between the cities.</param>
+    /// <param name="realizations">A sample of realizations of the stochastic instance</param>
+    /// <returns>A vector with length two containing mean and variance.</returns>
+    public static double[] Evaluate(Permutation tour, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
       // Estimation-based evaluation
-      MersenneTwister r = new MersenneTwister();
-      double estimatedSum = 0;
-      double[] partialSums = new double[realizations.Count];
-      for (int i = 0; i < realizations.Count; i++) {
+      var estimatedSum = 0.0;
+      var partialSums = new double[realizations.Count];
+      for (var i = 0; i < realizations.Count; i++) {
         partialSums[i] = 0;
         int singleRealization = -1, firstNode = -1;
-        for (int j = 0; j < realizations[i].Count; j++) {
-          if (realizations[i][individual[j]].Value == 1) {
+        for (var j = 0; j < realizations[i].Length; j++) {
+          if (realizations[i][tour[j]]) {
             if (singleRealization != -1) {
-              partialSums[i] += distances[singleRealization, individual[j]];
+              partialSums[i] += distanceMatrix[singleRealization, tour[j]];
             } else {
-              firstNode = individual[j];
+              firstNode = tour[j];
             }
-            singleRealization = individual[j];
+            singleRealization = tour[j];
           }
         }
         if (singleRealization != -1) {
-          partialSums[i] += distances[singleRealization, firstNode];
+          partialSums[i] += distanceMatrix[singleRealization, firstNode];
         }
         estimatedSum += partialSums[i];
       }
-      double mean = estimatedSum / realizations.Count;
-      double variance = 0;
-      for (int i = 0; i < realizations.Count; i++) {
+      var mean = estimatedSum / realizations.Count;
+      var variance = 0.0;
+      for (var i = 0; i < realizations.Count; i++) {
         variance += Math.Pow((partialSums[i] - mean), 2);
       }
       variance = variance / realizations.Count;
-      return new double[] {mean,variance};
-    }
-
-    
-
-    private void RegisterEventHandlers() {
-      //RealizationsSizeParameter.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
-      RealizationsSize.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
-      //RealizationsSizeParameter.Value.ValueChanged += new EventHandler(RealizationsSizeParameter_ValueChanged);
-    }
-
-    private void RealizationsSizeParameter_ValueChanged(object sender, EventArgs e) {
-      UpdateRealizations();
+      return new[] { mean, variance };
+    }
+
+    public double GetDistance(int from, int to) {
+      if (UseDistanceMatrix) return DistanceMatrix[from, to];
+      return DistanceCalculator.Calculate(from, to, Coordinates);
     }
 
     private void UpdateRealizations() {
-      MersenneTwister r = new MersenneTwister();
-      int countOnes = 0;
-      Realizations = new ItemList<ItemList<IntValue>>(RealizationsSize.Value);
-      for (int i = 0; i < RealizationsSize.Value; i++) {
-        ItemList<IntValue> newRealization = new ItemList<IntValue>();
-        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
+      var realizations = new ItemList<BoolArray>(RealizationsSize);
+      var rand = new MersenneTwister();
+      for (var i = 0; i < RealizationsSize; i++) {
+        var newRealization = new BoolArray(Probabilities.Length);
+        var countOnes = 0;
+        while (countOnes < 4) { // only generate realizations with at least 4 cities visited
           countOnes = 0;
-          newRealization.Clear();
-          for (int j = 0; j < DistanceMatrix.Rows; j++) {
-            if (ProbabilityMatrix[j] > r.NextDouble()) {
-              newRealization.Add(new IntValue(1));
-              countOnes++;
-            } else {
-              newRealization.Add(new IntValue(0));
-            }
+          for (var j = 0; j < Probabilities.Length; j++) {
+            newRealization[j] = Probabilities[j] < rand.NextDouble();
+            if (newRealization[j]) countOnes++;
           }
         }
-        countOnes = 0;
         Realizations.Add(newRealization);
       }
+      Realizations = realizations;
     }
 
@@ -178 +193 @@
       UpdateRealizations();
 
-      foreach (var op in Operators.OfType<PTSPMoveEvaluator>()) {
-        op.RealizationsParameter.Value = Realizations;
-      }
-      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
-        op.RealizationsParameter.Value = Realizations;
-      }
-      foreach (var op in Operators.OfType<PTSP25MoveEvaluator>()) {
-        op.RealizationsParameter.Value = Realizations;
-      }
-
+      foreach (var op in Operators.OfType<IEstimatedPTSPOperator>()) {
+        op.RealizationsParameter.ActualName = RealizationsParameter.Name;
+      }
     }
   }