Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/MoveEvaluators/OneShift/PTSPEstimatedInsertionEvaluator.cs @ 12272

Last change on this file since 12272 was 12272, checked in by apolidur, 9 years ago

#2221: Adding 2.5-opt-EEs operators to PTSP
File size: 8.7 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;
29
30namespace HeuristicLab.Problems.PTSP {
31  [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
32  [StorableClass]
33  public class PTSPEstimatedInsertionEvaluator : PTSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
34
35    public override Type EvaluatorType {
36      get { return typeof(PTSPEstimatedInsertionEvaluator); }
37    }
38    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
39      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }
40    }
41
42    public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
43      get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
44    }
45
46    [StorableConstructor]
47    protected PTSPEstimatedInsertionEvaluator(bool deserializing) : base(deserializing) { }
48    protected PTSPEstimatedInsertionEvaluator(PTSPEstimatedInsertionEvaluator original, Cloner cloner) : base(original, cloner) { }
49    public PTSPEstimatedInsertionEvaluator()
50      : base() {
51      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
52    }
53
54    public override IDeepCloneable Clone(Cloner cloner) {
55      return new PTSPEstimatedInsertionEvaluator(this, cloner);
56    }
57
58    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, PTSPEstimatedInsertionEvaluator evaluator) {
59      int edge1source = permutation.GetCircular(move.Index1 - 1);
60      int edge1target = permutation[move.Index1];
61      int edge2source = permutation[move.Index2];
62      int edge2target = permutation.GetCircular(move.Index2 + 1);
63      if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
64      double moveQuality = 0;
65      // remove two edges
66      moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
67            coordinates[edge1target, 0], coordinates[edge1target, 1]);
68      moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
69        coordinates[edge2target, 0], coordinates[edge2target, 1]);
70      // add two edges
71      moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
72        coordinates[edge2source, 0], coordinates[edge2source, 1]);
73      moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
74        coordinates[edge2target, 0], coordinates[edge2target, 1]);
75      return moveQuality;
76    }
77
78    public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
79      Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected,permutation);
80      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
81      double moveQuality = 0;
82      int[] edges = new int[12];
83      int[] indices = new int[12];
84      edges[0] = permutation.GetCircular(move.Index1 - 1);
85      indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
86      edges[1] = permutation[move.Index1];
87      indices[1] = move.Index1;
88      edges[2] = permutation[move.Index1];
89      indices[2] = move.Index1;
90      edges[3] = permutation.GetCircular(move.Index1 + 1);
91      indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
92
93      edges[6] = afterMove.GetCircular(move.Index3 - 1);
94      indices[6] = decreaseCircularIndex(afterMove.Length, move.Index3);
95      edges[7] = afterMove[move.Index3];
96      indices[7] = move.Index3;
97      edges[8] = afterMove[move.Index3];
98      indices[8] = move.Index3;
99      edges[9] = afterMove.GetCircular(move.Index3 + 1);
100      indices[9] = increaseCircularIndex(afterMove.Length, move.Index3);
101
102      if (move.Index3 > move.Index1) {
103        edges[4] = permutation[move.Index3];
104        indices[4] = move.Index3;
105        edges[5] = permutation.GetCircular(move.Index3 + 1);
106        indices[5] = indices[9];
107        edges[10] = afterMove.GetCircular(move.Index1 - 1);
108        indices[10] = indices[0];
109        edges[11] = afterMove[move.Index1];
110        indices[11] = move.Index1;
111      } else {
112        edges[4] = permutation.GetCircular(move.Index3 - 1);
113        indices[4] = indices[6];
114        edges[5] = permutation[move.Index3];
115        indices[5] = move.Index3;
116        edges[10] = afterMove[move.Index1];
117        indices[10] = move.Index1;
118        edges[11] = afterMove.GetCircular(move.Index1 + 1);
119        indices[11] = indices[3];
120      }
121      int[] aPosteriori = new int[12];
122      Permutation tempPermutation;
123      foreach (ItemList<IntValue> realization in realizations) {
124        for (int i = 0; i < edges.Length; i++) {
125          if (i < 6) {
126            tempPermutation = permutation;
127          } else {
128            tempPermutation = afterMove;
129          }
130          if (realization[edges[i]].Value == 1) {
131            aPosteriori[i] = edges[i];
132          } else {
133            int j=1;
134            if (i%2==0) {
135              // find nearest predecessor in realization if source edge
136              while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
137                j++;
138              }
139              aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
140            } else {
141              // find nearest successor in realization if target edge
142              while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
143                j++;
144              }
145              aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
146            }
147          }
148        }
149        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
150          !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
151          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
152          // compute cost difference between the two a posteriori solutions
153          moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
154          moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
155        }
156        Array.Clear(aPosteriori, 0, aPosteriori.Length);
157      }
158      // return average of cost differences
159      return moveQuality / realizations.Capacity;
160    }
161
162    private static int decreaseCircularIndex(int length, int index) {
163      int result = index - 1;
164      if (result == -1) {
165        result = length - 1;
166      }
167      return result;
168    }
169
170    private static int increaseCircularIndex(int length, int index) {
171      int result = index + 1;
172      if (result == length + 1) {
173        result = 0;
174      }
175      return result;
176    }
177
178    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
179      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, this);
180    }
181
182    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
183      return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
184    }
185
186    protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
187      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
188    }
189  }
190}
Note: See TracBrowser for help on using the repository browser.