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/OneShift
Files:
1 edited
1 copied

Legend:

Unmodified
Added
Removed

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/OneShift/PTSPAnalyticalInsertionMoveEvaluator.cs

    r13451 r13470  
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInsertionMoveEvaluator", "Evaluates an insertion move (1-shift)")]
     31  [Item("PTSP Analytical Insertion Move Evaluator", "Evaluates an insertion move (1-shift) by a full solution evaluation")]
    3232  [StorableClass]
    33   public class PTSPEstimatedInsertionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
     33  public class PTSPAnalyticalInsertionMoveEvaluator : AnalyticalPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
    3434
    3535    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
    … …  
    3838
    3939    [StorableConstructor]
    40     protected PTSPEstimatedInsertionMoveEvaluator(bool deserializing) : base(deserializing) { }
    41     protected PTSPEstimatedInsertionMoveEvaluator(PTSPEstimatedInsertionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    42     public PTSPEstimatedInsertionMoveEvaluator()
     40    protected PTSPAnalyticalInsertionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPAnalyticalInsertionMoveEvaluator(PTSPAnalyticalInsertionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPAnalyticalInsertionMoveEvaluator()
    4343      : base() {
    4444      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
    … …  
    4646
    4747    public override IDeepCloneable Clone(Cloner cloner) {
    48       return new PTSPEstimatedInsertionMoveEvaluator(this, cloner);
     48      return new PTSPAnalyticalInsertionMoveEvaluator(this, cloner);
    4949    }
    5050
    51     public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
    52       var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
     51    public static double EvaluateMove(Permutation tour, TranslocationMove move, Func<int, int, double> distance, DoubleArray probabilities) {
     52      var afterMove = (Permutation)tour.Clone();
    5353      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    54       double moveQuality = 0;
    55       var edges = new int[12];
    56       var indices = new int[12];
    57       edges[0] = permutation.GetCircular(move.Index1 - 1);
    58       indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    59       edges[1] = permutation[move.Index1];
    60       indices[1] = move.Index1;
    61       edges[2] = permutation[move.Index1];
    62       indices[2] = move.Index1;
    63       edges[3] = permutation.GetCircular(move.Index1 + 1);
    64       indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
    65 
    66       edges[6] = afterMove.GetCircular(move.Index3 - 1);
    67       indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
    68       edges[7] = afterMove[move.Index3];
    69       indices[7] = move.Index3;
    70       edges[8] = afterMove[move.Index3];
    71       indices[8] = move.Index3;
    72       edges[9] = afterMove.GetCircular(move.Index3 + 1);
    73       indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
    74 
    75       if (move.Index3 > move.Index1) {
    76         edges[4] = permutation[move.Index3];
    77         indices[4] = move.Index3;
    78         edges[5] = permutation.GetCircular(move.Index3 + 1);
    79         indices[5] = indices[9];
    80         edges[10] = afterMove.GetCircular(move.Index1 - 1);
    81         indices[10] = indices[0];
    82         edges[11] = afterMove[move.Index1];
    83         indices[11] = move.Index1;
    84       } else {
    85         edges[4] = permutation.GetCircular(move.Index3 - 1);
    86         indices[4] = indices[6];
    87         edges[5] = permutation[move.Index3];
    88         indices[5] = move.Index3;
    89         edges[10] = afterMove[move.Index1];
    90         indices[10] = move.Index1;
    91         edges[11] = afterMove.GetCircular(move.Index1 + 1);
    92         indices[11] = indices[3];
    93       }
    94       int[] aPosteriori = new int[12];
    95       foreach (var realization in realizations) {
    96         for (int i = 0; i < edges.Length; i++) {
    97           Permutation tempPermutation;
    98           if (i < 6) {
    99             tempPermutation = permutation;
    100           } else {
    101             tempPermutation = afterMove;
    102           }
    103           if (realization[edges[i]]) {
    104             aPosteriori[i] = edges[i];
    105           } else {
    106             int j = 1;
    107             if (i % 2 == 0) {
    108               // find nearest predecessor in realization if source edge
    109               while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
    110                 j++;
    111               }
    112               aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    113             } else {
    114               // find nearest successor in realization if target edge
    115               while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {
    116                 j++;
    117               }
    118               aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    119             }
    120           }
    121         }
    122         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
    123           !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
    124           !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    125           // compute cost difference between the two a posteriori solutions
    126 
    127           moveQuality += distanceCalculator.Calculate(aPosteriori[6], aPosteriori[7], coordinates)
    128                        + distanceCalculator.Calculate(aPosteriori[8], aPosteriori[9], coordinates)
    129                        + distanceCalculator.Calculate(aPosteriori[10], aPosteriori[11], coordinates)
    130                        - distanceCalculator.Calculate(aPosteriori[0], aPosteriori[1], coordinates)
    131                        - distanceCalculator.Calculate(aPosteriori[2], aPosteriori[3], coordinates)
    132                        - distanceCalculator.Calculate(aPosteriori[4], aPosteriori[5], coordinates);
    133         }
    134         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    135       }
    136       // return average of cost differences
    137       return moveQuality / realizations.Count;
     54      return AnalyticalProbabilisticTravelingSalesmanProblem.Evaluate(afterMove, distance, probabilities);
    13855    }
    13956
    140     public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
    141       var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    142       TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    143       double moveQuality = 0;
    144       var edges = new int[12];
    145       var indices = new int[12];
    146       edges[0] = permutation.GetCircular(move.Index1 - 1);
    147       indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    148       edges[1] = permutation[move.Index1];
    149       indices[1] = move.Index1;
    150       edges[2] = permutation[move.Index1];
    151       indices[2] = move.Index1;
    152       edges[3] = permutation.GetCircular(move.Index1 + 1);
    153       indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
    154 
    155       edges[6] = afterMove.GetCircular(move.Index3 - 1);
    156       indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
    157       edges[7] = afterMove[move.Index3];
    158       indices[7] = move.Index3;
    159       edges[8] = afterMove[move.Index3];
    160       indices[8] = move.Index3;
    161       edges[9] = afterMove.GetCircular(move.Index3 + 1);
    162       indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
    163 
    164       if (move.Index3 > move.Index1) {
    165         edges[4] = permutation[move.Index3];
    166         indices[4] = move.Index3;
    167         edges[5] = permutation.GetCircular(move.Index3 + 1);
    168         indices[5] = indices[9];
    169         edges[10] = afterMove.GetCircular(move.Index1 - 1);
    170         indices[10] = indices[0];
    171         edges[11] = afterMove[move.Index1];
    172         indices[11] = move.Index1;
    173       } else {
    174         edges[4] = permutation.GetCircular(move.Index3 - 1);
    175         indices[4] = indices[6];
    176         edges[5] = permutation[move.Index3];
    177         indices[5] = move.Index3;
    178         edges[10] = afterMove[move.Index1];
    179         indices[10] = move.Index1;
    180         edges[11] = afterMove.GetCircular(move.Index1 + 1);
    181         indices[11] = indices[3];
    182       }
    183       int[] aPosteriori = new int[12];
    184       foreach (var realization in realizations) {
    185         for (int i = 0; i < edges.Length; i++) {
    186           Permutation tempPermutation;
    187           if (i < 6) {
    188             tempPermutation = permutation;
    189           } else {
    190             tempPermutation = afterMove;
    191           }
    192           if (realization[edges[i]]) {
    193             aPosteriori[i] = edges[i];
    194           } else {
    195             int j = 1;
    196             if (i % 2 == 0) {
    197               // find nearest predecessor in realization if source edge
    198               while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
    199                 j++;
    200               }
    201               aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    202             } else {
    203               // find nearest successor in realization if target edge
    204               while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {
    205                 j++;
    206               }
    207               aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    208             }
    209           }
    210         }
    211         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
    212           !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
    213           !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    214           // compute cost difference between the two a posteriori solutions
    215           moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
    216           moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
    217         }
    218         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    219       }
    220       // return average of cost differences
    221       return moveQuality / realizations.Count;
    222     }
    223 
    224     private static int DecreaseCircularIndex(int length, int index) {
    225       var result = index - 1;
    226       if (result == -1) {
    227         result = length - 1;
    228       }
    229       return result;
    230     }
    231 
    232     private static int IncreaseCircularIndex(int length, int index) {
    233       var result = index + 1;
    234       if (result == length + 1) {
    235         result = 0;
    236       }
    237       return result;
    238     }
    239 
    240     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
    241       return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    242     }
    243 
    244     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    245       return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
     57    protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, DoubleArray probabilities) {
     58      return EvaluateMove(tour, TranslocationMoveParameter.ActualValue, distance, probabilities);
    24659    }
    24760  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/OneShift/PTSPEstimatedInsertionMoveEvaluator.cs

    r13412 r13470  
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInsertionMoveEvaluator", "Evaluates an insertion move (1-shift)")]
     31  [Item("PTSP Estimated Insertion Move Evaluator", "Evaluates an insertion move (1-shift)")]
    3232  [StorableClass]
    3333  public class PTSPEstimatedInsertionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
    … …  
    4949    }
    5050
    51     public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
    52       var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
     51    public static double EvaluateMove(Permutation tour, TranslocationMove move, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
     52      var afterMove = (Permutation)tour.Clone();
    5353      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    5454      double moveQuality = 0;
    5555      var edges = new int[12];
    5656      var indices = new int[12];
    57       edges[0] = permutation.GetCircular(move.Index1 - 1);
    58       indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    59       edges[1] = permutation[move.Index1];
     57      edges[0] = tour.GetCircular(move.Index1 - 1);
     58      indices[0] = DecreaseCircularIndex(tour.Length, move.Index1);
     59      edges[1] = tour[move.Index1];
    6060      indices[1] = move.Index1;
    61       edges[2] = permutation[move.Index1];
     61      edges[2] = tour[move.Index1];
    6262      indices[2] = move.Index1;
    63       edges[3] = permutation.GetCircular(move.Index1 + 1);
    64       indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
     63      edges[3] = tour.GetCircular(move.Index1 + 1);
     64      indices[3] = IncreaseCircularIndex(tour.Length, move.Index1);
    6565
    6666      edges[6] = afterMove.GetCircular(move.Index3 - 1);
    … …  
    7474
    7575      if (move.Index3 > move.Index1) {
    76         edges[4] = permutation[move.Index3];
     76        edges[4] = tour[move.Index3];
    7777        indices[4] = move.Index3;
    78         edges[5] = permutation.GetCircular(move.Index3 + 1);
     78        edges[5] = tour.GetCircular(move.Index3 + 1);
    7979        indices[5] = indices[9];
    8080        edges[10] = afterMove.GetCircular(move.Index1 - 1);
    … …  
    8383        indices[11] = move.Index1;
    8484      } else {
    85         edges[4] = permutation.GetCircular(move.Index3 - 1);
     85        edges[4] = tour.GetCircular(move.Index3 - 1);
    8686        indices[4] = indices[6];
    87         edges[5] = permutation[move.Index3];
     87        edges[5] = tour[move.Index3];
    8888        indices[5] = move.Index3;
    8989        edges[10] = afterMove[move.Index1];
    … …  
    9797          Permutation tempPermutation;
    9898          if (i < 6) {
    99             tempPermutation = permutation;
     99            tempPermutation = tour;
    100100          } else {
    101101            tempPermutation = afterMove;
    … …  
    124124          !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    125125          // compute cost difference between the two a posteriori solutions
    126 
    127           moveQuality += distanceCalculator.Calculate(aPosteriori[6], aPosteriori[7], coordinates)
    128                        + distanceCalculator.Calculate(aPosteriori[8], aPosteriori[9], coordinates)
    129                        + distanceCalculator.Calculate(aPosteriori[10], aPosteriori[11], coordinates)
    130                        - distanceCalculator.Calculate(aPosteriori[0], aPosteriori[1], coordinates)
    131                        - distanceCalculator.Calculate(aPosteriori[2], aPosteriori[3], coordinates)
    132                        - distanceCalculator.Calculate(aPosteriori[4], aPosteriori[5], coordinates);
    133         }
    134         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    135       }
    136       // return average of cost differences
    137       return moveQuality / realizations.Count;
    138     }
    139 
    140     public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<BoolArray> realizations) {
    141       var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    142       TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    143       double moveQuality = 0;
    144       var edges = new int[12];
    145       var indices = new int[12];
    146       edges[0] = permutation.GetCircular(move.Index1 - 1);
    147       indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    148       edges[1] = permutation[move.Index1];
    149       indices[1] = move.Index1;
    150       edges[2] = permutation[move.Index1];
    151       indices[2] = move.Index1;
    152       edges[3] = permutation.GetCircular(move.Index1 + 1);
    153       indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
    154 
    155       edges[6] = afterMove.GetCircular(move.Index3 - 1);
    156       indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
    157       edges[7] = afterMove[move.Index3];
    158       indices[7] = move.Index3;
    159       edges[8] = afterMove[move.Index3];
    160       indices[8] = move.Index3;
    161       edges[9] = afterMove.GetCircular(move.Index3 + 1);
    162       indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
    163 
    164       if (move.Index3 > move.Index1) {
    165         edges[4] = permutation[move.Index3];
    166         indices[4] = move.Index3;
    167         edges[5] = permutation.GetCircular(move.Index3 + 1);
    168         indices[5] = indices[9];
    169         edges[10] = afterMove.GetCircular(move.Index1 - 1);
    170         indices[10] = indices[0];
    171         edges[11] = afterMove[move.Index1];
    172         indices[11] = move.Index1;
    173       } else {
    174         edges[4] = permutation.GetCircular(move.Index3 - 1);
    175         indices[4] = indices[6];
    176         edges[5] = permutation[move.Index3];
    177         indices[5] = move.Index3;
    178         edges[10] = afterMove[move.Index1];
    179         indices[10] = move.Index1;
    180         edges[11] = afterMove.GetCircular(move.Index1 + 1);
    181         indices[11] = indices[3];
    182       }
    183       int[] aPosteriori = new int[12];
    184       foreach (var realization in realizations) {
    185         for (int i = 0; i < edges.Length; i++) {
    186           Permutation tempPermutation;
    187           if (i < 6) {
    188             tempPermutation = permutation;
    189           } else {
    190             tempPermutation = afterMove;
    191           }
    192           if (realization[edges[i]]) {
    193             aPosteriori[i] = edges[i];
    194           } else {
    195             int j = 1;
    196             if (i % 2 == 0) {
    197               // find nearest predecessor in realization if source edge
    198               while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
    199                 j++;
    200               }
    201               aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    202             } else {
    203               // find nearest successor in realization if target edge
    204               while (!realization[tempPermutation.GetCircular(indices[i] + j)]) {
    205                 j++;
    206               }
    207               aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    208             }
    209           }
    210         }
    211         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
    212           !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
    213           !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    214           // compute cost difference between the two a posteriori solutions
    215           moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
    216           moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
     126          moveQuality = moveQuality + distance(aPosteriori[6], aPosteriori[7]) + distance(aPosteriori[8], aPosteriori[9]) + distance(aPosteriori[10], aPosteriori[11]);
     127          moveQuality = moveQuality - distance(aPosteriori[0], aPosteriori[1]) - distance(aPosteriori[2], aPosteriori[3]) - distance(aPosteriori[4], aPosteriori[5]);
    217128        }
    218129        Array.Clear(aPosteriori, 0, aPosteriori.Length);
    … …  
    238149    }
    239150
    240     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
    241       return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    242     }
    243 
    244     protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    245       return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
     151    protected override double EvaluateMove(Permutation tour, Func<int, int, double> distance, ItemList<BoolArray> realizations) {
     152      return EvaluateMove(tour, TranslocationMoveParameter.ActualValue, distance, realizations);
    246153    }
    247154  }
Note: See TracChangeset for help on using the changeset viewer.