#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.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("OrienteeringShakingOperator", @"The used neighborhood operator is based on a two point exchange move. A move in
the k-th neighborhood consists of removing k consecutive vertices from the tour, starting
at a randomly selected position. Afterwards, a sorted list of all vertices not yet included
in the current tour is built. The vertices are sorted in descending order with respect to the
objective value increase using the current weights. Out of the first three entries with the
highest ranking in this list, one randomly selected vertex is reinserted into the current tour
at the same position as the removed vertices. This way, l new vertices are inserted into the
tour. The largest neighborhood is a complete exchange of all vertices on the tour.
The shaking procedure does not guarantee that the new tour does not exceed the cost
limit Tmax. Therefore, in a repair step, a sorted list of all vertices in the tour is created. The
vertices are sorted in descending order with respect to costs saved when removing the vertex
from the tour. Vertices are removed as long as the cost limit is violated.
(Schilde et. al. 2009)")]
[StorableClass]
public class OrienteeringShakingOperator : SingleSuccessorOperator, IMultiNeighborhoodShakingOperator, IStochasticOperator {
#region Shaking Parameter Properties
public IValueLookupParameter CurrentNeighborhoodIndexParameter {
get { return (IValueLookupParameter)Parameters["CurrentNeighborhoodIndex"]; }
}
public ILookupParameter NeighborhoodCountParameter {
get { return (ILookupParameter)Parameters["NeighborhoodCount"]; }
}
#endregion
#region Parameter Properties
public ILookupParameter IntegerVectorParameter {
get { return (ILookupParameter)Parameters["IntegerVector"]; }
}
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 DistanceMatrixParameter {
get { return (ILookupParameter)Parameters["DistanceMatrix"]; }
}
public ILookupParameter ScoresParameter {
get { return (ILookupParameter)Parameters["Scores"]; }
}
public ILookupParameter FixedPenaltyParameter {
get { return (ILookupParameter)Parameters["FixedPenalty"]; }
}
public ILookupParameter RandomParameter {
get { return (ILookupParameter)Parameters["Random"]; }
}
#endregion
[StorableConstructor]
private OrienteeringShakingOperator(bool deserializing) : base(deserializing) { }
private OrienteeringShakingOperator(OrienteeringShakingOperator original, Cloner cloner)
: base(original, cloner) {
}
public OrienteeringShakingOperator()
: base() {
Parameters.Add(new ValueLookupParameter("CurrentNeighborhoodIndex", "The index of the operator that should be applied (k)."));
Parameters.Add(new LookupParameter("NeighborhoodCount", "The number of operators that are available."));
Parameters.Add(new LookupParameter("IntegerVector", "The Orienteering Solution given in path representation."));
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("DistanceMatrix", "The matrix which contains the distances between the points."));
Parameters.Add(new LookupParameter("Scores", "The scores of the points."));
Parameters.Add(new LookupParameter("FixedPenalty", "The penalty for each visited vertex."));
Parameters.Add(new LookupParameter("Random", "The random number generator that will be used."));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new OrienteeringShakingOperator(this, cloner);
}
public override IOperation Apply() {
var initialTour = IntegerVectorParameter.ActualValue;
var distances = DistanceMatrixParameter.ActualValue;
var scores = ScoresParameter.ActualValue;
var startingPoint = StartingPointParameter.ActualValue.Value;
var terminusPoint = TerminusPointParameter.ActualValue.Value;
var fixedPenalty = FixedPenaltyParameter.ActualValue.Value;
double maxDistance = MaximumDistanceParameter.ActualValue.Value;
int numPoints = scores.Length;
if (NeighborhoodCountParameter.ActualValue == null)
NeighborhoodCountParameter.ActualValue = new IntValue(initialTour.Length);
else NeighborhoodCountParameter.ActualValue.Value = initialTour.Length;
var random = RandomParameter.ActualValue;
if (initialTour.Length > 2) {
// Limit the neighborhood to the tour length
int maxNeighborhood = CurrentNeighborhoodIndexParameter.ActualValue.Value + 1;
int limit = initialTour.Length - 3; // neighborhood limit within [0, length-1)
int neighborhood = random.Next((limit > maxNeighborhood) ? maxNeighborhood : limit) + 1;
// Find all points that are not yet included in the tour and are
// within the maximum distance allowed (ellipse)
// and sort them with regard to their utility
var visitablePoints = (
from point in Enumerable.Range(0, numPoints)
// Calculate the distance when going from the starting point to this point and then to the end point
let distance = distances[startingPoint, point] + distances[point, terminusPoint] + fixedPenalty
// If this distance is feasible and the point is neither starting nor ending point, check the point
where distance < maxDistance && point != startingPoint && point != terminusPoint
// The point was not yet visited, so add it to the candidate list
where !initialTour.Contains(point)
// Calculate the utility of the point at this position
let utility = scores[point]
orderby utility
select point
).ToList();
// Initialize the new tour
var actualTour = new List { startingPoint };
// Perform the insertions according to the utility sorting
InsertPoints(actualTour, initialTour, neighborhood, visitablePoints, random);
// Bring the tour back to be feasible
CleanupTour(actualTour, distances, maxDistance, fixedPenalty);
// Set new Tour
IntegerVectorParameter.ActualValue = new IntegerVector(actualTour.ToArray());
}
return base.Apply();
}
private void InsertPoints(List actualTour, IntegerVector initialTour,
int neighborhood, List visitablePoints, IRandom random) {
// Elect the starting index of the part to be replaced
int tourSize = initialTour.Length;
int randomPosition = random.Next(tourSize - neighborhood - 2) + 1;
for (int position = 1; position < tourSize; position++) {
if ((position < randomPosition) || (position > (randomPosition + neighborhood - 1))) {
// Copy from initial tour when outside shaking range
actualTour.Add(initialTour[position]);
// Delete this point from the candidate list
visitablePoints.Remove(initialTour[position]);
} else {
// Point from within shaking range
if (visitablePoints.Count > 0) {
// Add the point with the highest utility from the candidate list
int randomFactor = random.Next(3);
int insertionIndex = visitablePoints.Count - 1;
if (visitablePoints.Count > 4) insertionIndex -= randomFactor;
actualTour.Add(visitablePoints[insertionIndex]);
// Delete this point from the candidate list
visitablePoints.RemoveAt(insertionIndex);
} else {
// We don't have any points left that could be inserted so we can only re-insert
// the removed and not already re-inserted points in a random order
for (int reinsertPosition = randomPosition; reinsertPosition < randomPosition + neighborhood; reinsertPosition++) {
bool alreadyReinserted = actualTour.Contains(initialTour[reinsertPosition]);
if (!alreadyReinserted)
visitablePoints.Add(initialTour[reinsertPosition]);
}
int randomIndex = random.Next(visitablePoints.Count);
actualTour.Add(visitablePoints[randomIndex]);
visitablePoints.Clear();
}
}
}
}
private void CleanupTour(List actualTour, DistanceMatrix distances, double maxDistance, double fixedPenalty) {
// Sort the points on the tour according to their costs savings when removed
var distanceSavings = (
from removePosition in Enumerable.Range(1, actualTour.Count - 2)
let saving = distances.CalculateRemovementSaving(actualTour, removePosition, fixedPenalty)
orderby saving descending
select new SavingInfo { Index = removePosition, Saving = saving }
).ToList();
//double tourLength = distances.CalculateTourLength(actualTour, fixedPenalty);
// As long as the created path is infeasible, remove elements
while (distances.CalculateTourLength(actualTour, fixedPenalty) > maxDistance) {
// Remove the point that frees the largest distance
actualTour.RemoveAt(distanceSavings[0].Index);
//tourLength -= distanceSavings[0].Saving;
// Shift indices due to removal of a point in the tour
for (int i = 1; i < distanceSavings.Count; i++) {
if (distanceSavings[i].Index > distanceSavings[0].Index) {
distanceSavings[i].Index--;
// Note, distance savings are not updated after removal
}
}
distanceSavings.RemoveAt(0);
}
}
//
private class SavingInfo {
public int Index;
public double Saving;
}
}
}