Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
12/15/15 16:38:08 (9 years ago)
Author:
abeham
Message:

#2221:

  • implemented review comments
    • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
    • added missing probabilities
    • base class for instance providers
    • prebuild event events
    • build platforms
    • unit test will be removed on trunk integration
    • corrected assembly file version
    • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
    • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
  • added moves (full evaluation) for analytical tsp
  • added local improvement operators for analytical ptsp
  • added recalculation of distance matrix when parameters change
  • still lots of other changes
Location:
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPAnalyticalInversionMoveEvaluator.cs

    r13451 r13470  
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInversionMoveEvaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")]
     31  [Item("PTSP Analytical Inversion Move Evaluator", "Evaluates an inversion move (2-opt) by a full solution evaluation.")]
    3232  [StorableClass]
    33   public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
     33  public class PTSPAnalyticalInversionMoveEvaluator : AnalyticalPTSPMoveEvaluator, IPermutationInversionMoveOperator {
    3434
    3535    public ILookupParameter<InversionMove> InversionMoveParameter {
    … …  
    3838
    3939    [StorableConstructor]
    40     protected PTSPEstimatedInversionMoveEvaluator(bool deserializing) : base(deserializing) { }
    41     protected PTSPEstimatedInversionMoveEvaluator(PTSPEstimatedInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    42     public PTSPEstimatedInversionMoveEvaluator()
     40    protected PTSPAnalyticalInversionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPAnalyticalInversionMoveEvaluator(PTSPAnalyticalInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPAnalyticalInversionMoveEvaluator()
    4343      : base() {
    4444      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
    … …  
    4646
    4747    public override IDeepCloneable Clone(Cloner cloner) {
    48       return new PTSPEstimatedInversionMoveEvaluator(this, cloner);
     48      return new PTSPAnalyticalInversionMoveEvaluator(this, cloner);
    4949    }
    5050
    51     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
    52       double moveQuality = 0;
    53       var edges = new int[4];
    54       var indices = new int[4];
    55       edges[0] = permutation.GetCircular(move.Index1 - 1);
    56       indices[0] = move.Index1 - 1;
    57       if (indices[0] == -1) indices[0] = permutation.Length - 1;
    58       edges[1] = permutation[move.Index1];
    59       indices[1] = move.Index1;
    60       edges[2] = permutation[move.Index2];
    61       indices[2] = move.Index2;
    62       edges[3] = permutation.GetCircular(move.Index2 + 1);
    63       indices[3] = move.Index2 + 1;
    64       if (indices[3] == permutation.Length + 1) indices[3] = 0;
    65       var aPosteriori = new int[4];
    66       foreach (var realization in realizations) {
    67         for (var i = 0; i < edges.Length; i++) {
    68           if (realization[edges[i]]) {
    69             aPosteriori[i] = edges[i];
    70           } else {
    71             var j = 1;
    72             if (i % 2 == 0) {
    73               // find nearest predecessor in realization if source edge
    74               while (!realization[permutation.GetCircular(indices[i] - j)]) {
    75                 j++;
    76               }
    77               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
    78             } else {
    79               // find nearest successor in realization if target edge
    80               while (!realization[permutation.GetCircular(indices[i] + j)]) {
    81                 j++;
    82               }
    83               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
    84             }
    85           }
    86         }
    87         // compute cost difference between the two a posteriori solutions
    88         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    89           moveQuality = moveQuality
    90             + distanceCalculator.Calculate(0, 2, coordinates)
    91             + distanceCalculator.Calculate(1, 3, coordinates)
    92             - distanceCalculator.Calculate(0, 1, coordinates)
    93             - distanceCalculator.Calculate(2, 3, coordinates);
    94         }
    95         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    96       }
    97       // return average of cost differences
    98       return moveQuality / realizations.Count;
     51    public static double EvaluateMove(Permutation tour, InversionMove move, Func<int, int, double> distance, DoubleArray probabilities) {
     52      var afterMove = (Permutation)tour.Clone();
     53      InversionManipulator.Apply(afterMove, move.Index1, move.Index2);
     54      return AnalyticalProbabilisticTravelingSalesmanProblem.Evaluate(afterMove, distance, probabilities);
    9955    }
    10056
    101     public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
    102       double moveQuality = 0;
    103       var edges = new int[4];
    104       var indices = new int[4];
    105       edges[0] = permutation.GetCircular(move.Index1 - 1);
    106       indices[0] = move.Index1 - 1;
    107       if (indices[0] == -1) indices[0] = permutation.Length - 1;
    108       edges[1] = permutation[move.Index1];
    109       indices[1] = move.Index1;
    110       edges[2] = permutation[move.Index2];
    111       indices[2] = move.Index2;
    112       edges[3] = permutation.GetCircular(move.Index2 + 1);
    113       indices[3] = move.Index2 + 1;
    114       if (indices[3] == permutation.Length + 1) indices[3] = 0;
    115       var aPosteriori = new int[4];
    116       foreach (var realization in realizations) {
    117         for (var i = 0; i < edges.Length; i++) {
    118           if (realization[edges[i]]) {
    119             aPosteriori[i] = edges[i];
    120           } else {
    121             var j = 1;
    122             if (i % 2 == 0) {
    123               // find nearest predecessor in realization if source edge
    124               while (!realization[permutation.GetCircular(indices[i] - j)]) {
    125                 j++;
    126               }
    127               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
    128             } else {
    129               // find nearest successor in realization if target edge
    130               while (!realization[permutation.GetCircular(indices[i] + j)]) {
    131                 j++;
    132               }
    133               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
    134             }
    135           }
    136         }
    137         // compute cost difference between the two a posteriori solutions
    138         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    139           moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
    140         }
    141         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    142       }
    143       // return average of cost differences
    144       return moveQuality / realizations.Count;
    145     }
    146 
    147     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
    148       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    149     }
    150 
    151     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    152       return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
     57    protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, DoubleArray probabilities) {
     58      return EvaluateMove(tour, InversionMoveParameter.ActualValue, distance, probabilities);
    15359    }
    15460  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoOpt/PTSPEstimatedInversionMoveEvaluator.cs

    r13412 r13470  
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInversionMoveEvaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")]
     31  [Item("PTSP Estimated Inversion Move Evaluator", "Evaluates an inversion move (2-opt) over several realizations of tours by summing up the length of all added edges and subtracting the length of all deleted edges.")]
    3232  [StorableClass]
    3333  public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
    … …  
    4949    }
    5050
    51     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
     51    public static double EvaluateMove(Permutation tour, InversionMove move, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
    5252      double moveQuality = 0;
    5353      var edges = new int[4];
    5454      var indices = new int[4];
    55       edges[0] = permutation.GetCircular(move.Index1 - 1);
     55      edges[0] = tour.GetCircular(move.Index1 - 1);
    5656      indices[0] = move.Index1 - 1;
    57       if (indices[0] == -1) indices[0] = permutation.Length - 1;
    58       edges[1] = permutation[move.Index1];
     57      if (indices[0] == -1) indices[0] = tour.Length - 1;
     58      edges[1] = tour[move.Index1];
    5959      indices[1] = move.Index1;
    60       edges[2] = permutation[move.Index2];
     60      edges[2] = tour[move.Index2];
    6161      indices[2] = move.Index2;
    62       edges[3] = permutation.GetCircular(move.Index2 + 1);
     62      edges[3] = tour.GetCircular(move.Index2 + 1);
    6363      indices[3] = move.Index2 + 1;
    64       if (indices[3] == permutation.Length + 1) indices[3] = 0;
     64      if (indices[3] == tour.Length + 1) indices[3] = 0;
    6565      var aPosteriori = new int[4];
    6666      foreach (var realization in realizations) {
    … …  
    7272            if (i % 2 == 0) {
    7373              // find nearest predecessor in realization if source edge
    74               while (!realization[permutation.GetCircular(indices[i] - j)]) {
     74              while (!realization[tour.GetCircular(indices[i] - j)]) {
    7575                j++;
    7676              }
    77               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
     77              aPosteriori[i] = tour.GetCircular(indices[i] - j);
    7878            } else {
    7979              // find nearest successor in realization if target edge
    80               while (!realization[permutation.GetCircular(indices[i] + j)]) {
     80              while (!realization[tour.GetCircular(indices[i] + j)]) {
    8181                j++;
    8282              }
    83               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
     83              aPosteriori[i] = tour.GetCircular(indices[i] + j);
    8484            }
    8585          }
    … …  
    8787        // compute cost difference between the two a posteriori solutions
    8888        if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    89           moveQuality = moveQuality
    90             + distanceCalculator.Calculate(0, 2, coordinates)
    91             + distanceCalculator.Calculate(1, 3, coordinates)
    92             - distanceCalculator.Calculate(0, 1, coordinates)
    93             - distanceCalculator.Calculate(2, 3, coordinates);
     89          moveQuality = moveQuality + distance(aPosteriori[0], aPosteriori[2]) + distance(aPosteriori[1], aPosteriori[3])
     90            - distance(aPosteriori[0], aPosteriori[1]) - distance(aPosteriori[2], aPosteriori[3]);
    9491        }
    9592        Array.Clear(aPosteriori, 0, aPosteriori.Length);
    … …  
    9996    }
    10097
    101     public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
    102       double moveQuality = 0;
    103       var edges = new int[4];
    104       var indices = new int[4];
    105       edges[0] = permutation.GetCircular(move.Index1 - 1);
    106       indices[0] = move.Index1 - 1;
    107       if (indices[0] == -1) indices[0] = permutation.Length - 1;
    108       edges[1] = permutation[move.Index1];
    109       indices[1] = move.Index1;
    110       edges[2] = permutation[move.Index2];
    111       indices[2] = move.Index2;
    112       edges[3] = permutation.GetCircular(move.Index2 + 1);
    113       indices[3] = move.Index2 + 1;
    114       if (indices[3] == permutation.Length + 1) indices[3] = 0;
    115       var aPosteriori = new int[4];
    116       foreach (var realization in realizations) {
    117         for (var i = 0; i < edges.Length; i++) {
    118           if (realization[edges[i]]) {
    119             aPosteriori[i] = edges[i];
    120           } else {
    121             var j = 1;
    122             if (i % 2 == 0) {
    123               // find nearest predecessor in realization if source edge
    124               while (!realization[permutation.GetCircular(indices[i] - j)]) {
    125                 j++;
    126               }
    127               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
    128             } else {
    129               // find nearest successor in realization if target edge
    130               while (!realization[permutation.GetCircular(indices[i] + j)]) {
    131                 j++;
    132               }
    133               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
    134             }
    135           }
    136         }
    137         // compute cost difference between the two a posteriori solutions
    138         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    139           moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
    140         }
    141         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    142       }
    143       // return average of cost differences
    144       return moveQuality / realizations.Count;
    145     }
    146 
    147     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
    148       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    149     }
    150 
    151     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    152       return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
     98    protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
     99      return EvaluateMove(tour, InversionMoveParameter.ActualValue, distance, realizations);
    153100    }
    154101  }
Note: See TracChangeset for help on using the changeset viewer.