Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/TwoOpt/PTSPAnalyticalInversionMovePathEvaluator.cs @ 12228

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

#2221: Local improvement operator for VNS

File size: 7.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Parameters;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using System;
29namespace HeuristicLab.Problems.PTSP {
30  /// <summary>
31  /// An operator to evaluate inversion moves (2-opt).
32  /// </summary>
33  [Item("PTSPAnalyticalInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) of the PTSP in with the closed form expression")]
34  [StorableClass]
35  public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator {
36
37    private static DoubleArray probabilities;
38    private static DoubleMatrix A;
39    private static DoubleMatrix B;
40
41    public override Type EvaluatorType {
42      get { return typeof(PTSPAnalyticalInversionMovePathEvaluator); }
43    }
44    public ILookupParameter<InversionMove> InversionMoveParameter {
45      get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
46    }
47
48    public IValueParameter<DoubleArray> ProbabilitiesParameter {
49      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
50    }
51
52    public IValueParameter<DoubleMatrix> AParameter {
53      get { return (IValueParameter<DoubleMatrix>)Parameters["A"]; }
54    }
55
56    public IValueParameter<DoubleMatrix> BParameter {
57      get { return (IValueParameter<DoubleMatrix>)Parameters["B"]; }
58    }
59
60    [StorableConstructor]
61    protected PTSPAnalyticalInversionMovePathEvaluator(bool deserializing) : base(deserializing) { }
62    protected PTSPAnalyticalInversionMovePathEvaluator(PTSPAnalyticalInversionMovePathEvaluator original, Cloner cloner) : base(original, cloner) { }
63    public PTSPAnalyticalInversionMovePathEvaluator()
64      : base() {
65      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
66      Parameters.Add(new ValueParameter<ItemList<DoubleValue>>("Probabilities", "The probabilities of the current instance"));
67      Parameters.Add(new ValueParameter<DoubleMatrix>("A", "The matrix A for delta evaluation"));
68      Parameters.Add(new ValueParameter<DoubleMatrix>("B", "The matrix B for delta evaluation"));
69    }
70
71    public override IDeepCloneable Clone(Cloner cloner) {
72      return new PTSPAnalyticalInversionMovePathEvaluator(this, cloner);
73    }
74
75    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPAnalyticalInversionMovePathEvaluator evaluator) {
76      int edge1source = permutation.GetCircular(move.Index1 - 1);
77      int edge1target = permutation[move.Index1];
78      int edge2source = permutation[move.Index2];
79      int edge2target = permutation.GetCircular(move.Index2 + 1);
80      if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
81      double moveQuality = 0;
82      // remove two edges
83      moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
84            coordinates[edge1target, 0], coordinates[edge1target, 1]);
85      moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
86        coordinates[edge2target, 0], coordinates[edge2target, 1]);
87      // add two edges
88      moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
89        coordinates[edge2source, 0], coordinates[edge2source, 1]);
90      moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
91        coordinates[edge2target, 0], coordinates[edge2target, 1]);
92      return moveQuality;
93    }
94
95    public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix) {
96      int i = move.Index1;
97      int j = move.Index2;
98      return RecursiveExpectedCost(1, i, j) + RecursiveExpectedCost(2, i, j) - RecursiveExpectedCost(3, i, j);
99    }
100
101    protected static double RecursiveExpectedCost(int s, int i, int j) {
102      switch (s) {
103        case 1:
104          if (j == i + 1) {
105            return (1/(1-probabilities[i+1]))*A[i,2]+(1 - probabilities[i])*(A[i+1,1]-A[i+1,probabilities.Length-1]);
106          } else if (i == j) {
107            return A[i,1];
108          } else {
109            // Equation 25
110            return ((1 - probabilities[i]) / (1 - probabilities[j])) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i]) * (1);
111          }
112         
113        case 2:
114          if (j == i + 1) {
115            return (1 - probabilities[i + 1]) * (B[i, 1] - B[i, probabilities.Length - 1]) + (1 / (1 - probabilities[i])) * (B[i + 1, 2]);
116          } else if (i == j) {
117            return B[i,1];
118          } else {
119            return 0;
120            // Equation 26
121          }
122
123        case 3:
124          if (j == i + 1) {
125            return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Length - 1] + B[i, 1] - B[i, probabilities.Length - 1] + B[i + 1, 2];
126          } else if (i == j) {
127            return A[i,1]+B[i,1];
128          } else {
129            return 0;
130            // Equation 27
131          }
132        default:
133          return 0;
134      }
135    }
136
137    private double Q(int i, int j, DoubleArray probabilities) {
138      double prod = 1;
139      for (int k = i; k <= j; k++) {
140        prod *= (1 - probabilities[k]);
141      }
142      return prod;
143    }
144
145    private double Q_hat(int i, int j, DoubleArray probabilities) {
146      double prod = 1;
147      for (int k = i; k <= j; k++) {
148        prod *= (1-probabilities[k]);
149      }
150      return prod;
151    }
152
153    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
154      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
155    }
156
157    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
158      A = AParameter.Value;
159      B = BParameter.Value;
160      probabilities = ProbabilitiesParameter.Value;
161      return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix);
162    }
163
164    protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
165      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
166    }
167  }
168}
Note: See TracBrowser for help on using the repository browser.