Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PTSP/HeuristicLab.Problems.PTSP/3.3/PTSP.cs @ 13412

Last change on this file since 13412 was 13412, checked in by abeham, 8 years ago

#2221:

  • Completely refactored PTSP branch
    • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
    • Implemented missing EvaluateByCoordinates for 1-shift moves
    • Made it clear that move evaluators are for estimated PTSP only
    • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
    • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
    • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
    • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types
File size: 8.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 HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Optimization;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.Instances;
31
32namespace HeuristicLab.Problems.PTSP {
33  [Item("Probabilistic Traveling Salesman Problem (PTSP)", "Represents a Probabilistic Traveling Salesman Problem.")]
34  [StorableClass]
35  public abstract class ProbabilisticTravelingSalesmanProblem : SingleObjectiveBasicProblem<PermutationEncoding>,
36  IProblemInstanceConsumer<PTSPData> {
37    private static readonly int DistanceMatrixSizeLimit = 1000;
38
39    #region Parameter Properties
40    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
41      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
42    }
43    public OptionalValueParameter<DistanceCalculator> DistanceCalculatorParameter {
44      get { return (OptionalValueParameter<DistanceCalculator>)Parameters["DistanceCalculator"]; }
45    }
46    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
47      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
48    }
49    public IFixedValueParameter<BoolValue> UseDistanceMatrixParameter {
50      get { return (IFixedValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
51    }
52    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
53      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
54    }
55    public IValueParameter<DoubleArray> ProbabilitiesParameter {
56      get { return (IValueParameter<DoubleArray>)Parameters["Probabilities"]; }
57    }
58    #endregion
59
60    #region Properties
61    public DoubleMatrix Coordinates {
62      get { return CoordinatesParameter.Value; }
63      set { CoordinatesParameter.Value = value; }
64    }
65    public DistanceCalculator DistanceCalculator {
66      get { return DistanceCalculatorParameter.Value; }
67      set { DistanceCalculatorParameter.Value = value; }
68    }
69    public DistanceMatrix DistanceMatrix {
70      get { return DistanceMatrixParameter.Value; }
71      set { DistanceMatrixParameter.Value = value; }
72    }
73    public bool UseDistanceMatrix {
74      get { return UseDistanceMatrixParameter.Value.Value; }
75      set { UseDistanceMatrixParameter.Value.Value = value; }
76    }
77    public Permutation BestKnownSolution {
78      get { return BestKnownSolutionParameter.Value; }
79      set { BestKnownSolutionParameter.Value = value; }
80    }
81    public DoubleArray Probabilities {
82      get { return ProbabilitiesParameter.Value; }
83      set { ProbabilitiesParameter.Value = value; }
84    }
85
86    #endregion
87
88    public override bool Maximization {
89      get { return false; }
90    }
91
92    [StorableConstructor]
93    protected ProbabilisticTravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
94    protected ProbabilisticTravelingSalesmanProblem(ProbabilisticTravelingSalesmanProblem original, Cloner cloner) : base(original, cloner) { }
95    protected ProbabilisticTravelingSalesmanProblem() {
96      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
97      Parameters.Add(new OptionalValueParameter<DistanceCalculator>("DistanceCalculator", "Calculates the distance between two rows in the coordinates matrix."));
98      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
99      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)));
100      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
101      Parameters.Add(new ValueParameter<DoubleArray>("Probabilities", "This list describes for each city the probability of appearing in a realized instance."));
102
103      Coordinates = new DoubleMatrix(new double[,] {
104        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
105        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
106        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
107        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
108      });
109
110      Probabilities = new DoubleArray(new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 });
111    }
112
113    public override double Evaluate(Individual individual, IRandom random) {
114      return Evaluate(individual.Permutation(), random);
115    }
116
117    public abstract double Evaluate(Permutation tour, IRandom random);
118
119    public virtual void Load(PTSPData data) {
120      if (data.Coordinates == null && data.Distances == null)
121        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
122      if (data.Dimension > DistanceMatrixSizeLimit && (data.Coordinates == null || data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
123        throw new System.IO.InvalidDataException("The given instance is too large for using a distance matrix and there is a problem with the coordinates.");
124      if (data.Coordinates != null && (data.Coordinates.GetLength(0) != data.Dimension || data.Coordinates.GetLength(1) != 2))
125        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.");
126
127      switch (data.DistanceMeasure) {
128        case DistanceMeasure.Direct:
129          DistanceCalculator = null;
130          if (data.Dimension > DistanceMatrixSizeLimit && Coordinates != null) {
131            DistanceCalculator = new EuclideanDistance();
132            UseDistanceMatrix = false;
133          } else UseDistanceMatrix = true;
134          break;
135        case DistanceMeasure.Att: DistanceCalculator = new AttDistance(); break;
136        case DistanceMeasure.Euclidean: DistanceCalculator = new EuclideanDistance(); break;
137        case DistanceMeasure.Geo: DistanceCalculator = new GeoDistance(); break;
138        case DistanceMeasure.Manhattan: DistanceCalculator = new ManhattanDistance(); break;
139        case DistanceMeasure.Maximum: DistanceCalculator = new MaximumDistance(); break;
140        case DistanceMeasure.RoundedEuclidean: DistanceCalculator = new RoundedEuclideanDistance(); break;
141        case DistanceMeasure.UpperEuclidean: DistanceCalculator = new UpperEuclideanDistance(); break;
142        default: throw new ArgumentException("Distance measure is unknown");
143      }
144
145      Name = data.Name;
146      Description = data.Description;
147
148      Probabilities = new DoubleArray(data.Probabilities);
149      BestKnownSolution = data.BestKnownTour != null ? new Permutation(PermutationTypes.RelativeUndirected, data.BestKnownTour) : null;
150      Coordinates = data.Coordinates != null && data.Coordinates.GetLength(0) > 0 ? new DoubleMatrix(data.Coordinates) : null;
151      DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
152
153      Encoding.Length = data.Dimension;
154
155      OnReset();
156    }
157  }
158}
Note: See TracBrowser for help on using the repository browser.