#region License Information /* HeuristicLab * Copyright (C) 2002-2014 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; 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 { [Item("OrienteeringLocalImprovementOperator", @"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)")] [StorableClass] public class OrienteeringLocalImprovementOperator : SingleSuccessorOperator, ILocalImprovementOperator { #region IGenericLocalImprovementOperator Properties public Type ProblemType { get { return typeof(OrienteeringProblem); } } public IProblem Problem { get { return problem; } set { if (problem != value) { if (value != null && !(value is OrienteeringProblem)) throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned."); //if (problem != null) DeregisterProblemEventHandlers(); problem = (OrienteeringProblem)value; //if (problem != null) RegisterProblemEventHandlers(); //UpdateProblem(); } } } #endregion [Storable] private OrienteeringProblem problem; #region Parameter Properties public ILookupParameter IntegerVectorParameter { get { return (ILookupParameter)Parameters["IntegerVector"]; } } 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 TerminusPointParameter { get { return (ILookupParameter)Parameters["TerminusPoint"]; } } public ILookupParameter FixedPenaltyParameter { get { return (ILookupParameter)Parameters["FixedPenalty"]; } } #region ILocalImprovementOperator Parameters 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 #endregion [StorableConstructor] private OrienteeringLocalImprovementOperator(bool deserializing) : base(deserializing) { } private OrienteeringLocalImprovementOperator(OrienteeringLocalImprovementOperator original, Cloner cloner) : base(original, cloner) { this.problem = cloner.Clone(original.problem); //RegisterEventHandlers(); } public OrienteeringLocalImprovementOperator() : base() { Parameters.Add(new LookupParameter("IntegerVector", "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("TerminusPoint", "Index of the ending point.")); Parameters.Add(new LookupParameter("FixedPenalty", "The penalty for each visited vertex.")); 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.")); //RegisterEventHandlers(); } public override IDeepCloneable Clone(Cloner cloner) { return new OrienteeringLocalImprovementOperator(this, cloner); } [StorableHook(HookType.AfterDeserialization)] private void AfterDeserialization() { //RegisterEventHandlers(); } public override IOperation Apply() { // TODO Use LocalImprovementorOperator Parameters int numPoints = ScoresParameter.ActualValue.Length; var distances = DistanceMatrixParameter.ActualValue; var scores = ScoresParameter.ActualValue; double fixedPenalty = FixedPenaltyParameter.ActualValue.Value; bool optimizationDone = true; // Find the maximum distance restriction double maxLength = MaximumDistanceParameter.ActualValue.Value; var tour = IntegerVectorParameter.ActualValue.ToList(); double tourLength = distances.CalculateTourLength(tour, fixedPenalty); double score = tour.Sum(p => scores[p]); // Check if the tour can be improved by adding or replacing points while (optimizationDone) { optimizationDone = false; // Try to shorten the path ShortenPath(tour, distances, ref tourLength); // 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, fixedPenalty, maxLength, ref tourLength, ref optimizationDone); // 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 score, ref optimizationDone); } IntegerVectorParameter.ActualValue = new IntegerVector(tour.ToArray()); return base.Apply(); } private void ShortenPath(List tour, DistanceMatrix distances, ref double tourLength) { bool optimizationDone = true; int pathSize = tour.Count; int maxBlockLength = (pathSize > 31) ? 30 : (pathSize - 2); // Perform a 2-opt while (optimizationDone) { optimizationDone = false; for (int blockLength = 2; blockLength < maxBlockLength; blockLength++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; for (int position = 1; position < (pathSize - blockLength); position++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; double newLength = tourLength; for (int counterLength = (position - 1); counterLength < (position + blockLength); counterLength++) { newLength -= distances[tour[counterLength], tour[counterLength + 1]]; } for (int counterLength = (position + blockLength - 1); counterLength > (position); counterLength--) { newLength += distances[tour[counterLength], tour[counterLength - 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 partPath = tour.GetRange(position, blockLength); tour.RemoveRange(position, blockLength); tour.InsertRange(position, partPath.AsEnumerable().Reverse()); tourLength = newLength; // Re-run the optimization optimizationDone = true; } } } } } private void IncludeNewPoints(List tour, List visitablePoints, DistanceMatrix distances, double fixedPenalty, double maxLength, ref double tourLength, ref bool optimizationDone) { for (int tourPosition = 1; tourPosition < tour.Count; tourPosition++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; double detour = distances.CalculateInsertionCosts(tour, tourPosition, visitablePoints[i], fixedPenalty); // 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 tourLength += detour; // Re-run this optimization optimizationDone = true; } } } } private void ReplacePoints(List tour, List visitablePoints, DistanceMatrix distances, double maxLength, DoubleArray scores, ref double tourLength, ref double tourScore, ref bool optimizationDone) { for (int tourPosition = 1; tourPosition < tour.Count - 1; tourPosition++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; for (int i = 0; i < visitablePoints.Count; i++) { // If an optimization has been done, start from the beginning if (optimizationDone) break; 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 optimizationDone = true; } } } } } }