Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs @ 10300

Last change on this file since 10300 was 10300, checked in by bburlacu, 11 years ago

#1772: Cleaned up the design of the generic genealogy analyzer and related classes, created generic genealogy graph view. Added instrumentation code to TravelingSalesmapProblem.cs allowing genealogy tracking. Merged trunk changes (instrumentation for multi operators).
File size: 24.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2013 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.IO;
25using System.Linq;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Problems.Instances;
36using HeuristicLab.Problems.TravelingSalesman.Analyzers;
37
38namespace HeuristicLab.Problems.TravelingSalesman {
39  [Item("Traveling Salesman Problem", "Represents a symmetric Traveling Salesman Problem.")]
40  [Creatable("Problems")]
41  [StorableClass]
42  public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent,
43    IProblemInstanceConsumer<TSPData> {
44    private static readonly int DistanceMatrixSizeLimit = 1000;
45    public string Filename { get; set; }
46
47    #region Parameter Properties
48    public OptionalValueParameter<DoubleMatrix> CoordinatesParameter {
49      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
50    }
51    public OptionalValueParameter<DistanceMatrix> DistanceMatrixParameter {
52      get { return (OptionalValueParameter<DistanceMatrix>)Parameters["DistanceMatrix"]; }
53    }
54    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
55      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
56    }
57    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
58      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
59    }
60    #endregion
61
62    #region Properties
63    public DoubleMatrix Coordinates {
64      get { return CoordinatesParameter.Value; }
65      set { CoordinatesParameter.Value = value; }
66    }
67    public DistanceMatrix DistanceMatrix {
68      get { return DistanceMatrixParameter.Value; }
69      set { DistanceMatrixParameter.Value = value; }
70    }
71    public BoolValue UseDistanceMatrix {
72      get { return UseDistanceMatrixParameter.Value; }
73      set { UseDistanceMatrixParameter.Value = value; }
74    }
75    public Permutation BestKnownSolution {
76      get { return BestKnownSolutionParameter.Value; }
77      set { BestKnownSolutionParameter.Value = value; }
78    }
79    private BestTSPSolutionAnalyzer BestTSPSolutionAnalyzer {
80      get { return Operators.OfType<BestTSPSolutionAnalyzer>().FirstOrDefault(); }
81    }
82    private TSPAlleleFrequencyAnalyzer TSPAlleleFrequencyAnalyzer {
83      get { return Operators.OfType<TSPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
84    }
85    private SingleObjectivePopulationDiversityAnalyzer SingleObjectivePopulationDiversityAnalyzer {
86      get { return Operators.OfType<SingleObjectivePopulationDiversityAnalyzer>().FirstOrDefault(); }
87    }
88
89    private TSPGenealogyAnalyzer TSPGenealogyAnalyzer {
90      get { return Operators.OfType<TSPGenealogyAnalyzer>().FirstOrDefault(); }
91    }
92    private IPermutationCrossover TSPCrossover {
93      get { return Operators.OfType<IPermutationCrossover>().FirstOrDefault(); }
94    }
95
96    private IPermutationManipulator TSPManipulator {
97      get { return Operators.OfType<IPermutationManipulator>().FirstOrDefault(); }
98    }
99    #endregion
100
101    // BackwardsCompatibility3.3
102    #region Backwards compatible code, remove with 3.4
103    [Obsolete]
104    [Storable(Name = "operators")]
105    private IEnumerable<IOperator> oldOperators {
106      get { return null; }
107      set {
108        if (value != null && value.Any())
109          Operators.AddRange(value);
110      }
111    }
112    #endregion
113
114    [StorableConstructor]
115    private TravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
116    private TravelingSalesmanProblem(TravelingSalesmanProblem original, Cloner cloner)
117      : base(original, cloner) {
118      RegisterEventHandlers();
119    }
120    public override IDeepCloneable Clone(Cloner cloner) {
121      return new TravelingSalesmanProblem(this, cloner);
122    }
123    public TravelingSalesmanProblem()
124      : base(new TSPRoundedEuclideanPathEvaluator(), new RandomPermutationCreator()) {
125      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
126      Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
127      Parameters.Add(new ValueParameter<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)));
128      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
129
130      Maximization.Value = false;
131      MaximizationParameter.Hidden = true;
132      UseDistanceMatrixParameter.Hidden = true;
133      DistanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
134
135      Coordinates = new DoubleMatrix(new double[,] {
136        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
137        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
138        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
139        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
140      });
141
142      SolutionCreator.PermutationParameter.ActualName = "TSPTour";
143      Evaluator.QualityParameter.ActualName = "TSPTourLength";
144      ParameterizeSolutionCreator();
145      ParameterizeEvaluator();
146
147      InitializeOperators();
148      RegisterEventHandlers();
149    }
150
151    #region Events
152    protected override void OnSolutionCreatorChanged() {
153      base.OnSolutionCreatorChanged();
154      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
155      ParameterizeSolutionCreator();
156      ParameterizeEvaluator();
157      ParameterizeAnalyzers();
158      ParameterizeOperators();
159    }
160    protected override void OnEvaluatorChanged() {
161      base.OnEvaluatorChanged();
162      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
163      ParameterizeEvaluator();
164      ParameterizeSolutionCreator();
165      UpdateMoveEvaluators();
166      ParameterizeAnalyzers();
167      if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
168        ClearDistanceMatrix();
169    }
170    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
171      if (Coordinates != null) {
172        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
173        Coordinates.Reset += new EventHandler(Coordinates_Reset);
174      }
175      if (Evaluator is ITSPCoordinatesPathEvaluator) {
176        ParameterizeSolutionCreator();
177        ClearDistanceMatrix();
178      }
179    }
180    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
181      if (Evaluator is ITSPCoordinatesPathEvaluator) {
182        ClearDistanceMatrix();
183      }
184    }
185    private void Coordinates_Reset(object sender, EventArgs e) {
186      if (Evaluator is ITSPCoordinatesPathEvaluator) {
187        ParameterizeSolutionCreator();
188        ClearDistanceMatrix();
189      }
190    }
191    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
192      ParameterizeEvaluator();
193      ParameterizeAnalyzers();
194      ParameterizeOperators();
195    }
196    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
197      ParameterizeAnalyzers();
198    }
199    #endregion
200
201    #region Helpers
202    [StorableHook(HookType.AfterDeserialization)]
203    private void AfterDeserialization() {
204      // BackwardsCompatibility3.3
205      #region Backwards compatible code (remove with 3.4)
206      OptionalValueParameter<DoubleMatrix> oldDistanceMatrixParameter = Parameters["DistanceMatrix"] as OptionalValueParameter<DoubleMatrix>;
207      if (oldDistanceMatrixParameter != null) {
208        Parameters.Remove(oldDistanceMatrixParameter);
209        Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
210        DistanceMatrixParameter.GetsCollected = oldDistanceMatrixParameter.GetsCollected;
211        DistanceMatrixParameter.ReactOnValueToStringChangedAndValueItemImageChanged = false;
212        if (oldDistanceMatrixParameter.Value != null) {
213          DoubleMatrix oldDM = oldDistanceMatrixParameter.Value;
214          DistanceMatrix newDM = new DistanceMatrix(oldDM.Rows, oldDM.Columns, oldDM.ColumnNames, oldDM.RowNames);
215          newDM.SortableView = oldDM.SortableView;
216          for (int i = 0; i < newDM.Rows; i++)
217            for (int j = 0; j < newDM.Columns; j++)
218              newDM[i, j] = oldDM[i, j];
219          DistanceMatrixParameter.Value = (DistanceMatrix)newDM.AsReadOnly();
220        }
221      }
222
223      ValueParameter<DoubleMatrix> oldCoordinates = (Parameters["Coordinates"] as ValueParameter<DoubleMatrix>);
224      if (oldCoordinates != null) {
225        Parameters.Remove(oldCoordinates);
226        Parameters.Add(new OptionalValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", oldCoordinates.Value, oldCoordinates.GetsCollected));
227      }
228
229      if (Operators.Count == 0) InitializeOperators();
230      #endregion
231      RegisterEventHandlers();
232    }
233
234    private void RegisterEventHandlers() {
235      CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
236      if (Coordinates != null) {
237        Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
238        Coordinates.Reset += new EventHandler(Coordinates_Reset);
239      }
240      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
241      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
242    }
243
244    private void InitializeOperators() {
245      Operators.Add(new TSPImprovementOperator());
246      Operators.Add(new TSPMultipleGuidesPathRelinker());
247      Operators.Add(new TSPPathRelinker());
248      Operators.Add(new TSPSimultaneousPathRelinker());
249      Operators.Add(new TSPSimilarityCalculator());
250
251      Operators.Add(new BestTSPSolutionAnalyzer());
252      Operators.Add(new TSPAlleleFrequencyAnalyzer());
253      Operators.Add(new SingleObjectivePopulationDiversityAnalyzer());
254      Operators.Add(new TSPGenealogyAnalyzer());
255      ParameterizeAnalyzers();
256      var operators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
257        new OrderCrossover2(),
258        new InversionManipulator(),
259        new StochasticInversionMultiMoveGenerator()
260      }, new TypeEqualityComparer<IPermutationOperator>());
261      foreach (var op in ApplicationManager.Manager.GetInstances<IPermutationOperator>())
262        operators.Add(op);
263      Operators.AddRange(operators);
264      ParameterizeOperators();
265      UpdateMoveEvaluators();
266    }
267    private void UpdateMoveEvaluators() {
268      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
269      foreach (ITSPPathMoveEvaluator op in ApplicationManager.Manager.GetInstances<ITSPPathMoveEvaluator>())
270        if (op.EvaluatorType == Evaluator.GetType()) {
271          Operators.Add(op);
272        }
273      ParameterizeOperators();
274      OnOperatorsChanged();
275    }
276    private void ParameterizeSolutionCreator() {
277      if (Evaluator is ITSPDistanceMatrixEvaluator && DistanceMatrix != null)
278        SolutionCreator.LengthParameter.Value = new IntValue(DistanceMatrix.Rows);
279      else if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
280        SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
281      else {
282        SolutionCreator.LengthParameter.Value = null;
283        string error = "The given problem does not support the selected evaluator.";
284        if (Evaluator is ITSPDistanceMatrixEvaluator)
285          error += Environment.NewLine + "Please review that the " + DistanceMatrixParameter.Name + " parameter is defined or choose another evaluator.";
286        else error += Environment.NewLine + "Please review that the " + CoordinatesParameter.Name + " parameter is defined or choose another evaluator.";
287        PluginInfrastructure.ErrorHandling.ShowErrorDialog(error, null);
288      }
289      SolutionCreator.LengthParameter.Hidden = SolutionCreator.LengthParameter.Value != null;
290      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.RelativeUndirected);
291      SolutionCreator.PermutationTypeParameter.Hidden = true;
292    }
293    private void ParameterizeEvaluator() {
294      if (Evaluator is ITSPPathEvaluator) {
295        ITSPPathEvaluator evaluator = (ITSPPathEvaluator)Evaluator;
296        evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
297        evaluator.PermutationParameter.Hidden = true;
298      }
299      if (Evaluator is ITSPCoordinatesPathEvaluator) {
300        ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
301        evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
302        evaluator.CoordinatesParameter.Hidden = true;
303        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
304        evaluator.DistanceMatrixParameter.Hidden = true;
305        evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
306        evaluator.UseDistanceMatrixParameter.Hidden = true;
307      }
308      if (Evaluator is ITSPDistanceMatrixEvaluator) {
309        var evaluator = (ITSPDistanceMatrixEvaluator)Evaluator;
310        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
311        evaluator.DistanceMatrixParameter.Hidden = true;
312      }
313    }
314    private void ParameterizeAnalyzers() {
315      if (BestTSPSolutionAnalyzer != null) {
316        BestTSPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
317        BestTSPSolutionAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
318        BestTSPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
319        BestTSPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
320        BestTSPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
321        BestTSPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
322        BestTSPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
323      }
324
325      if (TSPAlleleFrequencyAnalyzer != null) {
326        TSPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
327        TSPAlleleFrequencyAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
328        TSPAlleleFrequencyAnalyzer.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
329        TSPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
330        TSPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
331        TSPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
332        TSPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
333      }
334
335      if (SingleObjectivePopulationDiversityAnalyzer != null) {
336        SingleObjectivePopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
337        SingleObjectivePopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
338        SingleObjectivePopulationDiversityAnalyzer.ResultsParameter.ActualName = "Results";
339        SingleObjectivePopulationDiversityAnalyzer.SimilarityCalculator = Operators.OfType<TSPSimilarityCalculator>().SingleOrDefault();
340      }
341
342    }
343    private void ParameterizeOperators() {
344      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
345        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
346        op.ParentsParameter.Hidden = true;
347        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
348        op.ChildParameter.Hidden = true;
349      }
350      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
351        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
352        op.PermutationParameter.Hidden = true;
353      }
354      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
355        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
356        op.PermutationParameter.Hidden = true;
357      }
358      foreach (ITSPPathMoveEvaluator op in Operators.OfType<ITSPPathMoveEvaluator>()) {
359        op.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
360        op.CoordinatesParameter.Hidden = true;
361        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
362        op.DistanceMatrixParameter.Hidden = true;
363        op.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
364        op.UseDistanceMatrixParameter.Hidden = true;
365        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
366        op.QualityParameter.Hidden = true;
367        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
368        op.PermutationParameter.Hidden = true;
369      }
370      foreach (IPermutationMultiNeighborhoodShakingOperator op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>()) {
371        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
372        op.PermutationParameter.Hidden = true;
373      }
374      foreach (ISingleObjectiveImprovementOperator op in Operators.OfType<ISingleObjectiveImprovementOperator>()) {
375        op.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
376        op.SolutionParameter.Hidden = true;
377      }
378      foreach (ISingleObjectivePathRelinker op in Operators.OfType<ISingleObjectivePathRelinker>()) {
379        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
380        op.ParentsParameter.Hidden = true;
381      }
382      foreach (TSPSimilarityCalculator op in Operators.OfType<TSPSimilarityCalculator>()) {
383        op.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
384        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
385      }
386      if (TSPGenealogyAnalyzer != null) {
387        if (TSPCrossover != null) {
388          TSPGenealogyAnalyzer.CrossoverParentsParameterName = TSPCrossover.ParentsParameter.Name;
389          TSPGenealogyAnalyzer.CrossoverChildParameterName = TSPCrossover.ChildParameter.Name;
390        }
391        if (TSPManipulator != null) {
392          TSPGenealogyAnalyzer.ManipulatorChildParameterName = TSPManipulator.PermutationParameter.Name;
393        }
394        TSPGenealogyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
395        if (Evaluator is ITSPPathEvaluator) {
396          TSPGenealogyAnalyzer.PopulationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
397        } else {
398          throw new Exception("Unknown Evaluator. Could not parameterize genealogy analyzer.");
399        }
400      }
401    }
402
403    private void ClearDistanceMatrix() {
404      DistanceMatrixParameter.Value = null;
405    }
406    #endregion
407
408    public void Load(TSPData data) {
409      if (data.Coordinates == null && data.Distances == null)
410        throw new System.IO.InvalidDataException("The given instance specifies neither coordinates nor distances!");
411      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == DistanceMeasure.Att
412        || data.DistanceMeasure == DistanceMeasure.Manhattan
413        || data.DistanceMeasure == DistanceMeasure.Maximum))
414        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
415      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
416        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.");
417
418      Name = data.Name;
419      Description = data.Description;
420
421      bool clearCoordinates = false, clearDistanceMatrix = false;
422      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
423        Coordinates = new DoubleMatrix(data.Coordinates);
424      else clearCoordinates = true;
425
426      TSPEvaluator evaluator;
427      if (data.DistanceMeasure == DistanceMeasure.Att
428        || data.DistanceMeasure == DistanceMeasure.Manhattan
429        || data.DistanceMeasure == DistanceMeasure.Maximum) {
430        evaluator = new TSPDistanceMatrixEvaluator();
431        UseDistanceMatrix = new BoolValue(true);
432        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
433      } else if (data.DistanceMeasure == DistanceMeasure.Direct && data.Distances != null) {
434        evaluator = new TSPDistanceMatrixEvaluator();
435        UseDistanceMatrix = new BoolValue(true);
436        DistanceMatrix = new DistanceMatrix(data.Distances);
437      } else {
438        clearDistanceMatrix = true;
439        UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
440        switch (data.DistanceMeasure) {
441          case DistanceMeasure.Euclidean:
442            evaluator = new TSPEuclideanPathEvaluator();
443            break;
444          case DistanceMeasure.RoundedEuclidean:
445            evaluator = new TSPRoundedEuclideanPathEvaluator();
446            break;
447          case DistanceMeasure.UpperEuclidean:
448            evaluator = new TSPUpperEuclideanPathEvaluator();
449            break;
450          case DistanceMeasure.Geo:
451            evaluator = new TSPGeoPathEvaluator();
452            break;
453          default:
454            throw new InvalidDataException("An unknown distance measure is given in the instance!");
455        }
456      }
457      evaluator.QualityParameter.ActualName = "TSPTourLength";
458      Evaluator = evaluator;
459
460      // reset them after assigning the evaluator
461      if (clearCoordinates) Coordinates = null;
462      if (clearDistanceMatrix) DistanceMatrix = null;
463
464      BestKnownSolution = null;
465      BestKnownQuality = null;
466
467      if (data.BestKnownTour != null) {
468        try {
469          EvaluateAndLoadTour(data.BestKnownTour);
470        }
471        catch (InvalidOperationException) {
472          if (data.BestKnownQuality.HasValue)
473            BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
474        }
475      } else if (data.BestKnownQuality.HasValue) {
476        BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
477      }
478      OnReset();
479    }
480
481    public void EvaluateAndLoadTour(int[] tour) {
482      var route = new Permutation(PermutationTypes.RelativeUndirected, tour);
483      BestKnownSolution = route;
484
485      double quality;
486      if (Evaluator is ITSPDistanceMatrixEvaluator) {
487        quality = TSPDistanceMatrixEvaluator.Apply(DistanceMatrix, route);
488      } else if (Evaluator is ITSPCoordinatesPathEvaluator) {
489        quality = TSPCoordinatesPathEvaluator.Apply((TSPCoordinatesPathEvaluator)Evaluator, Coordinates, route);
490      } else {
491        throw new InvalidOperationException("Cannot calculate solution quality, evaluator type is unknown.");
492      }
493      BestKnownQuality = new DoubleValue(quality);
494    }
495  }
496}
Note: See TracBrowser for help on using the repository browser.