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

Last change on this file since 17241 was 17241, checked in by abeham, 11 months ago

#2521: worked on refactoring TSP

File size: 9.3 KB
Line 
1using System;
2using System.Linq;
3using HEAL.Attic;
4using HeuristicLab.Common;
5using HeuristicLab.Core;
6using HeuristicLab.Data;
7using HeuristicLab.Encodings.PermutationEncoding;
8using HeuristicLab.Optimization;
9using HeuristicLab.Parameters;
10using HeuristicLab.PluginInfrastructure;
11using HeuristicLab.Problems.Instances;
12
13namespace HeuristicLab.Problems.TravelingSalesman {
14  [Item("Traveling Salesman Problem (TSP)", "Represents a symmetric Traveling Salesman Problem.")]
15  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 100)]
16  [StorableType("8415476a-69de-45ad-95be-298ed7c97e84")]
17  public class TSP : PermutationProblem, IProblemInstanceConsumer<TSPData> {
18    /// <summary>
19    /// This limit governs when a distance matrix is used. For all problems smaller than that, the distance matrix is
20    /// computed. This greatly speeds up computation time.
21    /// </summary>
22    public static int DistanceMatrixSizeLimit { get; set; } = 1000;
23
24    public override bool Maximization => false;
25
26    [Storable] public IValueParameter<ITSPData> TSPDataParameter { get; private set; }
27    [Storable] public IValueParameter<Permutation> BestKnownSolutionParameter { get; private set; }
28
29    public ITSPData TSPData {
30      get { return TSPDataParameter.Value; }
31      set { TSPDataParameter.Value = value; }
32    }
33    public Permutation BestKnownSolution {
34      get { return BestKnownSolutionParameter.Value; }
35      set { BestKnownSolutionParameter.Value = value; }
36    }
37
38    [StorableConstructor]
39    protected TSP(StorableConstructorFlag _) : base(_) { }
40
41    protected TSP(TSP original, Cloner cloner)
42      : base(original, cloner) {
43      TSPDataParameter = cloner.Clone(original.TSPDataParameter);
44      BestKnownSolutionParameter = cloner.Clone(original.BestKnownSolutionParameter);
45    }
46
47    public TSP() : base(new PermutationEncoding("Tour", 16, PermutationTypes.RelativeUndirected)) {
48      Parameters.Add(TSPDataParameter = new ValueParameter<ITSPData>("TSPData", "The main parameters of the TSP."));
49      Parameters.Add(BestKnownSolutionParameter = new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution."));
50     
51      TSPData = new EuclideanTSPData() {
52        Coordinates = new DoubleMatrix(new double[,] {
53        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
54        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
55        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
56        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
57        }),
58        Rounding = EuclideanTSPData.RoundingMode.Midpoint
59      };
60
61      InitializeOperators();
62    }
63
64    public override IDeepCloneable Clone(Cloner cloner) {
65      return new TSP(this, cloner);
66    }
67
68    public override double Evaluate(Permutation tour, IRandom random) {
69      return Evaluate(tour);
70    }
71
72    public double Evaluate(Permutation tour) {
73      var tourLength = 0.0;
74      for (var i = 0; i < tour.Length - 1; i++) {
75        tourLength += TSPData.GetDistance(tour[i], tour[i + 1]);
76      }
77      tourLength += TSPData.GetDistance(tour[tour.Length - 1], tour[0]);
78      return tourLength;
79    }
80
81    public override void Analyze(Permutation[] solutions, double[] qualities, ResultCollection results, IRandom random) {
82      base.Analyze(solutions, qualities, results, random);
83      int i = -1;
84      if (!Maximization)
85        i = qualities.Select((x, index) => new { index, Fitness = x }).OrderBy(x => x.Fitness).First().index;
86      else i = qualities.Select((x, index) => new { index, Fitness = x }).OrderByDescending(x => x.Fitness).First().index;
87
88      if (double.IsNaN(BestKnownQuality) ||
89          Maximization && qualities[i] > BestKnownQuality ||
90          !Maximization && qualities[i] < BestKnownQuality) {
91        BestKnownQualityParameter.ActualValue = new DoubleValue(qualities[i]);
92        BestKnownSolutionParameter.ActualValue = (Permutation)solutions[i].Clone();
93      }
94
95      var solution = TSPData.GetSolution(solutions[i], qualities[i]);
96      results.AddOrUpdateResult("Best TSP Solution", solution);
97    }
98
99    public void Load(TSPData data) {
100      if (data.Coordinates == null && data.Distances == null)
101        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
102      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
103        || data.DistanceMeasure == DistanceMeasure.Manhattan
104        || data.DistanceMeasure == DistanceMeasure.Maximum))
105        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
106      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
107        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.");
108
109      Encoding.Length = data.Dimension;
110      Name = data.Name;
111      Description = data.Description;
112
113      if (data.DistanceMeasure == DistanceMeasure.Att
114        || data.DistanceMeasure == DistanceMeasure.Manhattan
115        || data.DistanceMeasure == DistanceMeasure.Maximum
116        || data.Dimension <= DistanceMatrixSizeLimit) {
117        TSPData = new MatrixTSPData(data.GetDistanceMatrix(), data.Coordinates);
118      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
119        TSPData = new MatrixTSPData(data.Distances, data.Coordinates);
120      } else {
121        switch (data.DistanceMeasure) {
122          case DistanceMeasure.Euclidean:
123            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.None };
124            break;
125          case DistanceMeasure.RoundedEuclidean:
126            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.Midpoint };
127            break;
128          case DistanceMeasure.UpperEuclidean:
129            TSPData = new EuclideanTSPData(data.Coordinates) { Rounding = EuclideanTSPData.RoundingMode.Ceiling };
130            break;
131          case DistanceMeasure.Geo:
132            TSPData = new GeoTSPData(data.Coordinates);
133            break;
134          default:
135            throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
136        }
137      }
138      BestKnownSolution = null;
139      BestKnownQuality = double.NaN;
140
141      if (data.BestKnownTour != null) {
142        try {
143          BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
144          BestKnownQuality = Evaluate(BestKnownSolution);
145        } catch (InvalidOperationException) {
146          if (data.BestKnownQuality.HasValue)
147            BestKnownQuality = data.BestKnownQuality.Value;
148        }
149      } else if (data.BestKnownQuality.HasValue) {
150        BestKnownQuality = data.BestKnownQuality.Value;
151      }
152      OnReset();
153    }
154
155    protected override void OnEncodingChanged() {
156      base.OnEncodingChanged();
157      ParameterizeOperators();
158    }
159
160    protected override void OnEvaluatorChanged() {
161      base.OnEvaluatorChanged();
162      ParameterizeOperators();
163    }
164
165    private void InitializeOperators() {
166      Operators.Add(new TSPImprovementOperator());
167      Operators.Add(new TSPMultipleGuidesPathRelinker());
168      Operators.Add(new TSPPathRelinker());
169      Operators.Add(new TSPSimultaneousPathRelinker());
170
171      Operators.Add(new TSPAlleleFrequencyAnalyzer());
172      foreach (var op in ApplicationManager.Manager.GetInstances<ITSPMoveEvaluator>())
173        Operators.Add(op);
174
175      ParameterizeOperators();
176    }
177
178    private void ParameterizeOperators() {
179      foreach (var op in Operators.OfType<TSPAlleleFrequencyAnalyzer>()) {
180        op.MaximizationParameter.ActualName = MaximizationParameter.Name;
181        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
182        op.SolutionParameter.ActualName = Encoding.Name;
183        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
184        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
185        op.ResultsParameter.ActualName = "Results";
186      }
187      foreach (var op in Operators.OfType<ITSPMoveEvaluator>()) {
188        op.TSPDataParameter.ActualName = TSPDataParameter.Name;
189        op.TSPDataParameter.Hidden = true;
190        op.TourLengthParameter.ActualName = Evaluator.QualityParameter.ActualName;
191        op.TourLengthParameter.Hidden = true;
192        op.TSPTourParameter.ActualName = Encoding.Name;
193        op.TSPTourParameter.Hidden = true;
194      }
195      foreach (var op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
196        op.SolutionParameter.ActualName = Encoding.Name;
197        op.SolutionParameter.Hidden = true;
198      }
199      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
200        op.ParentsParameter.ActualName = Encoding.Name;
201        op.ParentsParameter.Hidden = true;
202      }
203      foreach (ISolutionSimilarityCalculator op in Operators.OfType<ISolutionSimilarityCalculator>()) {
204        op.SolutionVariableName = Encoding.Name;
205        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
206      }
207    }
208  }
209}
Note: See TracBrowser for help on using the repository browser.