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

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

#2521: working on refactoring TSP

File size: 5.4 KB
Line 
1using System;
2using HEAL.Attic;
3using HeuristicLab.Common;
4using HeuristicLab.Core;
5using HeuristicLab.Data;
6using HeuristicLab.Encodings.PermutationEncoding;
7using HeuristicLab.Optimization;
8using HeuristicLab.Problems.Instances;
9
10namespace HeuristicLab.Problems.TravelingSalesman {
11  [Item("Traveling Salesman Problem (TSP)", "Represents a symmetric Traveling Salesman Problem.")]
12  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 100)]
13  [StorableType("60511a03-b8b4-47cd-a119-78f97358a6b0")]
14  public class TSP : SingleObjectiveProblem<PermutationEncoding, Permutation>, IProblemInstanceConsumer<TSPData> {
15    public static int DistanceMatrixSizeLimit { get; set; } = 1000;
16
17    public override bool Maximization => false;
18
19    [Storable]
20    private IValueParameter<ITSPData> tspDataParameter;
21    public IValueParameter<ITSPData> TSPDataParameter {
22      get { return tspDataParameter; }
23    }
24    [Storable]
25    private IValueParameter<Permutation> bestKnownSolutionParameter;
26    public IValueParameter<Permutation> BestKnownSolutionParameter {
27      get { return bestKnownSolutionParameter; }
28    }
29
30    public ITSPData TSPData {
31      get { return tspDataParameter.Value; }
32      set { tspDataParameter.Value = value; }
33    }
34    public Permutation BestKnownSolution {
35      get { return bestKnownSolutionParameter.Value; }
36      set { bestKnownSolutionParameter.Value = value; }
37    }
38
39    [StorableConstructor]
40    protected TSP(StorableConstructorFlag _) : base(_) { }
41
42    protected TSP(TSP original, Cloner cloner)
43      : base(original, cloner) {
44      tspDataParameter = cloner.Clone(original.tspDataParameter);
45      bestKnownSolutionParameter = cloner.Clone(original.bestKnownSolutionParameter);
46    }
47
48    public TSP() : base(new PermutationEncoding("Tour", 16, PermutationTypes.RelativeUndirected)) {
49      TSPData = new RoundedEuclideanCoordinatesTSPData() {
50        Coordinates = new DoubleMatrix(new double[,] {
51        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
52        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
53        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
54        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
55        })
56      };
57    }
58
59    public override IDeepCloneable Clone(Cloner cloner) {
60      return new TSP(this, cloner);
61    }
62
63    public override double Evaluate(Permutation tour, IRandom random) {
64      return Evaluate(tour);
65    }
66
67    public double Evaluate(Permutation tour) {
68      var tourLength = 0.0;
69      for (var i = 0; i < tour.Length - 1; i++) {
70        tourLength += TSPData.GetDistance(tour[i], tour[i + 1]);
71      }
72      tourLength += TSPData.GetDistance(tour[tour.Length - 1], tour[0]);
73      return tourLength;
74    }
75
76    public void Load(TSPData data) {
77      if (data.Coordinates == null && data.Distances == null)
78        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
79      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
80        || data.DistanceMeasure == DistanceMeasure.Manhattan
81        || data.DistanceMeasure == DistanceMeasure.Maximum))
82        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
83      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
84        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.");
85
86      Name = data.Name;
87      Description = data.Description;
88
89      if (data.DistanceMeasure == DistanceMeasure.Att
90        || data.DistanceMeasure == DistanceMeasure.Manhattan
91        || data.DistanceMeasure == DistanceMeasure.Maximum
92        || data.Dimension <= DistanceMatrixSizeLimit) {
93        TSPData = new MatrixTSPData(data.GetDistanceMatrix(), data.Coordinates);
94      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
95        TSPData = new MatrixTSPData(data.Distances, data.Coordinates);
96      } else {
97        switch (data.DistanceMeasure) {
98          case DistanceMeasure.Euclidean:
99            throw new NotImplementedException();
100            break;
101          case DistanceMeasure.RoundedEuclidean:
102            TSPData = new RoundedEuclideanCoordinatesTSPData(data.Coordinates);
103            break;
104          case DistanceMeasure.UpperEuclidean:
105            throw new NotImplementedException();
106            break;
107          case DistanceMeasure.Geo:
108            throw new NotImplementedException();
109            break;
110          default:
111            throw new System.IO.InvalidDataException("An unknown distance measure is given in the instance!");
112        }
113      }
114      BestKnownSolution = null;
115      BestKnownQuality = double.NaN;
116
117      if (data.BestKnownTour != null) {
118        try {
119          BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour);
120          BestKnownQuality = Evaluate(BestKnownSolution);
121        } catch (InvalidOperationException) {
122          if (data.BestKnownQuality.HasValue)
123            BestKnownQuality = data.BestKnownQuality.Value;
124        }
125      } else if (data.BestKnownQuality.HasValue) {
126        BestKnownQuality = data.BestKnownQuality.Value;
127      }
128      OnReset();
129    }
130  }
131}
Note: See TracBrowser for help on using the repository browser.