Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17248 was 17248, checked in by abeham, 4 years ago

#2521: working on TSP refactoring

File size: 10.7 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> {
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    public override bool Maximization => false;
47
48    [Storable] public IValueParameter<ITSPData> TSPDataParameter { get; private set; }
49    [Storable] public IValueParameter<ITSPSolution> BestKnownSolutionParameter { get; private set; }
50
51    public ITSPData TSPData {
52      get { return TSPDataParameter.Value; }
53      set { TSPDataParameter.Value = value; }
54    }
55    public ITSPSolution BestKnownSolution {
56      get { return BestKnownSolutionParameter.Value; }
57      set { BestKnownSolutionParameter.Value = value; }
58    }
59
60    [StorableConstructor]
61    protected TSP(StorableConstructorFlag _) : base(_) { }
62
63    protected TSP(TSP original, Cloner cloner)
64      : base(original, cloner) {
65      TSPDataParameter = cloner.Clone(original.TSPDataParameter);
66      BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
67    }
68
69    public TSP() : base(new PermutationEncoding("Tour", 16, PermutationTypes.RelativeUndirected)) {
70      Parameters.Add(TSPDataParameter = new ValueParameter<ITSPData>("TSPData", "The main parameters of the TSP."));
71      Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter<ITSPSolution>("BestKnownSolution", "The best known solution."));
72     
73      TSPData = new EuclideanTSPData() {
74        Coordinates = new DoubleMatrix(new double[,] {
75        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
76        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
77        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
78        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
79        }),
80        Rounding = EuclideanTSPData.RoundingMode.Midpoint
81      };
82
83      InitializeOperators();
84    }
85
86    public override IDeepCloneable Clone(Cloner cloner) {
87      return new TSP(this, cloner);
88    }
89
90    public override double Evaluate(Permutation tour, IRandom random) {
91      return Evaluate(tour);
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      var solution = TSPData.GetSolution(solutions[i], qualities[i]);
110
111      if (double.IsNaN(BestKnownQuality) ||
112          Maximization && qualities[i] > BestKnownQuality ||
113          !Maximization && qualities[i] < BestKnownQuality) {
114        BestKnownQualityParameter.Value = new DoubleValue(qualities[i]);
115        BestKnownSolutionParameter.Value = solution;
116      }
117      results.AddOrUpdateResult("Best TSP Solution", solution);
118    }
119
120    public override IEnumerable<Permutation> GetNeighbors(Permutation solution, IRandom random) {
121      foreach (var move in ExhaustiveInversionMoveGenerator.Generate(solution)) {
122        var clone = (Permutation)solution.Clone();
123        InversionManipulator.Apply(clone, move.Index1, move.Index2);
124        yield return clone;
125      }
126    }
127
128    public void Load(TSPData data) {
129      if (data.Coordinates == null && data.Distances == null)
130        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
131      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
132        || data.DistanceMeasure == DistanceMeasure.Manhattan
133        || data.DistanceMeasure == DistanceMeasure.Maximum))
134        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
135      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
136        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.");
137
138      Encoding.Length = data.Dimension;
139      Name = data.Name;
140      Description = data.Description;
141
142      if (data.DistanceMeasure == DistanceMeasure.Att
143        || data.DistanceMeasure == DistanceMeasure.Manhattan
144        || data.DistanceMeasure == DistanceMeasure.Maximum
145        || data.Dimension <= DistanceMatrixSizeLimit) {
146        TSPData = new MatrixTSPData(data.GetDistanceMatrix(), data.Coordinates);
147      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
148        TSPData = new MatrixTSPData(data.Distances, data.Coordinates);
149      } else {
150        switch (data.DistanceMeasure) {
151          case DistanceMeasure.Euclidean:
152            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.None };
153            break;
154          case DistanceMeasure.RoundedEuclidean:
155            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.Midpoint };
156            break;
157          case DistanceMeasure.UpperEuclidean:
158            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.Ceiling };
159            break;
160          case DistanceMeasure.Geo:
161            TSPData = new GeoTSPData(data.Coordinates);
162            break;
163          default:
164            throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
165        }
166      }
167      BestKnownSolution = null;
168      BestKnownQuality = double.NaN;
169
170      if (data.BestKnownTour != null) {
171        try {
172          var tour = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
173          var tourLength = Evaluate(tour);
174          BestKnownSolution = new TSPSolution(data.Coordinates != null ? new DoubleMatrix(data.Coordinates) : null, tour, new DoubleValue(tourLength));
175          BestKnownQuality = tourLength;
176        } catch (InvalidOperationException) {
177          if (data.BestKnownQuality.HasValue)
178            BestKnownQuality = data.BestKnownQuality.Value;
179        }
180      } else if (data.BestKnownQuality.HasValue) {
181        BestKnownQuality = data.BestKnownQuality.Value;
182      }
183      OnReset();
184    }
185
186    protected override void OnEncodingChanged() {
187      base.OnEncodingChanged();
188      ParameterizeOperators();
189    }
190
191    protected override void OnEvaluatorChanged() {
192      base.OnEvaluatorChanged();
193      ParameterizeOperators();
194    }
195
196    private void InitializeOperators() {
197      Operators.Add(new TSPImprovementOperator());
198      Operators.Add(new TSPMultipleGuidesPathRelinker());
199      Operators.Add(new TSPPathRelinker());
200      Operators.Add(new TSPSimultaneousPathRelinker());
201
202      Operators.Add(new TSPAlleleFrequencyAnalyzer());
203      foreach (var op in ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>()) {
204        Encoding.ConfigureOperator(op);
205        Operators.Add(op);
206      }
207      ParameterizeOperators();
208    }
209
210    private void ParameterizeOperators() {
211      foreach (var op in Operators.OfType<TSPAlleleFrequencyAnalyzer>()) {
212        op.MaximizationParameter.ActualName = MaximizationParameter.Name;
213        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
214        op.SolutionParameter.ActualName = Encoding.Name;
215        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
216        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
217        op.ResultsParameter.ActualName = "Results";
218      }
219      foreach (var op in Operators.OfType<ITSPMoveEvaluator>()) {
220        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
221        op.TSPDataParameter.Hidden = true;
222        op.TourLengthParameter.ActualName = Evaluator.QualityParameter.ActualName;
223        op.TourLengthParameter.Hidden = true;
224        op.TSPTourParameter.ActualName = Encoding.Name;
225        op.TSPTourParameter.Hidden = true;
226      }
227      foreach (var op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
228        op.SolutionParameter.ActualName = Encoding.Name;
229        op.SolutionParameter.Hidden = true;
230      }
231      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
232        op.ParentsParameter.ActualName = Encoding.Name;
233        op.ParentsParameter.Hidden = true;
234      }
235      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
236        op.SolutionVariableName = Encoding.Name;
237        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
238      }
239    }
240  }
241}
Note: See TracBrowser for help on using the repository browser.