#region License Information
/* HeuristicLab
* Copyright (C) 2002-2019 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.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HEAL.Attic;
namespace HeuristicLab.Problems.PTSP {
///
/// An operator that improves probabilistic traveling salesman solutions.
///
///
/// The operator tries to improve the probabilistic traveling salesman solution by inserting a city in the tour between two other cities for a certain number of times.
///
[Item("PTSP Analytical Insertion Local Improvement", "An operator that improves probabilistic traveling salesman solutions. The operator tries to improve the probabilistic traveling salesman solution by swapping two randomly chosen edges for a certain number of times.")]
[StorableType("D63C6CB3-A5EF-4270-A252-2F5EBF1ED163")]
public sealed class PTSPAnalyticalInsertionLocalImprovement : SingleSuccessorOperator, IAnalyticalPTSPOperator, ILocalImprovementOperator {
public ILookupParameter LocalIterationsParameter {
get { return (ILookupParameter)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"]; }
}
public ILookupParameter PermutationParameter {
get { return (ILookupParameter)Parameters["Permutation"]; }
}
public ILookupParameter QualityParameter {
get { return (ILookupParameter)Parameters["Quality"]; }
}
public ILookupParameter MaximizationParameter {
get { return (ILookupParameter)Parameters["Maximization"]; }
}
public ILookupParameter DistanceMatrixParameter {
get { return (ILookupParameter)Parameters["DistanceMatrix"]; }
}
public ILookupParameter ProbabilitiesParameter {
get { return (ILookupParameter)Parameters["Probabilities"]; }
}
[StorableConstructor]
private PTSPAnalyticalInsertionLocalImprovement(StorableConstructorFlag _) : base(_) { }
private PTSPAnalyticalInsertionLocalImprovement(PTSPAnalyticalInsertionLocalImprovement original, Cloner cloner) : base(original, cloner) { }
public PTSPAnalyticalInsertionLocalImprovement()
: base() {
Parameters.Add(new LookupParameter("Permutation", "The solution as permutation."));
Parameters.Add(new LookupParameter("LocalIterations", "The number of iterations that have already been performed."));
Parameters.Add(new ValueLookupParameter("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached).", new IntValue(10000)));
Parameters.Add(new LookupParameter("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation)."));
Parameters.Add(new LookupParameter("Results", "The collection where to store results."));
Parameters.Add(new LookupParameter("Quality", "The quality value of the assignment."));
Parameters.Add(new LookupParameter("Maximization", "True if the problem should be maximized or minimized."));
Parameters.Add(new LookupParameter("DistanceMatrix", "The matrix which contains the distances between the cities."));
Parameters.Add(new LookupParameter("Probabilities", "The list of probabilities of the cities to appear."));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new PTSPAnalyticalInsertionLocalImprovement(this, cloner);
}
public static void Improve(Permutation assignment, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, DoubleArray probabilities, CancellationToken cancellation) {
var distanceM = (DistanceMatrix)distances;
Func distance = (a, b) => distanceM[a, b];
for (var i = localIterations.Value; i < maxIterations; i++) {
TranslocationMove bestMove = null;
var bestQuality = quality.Value; // we have to make an improvement, so current quality is the baseline
var evaluations = 0.0;
foreach (var move in ExhaustiveInsertionMoveGenerator.Generate(assignment)) {
var moveQuality = PTSPAnalyticalInsertionMoveEvaluator.EvaluateMove(assignment, move, distance, probabilities);
evaluations++;
if (maximization && moveQuality > bestQuality
|| !maximization && moveQuality < bestQuality) {
bestQuality = moveQuality;
bestMove = move;
}
}
evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
if (bestMove == null) break;
TranslocationManipulator.Apply(assignment, bestMove.Index1, bestMove.Index2, bestMove.Index3);
quality.Value = bestQuality;
localIterations.Value++;
cancellation.ThrowIfCancellationRequested();
}
}
public override IOperation Apply() {
var maxIterations = MaximumIterationsParameter.ActualValue.Value;
var assignment = PermutationParameter.ActualValue;
var maximization = MaximizationParameter.ActualValue.Value;
var distances = DistanceMatrixParameter.ActualValue;
var quality = QualityParameter.ActualValue;
var localIterations = LocalIterationsParameter.ActualValue;
var evaluations = EvaluatedSolutionsParameter.ActualValue;
var probabilities = ProbabilitiesParameter.ActualValue;
if (localIterations == null) {
localIterations = new IntValue(0);
LocalIterationsParameter.ActualValue = localIterations;
}
Improve(assignment, distances, quality, localIterations, evaluations, maximization, maxIterations, probabilities, CancellationToken);
localIterations.Value = 0;
return base.Apply();
}
}
}