#region License Information
/* HeuristicLab
* Copyright (C) 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.Linq;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.TravelingSalesman;
using HeuristicLab.Random;
namespace HeuristicLab.Problems.PTSP {
[Item("Probabilistic TSP (pTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
[StorableType("86041a8c-14e6-46e1-b20f-566892c871f6")]
public abstract class ProbabilisticTSP : PermutationProblem,
IProblemInstanceConsumer {
protected bool SuppressEvents { get; set; }
public static int DistanceMatrixSizeLimit = 1000;
#region Parameter Properties
[Storable] public ValueParameter PTSPDataParameter { get; private set; }
[Storable] public OptionalValueParameter BestKnownSolutionParameter { get; private set; }
#endregion
#region Properties
public IProbabilisticTSPData ProbabilisticTSPData {
get { return PTSPDataParameter.Value; }
set { PTSPDataParameter.Value = value; }
}
public IProbabilisticTSPSolution BestKnownSolution {
get { return BestKnownSolutionParameter.Value; }
set { BestKnownSolutionParameter.Value = value; }
}
#endregion
[StorableConstructor]
protected ProbabilisticTSP(StorableConstructorFlag _) : base(_) { }
protected ProbabilisticTSP(ProbabilisticTSP original, Cloner cloner)
: base(original, cloner) {
PTSPDataParameter = cloner.Clone(original.PTSPDataParameter);
BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
}
protected ProbabilisticTSP() : base(new PermutationEncoding("Tour")) {
Maximization = false;
Parameters.Add(PTSPDataParameter = new ValueParameter("PTSP Data", "The main parameters for the pTSP."));
Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter("BestKnownSolution", "The best known solution of this pTSP instance."));
ProbabilisticTSPData = new MatrixPTSPData();
Encoding.Length = ProbabilisticTSPData.Cities;
}
protected override void OnEncodingChanged() {
base.OnEncodingChanged();
Encoding.Length = ProbabilisticTSPData.Cities;
}
public override void Analyze(Permutation[] solutions, double[] qualities, ResultCollection results, IRandom random) {
base.Analyze(solutions, qualities, results, random);
var max = Maximization;
var i = !max ? qualities.Select((x, index) => new { index, Quality = x }).OrderBy(x => x.Quality).First().index
: qualities.Select((x, index) => new { index, Quality = x }).OrderByDescending(x => x.Quality).First().index;
if (double.IsNaN(BestKnownQuality) ||
max && qualities[i] > BestKnownQuality ||
!max && qualities[i] < BestKnownQuality) {
BestKnownQuality = qualities[i];
BestKnownSolution = ProbabilisticTSPData.GetSolution((Permutation)solutions[i].Clone(), qualities[i]);
}
IResult bestSolutionResult;
if (results.TryGetValue("Best pTSP Solution", out bestSolutionResult)) {
var bestSolution = bestSolutionResult.Value as ITSPSolution;
if (bestSolution == null || Maximization && bestSolution.TourLength.Value < qualities[i]
|| !Maximization && bestSolution.TourLength.Value > qualities[i]) {
bestSolutionResult.Value = ProbabilisticTSPData.GetSolution(solutions[i], qualities[i]);
}
} else results.Add(new Result("Best pTSP Solution", ProbabilisticTSPData.GetSolution(solutions[i], qualities[i])));
}
public virtual void Load(PTSPData data) {
if (data.Coordinates == null && data.Distances == null)
throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
|| data.DistanceMeasure == DistanceMeasure.Manhattan
|| data.DistanceMeasure == DistanceMeasure.Maximum))
throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
Encoding.Length = data.Dimension;
Name = data.Name;
Description = data.Description;
if (data.Dimension <= DistanceMatrixSizeLimit) {
ProbabilisticTSPData = new MatrixPTSPData(data.Name, data.GetDistanceMatrix(), data.Probabilities, data.Coordinates) { Description = data.Description };
} else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
ProbabilisticTSPData = new MatrixPTSPData(data.Name, data.Distances, data.Probabilities, data.Coordinates) { Description = data.Description };
} else {
switch (data.DistanceMeasure) {
case DistanceMeasure.Att:
ProbabilisticTSPData = new AttPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
break;
case DistanceMeasure.Euclidean:
ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.None) { Description = data.Description };
break;
case DistanceMeasure.RoundedEuclidean:
ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.Midpoint) { Description = data.Description };
break;
case DistanceMeasure.UpperEuclidean:
ProbabilisticTSPData = new EuclideanPTSPData(data.Name, data.Coordinates, data.Probabilities, EuclideanTSPData.DistanceRounding.Ceiling) { Description = data.Description };
break;
case DistanceMeasure.Geo:
ProbabilisticTSPData = new GeoPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
break;
case DistanceMeasure.Manhattan:
ProbabilisticTSPData = new ManhattanPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
break;
case DistanceMeasure.Maximum:
ProbabilisticTSPData = new MaximumPTSPData(data.Name, data.Coordinates, data.Probabilities) { Description = data.Description };
break;
default:
throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
}
}
BestKnownSolution = null;
BestKnownQuality = double.NaN;
if (data.BestKnownTour != null) {
try {
var tour = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
var tourLength = Evaluate(tour, new MersenneTwister(1));
BestKnownSolution = new ProbabilisticTSPSolution(data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null, new PercentArray(data.Probabilities), tour, new DoubleValue(tourLength));
BestKnownQuality = tourLength;
} catch (InvalidOperationException) {
if (data.BestKnownQuality.HasValue)
BestKnownQuality = data.BestKnownQuality.Value;
}
} else if (data.BestKnownQuality.HasValue) {
BestKnownQuality = data.BestKnownQuality.Value;
}
OnReset();
}
}
}