Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/28/15 23:38:51 (8 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/Moves
Files:
2 added
1 edited
9 copied

Legend:

Unmodified
Added
Removed

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/EstimatedPTSPMoveEvaluator.cs

    r13408 r13412  
    2525using HeuristicLab.Data;
    2626using HeuristicLab.Encodings.PermutationEncoding;
     27using HeuristicLab.Operators;
    2728using HeuristicLab.Parameters;
    2829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using HeuristicLab.Operators;
    30 using HeuristicLab.Optimization;
    3130
    3231namespace HeuristicLab.Problems.PTSP {
    33   /// <summary>
    34   /// A base class for operators which evaluate TSP solutions.
    35   /// </summary>
    36   [Item("PTSPMoveEvaluator", "A base class for operators which evaluate TSP moves.")]
     32  [Item("EstimatedPTSPMoveEvaluator", "A base class for operators which evaluate TSP moves.")]
    3733  [StorableClass]
    38   public abstract class PTSPMoveEvaluator : SingleSuccessorOperator, IPTSPMoveEvaluator, IMoveOperator {
     34  public abstract class EstimatedPTSPMoveEvaluator : SingleSuccessorOperator, IEstimatedPTSPMoveEvaluator {
    3935
    40     public abstract Type EvaluatorType { get; }
    4136    public override bool CanChangeName {
    4237      get { return false; }
    … …  
    5550      get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    5651    }
    57     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    58       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
     52    public ILookupParameter<ItemList<BoolArray>> RealizationsParameter {
     53      get { return (ILookupParameter<ItemList<BoolArray>>)Parameters["Realizations"]; }
    5954    }
    60 
    6155    public ILookupParameter<DoubleValue> QualityParameter {
    6256      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    … …  
    6559      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    6660    }
     61    public ILookupParameter<DistanceCalculator> DistanceCalculatorParameter {
     62      get { return (ILookupParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
     63    }
    6764
    6865    [StorableConstructor]
    69     protected PTSPMoveEvaluator(bool deserializing) : base(deserializing) { }
    70     protected PTSPMoveEvaluator(PTSPMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    71     protected PTSPMoveEvaluator()
     66    protected EstimatedPTSPMoveEvaluator(bool deserializing) : base(deserializing) { }
     67    protected EstimatedPTSPMoveEvaluator(EstimatedPTSPMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     68    protected EstimatedPTSPMoveEvaluator()
    7269      : base() {
    7370      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    … …  
    7572      Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    7673      Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
    77       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
     74      Parameters.Add(new LookupParameter<ItemList<BoolArray>>("Realizations", "The list of samples drawn from all possible stochastic instances."));
    7875      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
    7976      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
    80     }
    81 
    82     [StorableHook(HookType.AfterDeserialization)]
    83     private void AfterDeserialization() {
    84       // BackwardsCompatibility3.3
    85       #region Backwards compatible code (remove with 3.4)
    86       LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
    87       if (oldDistanceMatrixParameter != null) {
    88         Parameters.Remove(oldDistanceMatrixParameter);
    89         Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    90         DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
    91       }
    92       #endregion
     77      Parameters.Add(new LookupParameter<DistanceCalculator>("DistanceCalculator", "The class that can compute distances between coordinates."));
    9378    }
    9479
    9580    public override IOperation Apply() {
    96       Permutation permutation = PermutationParameter.ActualValue;
    97       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
     81      var permutation = PermutationParameter.ActualValue;
     82      var coordinates = CoordinatesParameter.ActualValue;
    9883      double relativeQualityDifference = 0;
    9984      if (UseDistanceMatrixParameter.ActualValue.Value) {
    100         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
    101         if (distanceMatrix == null) {
    102           if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
    103           distanceMatrix = CalculateDistanceMatrix(coordinates);
    104           DistanceMatrixParameter.ActualValue = distanceMatrix;
    105         }
     85        var distanceMatrix = DistanceMatrixParameter.ActualValue;
     86        if (distanceMatrix == null) throw new InvalidOperationException("The distance matrix has not been calculated.");
    10687        relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
    10788      } else {
    10889        if (coordinates == null) throw new InvalidOperationException("No coordinates were given.");
    109         relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates);
     90        var distanceCalculator = DistanceCalculatorParameter.ActualValue;
     91        if (distanceCalculator == null) throw new InvalidOperationException("Distance calculator is null!");
     92        relativeQualityDifference = EvaluateByCoordinates(permutation, coordinates, distanceCalculator);
    11093      }
    111       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
     94      var moveQuality = MoveQualityParameter.ActualValue;
    11295      if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
    11396      else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
    … …  
    11598    }
    11699
    117     protected abstract double CalculateDistance(double x1, double y1, double x2, double y2);
    118100    protected abstract double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix);
    119     protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates);
    120 
    121     private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
    122       DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
    123       for (int i = 0; i < distanceMatrix.Rows; i++) {
    124         for (int j = 0; j < distanceMatrix.Columns; j++)
    125           distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
    126       }
    127       return (DistanceMatrix)distanceMatrix.AsReadOnly();
    128     }
     101    protected abstract double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator);
    129102  }
    130103}

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

    r13408 r13412  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using System;
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   [Item("PTSPEstimatedInsertionEvaluator", "Evaluates an insertion move (1-shift)")]
     31  [Item("PTSPEstimatedInsertionMoveEvaluator", "Evaluates an insertion move (1-shift)")]
    3232  [StorableClass]
    33   public class PTSPEstimatedInsertionEvaluator : PTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
    34 
    35     public override Type EvaluatorType {
    36       get { return typeof(PTSPEstimatedInsertionEvaluator); }
    37     }
     33  public class PTSPEstimatedInsertionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationTranslocationMoveOperator {
     34
    3835    public ILookupParameter<TranslocationMove> TranslocationMoveParameter {
    3936      get { return (ILookupParameter<TranslocationMove>)Parameters["TranslocationMove"]; }
    4037    }
    4138
    42     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    43       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    44     }
    45 
    4639    [StorableConstructor]
    47     protected PTSPEstimatedInsertionEvaluator(bool deserializing) : base(deserializing) { }
    48     protected PTSPEstimatedInsertionEvaluator(PTSPEstimatedInsertionEvaluator original, Cloner cloner) : base(original, cloner) { }
    49     public PTSPEstimatedInsertionEvaluator()
     40    protected PTSPEstimatedInsertionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPEstimatedInsertionMoveEvaluator(PTSPEstimatedInsertionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPEstimatedInsertionMoveEvaluator()
    5043      : base() {
    5144      Parameters.Add(new LookupParameter<TranslocationMove>("TranslocationMove", "The move to evaluate."));
    … …  
    5346
    5447    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new PTSPEstimatedInsertionEvaluator(this, cloner);
    56     }
    57 
    58     public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, PTSPEstimatedInsertionEvaluator evaluator) {
    59       int edge1source = permutation.GetCircular(move.Index1 - 1);
    60       int edge1target = permutation[move.Index1];
    61       int edge2source = permutation[move.Index2];
    62       int edge2target = permutation.GetCircular(move.Index2 + 1);
    63       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
    64       double moveQuality = 0;
    65       // remove two edges
    66       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    67             coordinates[edge1target, 0], coordinates[edge1target, 1]);
    68       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
    69         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    70       // add two edges
    71       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    72         coordinates[edge2source, 0], coordinates[edge2source, 1]);
    73       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
    74         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    75       return moveQuality;
    76     }
    77 
    78     public static double EvaluateByDistanceMatrix(Permutation permutation, TranslocationMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    79       Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected,permutation);
     48      return new PTSPEstimatedInsertionMoveEvaluator(this, cloner);
     49    }
     50
     51    public static double EvaluateByCoordinates(Permutation permutation, TranslocationMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
     52      var afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    8053      TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index3);
    8154      double moveQuality = 0;
    82       int[] edges = new int[12];
    83       int[] indices = new int[12];
     55      var edges = new int[12];
     56      var indices = new int[12];
    8457      edges[0] = permutation.GetCircular(move.Index1 - 1);
    85       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
     58      indices[0] = DecreaseCircularIndex(permutation.Length, move.Index1);
    8659      edges[1] = permutation[move.Index1];
    8760      indices[1] = move.Index1;
    … …  
    8962      indices[2] = move.Index1;
    9063      edges[3] = permutation.GetCircular(move.Index1 + 1);
    91       indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
     64      indices[3] = IncreaseCircularIndex(permutation.Length, move.Index1);
    9265
    9366      edges[6] = afterMove.GetCircular(move.Index3 - 1);
    94       indices[6] = decreaseCircularIndex(afterMove.Length, move.Index3);
     67      indices[6] = DecreaseCircularIndex(afterMove.Length, move.Index3);
    9568      edges[7] = afterMove[move.Index3];
    9669      indices[7] = move.Index3;
    … …  
    9871      indices[8] = move.Index3;
    9972      edges[9] = afterMove.GetCircular(move.Index3 + 1);
    100       indices[9] = increaseCircularIndex(afterMove.Length, move.Index3);
     73      indices[9] = IncreaseCircularIndex(afterMove.Length, move.Index3);
    10174
    10275      if (move.Index3 > move.Index1) {
    … …  
    12093      }
    12194      int[] aPosteriori = new int[12];
    122       Permutation tempPermutation;
    123       foreach (ItemList<IntValue> realization in realizations) {
     95      foreach (var realization in realizations) {
    12496        for (int i = 0; i < edges.Length; i++) {
     97          Permutation tempPermutation;
    12598          if (i < 6) {
    12699            tempPermutation = permutation;
    … …  
    128101            tempPermutation = afterMove;
    129102          }
    130           if (realization[edges[i]].Value == 1) {
     103          if (realization[edges[i]]) {
    131104            aPosteriori[i] = edges[i];
    132105          } else {
    133             int j=1;
    134             if (i%2==0) {
     106            int j = 1;
     107            if (i % 2 == 0) {
    135108              // find nearest predecessor in realization if source edge
    136               while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
     109              while (!realization[tempPermutation.GetCircular(indices[i] - j)]) {
    137110                j++;
    138111              }
    … …  
    140113            } else {
    141114              // find nearest successor in realization if target edge
    142               while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
     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;
     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)]) {
    143205                j++;
    144206              }
    … …  
    160222    }
    161223
    162     private static int decreaseCircularIndex(int length, int index) {
    163       int result = index - 1;
     224    private static int DecreaseCircularIndex(int length, int index) {
     225      var result = index - 1;
    164226      if (result == -1) {
    165227        result = length - 1;
    … …  
    168230    }
    169231
    170     private static int increaseCircularIndex(int length, int index) {
    171       int result = index + 1;
     232    private static int IncreaseCircularIndex(int length, int index) {
     233      var result = index + 1;
    172234      if (result == length + 1) {
    173235        result = 0;
    … …  
    176238    }
    177239
    178     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    179       return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, this);
     240    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     241      return EvaluateByCoordinates(permutation, TranslocationMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    180242    }
    181243
    182244    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    183       return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
    184     }
    185 
    186     protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
    187       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     245      return EvaluateByDistanceMatrix(permutation, TranslocationMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
    188246    }
    189247  }

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

    r13408 r13412  
    2020#endregion
    2121
     22using System;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
    … …  
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using System;
    2929
    3030namespace HeuristicLab.Problems.PTSP {
    31   /// <summary>
    32   /// An operator to evaluate inversion moves (2-opt).
    33   /// </summary>
    34   [Item("PTSPInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) by summing up the length of all added edges and subtracting the length of all deleted edges.")]
     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.")]
    3532  [StorableClass]
    36   public class PTSPEstimatedInversionEvaluator : PTSPMoveEvaluator, IPermutationInversionMoveOperator {
    37     public override Type EvaluatorType {
    38       get { return typeof(PTSPEstimatedInversionEvaluator); }
    39     }
     33  public class PTSPEstimatedInversionMoveEvaluator : EstimatedPTSPMoveEvaluator, IPermutationInversionMoveOperator {
     34
    4035    public ILookupParameter<InversionMove> InversionMoveParameter {
    4136      get { return (ILookupParameter<InversionMove>)Parameters["InversionMove"]; }
    4237    }
    4338
    44    
    45 
    4639    [StorableConstructor]
    47     protected PTSPEstimatedInversionEvaluator(bool deserializing) : base(deserializing) { }
    48     protected PTSPEstimatedInversionEvaluator(PTSPEstimatedInversionEvaluator original, Cloner cloner) : base(original, cloner) { }
    49     public PTSPEstimatedInversionEvaluator()
     40    protected PTSPEstimatedInversionMoveEvaluator(bool deserializing) : base(deserializing) { }
     41    protected PTSPEstimatedInversionMoveEvaluator(PTSPEstimatedInversionMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     42    public PTSPEstimatedInversionMoveEvaluator()
    5043      : base() {
    5144      Parameters.Add(new LookupParameter<InversionMove>("InversionMove", "The move to evaluate."));
    … …  
    5346
    5447    public override IDeepCloneable Clone(Cloner cloner) {
    55       return new PTSPEstimatedInversionEvaluator(this, cloner);
     48      return new PTSPEstimatedInversionMoveEvaluator(this, cloner);
    5649    }
    5750
    58     public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPEstimatedInversionEvaluator evaluator) {
    59       int edge1source = permutation.GetCircular(move.Index1 - 1);
    60       int edge1target = permutation[move.Index1];
    61       int edge2source = permutation[move.Index2];
    62       int edge2target = permutation.GetCircular(move.Index2 + 1);
    63       if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
     51    public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, ItemList<BoolArray> realizations) {
    6452      double moveQuality = 0;
    65       // remove two edges
    66       moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    67             coordinates[edge1target, 0], coordinates[edge1target, 1]);
    68       moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
    69         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    70       // add two edges
    71       moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
    72         coordinates[edge2source, 0], coordinates[edge2source, 1]);
    73       moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
    74         coordinates[edge2target, 0], coordinates[edge2target, 1]);
    75       return moveQuality;
    76     }
    77 
    78     public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    79       double moveQuality = 0;
    80       int[] edges = new int[4];
    81       int[] indices = new int[4];
     53      var edges = new int[4];
     54      var indices = new int[4];
    8255      edges[0] = permutation.GetCircular(move.Index1 - 1);
    83       indices[0] = move.Index1-1;
     56      indices[0] = move.Index1 - 1;
    8457      if (indices[0] == -1) indices[0] = permutation.Length - 1;
    8558      edges[1] = permutation[move.Index1];
    … …  
    8861      indices[2] = move.Index2;
    8962      edges[3] = permutation.GetCircular(move.Index2 + 1);
    90       indices[3] = move.Index2+1;
     63      indices[3] = move.Index2 + 1;
    9164      if (indices[3] == permutation.Length + 1) indices[3] = 0;
    92       int[] aPosteriori = new int[4];
    93       foreach (ItemList<IntValue> realization in realizations) {
    94         for (int i = 0; i < edges.Length; i++) {
    95           if (realization[edges[i]].Value == 1) {
     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]]) {
    9669            aPosteriori[i] = edges[i];
    9770          } else {
    98             int j=1;
    99             if (i%2==0) {
     71            var j = 1;
     72            if (i % 2 == 0) {
    10073              // find nearest predecessor in realization if source edge
    101               while(realization[permutation.GetCircular(indices[i]-j)].Value==0) {
     74              while (!realization[permutation.GetCircular(indices[i] - j)]) {
    10275                j++;
    10376              }
    … …  
    10578            } else {
    10679              // find nearest successor in realization if target edge
    107               while(realization[permutation.GetCircular(indices[i]+j)].Value==0) {
     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;
     99    }
     100
     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)]) {
    108131                j++;
    109132              }
    … …  
    122145    }
    123146
    124     protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
    125       return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
     147    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     148      return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, distanceCalculator, RealizationsParameter.ActualValue);
    126149    }
    127150
    128151    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    129       return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.Value);
    130     }
    131 
    132     protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
    133       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     152      return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix, RealizationsParameter.ActualValue);
    134153    }
    135154  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/ExhaustiveTwoPointFiveMoveGenerator.cs

    r13408 r13412  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using System.Collections.Generic;
    324using System.Linq;
    425using HeuristicLab.Common;
    526using HeuristicLab.Core;
     27using HeuristicLab.Encodings.PermutationEncoding;
    628using HeuristicLab.Optimization;
    729using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    8 using HeuristicLab.Encodings.PermutationEncoding;
    9 using HeuristicLab.Parameters;
    10 using HeuristicLab.Operators;
    1130
    1231namespace HeuristicLab.Problems.PTSP {
    13   [Item("Exhaustive25MoveGenerator", "Generates all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     32  [Item("Exhaustive 2.5-MoveGenerator", "Generates all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    1433  [StorableClass]
    15   class Exhaustive25MoveGenerator : TwoPointFiveMoveGenerator, IExhaustiveMoveGenerator {
    16     public override bool CanChangeName {
    17       get { return false; }
     34  public sealed class ExhaustiveTwoPointFiveMoveGenerator : TwoPointFiveMoveGenerator, IExhaustiveMoveGenerator {
     35
     36    [StorableConstructor]
     37    private ExhaustiveTwoPointFiveMoveGenerator(bool deserializing) : base(deserializing) { }
     38    private ExhaustiveTwoPointFiveMoveGenerator(ExhaustiveTwoPointFiveMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     39    public ExhaustiveTwoPointFiveMoveGenerator() : base() { }
     40
     41    public override IDeepCloneable Clone(Cloner cloner) {
     42      return new ExhaustiveTwoPointFiveMoveGenerator(this, cloner);
    1843    }
    1944
    20     [StorableConstructor]
    21     protected Exhaustive25MoveGenerator(bool deserializing) : base(deserializing) { }
    22     protected Exhaustive25MoveGenerator(Exhaustive25MoveGenerator original, Cloner cloner) : base(original, cloner) { }
    23     public Exhaustive25MoveGenerator()
    24       : base() {
    25     }
    26 
    27     public override IDeepCloneable Clone(Cloner cloner) {
    28       return new Exhaustive25MoveGenerator(this, cloner);
    29     }
    30    
    3145    public static TwoPointFiveMove[] Apply(Permutation permutation) {
    3246      return Generate(permutation).ToArray();
    … …  
    3549    public static IEnumerable<TwoPointFiveMove> Generate(Permutation permutation) {
    3650      int length = permutation.Length;
    37       if (length == 1) throw new ArgumentException("Exhaustive25MoveGenerator: There cannot be a 2.5 move given a permutation of length 1.", "permutation");
     51      if (length == 1) throw new ArgumentException("Exhaustive 2.5-MoveGenerator: There cannot be a 2.5 move given a permutation of length 1.", "permutation");
    3852      int totalMoves = (length) * (length - 1) / 2;
    3953
    … …  
    4458              // doesn't make sense to inverse the whole permutation or the whole but one in case of relative undirected permutations
    4559              if (j - i >= length - 2) continue;
    46               yield return new TwoPointFiveMove(i, j,true);
     60              yield return new TwoPointFiveMove(i, j, true);
    4761              yield return new TwoPointFiveMove(i, j, false);
    4862            }
    4963          }
    5064        } else { // when length is 3 or less, there's actually no difference, but for the sake of not crashing the algorithm create a dummy move
    51           yield return new TwoPointFiveMove(0, 1,true);
     65          yield return new TwoPointFiveMove(0, 1, true);
    5266        }
    5367      } else {
    5468        for (int i = 0; i < length - 1; i++)
    5569          for (int j = i + 1; j < length; j++) {
    56             yield return new TwoPointFiveMove(i, j,true);
     70            yield return new TwoPointFiveMove(i, j, true);
    5771            yield return new TwoPointFiveMove(i, j, false);
    5872          }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/PTSPTwoPointFiveMoveEvaluator.cs

    r13408 r13412  
    2020#endregion
    2121
    22 using System;
    2322using HeuristicLab.Common;
    2423using HeuristicLab.Core;
    … …  
    2726using HeuristicLab.Parameters;
    2827using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    29 using HeuristicLab.Optimization;
    30 using HeuristicLab.Operators;
    3128
    3229namespace HeuristicLab.Problems.PTSP {
    33   /// <summary>
    34   /// A base class for operators which evaluate TSP solutions.
    35   /// </summary>
    36   [Item("PTSP25MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
     30  [Item("PTSP 2.5-MoveEvaluator", "Operator that evaluates 2.5-p-opt moves of PTSP")]
    3731  [StorableClass]
    38   public class PTSP25MoveEvaluator : SingleSuccessorOperator, I25MoveOperator, ISingleObjectiveMoveEvaluator {
    39     public ILookupParameter<Permutation> PermutationParameter {
    40       get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
    41     }
    42     public ILookupParameter<DoubleMatrix> CoordinatesParameter {
    43       get { return (ILookupParameter<DoubleMatrix>)Parameters["Coordinates"]; }
    44     }
    45     public ILookupParameter<DistanceMatrix> DistanceMatrixParameter {
    46       get { return (ILookupParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
    47     }
    48     public ILookupParameter<BoolValue> UseDistanceMatrixParameter {
    49       get { return (ILookupParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
    50     }
    51     public IValueParameter<ItemList<ItemList<IntValue>>> RealizationsParameter {
    52       get { return (IValueParameter<ItemList<ItemList<IntValue>>>)Parameters["Realizations"]; }
    53     }
     32  public class PTSPTwoPointFiveMoveEvaluator : EstimatedPTSPMoveEvaluator, ITwoPointFiveMoveOperator {
     33
    5434    public ILookupParameter<TwoPointFiveMove> TwoPointFiveMoveParameter {
    5535      get { return (ILookupParameter<TwoPointFiveMove>)Parameters["TwoPointFiveMove"]; }
    5636    }
    57     public ILookupParameter<DoubleValue> QualityParameter {
    58       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    59     }
    60     public ILookupParameter<DoubleValue> MoveQualityParameter {
    61       get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    62     }
    6337
    6438    [StorableConstructor]
    65     protected PTSP25MoveEvaluator(bool deserializing) : base(deserializing) { }
    66     protected PTSP25MoveEvaluator(PTSP25MoveEvaluator original, Cloner cloner) : base(original, cloner) { }
    67     public PTSP25MoveEvaluator()
     39    protected PTSPTwoPointFiveMoveEvaluator(bool deserializing) : base(deserializing) { }
     40    protected PTSPTwoPointFiveMoveEvaluator(PTSPTwoPointFiveMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
     41    public PTSPTwoPointFiveMoveEvaluator()
    6842      : base() {
    69       Parameters.Add(new LookupParameter<Permutation>("Permutation", "The solution as permutation."));
    70       Parameters.Add(new LookupParameter<DoubleMatrix>("Coordinates", "The city's coordinates."));
    71       Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    72       Parameters.Add(new LookupParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated (if it does not exist already) and used for evaluation, otherwise false."));
    73       Parameters.Add(new ValueParameter<ItemList<ItemList<IntValue>>>("Realizations", "The concrete..."));
    7443      Parameters.Add(new LookupParameter<TwoPointFiveMove>("TwoPointFiveMove", "The move to evaluate."));
    75       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a TSP solution."));
    76       Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The evaluated quality of a move on a TSP solution."));
    7744    }
    7845
    7946    public override IDeepCloneable Clone(Cloner cloner) {
    80       return new PTSP25MoveEvaluator(this, cloner);
     47      return new PTSPTwoPointFiveMoveEvaluator(this, cloner);
    8148    }
    8249
    83     [StorableHook(HookType.AfterDeserialization)]
    84     private void AfterDeserialization() {
    85       // BackwardsCompatibility3.3
    86       #region Backwards compatible code (remove with 3.4)
    87       LookupParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as LookupParameter<DoubleMatrix>;
    88       if (oldDistanceMatrixParameter != null) {
    89         Parameters.Remove(oldDistanceMatrixParameter);
    90         Parameters.Add(new LookupParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
    91         DistanceMatrixParameter.ActualName = oldDistanceMatrixParameter.ActualName;
    92       }
    93       #endregion
     50    protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator) {
     51      var move = TwoPointFiveMoveParameter.ActualValue;
     52      var realizations = RealizationsParameter.ActualValue;
     53      return EvaluateByCoordinates(permutation, coordinates, distanceCalculator, move, realizations);
    9454    }
    9555
    96     public override IOperation Apply() {
    97       Permutation permutation = PermutationParameter.ActualValue;
    98       DoubleMatrix coordinates = CoordinatesParameter.ActualValue;
    99       double relativeQualityDifference = 0;
    100       if (UseDistanceMatrixParameter.ActualValue.Value) {
    101         DistanceMatrix distanceMatrix = DistanceMatrixParameter.ActualValue;
    102         if (distanceMatrix == null) {
    103           if (coordinates == null) throw new InvalidOperationException("Neither a distance matrix nor coordinates were given.");
    104           distanceMatrix = CalculateDistanceMatrix(coordinates);
    105           DistanceMatrixParameter.ActualValue = distanceMatrix;
    106         }
    107         relativeQualityDifference = EvaluateByDistanceMatrix(permutation, distanceMatrix);
    108       }
    109       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
    110       if (moveQuality == null) MoveQualityParameter.ActualValue = new DoubleValue(QualityParameter.ActualValue.Value + relativeQualityDifference);
    111       else moveQuality.Value = QualityParameter.ActualValue.Value + relativeQualityDifference;
    112       return base.Apply();
     56    public static double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates, DistanceCalculator distanceCalculator, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
     57      if (move.IsInvert) {
     58        return PTSPEstimatedInversionMoveEvaluator.EvaluateByCoordinates(permutation,
     59          new InversionMove(move.Index1, move.Index2, move.Permutation),
     60          coordinates, distanceCalculator, realizations);
     61      } else {
     62        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByCoordinates(permutation,
     63          new TranslocationMove(move.Index1, move.Index1, move.Index2),
     64          coordinates, distanceCalculator, realizations);
     65      }
    11366    }
    11467
    115     protected double CalculateDistance(double x1, double y1, double x2, double y2) {
    116       return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
     68    protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
     69      var move = TwoPointFiveMoveParameter.ActualValue;
     70      var realizations = RealizationsParameter.ActualValue;
     71      return EvaluateByDistanceMatrix(permutation, distanceMatrix, move, realizations);
    11772    }
    11873
    119     private static int decreaseCircularIndex(int length, int index) {
    120       int result = index - 1;
    121       if (result == -1) {
    122         result = length - 1;
     74    public static double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix, TwoPointFiveMove move, ItemList<BoolArray> realizations) {
     75      if (move.IsInvert) {
     76        return PTSPEstimatedInversionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
     77          new InversionMove(move.Index1, move.Index2, move.Permutation),
     78          distanceMatrix, realizations);
     79      } else {
     80        return PTSPEstimatedInsertionMoveEvaluator.EvaluateByDistanceMatrix(permutation,
     81          new TranslocationMove(move.Index1, move.Index1, move.Index2),
     82          distanceMatrix, realizations);
    12383      }
    124       return result;
    125     }
    126 
    127     private static int increaseCircularIndex(int length, int index) {
    128       int result = index + 1;
    129       if (result == length + 1) {
    130         result = 0;
    131       }
    132       return result;
    133     }
    134    
    135 
    136     public static double EvaluateInversionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    137       double moveQuality = 0;
    138       int[] edges = new int[4];
    139       int[] indices = new int[4];
    140       edges[0] = permutation.GetCircular(move.Index1 - 1);
    141       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
    142       edges[1] = permutation[move.Index1];
    143       indices[1] = move.Index1;
    144       edges[2] = permutation[move.Index2];
    145       indices[2] = move.Index2;
    146       edges[3] = permutation.GetCircular(move.Index2 + 1);
    147       indices[3] = increaseCircularIndex(permutation.Length, move.Index2);
    148       int[] aPosteriori = new int[4];
    149       foreach (ItemList<IntValue> realization in realizations) {
    150         for (int i = 0; i < edges.Length; i++) {
    151           if (realization[edges[i]].Value == 1) {
    152             aPosteriori[i] = edges[i];
    153           } else {
    154             int j = 1;
    155             if (i % 2 == 0) {
    156               // find nearest predecessor in realization if source edge
    157               while (realization[permutation.GetCircular(indices[i] - j)].Value == 0) {
    158                 j++;
    159               }
    160               aPosteriori[i] = permutation.GetCircular(indices[i] - j);
    161             } else {
    162               // find nearest successor in realization if target edge
    163               while (realization[permutation.GetCircular(indices[i] + j)].Value == 0) {
    164                 j++;
    165               }
    166               aPosteriori[i] = permutation.GetCircular(indices[i] + j);
    167             }
    168           }
    169         }
    170         // compute cost difference between the two a posteriori solutions
    171         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3])) {
    172           moveQuality = moveQuality + distanceMatrix[aPosteriori[0], aPosteriori[2]] + distanceMatrix[aPosteriori[1], aPosteriori[3]] - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]];
    173         }
    174         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    175       }
    176       // return average of cost differences
    177       return moveQuality / realizations.Count;
    178     }
    179     public static double EvaluateInsertionByDistanceMatrix(Permutation permutation, TwoPointFiveMove move, DistanceMatrix distanceMatrix, ItemList<ItemList<IntValue>> realizations) {
    180       Permutation afterMove = new Permutation(PermutationTypes.RelativeUndirected, permutation);
    181       TranslocationManipulator.Apply(afterMove, move.Index1, move.Index1, move.Index2);
    182       double moveQuality = 0;
    183       int[] edges = new int[12];
    184       int[] indices = new int[12];
    185       edges[0] = permutation.GetCircular(move.Index1 - 1);
    186       indices[0] = decreaseCircularIndex(permutation.Length, move.Index1);
    187       edges[1] = permutation[move.Index1];
    188       indices[1] = move.Index1;
    189       edges[2] = permutation[move.Index1];
    190       indices[2] = move.Index1;
    191       edges[3] = permutation.GetCircular(move.Index1 + 1);
    192       indices[3] = increaseCircularIndex(permutation.Length, move.Index1);
    193 
    194       edges[6] = afterMove.GetCircular(move.Index2 - 1);
    195       indices[6] = decreaseCircularIndex(afterMove.Length, move.Index2);
    196       edges[7] = afterMove[move.Index2];
    197       indices[7] = move.Index2;
    198       edges[8] = afterMove[move.Index2];
    199       indices[8] = move.Index2;
    200       edges[9] = afterMove.GetCircular(move.Index2 + 1);
    201       indices[9] = increaseCircularIndex(afterMove.Length, move.Index2);
    202 
    203       if (move.Index2 > move.Index1) {
    204         edges[4] = permutation[move.Index2];
    205         indices[4] = move.Index2;
    206         edges[5] = permutation.GetCircular(move.Index2 + 1);
    207         indices[5] = indices[9];
    208         edges[10] = afterMove.GetCircular(move.Index1 - 1);
    209         indices[10] = indices[0];
    210         edges[11] = afterMove[move.Index1];
    211         indices[11] = move.Index1;
    212       } else {
    213         edges[4] = permutation.GetCircular(move.Index2 - 1);
    214         indices[4] = indices[6];
    215         edges[5] = permutation[move.Index2];
    216         indices[5] = move.Index2;
    217         edges[10] = afterMove[move.Index1];
    218         indices[10] = move.Index1;
    219         edges[11] = afterMove.GetCircular(move.Index1 + 1);
    220         indices[11] = indices[3];
    221       }
    222       int[] aPosteriori = new int[12];
    223       Permutation tempPermutation;
    224       foreach (ItemList<IntValue> realization in realizations) {
    225         for (int i = 0; i < edges.Length; i++) {
    226           if (i < 6) {
    227             tempPermutation = permutation;
    228           } else {
    229             tempPermutation = afterMove;
    230           }
    231           if (realization[edges[i]].Value == 1) {
    232             aPosteriori[i] = edges[i];
    233           } else {
    234             int j = 1;
    235             if (i % 2 == 0) {
    236               // find nearest predecessor in realization if source edge
    237               while (realization[tempPermutation.GetCircular(indices[i] - j)].Value == 0) {
    238                 j++;
    239               }
    240               aPosteriori[i] = tempPermutation.GetCircular(indices[i] - j);
    241             } else {
    242               // find nearest successor in realization if target edge
    243               while (realization[tempPermutation.GetCircular(indices[i] + j)].Value == 0) {
    244                 j++;
    245               }
    246               aPosteriori[i] = tempPermutation.GetCircular(indices[i] + j);
    247             }
    248           }
    249         }
    250         if (!(aPosteriori[0] == aPosteriori[2] && aPosteriori[1] == aPosteriori[3]) &&
    251           !(aPosteriori[0] == aPosteriori[4] && aPosteriori[1] == aPosteriori[5]) &&
    252           !(aPosteriori[2] == aPosteriori[4] && aPosteriori[3] == aPosteriori[5])) {
    253           // compute cost difference between the two a posteriori solutions
    254           moveQuality = moveQuality + distanceMatrix[aPosteriori[6], aPosteriori[7]] + distanceMatrix[aPosteriori[8], aPosteriori[9]] + distanceMatrix[aPosteriori[10], aPosteriori[11]];
    255           moveQuality = moveQuality - distanceMatrix[aPosteriori[0], aPosteriori[1]] - distanceMatrix[aPosteriori[2], aPosteriori[3]] - distanceMatrix[aPosteriori[4], aPosteriori[5]];
    256         }
    257         Array.Clear(aPosteriori, 0, aPosteriori.Length);
    258       }
    259       // return average of cost differences
    260       return moveQuality / realizations.Count;
    261     }
    262     protected double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
    263       TwoPointFiveMove currentMove = TwoPointFiveMoveParameter.ActualValue;
    264       if (currentMove.IsInvert) {
    265         return EvaluateInversionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
    266       } else {
    267         return EvaluateInsertionByDistanceMatrix(permutation, currentMove, distanceMatrix, RealizationsParameter.Value);
    268       }
    269     }
    270 
    271     private DistanceMatrix CalculateDistanceMatrix(DoubleMatrix c) {
    272       DistanceMatrix distanceMatrix = new DistanceMatrix(c.Rows, c.Rows);
    273       for (int i = 0; i < distanceMatrix.Rows; i++) {
    274         for (int j = 0; j < distanceMatrix.Columns; j++)
    275           distanceMatrix[i, j] = CalculateDistance(c[i, 0], c[i, 1], c[j, 0], c[j, 1]);
    276       }
    277       return (DistanceMatrix)distanceMatrix.AsReadOnly();
    27884    }
    27985  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/StochasticTwoPointFiveMultiMoveGenerator.cs

    r13408 r13412  
    2424using HeuristicLab.Data;
    2525using HeuristicLab.Encodings.PermutationEncoding;
    26 using HeuristicLab.Operators;
    2726using HeuristicLab.Optimization;
    2827using HeuristicLab.Parameters;
    … …  
    3029
    3130namespace HeuristicLab.Problems.PTSP {
    32   [Item("Stochastic25MultiMoveGenerator", "Randomly samples n from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     31  [Item("Stochastic 2.5-MultiMoveGenerator", "Randomly samples n from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    3332  [StorableClass]
    34   class Stochastic25MultiMoveGenerator : TwoPointFiveMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
     33  public sealed class StochasticTwoPointFiveMultiMoveGenerator : TwoPointFiveMoveGenerator, IMultiMoveGenerator, IStochasticOperator {
    3534    public ILookupParameter<IRandom> RandomParameter {
    3635      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    … …  
    4645
    4746    [StorableConstructor]
    48     protected Stochastic25MultiMoveGenerator(bool deserializing) : base(deserializing) { }
    49     protected Stochastic25MultiMoveGenerator(Stochastic25MultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    50     public Stochastic25MultiMoveGenerator()
     47    private StochasticTwoPointFiveMultiMoveGenerator(bool deserializing) : base(deserializing) { }
     48    private StochasticTwoPointFiveMultiMoveGenerator(StochasticTwoPointFiveMultiMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     49    public StochasticTwoPointFiveMultiMoveGenerator()
    5150      : base() {
    5251      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
    … …  
    5554
    5655    public override IDeepCloneable Clone(Cloner cloner) {
    57       return new Stochastic25MultiMoveGenerator(this, cloner);
     56      return new StochasticTwoPointFiveMultiMoveGenerator(this, cloner);
    5857    }
    5958
    6059    public static TwoPointFiveMove[] Apply(Permutation permutation, IRandom random, int sampleSize) {
    61       int length = permutation.Length;
    62       TwoPointFiveMove[] moves = new TwoPointFiveMove[sampleSize];
    63       for (int i = 0; i < sampleSize; i++) {
    64         moves[i] = Stochastic25SingleMoveGenerator.Apply(permutation, random);
     60      var moves = new TwoPointFiveMove[sampleSize];
     61      for (var i = 0; i < sampleSize; i++) {
     62        moves[i] = StochasticTwoPointFiveSingleMoveGenerator.Apply(permutation, random);
    6563      }
    6664      return moves;
    … …  
    6866
    6967    protected override TwoPointFiveMove[] GenerateMoves(Permutation permutation) {
    70       IRandom random = RandomParameter.ActualValue;
    71       return Apply(permutation, random, SampleSizeParameter.ActualValue.Value);
     68      return Apply(permutation, RandomParameter.ActualValue, SampleSizeParameter.ActualValue.Value);
    7269    }
    7370  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/StochasticTwoPointFiveSingleMoveGenerator.cs

    r13408 r13412  
    2323using HeuristicLab.Common;
    2424using HeuristicLab.Core;
     25using HeuristicLab.Encodings.PermutationEncoding;
    2526using HeuristicLab.Optimization;
    2627using HeuristicLab.Parameters;
    2728using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    28 using HeuristicLab.Operators;
    29 using HeuristicLab.Encodings.PermutationEncoding;
    30 
    3129
    3230namespace HeuristicLab.Problems.PTSP {
    33   [Item("Stochastic25SingleMoveGenerator", "Randomly samples a single from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
     31  [Item("Stochastic 2.5-SingleMoveGenerator", "Randomly samples a single from all possible inversion and shift moves (2.5-opt) from a given permutation.")]
    3432  [StorableClass]
    35   class Stochastic25SingleMoveGenerator : TwoPointFiveMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
     33  public sealed class StochasticTwoPointFiveSingleMoveGenerator : TwoPointFiveMoveGenerator, IStochasticOperator, ISingleMoveGenerator {
    3634    public ILookupParameter<IRandom> RandomParameter {
    3735      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    … …  
    3937
    4038    [StorableConstructor]
    41     protected Stochastic25SingleMoveGenerator(bool deserializing) : base(deserializing) { }
    42     protected Stochastic25SingleMoveGenerator(Stochastic25SingleMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    43     public Stochastic25SingleMoveGenerator()
     39    private StochasticTwoPointFiveSingleMoveGenerator(bool deserializing) : base(deserializing) { }
     40    private StochasticTwoPointFiveSingleMoveGenerator(StochasticTwoPointFiveSingleMoveGenerator original, Cloner cloner) : base(original, cloner) { }
     41    public StochasticTwoPointFiveSingleMoveGenerator()
    4442      : base() {
    4543      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator."));
    … …  
    4745
    4846    public override IDeepCloneable Clone(Cloner cloner) {
    49       return new Stochastic25SingleMoveGenerator(this, cloner);
     47      return new StochasticTwoPointFiveSingleMoveGenerator(this, cloner);
    5048    }
    5149
    5250    public static TwoPointFiveMove Apply(Permutation permutation, IRandom random) {
    5351      int length = permutation.Length;
    54       if (length == 1) throw new ArgumentException("Stochastic25SingleMoveGenerator: There cannot be an inversion move given a permutation of length 1.", "permutation");
     52      if (length == 1) throw new ArgumentException("Stochastic 2.5-SingleMoveGenerator: There cannot be an inversion move given a permutation of length 1.", "permutation");
    5553      int index1 = random.Next(length - 1);
    5654      int index2 = random.Next(index1 + 1, length);
    … …  
    6361      bool isInvert = random.NextDouble() > 0.5;
    6462      return new TwoPointFiveMove(index1, index2, isInvert);
    65      
     63
    6664    }
    6765
    6866    protected override TwoPointFiveMove[] GenerateMoves(Permutation permutation) {
    69       IRandom random = RandomParameter.ActualValue;
    70       return new TwoPointFiveMove[] { Apply(permutation, random) };
     67      return new[] { Apply(permutation, RandomParameter.ActualValue) };
    7168    }
    7269  }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMove.cs

    r12272 r13412  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Encodings.PermutationEncoding;
    … …  
    526
    627namespace HeuristicLab.Problems.PTSP {
    7   public class TwoPointFiveMove : Item {
    8    
     28  [Item("2.5-Move", "Represents a 2.5-move.")]
     29  [StorableClass]
     30  public sealed class TwoPointFiveMove : Item {
     31    [Storable]
     32    public int Index1 { get; protected set; }
     33    [Storable]
     34    public int Index2 { get; protected set; }
     35    [Storable]
     36    public Permutation Permutation { get; protected set; }
     37    [Storable]
     38    public bool IsInvert { get; protected set; }
     39
    940    [StorableConstructor]
    10     public TwoPointFiveMove() : this(-1, -1,null, true) { }
    11     protected TwoPointFiveMove(bool deserializing) : base(deserializing) { }
    12     protected TwoPointFiveMove(TwoPointFiveMove original, Cloner cloner)
     41    public TwoPointFiveMove() : this(-1, -1, null, true) { }
     42    private TwoPointFiveMove(bool deserializing) : base(deserializing) { }
     43    private TwoPointFiveMove(TwoPointFiveMove original, Cloner cloner)
    1344      : base(original, cloner) {
    1445      this.Index1 = original.Index1;
    1546      this.Index2 = original.Index2;
    1647      this.IsInvert = original.IsInvert;
    17       if (original.Permutation != null)
    18         this.Permutation = cloner.Clone(original.Permutation);
     48      this.Permutation = cloner.Clone(original.Permutation);
    1949    }
    2050    public TwoPointFiveMove(int index1, int index2, Permutation permutation, bool isinvert)
    … …  
    3464    }
    3565
    36     [Storable]
    37     public int Index1 { get; protected set; }
    38     [Storable]
    39     public int Index2 { get; protected set; }
    40     [Storable]
    41     public Permutation Permutation { get; protected set; }
    42     [Storable]
    43     public bool IsInvert { get; protected set; }
    44 
    4566    public override IDeepCloneable Clone(Cloner cloner) {
    4667      return new TwoPointFiveMove(this, cloner);

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMoveGenerator.cs

    r13408 r13412  
    3232  [Item("TwoPointFiveMoveGenerator", "Base class for all inversion and shift (2.5-opt) move generators.")]
    3333  [StorableClass]
    34   public abstract class TwoPointFiveMoveGenerator : SingleSuccessorOperator, I25MoveOperator, IMoveGenerator {
     34  public abstract class TwoPointFiveMoveGenerator : SingleSuccessorOperator, ITwoPointFiveMoveOperator, IMoveGenerator {
    3535    public override bool CanChangeName {
    3636      get { return false; }
    3737    }
     38
    3839    public ILookupParameter<Permutation> PermutationParameter {
    3940      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
    … …  
    4243      get { return (LookupParameter<TwoPointFiveMove>)Parameters["TwoPointFiveMove"]; }
    4344    }
    44     protected ScopeParameter CurrentScopeParameter {
    45       get { return (ScopeParameter)Parameters["CurrentScope"]; }
    46     }
    4745
    4846    [StorableConstructor]
    4947    protected TwoPointFiveMoveGenerator(bool deserializing) : base(deserializing) { }
    5048    protected TwoPointFiveMoveGenerator(TwoPointFiveMoveGenerator original, Cloner cloner) : base(original, cloner) { }
    51     public TwoPointFiveMoveGenerator()
     49    protected TwoPointFiveMoveGenerator()
    5250      : base() {
    5351      Parameters.Add(new LookupParameter<Permutation>("Permutation", "The permutation for which moves should be generated."));
    … …  
    5755
    5856    public override IOperation Apply() {
    59       Permutation p = PermutationParameter.ActualValue;
    60       TwoPointFiveMove[] moves = GenerateMoves(p);
    61       Scope[] moveScopes = new Scope[moves.Length];
     57      var p = PermutationParameter.ActualValue;
     58      var moves = GenerateMoves(p);
     59      var moveScopes = new Scope[moves.Length];
    6260      for (int i = 0; i < moveScopes.Length; i++) {
    6361        moveScopes[i] = new Scope(i.ToString());
    6462        moveScopes[i].Variables.Add(new Variable(TwoPointFiveMoveParameter.ActualName, moves[i]));
    6563      }
    66       CurrentScopeParameter.ActualValue.SubScopes.AddRange(moveScopes);
     64      ExecutionContext.Scope.SubScopes.AddRange(moveScopes);
    6765      return base.Apply();
    6866    }

  • branches/PTSP/HeuristicLab.Problems.PTSP/3.3/Moves/TwoPointFiveOpt/TwoPointFiveMoveMaker.cs

    r13408 r13412  
    1 using HeuristicLab.Common;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using HeuristicLab.Common;
    223using HeuristicLab.Core;
    324using HeuristicLab.Data;
    … …  
    1132  [Item("TwoPointFiveMoveMaker", "Peforms an inversion and shift (2.5-opt) on a given permutation and updates the quality.")]
    1233  [StorableClass]
    13   public class TwoPointFiveMoveMaker : SingleSuccessorOperator, I25MoveOperator, IMoveMaker {
     34  public class TwoPointFiveMoveMaker : SingleSuccessorOperator, ITwoPointFiveMoveOperator, IMoveMaker {
    1435    public override bool CanChangeName {
    1536      get { return false; }
    1637    }
     38
    1739    public ILookupParameter<DoubleValue> QualityParameter {
    1840      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    … …  
    2749      get { return (ILookupParameter<Permutation>)Parameters["Permutation"]; }
    2850    }
     51
    2952    [StorableConstructor]
    3053    protected TwoPointFiveMoveMaker(bool deserializing) : base(deserializing) { }
    … …  
    4366
    4467    public override IOperation Apply() {
    45       TwoPointFiveMove move = TwoPointFiveMoveParameter.ActualValue;
    46       Permutation permutation = PermutationParameter.ActualValue;
    47       DoubleValue moveQuality = MoveQualityParameter.ActualValue;
    48       DoubleValue quality = QualityParameter.ActualValue;
     68      var move = TwoPointFiveMoveParameter.ActualValue;
     69      var permutation = PermutationParameter.ActualValue;
     70      var moveQuality = MoveQualityParameter.ActualValue;
     71      var quality = QualityParameter.ActualValue;
    4972
    5073      if (move.IsInvert) {
    … …  
    5376        TranslocationManipulator.Apply(permutation, move.Index1, move.Index1, move.Index2);
    5477      }
    55      
     78
    5679      quality.Value = moveQuality.Value;
    5780
Note: See TracChangeset for help on using the changeset viewer.