source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.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: 5.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Threading.Tasks;
6using HeuristicLab.Optimization;
7using HeuristicLab.PluginInfrastructure;
8using HeuristicLab.Core;
9using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
10using HeuristicLab.Problems.Instances;
11using HeuristicLab.Encodings.PermutationEncoding;
12using HeuristicLab.Common;
13using HeuristicLab.Parameters;
14using HeuristicLab.Data;
15
16namespace HeuristicLab.Problems.PTSP {
17  [Item("Analytical Probabilistic Traveling Salesman Problem", "Represents an analytical Probabilistic Traveling Salesman Problem.")]
18  [Creatable("Problems")]
19  [StorableClass]
20  public sealed class AnalyticalProbabilisticTravelingSalesmanProblem : ProbabilisticTravelingSalesmanProblem, IStorableContent,
21  IProblemInstanceConsumer<TSPData> {
22
23    [StorableConstructor]
24    private AnalyticalProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
25    private AnalyticalProbabilisticTravelingSalesmanProblem(AnalyticalProbabilisticTravelingSalesmanProblem original, Cloner cloner)
26      : base(original, cloner) {
27    }
28
29    public override IDeepCloneable Clone(Cloner cloner) {
30      return new AnalyticalProbabilisticTravelingSalesmanProblem(this, cloner);
31    }
32
33    public override double Evaluate(Individual individual, IRandom random) {
34      Permutation p = individual.Permutation();
35      // Compute A and B matrices
36      DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
37      DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
38      //for (int i = 0; i < p.Length; i++) {
39      //  for (int k = 0; k < p.Length - 1; k++) {
40      //    double firstPartial = 0;
41      //    for (int r = k; k < p.Length - 1; r++) {
42      //       double sum0 = DistanceMatrix[p[i],p[i+r]]* ProbabilityMatrix[0, p[i]] * ProbabilityMatrix[0, p[i+r]];
43      //       for(int s = i+1; s < i+r; s++) {
44      //         sum0 = sum0 * (1 - ProbabilityMatrix[0, p[s]]);
45      //       }
46      //       firstPartial+=sum0;
47      //    }
48      //    double secondPartial = 0;
49      //    for (int r = k; k < p.Length - 1; r++) {
50      //       double sum1 = DistanceMatrix[p[i-r],p[i]]* ProbabilityMatrix[0, p[i-r]] * ProbabilityMatrix[0, p[i]];
51      //       for (int s = i + 1; s < p.Length-1; s++) {
52      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[s]]);
53      //       }
54      //       for (int t = 1; t < i-1; t++) {
55      //         sum1 = sum1 * (1 - ProbabilityMatrix[0, p[t]]);
56      //       }
57      //       secondPartial+=sum1;
58      //    }
59      //    A[i, k] = firstPartial;
60      //    B[i, k] = secondPartial;
61      //  }
62      //}
63     
64      // Analytical evaluation
65      double firstSum = 0;
66      for (int i = 0; i < p.Length - 1; i++) {
67        for (int j = i + 1; j < p.Length - 1; j++) {
68          double sum1 = DistanceMatrix[p[i], p[j]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
69          for (int k = i + 1; k < j; k++) {
70            sum1 = sum1 * (1 - ProbabilityMatrix[p[k]]);
71          }
72          A[i, j - 1] = sum1;
73          firstSum += sum1;
74        }
75      }
76      double secondSum = 0;
77      for (int j = 0; j < p.Length - 1; j++) {
78        for (int i = 0; i < j; i++) {
79          double sum2 = DistanceMatrix[p[j], p[i]] * ProbabilityMatrix[p[i]] * ProbabilityMatrix[p[j]];
80          for (int k = j + 1; k < p.Length - 1; k++) {
81            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
82          }
83          for (int k = 1; k < i; k++) {
84            sum2 = sum2 * (1 - ProbabilityMatrix[p[k]]);
85          }
86          B[i, j] = sum2;
87          secondSum += sum2;
88        }
89      }
90      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
91        op.AParameter.Value = A;
92        op.BParameter.Value = B;
93      }
94      return firstSum + secondSum;
95    }
96
97    public double EvaluateWithParams(DistanceMatrix distances, DoubleArray probabilities, Permutation individual) {
98      Permutation p = individual;
99      // Compute A and B matrices
100      DoubleMatrix A = new DoubleMatrix(p.Length, p.Length - 1);
101      DoubleMatrix B = new DoubleMatrix(p.Length, p.Length - 1);
102      // Analytical evaluation
103      double firstSum = 0;
104      for (int i = 0; i < p.Length; i++) {
105        for (int j = i + 1; j < p.Length; j++) {
106          double sum1 = distances[p[i], p[j]] * probabilities[p[i]] * probabilities[p[j]];
107          for (int k = i + 1; k < j; k++) {
108            sum1 = sum1 * (1 - probabilities[p[k]]);
109          }
110          A[i, j - 1] = sum1;
111          firstSum += sum1;
112        }
113      }
114      double secondSum = 0;
115      for (int j = 0; j < p.Length; j++) {
116        for (int i = 0; i < j; i++) {
117          double sum2 = distances[p[j], p[i]] * probabilities[p[i]] * probabilities[p[j]];
118          for (int k = j + 1; k < p.Length; k++) {
119            sum2 = sum2 * (1 - probabilities[p[k]]);
120          }
121          for (int k = 0; k < i; k++) {
122            sum2 = sum2 * (1 - probabilities[p[k]]);
123          }
124          B[j,i] = sum2;
125          secondSum += sum2;
126        }
127      }
128      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
129        op.AParameter.Value = A;
130        op.BParameter.Value = B;
131      }
132      return firstSum + secondSum;
133    }
134
135    public AnalyticalProbabilisticTravelingSalesmanProblem() {
136      Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());
137    }
138
139    public override void Load(TSPData data) {
140      base.Load(data);
141      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
142        op.ProbabilitiesParameter.Value = ProbabilityMatrix;
143      }
144    }
145
146  }
147}
Note: See TracBrowser for help on using the repository browser.