Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/ThreeOpt/TSPTranslocationMovePathEvaluator.cs @ 3376

Last change on this file since 3376 was 3376, checked in by swagner, 14 years ago

Moved interfaces and classes for deep cloning from HeuristicLab.Core to HeuristicLab.Common (#975).

File size: 5.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 System;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30
31namespace HeuristicLab.Problems.TravelingSalesman {
32  /// <summary>
33  /// An operator to evaluate a translocation or insertion move.
34  /// </summary>
35  [Item("TSPTranslocationMovePathEvaluator", "Evaluates a translocation or insertion move (3-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
36  [StorableClass]
37  public abstract class TSPTranslocationMovePathEvaluator : TSPPathMoveEvaluator, IPermutationTranslocationMoveOperator {
38    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
39      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }
40    }
41
42    public TSPTranslocationMovePathEvaluator()
43      : base() {
44      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
45    }
46
47    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
48      TranslocationMove move = TranslocationMoveParameter.ActualValue;
49      int edge1source = permutation.GetCircular(move.Index1 - 1);
50      int edge1target = permutation[move.Index1];
51      int edge2source = permutation[move.Index2];
52      int edge2target = permutation.GetCircular(move.Index2 + 1);
53      int edge3source, edge3target;
54      if (move.Index3 > move.Index1) {
55        edge3source = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
56        edge3target = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
57      } else {
58        edge3source = permutation.GetCircular(move.Index3 - 1);
59        edge3target = permutation[move.Index3];
60      }
61      if (move.Index1 == move.Index3
62        || move.Index2 - move.Index1 >= permutation.Length - 2
63        || move.Index1 == permutation.Length - 1 && move.Index3 == 0
64        || move.Index1 == 0 && move.Index3 == permutation.Length - 1) return 0;
65      double moveQuality = 0;
66      // remove three edges
67      moveQuality -= CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
68        coordinates[edge1target, 0], coordinates[edge1target, 1]);
69      moveQuality -= CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
70        coordinates[edge2target, 0], coordinates[edge2target, 1]);
71      moveQuality -= CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
72        coordinates[edge3target, 0], coordinates[edge3target, 1]);
73      // add three edges
74      moveQuality += CalculateDistance(coordinates[edge3source, 0], coordinates[edge3source, 1],
75        coordinates[edge1target, 0], coordinates[edge1target, 1]);
76      moveQuality += CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
77        coordinates[edge3target, 0], coordinates[edge3target, 1]);
78      moveQuality += CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
79        coordinates[edge2target, 0], coordinates[edge2target, 1]);
80      return moveQuality;
81    }
82
83    protected override double EvaluateByDistanceMatrix(Permutation permutation, DoubleMatrix distanceMatrix) {
84      TranslocationMove move = TranslocationMoveParameter.ActualValue;
85      int edge1source = permutation.GetCircular(move.Index1 - 1);
86      int edge1target = permutation[move.Index1];
87      int edge2source = permutation[move.Index2];
88      int edge2target = permutation.GetCircular(move.Index2 + 1);
89      int edge3source, edge3target;
90      if (move.Index3 > move.Index1) {
91        edge3source = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1);
92        edge3target = permutation.GetCircular(move.Index3 + move.Index2 - move.Index1 + 1);
93      } else {
94        edge3source = permutation.GetCircular(move.Index3 - 1);
95        edge3target = permutation[move.Index3];
96      }
97      if (move.Index1 == move.Index3
98        || move.Index2 - move.Index1 >= permutation.Length - 2
99        || move.Index1 == permutation.Length - 1 && move.Index3 == 0
100        || move.Index1 == 0 && move.Index3 == permutation.Length - 1) return 0;
101      double moveQuality = 0;
102      // remove three edges
103      moveQuality -= distanceMatrix[edge1source, edge1target];
104      moveQuality -= distanceMatrix[edge2source, edge2target];
105      moveQuality -= distanceMatrix[edge3source, edge3target];
106      // add three edges
107      moveQuality += distanceMatrix[edge3source, edge1target];
108      moveQuality += distanceMatrix[edge2source, edge3target];
109      moveQuality += distanceMatrix[edge1source, edge2target];
110      return moveQuality;
111    }
112  }
113}
Note: See TracBrowser for help on using the repository browser.