#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;
}
}
}
}
}
}