#region License Information
/* HeuristicLab
* Copyright (C) 2002-2015 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 HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using System;
namespace HeuristicLab.Problems.PTSP {
///
/// An operator to evaluate inversion moves (2-opt).
///
[Item("PTSPAnalyticalInversionMovePathEvaluator", "Evaluates an inversion move (2-opt) of the PTSP in with the closed form expression")]
[StorableClass]
public class PTSPAnalyticalInversionMovePathEvaluator : PTSPPathMoveEvaluator, IPermutationInversionMoveOperator {
private static DoubleArray probabilities;
private static DoubleMatrix A;
private static DoubleMatrix B;
public override Type EvaluatorType {
get { return typeof(PTSPAnalyticalInversionMovePathEvaluator); }
}
public ILookupParameter InversionMoveParameter {
get { return (ILookupParameter)Parameters["InversionMove"]; }
}
public IValueParameter ProbabilitiesParameter {
get { return (IValueParameter)Parameters["Probabilities"]; }
}
public IValueParameter AParameter {
get { return (IValueParameter)Parameters["A"]; }
}
public IValueParameter BParameter {
get { return (IValueParameter)Parameters["B"]; }
}
[StorableConstructor]
protected PTSPAnalyticalInversionMovePathEvaluator(bool deserializing) : base(deserializing) { }
protected PTSPAnalyticalInversionMovePathEvaluator(PTSPAnalyticalInversionMovePathEvaluator original, Cloner cloner) : base(original, cloner) { }
public PTSPAnalyticalInversionMovePathEvaluator()
: base() {
Parameters.Add(new LookupParameter("InversionMove", "The move to evaluate."));
Parameters.Add(new ValueParameter>("Probabilities", "The probabilities of the current instance"));
Parameters.Add(new ValueParameter("A", "The matrix A for delta evaluation"));
Parameters.Add(new ValueParameter("B", "The matrix B for delta evaluation"));
}
public override IDeepCloneable Clone(Cloner cloner) {
return new PTSPAnalyticalInversionMovePathEvaluator(this, cloner);
}
public static double EvaluateByCoordinates(Permutation permutation, InversionMove move, DoubleMatrix coordinates, PTSPAnalyticalInversionMovePathEvaluator evaluator) {
int edge1source = permutation.GetCircular(move.Index1 - 1);
int edge1target = permutation[move.Index1];
int edge2source = permutation[move.Index2];
int edge2target = permutation.GetCircular(move.Index2 + 1);
if (move.Index2 - move.Index1 >= permutation.Length - 2) return 0;
double moveQuality = 0;
// remove two edges
moveQuality -= evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
coordinates[edge1target, 0], coordinates[edge1target, 1]);
moveQuality -= evaluator.CalculateDistance(coordinates[edge2source, 0], coordinates[edge2source, 1],
coordinates[edge2target, 0], coordinates[edge2target, 1]);
// add two edges
moveQuality += evaluator.CalculateDistance(coordinates[edge1source, 0], coordinates[edge1source, 1],
coordinates[edge2source, 0], coordinates[edge2source, 1]);
moveQuality += evaluator.CalculateDistance(coordinates[edge1target, 0], coordinates[edge1target, 1],
coordinates[edge2target, 0], coordinates[edge2target, 1]);
return moveQuality;
}
public static double EvaluateByDistanceMatrix(Permutation permutation, InversionMove move, DistanceMatrix distanceMatrix) {
int i = move.Index1;
int j = move.Index2;
return RecursiveExpectedCost(1, i, j) + RecursiveExpectedCost(2, i, j) - RecursiveExpectedCost(3, i, j);
}
protected static double RecursiveExpectedCost(int s, int i, int j) {
switch (s) {
case 1:
if (j == i + 1) {
return (1/(1-probabilities[i+1]))*A[i,2]+(1 - probabilities[i])*(A[i+1,1]-A[i+1,probabilities.Length-1]);
} else if (i == j) {
return A[i,1];
} else {
// Equation 25
return ((1 - probabilities[i]) / (1 - probabilities[j])) * RecursiveExpectedCost(1, i + 1, j - 1) + (1 - probabilities[i]) * (1);
}
case 2:
if (j == i + 1) {
return (1 - probabilities[i + 1]) * (B[i, 1] - B[i, probabilities.Length - 1]) + (1 / (1 - probabilities[i])) * (B[i + 1, 2]);
} else if (i == j) {
return B[i,1];
} else {
return 0;
// Equation 26
}
case 3:
if (j == i + 1) {
return A[i, 2] + A[i + 1, 1] - A[i + 1, probabilities.Length - 1] + B[i, 1] - B[i, probabilities.Length - 1] + B[i + 1, 2];
} else if (i == j) {
return A[i,1]+B[i,1];
} else {
return 0;
// Equation 27
}
default:
return 0;
}
}
private double Q(int i, int j, DoubleArray probabilities) {
double prod = 1;
for (int k = i; k <= j; k++) {
prod *= (1 - probabilities[k]);
}
return prod;
}
private double Q_hat(int i, int j, DoubleArray probabilities) {
double prod = 1;
for (int k = i; k <= j; k++) {
prod *= (1-probabilities[k]);
}
return prod;
}
protected override double EvaluateByCoordinates(Permutation permutation, DoubleMatrix coordinates) {
return EvaluateByCoordinates(permutation, InversionMoveParameter.ActualValue, coordinates, this);
}
protected override double EvaluateByDistanceMatrix(Permutation permutation, DistanceMatrix distanceMatrix) {
A = AParameter.Value;
B = BParameter.Value;
probabilities = ProbabilitiesParameter.Value;
return EvaluateByDistanceMatrix(permutation, InversionMoveParameter.ActualValue, distanceMatrix);
}
protected override double CalculateDistance(double x1, double y1, double x2, double y2) {
return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
}
}