Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/01/15 00:36:27 (9 years ago)
Author:
abeham
Message:

#2481:

  • Implemented TSPTranslocationMoveDistanceMatrixEvaluator
  • Implemented TSPInversionMoveDistanceMatrixEvaluator
  • Changed move check in TravelingSalesmanProblem to include all ITSPMoveEvaluators
File:
1 copied

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/ThreeOpt/TSPTranslocationMoveDistanceMatrixEvaluator.cs

    r12971 r12978  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     
    3132  /// An operator to evaluate inversion moves (2-opt).
    3233  /// </summary>
    33   [Item("TSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
     34  [Item("TSPTranslocationMoveDistanceMatrixEvaluator", "Evaluates a translocation or insertion move (3-opt).")]
    3435  [StorableClass]
    35   public abstract class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
    36     public ILookupParameter<InversionMove> InversionMoveParameter {
    37       get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
     36  public class TSPTranslocationMoveDistanceMatrixEvaluator : TSPMoveEvaluator, IPermutationTranslocationMoveOperator {
     37    public override Type EvaluatorType {
     38      get { return typeof(TSPDistanceMatrixEvaluator); }
     39    }
     40
     41    public ILookupParameter<Permutation> PermutationParameter {
     42      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
     43    }
     44    public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
     45      get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
     46    }
     47    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
     48      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }
    3849    }
    3950
    4051    [StorableConstructor]
    41     protected TSPInversionMovePathEvaluator(bool deserializing) : base(deserializing) { }
    42     protected TSPInversionMovePathEvaluator(TSPInversionMovePathEvaluator original, Cloner cloner) : base(original, cloner) { }
    43     public TSPInversionMovePathEvaluator()
     52    protected TSPTranslocationMoveDistanceMatrixEvaluator(bool deserializing) : base(deserializing) { }
     53    protected TSPTranslocationMoveDistanceMatrixEvaluator(TSPTranslocationMoveDistanceMatrixEvaluator original, Cloner cloner) : base(original, cloner) { }
     54    public TSPTranslocationMoveDistanceMatrixEvaluator()
    4455      : base() {
    45       Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
     56      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
     57      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
     58      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
    4659    }
    4760
    48     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, TSPInversionMovePathEvaluator evaluator) {
    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       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
    54       double moveQuality = 0;
    55       // remove two edges
    56       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    57             coordinates[edge1target, 0], coordinates[edge1target, 1]);
    58       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
    59         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    60       // add two edges
    61       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    62         coordinates[edge2source, 0], coordinates[edge2source, 1]);
    63       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
    64         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    65       return moveQuality;
     61    public override IDeepCloneable Clone(Cloner cloner) {
     62      return new TSPTranslocationMoveDistanceMatrixEvaluator(this, cloner);
    6663    }
    6764
    68     public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix) {
    69       int edge1source = permutation.GetCircular(move.Index1 - 1);
    70       int edge1target = permutation[move.Index1];
    71       int edge2source = permutation[move.Index2];
    72       int edge2target = permutation.GetCircular(move.Index2 + 1);
    73       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
    74       double moveQuality = 0;
    75       // remove two edges
    76       moveQuality -= distanceMatrix[edge1source, edge1target];
    77       moveQuality -= distanceMatrix[edge2source, edge2target];
    78       // add two edges
    79       moveQuality += distanceMatrix[edge1source, edge2source];
    80       moveQuality += distanceMatrix[edge1target, edge2target];
    81       return moveQuality;
    82     }
     65    public override IOperation Apply() {
     66      var permutation = PermutationParameter.ActualValue;
     67      double relativeQualityDifference = 0;
     68      var distanceMatrix = DistanceMatrixParameter.ActualValue;
     69      if (distanceMatrix == null) throw new InvalidOperationException("The distance matrix is not given.");
     70      var move = TranslocationMoveParameter.ActualValue;
     71      relativeQualityDifference = TSPTranslocationMovePathEvaluator.EvaluateByDistanceMatrix(permutation, move, distanceMatrix);
    8372
    84     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    85       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
    86     }
    87 
    88     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    89       return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix);
     73      var moveQuality = MoveQualityParameter.ActualValue;
     74      if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
     75      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
     76      return base.Apply();
    9077    }
    9178  }
Note: See TracChangeset for help on using the changeset viewer.