Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 14312 was 14312, checked in by bburlacu, 8 years ago

#1772: Merge trunk changes. Delete unnecessary files (sliding window).

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