Free cookie consent management tool by TermsFeed Policy Generator

source: branches/MemPRAlgorithm/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs @ 16095

Last change on this file since 16095 was 14456, checked in by abeham, 8 years ago

#2701:

  • Using evaluated solutions from HC as max evaluations for tabu walking in MemPR
  • Fixed some bugs in MemPR (permutation) regarding subspace calculation (true means okay, false means no)
  • Fixed bug in TSP
File size: 20.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 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.IO;
24using System.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Problems.Instances;
36
37namespace HeuristicLab.Problems.TravelingSalesman {
38  public enum TSPDistanceFunction { Euclidean, RoundedEuclidean, UpperEuclidean, Geo, DistanceMatrix };
39
40  [Item("Traveling Salesman Problem (TSP)", "Represents a symmetric Traveling Salesman Problem.")]
41  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 999)]
42  [StorableClass]
43  public sealed class TravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>, IStorableContent, IProblemInstanceConsumer<TSPData> {
44    public const double PI = 3.141592;
45    public const double RADIUS = 6378.388;
46    private static readonly int DistanceMatrixSizeLimit = 1000;
47
48    public override bool Maximization {
49      get { return false; }
50    }
51
52    #region Parameter Properties
53    [Storable]
54    private IFixedValueParameter<EnumValue<TSPDistanceFunction>> distanceFunctionParameter;
55    public IFixedValueParameter<EnumValue<TSPDistanceFunction>> DistanceFunctionParameter {
56      get { return distanceFunctionParameter; }
57    }
58    [Storable]
59    private OptionalValueParameter<DoubleMatrix> coordinatesParameter;
60    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
61      get { return coordinatesParameter; }
62    }
63    [Storable]
64    private OptionalValueParameter<DistanceMatrix> distanceMatrixParameter;
65    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
66      get { return distanceMatrixParameter; }
67    }
68    [Storable]
69    private IFixedValueParameter<BoolValue> useDistanceMatrixParameter;
70    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
71      get { return useDistanceMatrixParameter; }
72    }
73    [Storable]
74    private OptionalValueParameter<Permutation> bestKnownSolutionParameter;
75    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
76      get { return bestKnownSolutionParameter; }
77    }
78    #endregion
79
80    #region Properties
81    public TSPDistanceFunction DistanceFunction {
82      get { return distanceFunctionParameter.Value.Value; }
83      set { distanceFunctionParameter.Value.Value = value; }
84    }
85    public DoubleMatrix Coordinates {
86      get { return coordinatesParameter.Value; }
87      set { coordinatesParameter.Value = value; }
88    }
89    public DistanceMatrix DistanceMatrix {
90      get { return distanceMatrixParameter.Value; }
91      set { distanceMatrixParameter.Value = value; }
92    }
93    public bool UseDistanceMatrix {
94      get { return useDistanceMatrixParameter.Value.Value; }
95      set { useDistanceMatrixParameter.Value.Value = value; }
96    }
97    public Permutation BestKnownSolution {
98      get { return bestKnownSolutionParameter.Value; }
99      set { bestKnownSolutionParameter.Value = value; }
100    }
101    private BestTSPSolutionAnalyzer BestTSPSolutionAnalyzer {
102      get { return Operators.OfType<BestTSPSolutionAnalyzer>().FirstOrDefault(); }
103    }
104    private TSPAlleleFrequencyAnalyzer TSPAlleleFrequencyAnalyzer {
105      get { return Operators.OfType<TSPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
106    }
107    #endregion
108
109    [StorableConstructor]
110    private TravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
111    private TravelingSalesmanProblem(TravelingSalesmanProblem original, Cloner cloner)
112      : base(original, cloner) {
113      distanceFunctionParameter = cloner.Clone(original.distanceFunctionParameter);
114      coordinatesParameter = cloner.Clone(original.coordinatesParameter);
115      distanceMatrixParameter = cloner.Clone(original.distanceMatrixParameter);
116      useDistanceMatrixParameter = cloner.Clone(original.useDistanceMatrixParameter);
117      bestKnownSolutionParameter = cloner.Clone(original.bestKnownSolutionParameter);
118      RegisterEventHandlers();
119    }
120    public override IDeepCloneable Clone(Cloner cloner) {
121      return new TravelingSalesmanProblem(this, cloner);
122    }
123    public TravelingSalesmanProblem() : base() {
124      Encoding = new PermutationEncoding("TSPTour") { Length = 16 };
125      Encoding.PermutationTypeParameter.Value.Value = PermutationTypes.RelativeUndirected;
126
127      Parameters.Add(distanceFunctionParameter = new FixedValueParameter<EnumValue<TSPDistanceFunction>>("DistanceFunction", "The distance function that is used to calculate distance among the coordinates.", new EnumValue<TSPDistanceFunction>(TSPDistanceFunction.RoundedEuclidean)));
128      Parameters.Add(coordinatesParameter = new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
129      Parameters.Add(distanceMatrixParameter = new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
130      Parameters.Add(useDistanceMatrixParameter = 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)));
131      Parameters.Add(bestKnownSolutionParameter = new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
132     
133      useDistanceMatrixParameter.Hidden = true;
134      distanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
135
136      Coordinates = new DoubleMatrix(new double[,] {
137        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
138        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
139        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
140        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
141      });
142     
143      Evaluator.QualityParameter.ActualName = "TSPTourLength";
144
145      InitializeOperators();
146      RegisterEventHandlers();
147    }
148   
149    #region Helpers
150    [StorableHook(HookType.AfterDeserialization)]
151    private void AfterDeserialization() {
152      RegisterEventHandlers();
153    }
154
155    public override double Evaluate(Individual individual, IRandom random) {
156      var tour = individual.Permutation(Encoding.Name);
157      return Evaluate(tour);
158    }
159
160    public double Evaluate(Permutation tour) {
161      if (UseDistanceMatrix) return EvaluateWithDistanceMatrix(tour);
162
163      switch (DistanceFunction) {
164        case TSPDistanceFunction.DistanceMatrix:
165          return EvaluateWithDistanceMatrix(tour);
166        case TSPDistanceFunction.Euclidean:
167        case TSPDistanceFunction.RoundedEuclidean:
168        case TSPDistanceFunction.UpperEuclidean:
169        case TSPDistanceFunction.Geo:
170          return EvaluateWithDistanceCalculation(tour);
171        default: throw new InvalidOperationException(string.Format("Unknown distance function: {0}", DistanceFunction));
172      }
173    }
174
175    private double EvaluateWithDistanceMatrix(Permutation tour) {
176      var distances = DistanceMatrix;
177      double length = 0;
178      for (var i = 0; i < tour.Length - 1; i++)
179        length += distances[tour[i], tour[i + 1]];
180      length += distances[tour[tour.Length - 1], tour[0]];
181      return length;
182    }
183
184    private double EvaluateWithDistanceCalculation(Permutation tour) {
185      var coordinates = Coordinates;
186      var distanceFunction = DistanceFunction;
187      double length = 0;
188      for (var i = 0; i < tour.Length - 1; i++)
189        length += CalculateDistance(distanceFunction, coordinates[tour[i], 0], coordinates[tour[i], 1], coordinates[tour[i + 1], 0], coordinates[tour[i + 1], 1]);
190      length += CalculateDistance(distanceFunction, coordinates[tour[tour.Length - 1], 0], coordinates[tour[tour.Length - 1], 1], coordinates[tour[0], 0], coordinates[tour[0], 1]);
191      return length;
192    }
193
194    private void RegisterEventHandlers() {
195      coordinatesParameter.ValueChanged += coordinatesParameter_ValueChanged;
196      if (Coordinates != null) {
197        Coordinates.ItemChanged += Coordinates_ItemChanged;
198        Coordinates.Reset += Coordinates_Reset;
199      }
200      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
201    }
202
203    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
204      ParameterizeAnalyzers();
205      ParameterizeOperators();
206    }
207
208    private void Coordinates_Reset(object sender, EventArgs e) {
209      DistanceMatrix = null;
210    }
211
212    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
213      DistanceMatrix = null;
214    }
215
216    private void coordinatesParameter_ValueChanged(object sender, EventArgs e) {
217      if (Coordinates != null) {
218        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
219        Coordinates.Reset += new EventHandler(Coordinates_Reset);
220        DistanceMatrix = null;
221      }
222    }
223
224    private void InitializeOperators() {
225      Operators.Add(new TSPImprovementOperator());
226      Operators.Add(new TSPMultipleGuidesPathRelinker());
227      Operators.Add(new TSPPathRelinker());
228      Operators.Add(new TSPSimultaneousPathRelinker());
229      Operators.Add(new HammingSimilarityCalculator());
230      Operators.Add(new QualitySimilarityCalculator());
231
232      Operators.Add(new BestTSPSolutionAnalyzer());
233      Operators.Add(new TSPAlleleFrequencyAnalyzer());
234      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
235      Operators.AddRange(ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>());
236
237      ParameterizeAnalyzers();
238      ParameterizeOperators();
239      UpdateMoveEvaluators();
240    }
241    private void UpdateMoveEvaluators() {
242      ParameterizeOperators();
243      OnOperatorsChanged();
244    }
245    private void ParameterizeAnalyzers() {
246      if (BestTSPSolutionAnalyzer != null) {
247        BestTSPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
248        BestTSPSolutionAnalyzer.CoordinatesParameter.ActualName = coordinatesParameter.Name;
249        BestTSPSolutionAnalyzer.PermutationParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
250        BestTSPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
251        BestTSPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
252        BestTSPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = bestKnownSolutionParameter.Name;
253        BestTSPSolutionAnalyzer.MaximizationParameter.ActualName = ((ISingleObjectiveHeuristicOptimizationProblem)this).MaximizationParameter.Name;
254      }
255
256      if (TSPAlleleFrequencyAnalyzer != null) {
257        TSPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = ((ISingleObjectiveHeuristicOptimizationProblem)this).MaximizationParameter.Name;
258        TSPAlleleFrequencyAnalyzer.CoordinatesParameter.ActualName = coordinatesParameter.Name;
259        TSPAlleleFrequencyAnalyzer.DistanceMatrixParameter.ActualName = distanceMatrixParameter.Name;
260        TSPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
261        TSPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
262        TSPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = bestKnownSolutionParameter.Name;
263        TSPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
264      }
265    }
266    private void ParameterizeOperators() {
267      foreach (ITSPPathMoveEvaluator op in Operators.OfType<ITSPPathMoveEvaluator>()) {
268        op.DistanceFunctionParameter.ActualName = distanceFunctionParameter.Name;
269        op.DistanceFunctionParameter.Hidden = true;
270        op.CoordinatesParameter.ActualName = coordinatesParameter.Name;
271        op.CoordinatesParameter.Hidden = true;
272        op.DistanceMatrixParameter.ActualName = distanceMatrixParameter.Name;
273        op.DistanceMatrixParameter.Hidden = true;
274        op.UseDistanceMatrixParameter.ActualName = useDistanceMatrixParameter.Name;
275        op.UseDistanceMatrixParameter.Hidden = true;
276        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
277        op.QualityParameter.Hidden = true;
278        op.PermutationParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
279        op.PermutationParameter.Hidden = true;
280      }
281      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
282        op.SolutionParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
283        op.SolutionParameter.Hidden = true;
284      }
285      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
286        op.ParentsParameter.ActualName = Encoding.SolutionCreator.PermutationParameter.ActualName;
287        op.ParentsParameter.Hidden = true;
288      }
289      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
290        op.SolutionVariableName = Encoding.SolutionCreator.PermutationParameter.ActualName;
291        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
292      }
293    }
294
295    public void UpdateDistanceMatrix() {
296      var df = DistanceFunction;
297      var c = Coordinates;
298      if (c == null) throw new InvalidOperationException("No coordinates are given to calculate distance matrix.");
299      DistanceMatrix = CalculateDistanceMatrix(df, c);
300    }
301
302    public static DistanceMatrix CalculateDistanceMatrix(TSPDistanceFunction distance, DoubleMatrix coordinates) {
303      var dm = new double[coordinates.Rows, coordinates.Rows];
304      for (var i = 0; i < dm.GetLength(0); i++) {
305        for (var j = 0; j < dm.GetLength(1); j++)
306          dm[i, j] = CalculateDistance(distance, coordinates[i, 0], coordinates[i, 1], coordinates[j, 0], coordinates[j, 1]);
307      }
308      return new DistanceMatrix(dm, readOnly: true);
309    }
310    #endregion
311
312    public void Load(TSPData data) {
313      if (data.Coordinates == null && data.Distances == null)
314        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
315      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
316        || data.DistanceMeasure == DistanceMeasure.Manhattan
317        || data.DistanceMeasure == DistanceMeasure.Maximum))
318        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
319      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
320        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.");
321
322      Name = data.Name;
323      Description = data.Description;
324     
325      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
326        Coordinates = new DoubleMatrix(data.Coordinates);
327      else Coordinates = null;
328     
329      if (data.DistanceMeasure == DistanceMeasure.Att
330        || data.DistanceMeasure == DistanceMeasure.Manhattan
331        || data.DistanceMeasure == DistanceMeasure.Maximum) {
332        UseDistanceMatrix = true;
333        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
334        DistanceFunction = TSPDistanceFunction.DistanceMatrix;
335      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
336        UseDistanceMatrix = true;
337        DistanceMatrix = new DistanceMatrix(data.Distances);
338        DistanceFunction = TSPDistanceFunction.DistanceMatrix;
339      } else {
340        UseDistanceMatrix = data.Dimension <= DistanceMatrixSizeLimit;
341        switch (data.DistanceMeasure) {
342          case DistanceMeasure.Euclidean:
343            DistanceFunction = TSPDistanceFunction.Euclidean;
344            break;
345          case DistanceMeasure.RoundedEuclidean:
346            DistanceFunction = TSPDistanceFunction.RoundedEuclidean;
347            break;
348          case DistanceMeasure.UpperEuclidean:
349            DistanceFunction = TSPDistanceFunction.UpperEuclidean;
350            break;
351          case DistanceMeasure.Geo:
352            DistanceFunction = TSPDistanceFunction.Geo;
353            break;
354          default:
355            throw new InvalidDataException("An unknown distance measure is given in the instance!");
356        }
357        if (UseDistanceMatrix) UpdateDistanceMatrix();
358        else DistanceMatrix = null;
359      }
360      Evaluator.QualityParameter.ActualName = "TSPTourLength";
361     
362      BestKnownSolution = null;
363      BestKnownQualityParameter.Value = null;
364
365      if (data.BestKnownTour != null) {
366        try {
367          EvaluateAndLoadTour(data.BestKnownTour);
368        } catch (InvalidOperationException) {
369          if (data.BestKnownQuality.HasValue)
370            BestKnownQuality = data.BestKnownQuality.Value;
371        }
372      } else if (data.BestKnownQuality.HasValue) {
373        BestKnownQuality = data.BestKnownQuality.Value;
374      }
375      Encoding.Length = data.Dimension;
376
377      OnReset();
378    }
379
380    public void EvaluateAndLoadTour(int[] tour) {
381      var route = new Permutation(PermutationTypes.RelativeUndirected, tour);
382      BestKnownSolution = route;
383      BestKnownQuality = Evaluate(route);
384    }
385
386    public static double CalculateDistance(TSPDistanceFunction distanceFunction, double x1, double y1, double x2, double y2) {
387      switch (distanceFunction) {
388        case TSPDistanceFunction.Euclidean:
389          return CalculateEuclideanDistance(x1, y1, x2, y2);
390        case TSPDistanceFunction.RoundedEuclidean:
391          return CalculateRoundedEuclideanDistance(x1, y1, x2, y2);
392        case TSPDistanceFunction.UpperEuclidean:
393          return CalculateUpperEuclideanDistance(x1, y1, x2, y2);
394        case TSPDistanceFunction.Geo:
395          return CalculateGeoDistance(x1, y1, x2, y2);
396        default: throw new ArgumentException(string.Format("Distance calculation not available for {0}", distanceFunction));
397      }
398    }
399
400    public static double CalculateEuclideanDistance(double x1, double y1, double x2, double y2) {
401      return Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
402    }
403
404    public static double CalculateRoundedEuclideanDistance(double x1, double y1, double x2, double y2) {
405      return Math.Round(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
406    }
407
408    public static double CalculateUpperEuclideanDistance(double x1, double y1, double x2, double y2) {
409      return Math.Ceiling(Math.Sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
410    }
411
412    public static double CalculateGeoDistance(double x1, double y1, double x2, double y2) {
413      double latitude1, longitude1, latitude2, longitude2;
414      double q1, q2, q3;
415      double length;
416
417      latitude1 = ConvertToRadian(x1);
418      longitude1 = ConvertToRadian(y1);
419      latitude2 = ConvertToRadian(x2);
420      longitude2 = ConvertToRadian(y2);
421
422      q1 = Math.Cos(longitude1 - longitude2);
423      q2 = Math.Cos(latitude1 - latitude2);
424      q3 = Math.Cos(latitude1 + latitude2);
425
426      length = (int)(RADIUS * Math.Acos(0.5 * ((1.0 + q1) * q2 - (1.0 - q1) * q3)) + 1.0);
427      return (length);
428    }
429
430    private static double ConvertToRadian(double x) {
431      return PI * (Math.Truncate(x) + 5.0 * (x - Math.Truncate(x)) / 3.0) / 180.0;
432    }
433  }
434}
Note: See TracBrowser for help on using the repository browser.