Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17594 was 17594, checked in by mkommend, 4 years ago

#2521: Added first version of new results. The first algorithm that has been adapted for testing purposes is the hill climber.

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