Changeset 11242


Ignore:
Timestamp:
07/30/14 15:02:35 (7 years ago)
Author:
pfleck
Message:

#2208

  • Added MaximumBlockLength parameter in OrienteeringLocalImprovementOperator
  • Use and set parameter from ILocalImprovementOperator
File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

    r11237 r11242  
    8383    }
    8484    #region ILocalImprovementOperator Parameters
     85    public IValueLookupParameter<IntValue> LocalIterationsParameter {
     86      get { return (IValueLookupParameter<IntValue>)Parameters["LocalIterations"]; }
     87    }
    8588    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
    8689      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
     
    9598    public ILookupParameter<DoubleValue> QualityParameter {
    9699      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     100    }
     101    public IValueParameter<IntValue> MaximumBlockLengthParmeter {
     102      get { return (IValueParameter<IntValue>)Parameters["MaximumBlockLength"]; }
     103    }
     104    public IValueParameter<BoolValue> UseMaximumBlockLengthParmeter {
     105      get { return (IValueParameter<BoolValue>)Parameters["UseMaximumBlockLength"]; }
    97106    }
    98107    #endregion
     
    114123      Parameters.Add(new LookupParameter<DoubleValue>("FixedPenalty", "The penalty for each visited vertex."));
    115124
     125      Parameters.Add(new ValueLookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed.", new IntValue(0)));
    116126      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
    117127      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
    118128      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
    119129      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality value of the solution."));
     130
     131      Parameters.Add(new ValueParameter<IntValue>("MaximumBlockLength", "The maximum length of the 2-opt shortening.", new IntValue(30)));
     132      Parameters.Add(new ValueParameter<BoolValue>("UseMaximumBlockLength", "Use a limitation of the length for the 2-opt shortening.", new BoolValue(true)));
    120133    }
    121134
     
    130143      double fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
    131144      double maxLength = MaximumDistanceParameter.ActualValue.Value;
     145      int maxIterations = MaximumIterationsParameter.ActualValue.Value;
     146      int maxBlockLength = MaximumBlockLengthParmeter.Value.Value;
     147      bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value;
    132148
    133149      bool optimizationDone = true;
     
    138154      double tourScore = tour.Sum(point => scores[point]);
    139155
     156      var localIterations = LocalIterationsParameter.ActualValue;
     157      var evaluatedSolutions = EvaluatedSolutionsParameter.ActualValue;
     158      int evaluations = 0;
     159
    140160      // Check if the tour can be improved by adding or replacing points
    141       while (optimizationDone) {
     161      while (optimizationDone && localIterations.Value < maxIterations) {
    142162        optimizationDone = false;
    143163
    144164        // Try to shorten the path
    145         ShortenPath(tour, distances, ref tourLength);
     165        ShortenPath(tour, distances, maxBlockLength, useMaxBlockLength, ref tourLength, ref evaluations);
    146166
    147167        // Determine all points that have not yet been visited by this tour
     
    151171        IncludeNewPoints(tour, visitablePoints,
    152172          distances, fixedPenalty, maxLength, scores,
    153           ref tourLength, ref tourScore, ref optimizationDone);
     173          ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
    154174
    155175        // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
    156176        ReplacePoints(tour, visitablePoints,
    157177          distances, maxLength, scores,
    158           ref tourLength, ref tourScore, ref optimizationDone);
    159       }
     178          ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
     179
     180        localIterations.Value++;
     181      }
     182
     183      localIterations.Value = 0;
     184      evaluatedSolutions.Value += evaluations;
    160185
    161186      // Set new tour
     
    166191    }
    167192
    168     private void ShortenPath(List<int> tour, DistanceMatrix distances, ref double tourLength) {
     193    private void ShortenPath(List<int> tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) {
    169194      bool optimizationDone = true;
    170195      int pathSize = tour.Count;
    171       int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2);
     196      maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2);
    172197
    173198      // Perform a 2-opt
     
    182207            // If an optimization has been done, start from the beginning
    183208            if (optimizationDone) break;
     209
     210            evaluations++;
    184211
    185212            double newLength = tourLength;
     
    207234    private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
    208235      DistanceMatrix distances, double fixedPenalty, double maxLength, DoubleArray scores,
    209       ref double tourLength, ref double tourScore, ref bool optimizationDone) {
     236      ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
    210237
    211238      for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
     
    216243          // If an optimization has been done, start from the beginning
    217244          if (optimizationDone) break;
     245
     246          evaluations++;
    218247
    219248          double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], fixedPenalty);
     
    236265    private void ReplacePoints(List<int> tour, List<int> visitablePoints,
    237266      DistanceMatrix distances, double maxLength, DoubleArray scores,
    238       ref double tourLength, ref double tourScore, ref bool optimizationDone) {
     267      ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
    239268
    240269      for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) {
     
    245274          // If an optimization has been done, start from the beginning
    246275          if (optimizationDone) break;
     276
     277          evaluations++;
    247278
    248279          double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]);
Note: See TracChangeset for help on using the changeset viewer.