Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/28/15 23:38:51 (9 years ago)
Author:
abeham
Message:

#2221:

  • Completely refactored PTSP branch
    • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
    • Implemented missing EvaluateByCoordinates for 1-shift moves
    • Made it clear that move evaluators are for estimated PTSP only
    • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
    • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
    • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
    • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types
Location:
branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Improvers
Files:
2 edited

Legend:

Unmodified
Added
Removed

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

    r12261 r13412  
    2121
    2222using System;
     23using System.Threading;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
    … …  
    2930using HeuristicLab.Parameters;
    3031using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    31 using System.Threading;
    3232
    3333namespace HeuristicLab.Problems.PTSP {
    … …  
    3636  /// </summary>
    3737  /// <remarks>
    38   /// The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.
     38  /// 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>
    4040  [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.")]
    4141  [StorableClass]
    42   public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator {
    43  
     42  public sealed class PTSPExhaustiveInsertionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
     43
    4444    public ILookupParameter<IntValue> LocalIterationsParameter {
    4545      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
    … …  
    7474    }
    7575
    76     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    77       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     76    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     77      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    7878    }
    7979
    8080    [StorableConstructor]
    81     protected PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
    82     protected PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner)
    83       : base(original, cloner) {
    84     }
     81    private PTSPExhaustiveInsertionLocalImprovement(bool deserializing) : base(deserializing) { }
     82    private PTSPExhaustiveInsertionLocalImprovement(PTSPExhaustiveInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
    8583    public PTSPExhaustiveInsertionLocalImprovement()
    8684      : base() {
    … …  
    9391      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
    9492      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    95       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     93      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    9694    }
    9795
    … …  
    10098    }
    10199
    102     public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<ItemList<IntValue>> realizations) {
    103       DistanceMatrix distanceM = (DistanceMatrix)distances;
    104       for (int i = localIterations.Value; i < maxIterations; i++) {
     100    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
     101      var distanceM = (DistanceMatrix)distances;
     102      for (var i = localIterations.Value; i < maxIterations; i++) {
    105103        TranslocationMove bestMove = null;
    106104        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
    107105        double evaluations = 0.0;
    108106        foreach (var move in ExhaustiveInsertionMoveGenerator.Generate(assignment)) {
    109           double moveQuality = PTSPEstimatedInsertionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
     107          double moveQuality = PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
    110108          int min = Math.Min(move.Index1, move.Index3);
    111109          int max = Math.Max(move.Index2, move.Index3 + (move.Index2 - move.Index1));
    … …  
    135133      var localIterations = LocalIterationsParameter.ActualValue;
    136134      var evaluations = EvaluatedSolutionsParameter.ActualValue;
    137       var realizations = RealizationsParameter.Value;
     135      var realizations = RealizationsParameter.ActualValue;
    138136      if (localIterations == null) {
    139137        localIterations = new IntValue(0);

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

    r12380 r13412  
    2121
    2222using System;
     23using System.Threading;
    2324using HeuristicLab.Common;
    2425using HeuristicLab.Core;
    … …  
    2930using HeuristicLab.Parameters;
    3031using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    31 using System.Threading;
    3232
    3333namespace HeuristicLab.Problems.PTSP {
    … …  
    4040  [Item("PTSPExhaustiveInversionLocalImprovement", "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 PTSPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, ILocalImprovementOperator {
    43  
     42  public sealed class PTSPExhaustiveInversionLocalImprovement : SingleSuccessorOperator, IEstimatedPTSPOperator, ILocalImprovementOperator {
     43
    4444    public ILookupParameter<IntValue> LocalIterationsParameter {
    4545      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
    … …  
    7474    }
    7575
    76     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    77       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     76    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     77      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    7878    }
    7979
    8080    [StorableConstructor]
    81     protected PTSPExhaustiveInversionLocalImprovement(bool deserializing) : base(deserializing) { }
    82     protected PTSPExhaustiveInversionLocalImprovement(PTSPExhaustiveInversionLocalImprovement original, Cloner cloner)
    83       : base(original, cloner) {
    84     }
     81    private PTSPExhaustiveInversionLocalImprovement(bool deserializing) : base(deserializing) { }
     82    private PTSPExhaustiveInversionLocalImprovement(PTSPExhaustiveInversionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
    8583    public PTSPExhaustiveInversionLocalImprovement()
    8684      : base() {
    … …  
    9391      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem should be maximized or minimized."));
    9492      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    95       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     93      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    9694    }
    9795
    … …  
    10098    }
    10199
    102     public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<ItemList<IntValue>> realizations) {
    103       DistanceMatrix distanceM = (DistanceMatrix)distances;
    104       for (int i = localIterations.Value; i < maxIterations; i++) {
     100    public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation, ItemList<BoolArray> realizations) {
     101      var distanceM = (DistanceMatrix)distances;
     102      for (var i = localIterations.Value; i < maxIterations; i++) {
    105103        InversionMove bestMove = null;
    106104        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
    107105        double evaluations = 0.0;
    108106        foreach (var move in ExhaustiveInversionMoveGenerator.Generate(assignment)) {
    109           double moveQuality = PTSPEstimatedInversionEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
     107          double moveQuality = PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(assignment, move, distanceM, realizations);
    110108          evaluations += 2 * (move.Index2 - move.Index1 + 1) / (double)assignment.Length;
    111109          if (maximization && moveQuality > bestQuality
    … …  
    132130      var localIterations = LocalIterationsParameter.ActualValue;
    133131      var evaluations = EvaluatedSolutionsParameter.ActualValue;
    134       var realizations = RealizationsParameter.Value;
     132      var realizations = RealizationsParameter.ActualValue;
    135133      if (localIterations == null) {
    136134        localIterations = new IntValue(0);
Note: See TracChangeset for help on using the changeset viewer.