Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/10/15 16:38:17 (9 years ago)
Author:
abeham
Message:

#2208:

  • Added missing license headers
  • Updates copyright year
  • Renamed analyzer (us spelling)
  • Removed script
  • Implemented samples unit test
  • Changed solution view to use horizontal splitting, removed viewhosts
  • Updated instance provider to use .NET45 zip compression
  • Restructuring and reformatting
Location:
branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3

    • Property svn:ignore
      •  

        old new  
        22obj
        33Plugin.cs
         4*.DotSettings
  • branches/HeuristicLab.Problems.Orienteering/HeuristicLab.Problems.Orienteering/3.3/Improvers/OrienteeringLocalImprovementOperator.cs

    r11323 r12721  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    2020#endregion
    2121
    22 using System;
    2322using System.Collections.Generic;
    2423using System.Linq;
     
    3332
    3433namespace HeuristicLab.Problems.Orienteering {
    35   [Item("OrienteeringLocalImprovementOperator", @"Iterative improvement consists of three basic operators: shortening, vertex insert and vertex
    36 exchange. The shortening operator tries to rearrange the vertices within a tour in order to
    37 minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009)")]
     34  /// <summary>
     35  /// Iterative improvement consists of three basic operators: shortening, vertex insert and vertex
     36  /// exchange. The shortening operator tries to rearrange the vertices within a tour in order to
     37  /// minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009)
     38  /// </summary>
     39  [Item("OrienteeringLocalImprovementOperator", @"Implements the iterative improvement procedure described in Schilde M., Doerner K.F., Hartl R.F., Kiechle G. 2009. Metaheuristics for the bi-objective orienteering problem. Swarm Intelligence, Volume 3, Issue 3, pp 179-201.")]
    3840  [StorableClass]
    3941  public sealed class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator {
     
    125127      bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value;
    126128
    127       bool optimizationDone = true;
     129      bool solutionChanged = true;
    128130
    129131      var tour = IntegerVectorParameter.ActualValue.ToList();
     
    137139
    138140      // Check if the tour can be improved by adding or replacing points
    139       while (optimizationDone && localIterations.Value < maxIterations) {
    140         optimizationDone = false;
     141      while (solutionChanged && localIterations.Value < maxIterations) {
     142        solutionChanged = false;
    141143
    142144        if (localIterations.Value == 0)
     
    152154        IncludeNewPoints(tour, visitablePoints,
    153155          distances, pointVisitingCosts, maxLength, scores,
    154           ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
     156          ref tourLength, ref tourScore, ref evaluations, ref solutionChanged);
    155157
    156158        // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores
    157159        ReplacePoints(tour, visitablePoints,
    158160          distances, maxLength, scores,
    159           ref tourLength, ref tourScore, ref evaluations, ref optimizationDone);
     161          ref tourLength, ref tourScore, ref evaluations, ref solutionChanged);
    160162
    161163        localIterations.Value++;
     
    173175
    174176    private void ShortenPath(List<int> tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) {
    175       bool optimizationDone = true;
     177      bool solutionChanged;
    176178      int pathSize = tour.Count;
    177179      maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2);
    178180
    179181      // Perform a 2-opt
    180       while (optimizationDone) {
    181         optimizationDone = false;
     182      do {
     183        solutionChanged = false;
    182184
    183185        for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) {
    184186          // If an optimization has been done, start from the beginning
    185           if (optimizationDone) break;
     187          if (solutionChanged) break;
    186188
    187189          for (int position = 1; position < (pathSize - blockLength); position++) {
    188190            // If an optimization has been done, start from the beginning
    189             if (optimizationDone) break;
     191            if (solutionChanged) break;
    190192
    191193            evaluations++;
     
    198200            newLength += distances[tour[position], tour[position + blockLength]];
    199201
    200             if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision
     202            if (newLength < tourLength - 0.00001) {
     203              // Avoid cycling caused by precision
    201204              var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse();
    202205
     
    207210
    208211              // Re-run the optimization
    209               optimizationDone = true;
     212              solutionChanged = true;
    210213            }
    211214          }
    212215        }
    213       }
    214     }
     216      } while (solutionChanged);
     217    }
     218
    215219    private void IncludeNewPoints(List<int> tour, List<int> visitablePoints,
    216220      DistanceMatrix distances, double pointVisitingCosts, double maxLength, DoubleArray scores,
    217       ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
     221      ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) {
    218222
    219223      for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) {
    220224        // If an optimization has been done, start from the beginning
    221         if (optimizationDone) break;
     225        if (solutionChanged) break;
    222226
    223227        for (int i = 0; i < visitablePoints.Count; i++) {
    224228          // If an optimization has been done, start from the beginning
    225           if (optimizationDone) break;
     229          if (solutionChanged) break;
    226230
    227231          evaluations++;
     
    239243
    240244            // Re-run this optimization
    241             optimizationDone = true;
     245            solutionChanged = true;
    242246          }
    243247        }
    244248      }
    245249    }
     250
    246251    private void ReplacePoints(List<int> tour, List<int> visitablePoints,
    247252      DistanceMatrix distances, double maxLength, DoubleArray scores,
    248       ref double tourLength, ref double tourScore, ref int evaluations, ref bool optimizationDone) {
     253      ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) {
    249254
    250255      for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) {
    251256        // If an optimization has been done, start from the beginning
    252         if (optimizationDone) break;
     257        if (solutionChanged) break;
    253258
    254259        for (int i = 0; i < visitablePoints.Count; i++) {
    255260          // If an optimization has been done, start from the beginning
    256           if (optimizationDone) break;
     261          if (solutionChanged) break;
    257262
    258263          evaluations++;
     
    274279
    275280            // Re-run this optimization
    276             optimizationDone = true;
     281            solutionChanged = true;
    277282          }
    278283        }
Note: See TracChangeset for help on using the changeset viewer.