1 | using System.Text;
|
---|
2 | using System.Threading.Tasks;
|
---|
3 | using HeuristicLab.Optimization;
|
---|
4 | using HeuristicLab.PluginInfrastructure;
|
---|
5 | using HeuristicLab.Core;
|
---|
6 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
7 | using HeuristicLab.Problems.Instances;
|
---|
8 | using HeuristicLab.Encodings.PermutationEncoding;
|
---|
9 | using HeuristicLab.Common;
|
---|
10 | using HeuristicLab.Parameters;
|
---|
11 | using HeuristicLab.Data;
|
---|
12 | using HeuristicLab.Random;
|
---|
13 | using System;
|
---|
14 | using System.Linq;
|
---|
15 |
|
---|
16 | namespace 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 | } |
---|