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
File:
1 copied

Legend:

Unmodified
Added
Removed

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers/PTSPAnalyticalInsertionLocalImprovement.cs

    r13451 r13470  
    3838  /// The operator tries to improve the probabilistic traveling salesman solution by inserting a city in the tour between two other cities for a certain number of times.
    3939  /// </remarks>
    40   [Item("PTSPExhaustiveInsertionLocalImprovement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
     40  [Item("PTSP Analytical Insertion Local Improvement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
    4141  [StorableClass]
    42   public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
     42  public sealed class PTSPAnalyticalInsertionLocalImprovement : SingleSuccessorOperator, IAnalyticalPTSPOperator, ILocalImprovementOperator {
    4343
    4444    public ILookupParameter<IntValue> LocalIterationsParameter {
    … …  
    7474    }
    7575
    76     public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
    77       get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
     76    public ILookupParameter<DoubleArray> ProbabilitiesParameter {
     77      get { return (ILookupParameter<DoubleArray>)Parameters["Probabilities"]; }
    7878    }
    7979
    8080    [StorableConstructor]
    81     private PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
    82     private PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
    83     public PTSPExhaustiveInsertionLocalImprovement()
     81    private PTSPAnalyticalInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
     82    private PTSPAnalyticalInsertionLocalImprovement(PTSPAnalyticalInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
     83    public PTSPAnalyticalInsertionLocalImprovement()
    8484      : base() {
    8585      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    … …  
    9191      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
    9292      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    93       Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
     93      Parameters.Add(new LookupParameter<DoubleArray>("Probabilities", "The list of probabilities of the cities to appear."));
    9494    }
    9595
    9696    public override IDeepCloneable Clone(Cloner cloner) {
    97       return new PTSPExhaustiveInsertionLocalImprovement(this, cloner);
     97      return new PTSPAnalyticalInsertionLocalImprovement(this, cloner);
    9898    }
    9999
    100     public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
     100    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, DoubleArray probabilities, CancellationToken cancellation) {
    101101      var distanceM = (DistanceMatrix)distances;
     102      Func<int, int, double> distance = (a, b) => distanceM[a, b];
    102103      for (var i = localIterations.Value; i < maxIterations; i++) {
    103104        TranslocationMove bestMove = null;
    104         double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
    105         double evaluations = 0.0;
     105        var bestQuality = quality.Value; // we have to make an improvement, so current quality is the baseline
     106        var evaluations = 0.0;
    106107        foreach (var move in ExhaustiveInsertionMoveGenerator.Generate(assignment)) {
    107           double moveQuality = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
    108           int min = Math.Min(move.Index1, move.Index3);
    109           int max = Math.Max(move.Index2, move.Index3 + (move.Index2 - move.Index1));
    110           evaluations += 2.0 * (max - min + 1) / assignment.Length
    111             + 4.0 * (assignment.Length - (max - min + 1)) / assignment.Length;
     108          var moveQuality = PTSPAnalyticalInsertionMoveEvaluator.EvaluateMove(assignment, move, distance, probabilities);
     109          evaluations++;
    112110          if (maximization && moveQuality > bestQuality
    113111            || !maximization && moveQuality < bestQuality) {
    … …  
    119117        if (bestMove == null) break;
    120118        TranslocationManipulator.Apply(assignment, bestMove.Index1, bestMove.Index2, bestMove.Index3);
    121         quality.Value += bestQuality;
     119        quality.Value = bestQuality;
    122120        localIterations.Value++;
    123121        cancellation.ThrowIfCancellationRequested();
    … …  
    133131      var localIterations = LocalIterationsParameter.ActualValue;
    134132      var evaluations = EvaluatedSolutionsParameter.ActualValue;
    135       var realizations = RealizationsParameter.ActualValue;
     133      var probabilities = ProbabilitiesParameter.ActualValue;
    136134      if (localIterations == null) {
    137135        localIterations = new IntValue(0);
    … …  
    139137      }
    140138
    141       Improve(assignment, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken, realizations);
     139      Improve(assignment, distances, quality, localIterations, evaluations, maximization, maxIterations, probabilities, CancellationToken);
    142140
    143141      localIterations.Value = 0;
Note: See TracChangeset for help on using the changeset viewer.