Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.PTSP/3.3/PTSP.cs @ 14041

Last change on this file since 14041 was 13470, checked in by abeham, 9 years ago

#2221:

  • implemented review comments
    • hid rng as private class, implemented djb2 hash function (hash function implementation may also change)
    • added missing probabilities
    • base class for instance providers
    • prebuild event events
    • build platforms
    • unit test will be removed on trunk integration
    • corrected assembly file version
    • distance calculator parameter was not hidden, can be changed by user, updates distance matrix
    • fixed performance problems (ouch!) also for estimated ptsp (inlined GetDistance method)
  • added moves (full evaluation) for analytical tsp
  • added local improvement operators for analytical ptsp
  • added recalculation of distance matrix when parameters change
  • still lots of other changes
File size: 11.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.PermutationEncoding;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.Instances;
32
33namespace HeuristicLab.Problems.PTSP {
34  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
35  [StorableClass]
36  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
37  IProblemInstanceConsumer<PTSPData> {
38    protected bool SuppressEvents { get; set; }
39
40    private static readonly int DistanceMatrixSizeLimit = 1000;
41
42    #region Parameter Properties
43    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
44      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
45    }
46    public OptionalValueParameter<DistanceCalculator> DistanceCalculatorParameter {
47      get { return (OptionalValueParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
48    }
49    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
50      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
51    }
52    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
53      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
54    }
55    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
56      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
57    }
58    public IValueParameter<DoubleArray> ProbabilitiesParameter {
59      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
60    }
61    #endregion
62
63    #region Properties
64    public DoubleMatrix Coordinates {
65      get { return CoordinatesParameter.Value; }
66      set { CoordinatesParameter.Value = value; }
67    }
68    public DistanceCalculator DistanceCalculator {
69      get { return DistanceCalculatorParameter.Value; }
70      set { DistanceCalculatorParameter.Value = value; }
71    }
72    public DistanceMatrix DistanceMatrix {
73      get { return DistanceMatrixParameter.Value; }
74      set { DistanceMatrixParameter.Value = value; }
75    }
76    public bool UseDistanceMatrix {
77      get { return UseDistanceMatrixParameter.Value.Value; }
78      set { UseDistanceMatrixParameter.Value.Value = value; }
79    }
80    public Permutation BestKnownSolution {
81      get { return BestKnownSolutionParameter.Value; }
82      set { BestKnownSolutionParameter.Value = value; }
83    }
84    public DoubleArray Probabilities {
85      get { return ProbabilitiesParameter.Value; }
86      set { ProbabilitiesParameter.Value = value; }
87    }
88
89    #endregion
90
91    public override bool Maximization {
92      get { return false; }
93    }
94
95    [StorableConstructor]
96    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
97    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner)
98      : base(original, cloner) {
99      RegisterEventHandlers();
100    }
101    protected ProbabilisticTravelingSalesmanProblem() {
102      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
103      Parameters.Add(new OptionalValueParameter<DistanceCalculator>("DistanceCalculator", "Calculates the distance between two rows in the coordinates matrix."));
104      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
105      Parameters.Add(new FixedValueParameter<BoolValue>("UseDistanceMatrix", "True if the coordinates based evaluators should calculate the distance matrix from the coordinates and use it for evaluation similar to the distance matrix evaluator, otherwise false.", new BoolValue(true)));
106      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
107      Parameters.Add(new ValueParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
108
109      var coordinates = new DoubleMatrix(new double[,] {
110        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
111        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
112        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
113        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
114      });
115      Coordinates = coordinates;
116      Encoding.Length = coordinates.Rows;
117      DistanceCalculator = new EuclideanDistance();
118      DistanceMatrix = new DistanceMatrix(CalculateDistances());
119      Probabilities = new DoubleArray(Enumerable.Range(0, coordinates.Rows).Select(x => 0.5).ToArray());
120
121      RegisterEventHandlers();
122    }
123
124    [StorableHook(HookType.AfterDeserialization)]
125    private void AfterDeserialization() {
126      RegisterEventHandlers();
127    }
128
129    private void RegisterEventHandlers() {
130      CoordinatesParameter.ValueChanged += CoordinatesParameterOnValueChanged;
131      if (Coordinates != null) {
132        Coordinates.RowsChanged += CoordinatesOnChanged;
133        Coordinates.ItemChanged += CoordinatesOnChanged;
134      }
135      UseDistanceMatrixParameter.Value.ValueChanged += UseDistanceMatrixValueChanged;
136      DistanceCalculatorParameter.ValueChanged += DistanceCalculatorParameterOnValueChanged;
137    }
138
139    private void CoordinatesParameterOnValueChanged(object sender, EventArgs eventArgs) {
140      if (Coordinates != null) {
141        Coordinates.RowsChanged += CoordinatesOnChanged;
142        Coordinates.ItemChanged += CoordinatesOnChanged;
143      }
144      if (SuppressEvents) return;
145      UpdateInstance();
146    }
147
148    private void CoordinatesOnChanged(object sender, EventArgs eventArgs) {
149      if (SuppressEvents) return;
150      UpdateInstance();
151    }
152
153    private void UseDistanceMatrixValueChanged(object sender, EventArgs eventArgs) {
154      if (SuppressEvents) return;
155      UpdateInstance();
156    }
157
158    private void DistanceCalculatorParameterOnValueChanged(object sender, EventArgs eventArgs) {
159      if (SuppressEvents) return;
160      UpdateInstance();
161    }
162
163    public override double Evaluate(Individual individual, IRandom random) {
164      return Evaluate(individual.Permutation(), random);
165    }
166
167    public abstract double Evaluate(Permutation tour, IRandom random);
168
169    public double[,] CalculateDistances() {
170      var coords = Coordinates;
171      var len = coords.Rows;
172      var dist = DistanceCalculator;
173
174      var matrix = new double[len, len];
175      for (var i = 0; i < len - 1; i++)
176        for (var j = i + 1; j < len; j++)
177          matrix[i, j] = matrix[j, i] = dist.Calculate(i, j, coords);
178
179      return matrix;
180    }
181
182    public virtual void Load(PTSPData data) {
183      try {
184        SuppressEvents = true;
185        if (data.Coordinates == null && data.Distances == null)
186          throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
187        if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
188          throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
189        if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
190          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 respectively.");
191
192        switch (data.DistanceMeasure) {
193          case DistanceMeasure.Direct:
194            DistanceCalculator = null;
195            if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
196              DistanceCalculator = new EuclideanDistance();
197              UseDistanceMatrix = false;
198            } else UseDistanceMatrix = true;
199            break;
200          case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
201          case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
202          case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
203          case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
204          case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
205          case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
206          case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
207          default: throw new ArgumentException("Distance measure is unknown");
208        }
209
210        Name = data.Name;
211        Description = data.Description;
212
213        Probabilities = new DoubleArray(data.Probabilities);
214        BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
215        Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
216        DistanceMatrix = data.Dimension <= DistanceMatrixSizeLimit && UseDistanceMatrix ? new DistanceMatrix(data.GetDistanceMatrix()) : null;
217
218        Encoding.Length = data.Dimension;
219      } finally { SuppressEvents = false; }
220      OnReset();
221    }
222
223    private void UpdateInstance() {
224      var len = GetProblemDimension();
225      if (Coordinates != null && Coordinates.Rows <= DistanceMatrixSizeLimit
226        && DistanceCalculator != null && UseDistanceMatrix)
227        DistanceMatrix = new DistanceMatrix(CalculateDistances());
228      if (!UseDistanceMatrix) DistanceMatrix = null;
229      Encoding.Length = len;
230
231      OnReset();
232    }
233
234    private int GetProblemDimension() {
235      if (Coordinates == null && DistanceMatrix == null) throw new InvalidOperationException("Both coordinates and distance matrix are null, please specify at least one of them.");
236      return Coordinates != null ? Coordinates.Rows : DistanceMatrix.Rows;
237    }
238  }
239}
Note: See TracBrowser for help on using the repository browser.