Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.PTSP/3.3/PTSP.cs @ 16125

Last change on this file since 16125 was 15584, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers on stable

File size: 12.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Encodings.PermutationEncoding;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Problems.Instances;
34
35namespace HeuristicLab.Problems.PTSP {
36  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
37  [StorableClass]
38  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
39  IProblemInstanceConsumer<PTSPData> {
40    protected bool SuppressEvents { get; set; }
41
42    private static readonly int DistanceMatrixSizeLimit = 1000;
43
44    #region Parameter Properties
45    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
46      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
47    }
48    public OptionalValueParameter<DistanceCalculator> DistanceCalculatorParameter {
49      get { return (OptionalValueParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
50    }
51    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
52      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
53    }
54    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
55      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
56    }
57    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
58      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
59    }
60    public IValueParameter<DoubleArray> ProbabilitiesParameter {
61      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
62    }
63    #endregion
64
65    #region Properties
66    public DoubleMatrix Coordinates {
67      get { return CoordinatesParameter.Value; }
68      set { CoordinatesParameter.Value = value; }
69    }
70    public DistanceCalculator DistanceCalculator {
71      get { return DistanceCalculatorParameter.Value; }
72      set { DistanceCalculatorParameter.Value = value; }
73    }
74    public DistanceMatrix DistanceMatrix {
75      get { return DistanceMatrixParameter.Value; }
76      set { DistanceMatrixParameter.Value = value; }
77    }
78    public bool UseDistanceMatrix {
79      get { return UseDistanceMatrixParameter.Value.Value; }
80      set { UseDistanceMatrixParameter.Value.Value = value; }
81    }
82    public Permutation BestKnownSolution {
83      get { return BestKnownSolutionParameter.Value; }
84      set { BestKnownSolutionParameter.Value = value; }
85    }
86    public DoubleArray Probabilities {
87      get { return ProbabilitiesParameter.Value; }
88      set { ProbabilitiesParameter.Value = value; }
89    }
90
91    #endregion
92
93    public override bool Maximization {
94      get { return false; }
95    }
96
97    [StorableConstructor]
98    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
99    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
100      : base(original, cloner) {
101      RegisterEventHandlers();
102    }
103    protected ProbabilisticTravelingSalesmanProblem() {
104      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
105      Parameters.Add(new OptionalValueParameter<DistanceCalculator>("DistanceCalculator", "Calculates the distance between two rows in the coordinates matrix."));
106      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
107      Parameters.Add(new FixedValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
108      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
109      Parameters.Add(new ValueParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
110
111      var coordinates = new DoubleMatrix(new double[,] {
112        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
113        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
114        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
115        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
116      });
117      Coordinates = coordinates;
118      Encoding.Length = coordinates.Rows;
119      DistanceCalculator = new EuclideanDistance();
120      DistanceMatrix = new DistanceMatrix(CalculateDistances());
121      Probabilities = new DoubleArray(Enumerable.Range(0, coordinates.Rows).Select(x => 0.5).ToArray());
122
123      InitializeOperators();
124      Parameterize();
125      RegisterEventHandlers();
126    }
127
128    private void InitializeOperators() {
129      Operators.Add(new HammingSimilarityCalculator());
130      Operators.Add(new QualitySimilarityCalculator());
131      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
132    }
133
134    [StorableHook(HookType.AfterDeserialization)]
135    private void AfterDeserialization() {
136      RegisterEventHandlers();
137    }
138
139    protected override void OnEncodingChanged() {
140      base.OnEncodingChanged();
141      Encoding.Length = Coordinates.Rows;
142      Parameterize();
143    }
144
145    private void RegisterEventHandlers() {
146      CoordinatesParameter.ValueChanged += CoordinatesParameterOnValueChanged;
147      if (Coordinates != null) {
148        Coordinates.RowsChanged += CoordinatesOnChanged;
149        Coordinates.ItemChanged += CoordinatesOnChanged;
150      }
151      UseDistanceMatrixParameter.Value.ValueChanged += UseDistanceMatrixValueChanged;
152      DistanceCalculatorParameter.ValueChanged += DistanceCalculatorParameterOnValueChanged;
153    }
154
155    private void CoordinatesParameterOnValueChanged(object sender, EventArgs eventArgs) {
156      if (Coordinates != null) {
157        Coordinates.RowsChanged += CoordinatesOnChanged;
158        Coordinates.ItemChanged += CoordinatesOnChanged;
159      }
160      if (SuppressEvents) return;
161      UpdateInstance();
162    }
163
164    private void CoordinatesOnChanged(object sender, EventArgs eventArgs) {
165      if (SuppressEvents) return;
166      UpdateInstance();
167    }
168
169    private void UseDistanceMatrixValueChanged(object sender, EventArgs eventArgs) {
170      if (SuppressEvents) return;
171      UpdateInstance();
172    }
173
174    private void DistanceCalculatorParameterOnValueChanged(object sender, EventArgs eventArgs) {
175      if (SuppressEvents) return;
176      UpdateInstance();
177    }
178
179    public override double Evaluate(Individual individual, IRandom random) {
180      return Evaluate(individual.Permutation(), random);
181    }
182
183    public abstract double Evaluate(Permutation tour, IRandom random);
184
185    public double[,] CalculateDistances() {
186      var coords = Coordinates;
187      var len = coords.Rows;
188      var dist = DistanceCalculator;
189
190      var matrix = new double[len, len];
191      for (var i = 0; i < len - 1; i++)
192        for (var j = i + 1; j < len; j++)
193          matrix[i, j] = matrix[j, i] = dist.Calculate(i, j, coords);
194
195      return matrix;
196    }
197
198    public virtual void Load(PTSPData data) {
199      try {
200        SuppressEvents = true;
201        if (data.Coordinates == null && data.Distances == null)
202          throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
203        if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
204          throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
205        if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
206          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 respectively.");
207
208        switch (data.DistanceMeasure) {
209          case DistanceMeasure.Direct:
210            DistanceCalculator = null;
211            if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
212              DistanceCalculator = new EuclideanDistance();
213              UseDistanceMatrix = false;
214            } else UseDistanceMatrix = true;
215            break;
216          case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
217          case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
218          case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
219          case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
220          case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
221          case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
222          case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
223          default: throw new ArgumentException("Distance measure is unknown");
224        }
225
226        Name = data.Name;
227        Description = data.Description;
228
229        Probabilities = new DoubleArray(data.Probabilities);
230        BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
231        Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
232        DistanceMatrix = data.Dimension <= DistanceMatrixSizeLimit && UseDistanceMatrix ? new DistanceMatrix(data.GetDistanceMatrix()) : null;
233
234        Encoding.Length = data.Dimension;
235      } finally { SuppressEvents = false; }
236      OnReset();
237    }
238
239    private void UpdateInstance() {
240      var len = GetProblemDimension();
241      if (Coordinates != null && Coordinates.Rows <= DistanceMatrixSizeLimit
242        && DistanceCalculator != null && UseDistanceMatrix)
243        DistanceMatrix = new DistanceMatrix(CalculateDistances());
244      if (!UseDistanceMatrix) DistanceMatrix = null;
245      Encoding.Length = len;
246
247      OnReset();
248    }
249
250    private int GetProblemDimension() {
251      if (Coordinates == null && DistanceMatrix == null) throw new InvalidOperationException("Both coordinates and distance matrix are null, please specify at least one of them.");
252      return Coordinates != null ? Coordinates.Rows : DistanceMatrix.Rows;
253    }
254
255    private void Parameterize() {
256      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
257        similarityCalculator.SolutionVariableName = Encoding.SolutionCreator.PermutationParameter.ActualName;
258        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
259      }
260    }
261  }
262}
Note: See TracBrowser for help on using the repository browser.