source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.TravelingSalesman/3.3/TSP.cs @ 17270

Last change on this file since 17270 was 17270, checked in by abeham, 3 years ago

#2521: worked on removing virtual from Maximization for single-objective problems

File size: 11.8 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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.Collections.Generic;
24using System.Linq;
25using HEAL.Attic;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Problems.Instances;
34
35namespace HeuristicLab.Problems.TravelingSalesman {
36  [Item("Traveling Salesman Problem (TSP)", "Represents a symmetric Traveling Salesman Problem.")]
37  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 100)]
38  [StorableType("8415476a-69de-45ad-95be-298ed7c97e84")]
39  public class TSP : PermutationProblem, IProblemInstanceConsumer<TSPData>, IProblemInstanceExporter<TSPData> {
40    /// <summary>
41    /// This limit governs when a distance matrix is used. For all problems smaller than that, the distance matrix is
42    /// computed. This greatly speeds up computation time.
43    /// </summary>
44    public static int DistanceMatrixSizeLimit { get; set; } = 1000;
45
46    [Storable] public IValueParameter<ITSPData> TSPDataParameter { get; private set; }
47    [Storable] public IValueParameter<ITSPSolution> BestKnownSolutionParameter { get; private set; }
48
49    public ITSPData TSPData {
50      get { return TSPDataParameter.Value; }
51      set { TSPDataParameter.Value = value; }
52    }
53    public ITSPSolution BestKnownSolution {
54      get { return BestKnownSolutionParameter.Value; }
55      set { BestKnownSolutionParameter.Value = value; }
56    }
57
58    [StorableConstructor]
59    protected TSP(StorableConstructorFlag _) : base(_) { }
60
61    protected TSP(TSP original, Cloner cloner)
62      : base(original, cloner) {
63      TSPDataParameter = cloner.Clone(original.TSPDataParameter);
64      BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
65    }
66
67    public TSP() : base(new PermutationEncoding("Tour", 16, PermutationTypes.RelativeUndirected)) {
68      Maximization = false;
69      Parameters.Add(TSPDataParameter = new ValueParameter<ITSPData>("TSPData", "The main parameters of the TSP."));
70      Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter<ITSPSolution>("BestKnownSolution", "The best known solution."));
71
72      TSPData = new EuclideanTSPData();
73      Encoding.Length = TSPData.Cities;
74
75      InitializeOperators();
76    }
77
78    // TODO: encoding length should not be changeable
79
80    public override IDeepCloneable Clone(Cloner cloner) {
81      return new TSP(this, cloner);
82    }
83
84    public override double Evaluate(Permutation tour, IRandom random) {
85      return Evaluate(tour);
86    }
87
88    public double Evaluate(Permutation tour) {
89      var tourLength = 0.0;
90      for (var i = 0; i < tour.Length - 1; i++) {
91        tourLength += TSPData.GetDistance(tour[i], tour[i + 1]);
92      }
93      tourLength += TSPData.GetDistance(tour[tour.Length - 1], tour[0]);
94      return tourLength;
95    }
96
97    public override void Analyze(Permutation[] solutions, double[] qualities, ResultCollection results, IRandom random) {
98      base.Analyze(solutions, qualities, results, random);
99      int i = -1;
100      if (!Maximization)
101        i = qualities.Select((x, index) => new { index, Fitness = x }).OrderBy(x => x.Fitness).First().index;
102      else i = qualities.Select((x, index) => new { index, Fitness = x }).OrderByDescending(x => x.Fitness).First().index;
103
104      if (double.IsNaN(BestKnownQuality) ||
105          Maximization && qualities[i] > BestKnownQuality ||
106          !Maximization && qualities[i] < BestKnownQuality) {
107        var bestKnown = TSPData.GetSolution(solutions[i], qualities[i]);
108        BestKnownQualityParameter.Value = new DoubleValue(qualities[i]);
109        BestKnownSolutionParameter.Value = bestKnown;
110      }
111
112      IResult bestSolutionResult;
113      if (results.TryGetValue("Best TSP Solution", out bestSolutionResult)) {
114        var bestSolution = bestSolutionResult.Value as ITSPSolution;
115        if (bestSolution == null || Maximization && bestSolution.TourLength.Value < qualities[i]
116          || !Maximization && bestSolution.TourLength.Value > qualities[i]) {
117          bestSolutionResult.Value = TSPData.GetSolution(solutions[i], qualities[i]);
118        }
119      } else results.Add(new Result("Best TSP Solution", TSPData.GetSolution(solutions[i], qualities[i])));
120    }
121
122    public override IEnumerable<Permutation> GetNeighbors(Permutation solution, IRandom random) {
123      foreach (var move in ExhaustiveInversionMoveGenerator.Generate(solution)) {
124        var clone = (Permutation)solution.Clone();
125        InversionManipulator.Apply(clone, move.Index1, move.Index2);
126        yield return clone;
127      }
128    }
129
130    public void Load(TSPData data) {
131      if (data.Coordinates == null && data.Distances == null)
132        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
133      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
134        || data.DistanceMeasure == DistanceMeasure.Manhattan
135        || data.DistanceMeasure == DistanceMeasure.Maximum))
136        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
137      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
138        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.");
139
140      Encoding.Length = data.Dimension;
141      Name = data.Name;
142      Description = data.Description;
143
144      if (data.Dimension <= DistanceMatrixSizeLimit) {
145        TSPData = new MatrixTSPData(data.Name, data.GetDistanceMatrix(), data.Coordinates) { Description = data.Description };
146      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
147        TSPData = new MatrixTSPData(data.Name, data.Distances, data.Coordinates) { Description = data.Description };
148      } else {
149        switch (data.DistanceMeasure) {
150          case DistanceMeasure.Att:
151            TSPData = new AttTSPData(data.Name, data.Coordinates) { Description = data.Description };
152            break;
153          case DistanceMeasure.Euclidean:
154            TSPData = new EuclideanTSPData(data.Name, data.Coordinates, EuclideanTSPData.DistanceRounding.None) { Description = data.Description };
155            break;
156          case DistanceMeasure.RoundedEuclidean:
157            TSPData = new EuclideanTSPData(data.Name, data.Coordinates, EuclideanTSPData.DistanceRounding.Midpoint) { Description = data.Description };
158            break;
159          case DistanceMeasure.UpperEuclidean:
160            TSPData = new EuclideanTSPData(data.Name, data.Coordinates, EuclideanTSPData.DistanceRounding.Ceiling) { Description = data.Description };
161            break;
162          case DistanceMeasure.Geo:
163            TSPData = new GeoTSPData(data.Name, data.Coordinates) { Description = data.Description };
164            break;
165          case DistanceMeasure.Manhattan:
166            TSPData = new ManhattanTSPData(data.Name, data.Coordinates) { Description = data.Description };
167            break;
168          case DistanceMeasure.Maximum:
169            TSPData = new MaximumTSPData(data.Name, data.Coordinates) { Description = data.Description };
170            break;
171          default:
172            throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
173        }
174      }
175      BestKnownSolution = null;
176      BestKnownQuality = double.NaN;
177
178      if (data.BestKnownTour != null) {
179        try {
180          var tour = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
181          var tourLength = Evaluate(tour);
182          BestKnownSolution = new TSPSolution(data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null, tour, new DoubleValue(tourLength));
183          BestKnownQuality = tourLength;
184        } catch (InvalidOperationException) {
185          if (data.BestKnownQuality.HasValue)
186            BestKnownQuality = data.BestKnownQuality.Value;
187        }
188      } else if (data.BestKnownQuality.HasValue) {
189        BestKnownQuality = data.BestKnownQuality.Value;
190      }
191      OnReset();
192    }
193
194    public TSPData Export() {
195      var instance = TSPData.Export();
196      if (!double.IsNaN(BestKnownQuality))
197        instance.BestKnownQuality = BestKnownQuality;
198      if (BestKnownSolution?.Tour != null)
199        instance.BestKnownTour = BestKnownSolution.Tour.ToArray();
200      return instance;
201    }
202
203
204    protected override void OnEncodingChanged() {
205      base.OnEncodingChanged();
206      Encoding.Length = TSPData.Cities;
207      ParameterizeOperators();
208    }
209
210    protected override void OnEvaluatorChanged() {
211      base.OnEvaluatorChanged();
212      ParameterizeOperators();
213    }
214
215    private void InitializeOperators() {
216      Operators.Add(new TSPImprovementOperator());
217      Operators.Add(new TSPMultipleGuidesPathRelinker());
218      Operators.Add(new TSPPathRelinker());
219      Operators.Add(new TSPSimultaneousPathRelinker());
220
221      Operators.Add(new TSPAlleleFrequencyAnalyzer());
222      foreach (var op in ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>()) {
223        Encoding.ConfigureOperator(op);
224        Operators.Add(op);
225      }
226      ParameterizeOperators();
227    }
228
229    private void ParameterizeOperators() {
230      foreach (var op in Operators.OfType<TSPAlleleFrequencyAnalyzer>()) {
231        op.MaximizationParameter.ActualName = MaximizationParameter.Name;
232        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
233        op.SolutionParameter.ActualName = Encoding.Name;
234        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
235        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
236        op.ResultsParameter.ActualName = "Results";
237      }
238      foreach (var op in Operators.OfType<ITSPMoveEvaluator>()) {
239        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
240        op.TSPDataParameter.Hidden = true;
241        op.TourLengthParameter.ActualName = Evaluator.QualityParameter.ActualName;
242        op.TourLengthParameter.Hidden = true;
243        op.TSPTourParameter.ActualName = Encoding.Name;
244        op.TSPTourParameter.Hidden = true;
245      }
246      foreach (var op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
247        op.SolutionParameter.ActualName = Encoding.Name;
248        op.SolutionParameter.Hidden = true;
249      }
250      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
251        op.ParentsParameter.ActualName = Encoding.Name;
252        op.ParentsParameter.Hidden = true;
253      }
254      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
255        op.SolutionVariableName = Encoding.Name;
256        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
257      }
258    }
259  }
260}
Note: See TracBrowser for help on using the repository browser.