#region License Information /* HeuristicLab * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL) * * This file is part of HeuristicLab. * * HeuristicLab is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * HeuristicLab is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with HeuristicLab. If not, see . */ #endregion using System.Collections.Generic; using System.Linq; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Operators; using HeuristicLab.Optimization; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.Orienteering { /// /// Iterative improvement consists of three basic operators: shortening, vertex insert and vertex /// exchange. The shortening operator tries to rearrange the vertices within a tour in order to /// minimize the cost of the tour. As shortening operator a 2-opt is applied. (Schilde et. al. 2009) /// [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.")] [StorableClass] public sealed class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator { #region Parameter Properties public ILookupParameter IntegerVectorParameter { get { return (ILookupParameter)Parameters["OrienteeringSolution"]; } } public ILookupParameter DistanceMatrixParameter { get { return (ILookupParameter)Parameters["DistanceMatrix"]; } } public ILookupParameter ScoresParameter { get { return (ILookupParameter)Parameters["Scores"]; } } public ILookupParameter MaximumDistanceParameter { get { return (ILookupParameter)Parameters["MaximumDistance"]; } } public ILookupParameter StartingPointParameter { get { return (ILookupParameter)Parameters["StartingPoint"]; } } public ILookupParameter TerminalPointParameter { get { return (ILookupParameter)Parameters["TerminalPoint"]; } } public ILookupParameter PointVisitingCostsParameter { get { return (ILookupParameter)Parameters["PointVisitingCosts"]; } } #region ILocalImprovementOperator Parameters public IValueLookupParameter LocalIterationsParameter { get { return (IValueLookupParameter)Parameters["LocalIterations"]; } } public IValueLookupParameter MaximumIterationsParameter { get { return (IValueLookupParameter)Parameters["MaximumIterations"]; } } public ILookupParameter EvaluatedSolutionsParameter { get { return (ILookupParameter)Parameters["EvaluatedSolutions"]; } } public ILookupParameter ResultsParameter { get { return (ILookupParameter)Parameters["Results"]; } } #endregion public ILookupParameter QualityParameter { get { return (ILookupParameter)Parameters["Quality"]; } } public IValueParameter MaximumBlockLengthParmeter { get { return (IValueParameter)Parameters["MaximumBlockLength"]; } } public IValueParameter UseMaximumBlockLengthParmeter { get { return (IValueParameter)Parameters["UseMaximumBlockLength"]; } } #endregion [StorableConstructor] private OrienteeringLocalImprovementOperator(bool deserializing) : base(deserializing) { } private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner) : base(original, cloner) { } public OrienteeringLocalImprovementOperator() : base() { Parameters.Add(new LookupParameter("OrienteeringSolution", "The Orienteering Solution given in path representation.")); Parameters.Add(new LookupParameter("DistanceMatrix", "The matrix which contains the distances between the points.")); Parameters.Add(new LookupParameter("Scores", "The scores of the points.")); Parameters.Add(new LookupParameter("MaximumDistance", "The maximum distance constraint for a Orienteering solution.")); Parameters.Add(new LookupParameter("StartingPoint", "Index of the starting point.")); Parameters.Add(new LookupParameter("TerminalPoint", "Index of the ending point.")); Parameters.Add(new LookupParameter("PointVisitingCosts", "The costs for visiting a point.")); Parameters.Add(new ValueLookupParameter("LocalIterations", "The number of iterations that have already been performed.", new IntValue(0))); Parameters.Add(new ValueLookupParameter("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150))); Parameters.Add(new LookupParameter("EvaluatedSolutions", "The number of evaluated moves.")); Parameters.Add(new LookupParameter("Results", "The name of the collection where the results are stored.")); Parameters.Add(new LookupParameter("Quality", "The quality value of the solution.")); Parameters.Add(new ValueParameter("MaximumBlockLength", "The maximum length of the 2-opt shortening.", new IntValue(30))); Parameters.Add(new ValueParameter("UseMaximumBlockLength", "Use a limitation of the length for the 2-opt shortening.", new BoolValue(false))); } public override IDeepCloneable Clone(Cloner cloner) { return new OrienteeringLocalImprovementOperator(this, cloner); } public override IOperation Apply() { int numPoints = ScoresParameter.ActualValue.Length; var distances = DistanceMatrixParameter.ActualValue; var scores = ScoresParameter.ActualValue; double pointVisitingCosts = PointVisitingCostsParameter.ActualValue.Value; double maxLength = MaximumDistanceParameter.ActualValue.Value; int maxIterations = MaximumIterationsParameter.ActualValue.Value; int maxBlockLength = MaximumBlockLengthParmeter.Value.Value; bool useMaxBlockLength = UseMaximumBlockLengthParmeter.Value.Value; bool solutionChanged = true; var tour = IntegerVectorParameter.ActualValue.ToList(); double tourLength = 0; double tourScore = tour.Sum(point => scores[point]); var localIterations = LocalIterationsParameter.ActualValue; var evaluatedSolutions = EvaluatedSolutionsParameter.ActualValue; int evaluations = 0; // Check if the tour can be improved by adding or replacing points while (solutionChanged && localIterations.Value < maxIterations) { solutionChanged = false; if (localIterations.Value == 0) tourLength = distances.CalculateTourLength(tour, pointVisitingCosts); // Try to shorten the path ShortenPath(tour, distances, maxBlockLength, useMaxBlockLength, ref tourLength, ref evaluations); // Determine all points that have not yet been visited by this tour var visitablePoints = Enumerable.Range(0, numPoints).Except(tour).ToList(); // Determine if any of the visitable points can be included at any position within the tour IncludeNewPoints(tour, visitablePoints, distances, pointVisitingCosts, maxLength, scores, ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); // Determine if any of the visitable points can take the place of an already visited point in the tour to improve the scores ReplacePoints(tour, visitablePoints, distances, maxLength, scores, ref tourLength, ref tourScore, ref evaluations, ref solutionChanged); localIterations.Value++; } localIterations.Value = 0; evaluatedSolutions.Value += evaluations; // Set new tour IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray()); QualityParameter.ActualValue.Value = tourScore; return base.Apply(); } private void ShortenPath(List tour, DistanceMatrix distances, int maxBlockLength, bool useMaxBlockLength, ref double tourLength, ref int evaluations) { bool solutionChanged; int pathSize = tour.Count; maxBlockLength = (useMaxBlockLength && (pathSize > maxBlockLength + 1)) ? maxBlockLength : (pathSize - 2); // Perform a 2-opt do { solutionChanged = false; for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; for (int position = 1; position < (pathSize - blockLength); position++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; evaluations++; double newLength = tourLength; // Recalculate length of whole swapped part, in case distances are not symmetric for (int index = position - 1; index < position + blockLength; index++) newLength -= distances[tour[index], tour[index + 1]]; for (int index = position + blockLength - 1; index > position; index--) newLength += distances[tour[index], tour[index - 1]]; newLength += distances[tour[position - 1], tour[position + blockLength - 1]]; newLength += distances[tour[position], tour[position + blockLength]]; if (newLength < tourLength - 0.00001) { // Avoid cycling caused by precision var reversePart = tour.GetRange(position, blockLength).AsEnumerable().Reverse(); tour.RemoveRange(position, blockLength); tour.InsertRange(position, reversePart); tourLength = newLength; // Re-run the optimization solutionChanged = true; } } } } while (solutionChanged); } private void IncludeNewPoints(List tour, List visitablePoints, DistanceMatrix distances, double pointVisitingCosts, double maxLength, DoubleArray scores, ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; evaluations++; double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], pointVisitingCosts); // Determine if including the point does not violate any constraint if (tourLength + detour <= maxLength) { // Insert the new point at this position tour.Insert(tourPosition, visitablePoints[i]); // Update the overall tour tourLength and score tourLength += detour; tourScore += scores[visitablePoints[i]]; // Re-run this optimization solutionChanged = true; } } } } private void ReplacePoints(List tour, List visitablePoints, DistanceMatrix distances, double maxLength, DoubleArray scores, ref double tourLength, ref double tourScore, ref int evaluations, ref bool solutionChanged) { for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (solutionChanged) break; evaluations++; double detour = distances.CalculateReplacementCosts(tour, tourPosition, visitablePoints[i]); double oldPointScore = scores[tour[tourPosition]]; double newPointScore = scores[visitablePoints[i]]; if ((tourLength + detour <= maxLength) && (newPointScore > oldPointScore)) { // Replace the old point by the new one tour[tourPosition] = visitablePoints[i]; // Update the overall tour tourLength tourLength += detour; // Update the scores achieved by visiting this point tourScore += newPointScore - oldPointScore; // Re-run this optimization solutionChanged = true; } } } } } }