Free cookie consent management tool by TermsFeed Policy Generator

Changeset 12978 for trunk


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
Location:
trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3
Files:
2 edited
2 copied

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/HeuristicLab.Problems.TravelingSalesman-3.3.csproj

    r11623 r12978  
    128128    <Compile Include="Improvers\TSPImprovementOperator.cs" />
    129129    <Compile Include="Interfaces\ITSPDistanceMatrixEvaluator.cs" />
     130    <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveDistanceMatrixEvaluator.cs" />
    130131    <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveEuclideanPathEvaluator.cs" />
    131132    <Compile Include="MoveEvaluators\ThreeOpt\TSPTranslocationMoveGeoPathEvaluator.cs" />
    … …  
    134135    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveEuclideanPathEvaluator.cs" />
    135136    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveGeoPathEvaluator.cs" />
     137    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveDistanceMatrixEvaluator.cs" />
    136138    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMovePathEvaluator.cs" />
    137139    <Compile Include="MoveEvaluators\TwoOpt\TSPInversionMoveRoundedEuclideanPathEvaluator.cs" />

  • 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  }

  • trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/MoveEvaluators/TwoOpt/TSPInversionMoveDistanceMatrixEvaluator.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("TSPInversionMoveDistanceMatrixEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
    3435  [StorableClass]
    35   public abstract class TSPInversionMovePathEvaluator : TSPPathMoveEvaluator, IPermutationInversionMoveOperator {
     36  public class TSPInversionMoveDistanceMatrixEvaluator : TSPMoveEvaluator, IPermutationInversionMoveOperator {
     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    }
    3647    public ILookupParameter<InversionMove> InversionMoveParameter {
    3748      get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
    … …  
    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 TSPInversionMoveDistanceMatrixEvaluator(bool deserializing) : base(deserializing) { }
     53    protected TSPInversionMoveDistanceMatrixEvaluator(TSPInversionMoveDistanceMatrixEvaluator original, Cloner cloner) : base(original, cloner) { }
     54    public TSPInversionMoveDistanceMatrixEvaluator()
    4455      : base() {
     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."));
    4558      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "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 TSPInversionMoveDistanceMatrixEvaluator(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 = InversionMoveParameter.ActualValue;
     71      relativeQualityDifference = TSPInversionMovePathEvaluator.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  }

  • trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

    r12504 r12978  
    254254    private void UpdateMoveEvaluators() {
    255255      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
    256       foreach (ITSPPathMoveEvaluator op in ApplicationManager.Manager.GetInstances<ITSPPathMoveEvaluator>())
     256      foreach (var op in ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>())
    257257        if (op.EvaluatorType == Evaluator.GetType()) {
    258258          Operators.Add(op);
    … …  
    432432        try {
    433433          EvaluateAndLoadTour(data.BestKnownTour);
    434         }
    435         catch (InvalidOperationException) {
     434        } catch (InvalidOperationException) {
    436435          if (data.BestKnownQuality.HasValue)
    437436            BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
Note: See TracChangeset for help on using the changeset viewer.