source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/AnalyticalPTSP.cs @ 12228

Last change on this file since 12228 was 12228, checked in by apolidur, 5 years ago

#2221: Local improvement operator for VNS

File size: 4.3 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 AnalyticalProbabilisticTravelingSalesmanProblem() {
98      Operators.Add(new PTSPAnalyticalInversionMovePathEvaluator());
99    }
100
101    public override void Load(TSPData data) {
102      base.Load(data);
103      foreach (var op in Operators.OfType<PTSPAnalyticalInversionMovePathEvaluator>()) {
104        op.ProbabilitiesParameter.Value = ProbabilityMatrix;
105      }
106    }
107
108  }
109}
Note: See TracBrowser for help on using the repository browser.