source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/EstimatedPTSP.cs @ 12269

Last change on this file since 12269 was 12269, checked in by apolidur, 6 years ago

#2221: Adding Tests and Views for PTSP

File size: 6.6 KB
Line 
1using System.Text;
2using System.Threading.Tasks;
3using HeuristicLab.Optimization;
4using HeuristicLab.PluginInfrastructure;
5using HeuristicLab.Core;
6using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
7using HeuristicLab.Problems.Instances;
8using HeuristicLab.Encodings.PermutationEncoding;
9using HeuristicLab.Common;
10using HeuristicLab.Parameters;
11using HeuristicLab.Data;
12using HeuristicLab.Random;
13using System;
14using System.Linq;
15
16namespace HeuristicLab.Problems.PTSP {
17  [Item("Estimated Probabilistic Traveling Salesman Problem", "Represents an estimated Probabilistic Traveling Salesman Problem.")]
18  [Creatable("Problems")]
19  [StorableClass]
20  public sealed class EstimatedProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
21  IProblemInstanceConsumer<TSPData> {
22
23    private ItemList<ItemList<IntValue>> realizations;
24
25    [StorableConstructor]
26    private EstimatedProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
27    private EstimatedProbabilisticTravelingSalesmanProblem(EstimatedProbabilisticTravelingSalesmanProblem original, Cloner cloner)
28      : base(original, cloner) {
29    }
30
31    public override IDeepCloneable Clone(Cloner cloner) {
32      return new EstimatedProbabilisticTravelingSalesmanProblem(this, cloner);
33    }
34
35    public override double Evaluate(Individual individual, IRandom random) {
36      Permutation p = individual.Permutation();
37      // Estimation-based evaluation
38      MersenneTwister r = new MersenneTwister();
39      double estimatedSum = 0;
40      for (int i = 0; i < realizations.Count; i++) {
41        int singleRealization = -1, firstNode = -1;
42        for (int j = 0; j < realizations[i].Count; j++) {
43          if (realizations[i][p[j]].Value == 1) {
44            if (singleRealization != -1) {
45              estimatedSum += DistanceMatrix[singleRealization, p[j]];
46            } else {
47              firstNode = p[j];
48            }
49            singleRealization = p[j];
50          }
51        }
52        if (singleRealization != -1) {
53          estimatedSum += DistanceMatrix[singleRealization, firstNode];
54        }
55      }
56      return estimatedSum / SampleSize.Value;
57    }
58
59    public double[] EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, ItemList<ItemList<IntValue>> realizations, Permutation individual ) {
60      // Estimation-based evaluation
61      MersenneTwister r = new MersenneTwister();
62      double estimatedSum = 0;
63      double[] partialSums = new double[realizations.Count];
64      for (int i = 0; i < realizations.Count; i++) {
65        partialSums[i] = 0;
66        int singleRealization = -1, firstNode = -1;
67        for (int j = 0; j < realizations[i].Count; j++) {
68          if (realizations[i][individual[j]].Value == 1) {
69            if (singleRealization != -1) {
70              partialSums[i] += distances[singleRealization, individual[j]];
71            } else {
72              firstNode = individual[j];
73            }
74            singleRealization = individual[j];
75          }
76        }
77        if (singleRealization != -1) {
78          partialSums[i] += distances[singleRealization, firstNode];
79        }
80        estimatedSum += partialSums[i];
81      }
82      double mean = estimatedSum / realizations.Count;
83      double variance = 0;
84      for (int i = 0; i < realizations.Count; i++) {
85        variance += Math.Pow((partialSums[i] - mean), 2);
86      }
87      variance = variance / realizations.Count;
88      return new double[] {mean,variance};
89    }
90
91    public EstimatedProbabilisticTravelingSalesmanProblem() {
92      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Size of the sample for the estimation-based evaluation"));
93      Operators.Add(new PTSPEstimatedInversionMovePathEvaluator());
94      Operators.Add(new PTSPEstimatedInsertionEvaluator());
95      Operators.Add(new PTSPExhaustiveInversionLocalImprovement());
96      Operators.Add(new PTSPExhaustiveInsertionLocalImprovement());
97      Encoding.ConfigureOperators(Operators.OfType<IOperator>());
98    }
99
100    private int Ttest(int ProblemSize) {
101      MersenneTwister random = new MersenneTwister();
102      Permutation p1 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
103      Permutation p2 = new Permutation(PermutationTypes.RelativeUndirected, ProblemSize, random);
104      ItemList<ItemList<IntValue>> realizations = new ItemList<ItemList<IntValue>>();
105      int index = -1;
106      while (true) {
107        for (int i = index+1; i < index+5; i++) {
108          realizations.Add(new ItemList<IntValue>());
109          for (int j = 0; j < ProblemSize; j++) {
110            if (ProbabilityMatrix[j] > random.NextDouble()) {
111              realizations.ElementAt(i).Add(new IntValue(1));
112            } else {
113              realizations.ElementAt(i).Add(new IntValue(0));
114            }
115          }
116        }
117        index += 4;
118        double[] eval1 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p1);
119        double[] eval2 = EvaluateWithParams(DistanceMatrix, ProbabilityMatrix, realizations, p2);
120        double sx1x2 = Math.Sqrt((eval1[1]+eval2[1])/2);
121        int degrees = 2 * realizations.Count - 2;
122        double t = (eval1[0]-eval2[0])/(sx1x2*Math.Sqrt(2.0/(double)realizations.Count));
123      }
124    }
125
126    public override void Load(TSPData data) {
127      base.Load(data);
128      // For now uses sample size of 20 but should use Student's t-test
129      //Ttest(data.Dimension);
130      SampleSize = new IntValue(100);
131      MersenneTwister r = new MersenneTwister();
132      int countOnes = 0;
133      realizations = new ItemList<ItemList<IntValue>>(SampleSize.Value);
134      for (int i = 0; i < SampleSize.Value; i++) {
135        ItemList<IntValue> newRealization = new ItemList<IntValue>();
136        while (countOnes < 4) { //only generate realizations with at least 4 cities visited
137          countOnes = 0;
138          newRealization.Clear();
139          for (int j = 0; j < data.Dimension; j++) {
140            if (ProbabilityMatrix[j] > r.NextDouble()) {
141              newRealization.Add(new IntValue(1));
142              countOnes++;
143            } else {
144              newRealization.Add(new IntValue(0));
145            }
146          }
147        }
148        countOnes = 0;
149        realizations.Add(newRealization);
150      }
151
152      foreach (var op in Operators.OfType<PTSPPathMoveEvaluator>()) {
153        op.RealizationsParameter.Value = realizations;
154      }
155      foreach (var op in Operators.OfType<PTSPExhaustiveInversionLocalImprovement>()) {
156        op.RealizationsParameter.Value = realizations;
157      }
158    }
159  }
160}
Note: See TracBrowser for help on using the repository browser.