Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.DiversityAnalysis/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs @ 4420

Last change on this file since 4420 was 4420, checked in by swinkler, 14 years ago

Implemented population diversity analyzer for TSP. (#1188)
File size: 18.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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.Drawing;
25using System.IO;
26using System.Linq;
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;
35
36namespace HeuristicLab.Problems.TravelingSalesman {
37  [Item("Traveling Salesman Problem", "Represents a symmetric Traveling Salesman Problem.")]
38  [Creatable("Problems")]
39  [StorableClass]
40  public sealed class TravelingSalesmanProblem : ParameterizedNamedItem, ISingleObjectiveProblem {
41    public override Image ItemImage {
42      get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Type; }
43    }
44
45    #region Parameter Properties
46    public ValueParameter<BoolValue> MaximizationParameter {
47      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
48    }
49    IParameter ISingleObjectiveProblem.MaximizationParameter {
50      get { return MaximizationParameter; }
51    }
52    public ValueParameter<DoubleMatrix> CoordinatesParameter {
53      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
54    }
55    public OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
56      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
57    }
58    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
59      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
60    }
61    public ValueParameter<IPermutationCreator> SolutionCreatorParameter {
62      get { return (ValueParameter<IPermutationCreator>)Parameters["SolutionCreator"]; }
63    }
64    IParameter IProblem.SolutionCreatorParameter {
65      get { return SolutionCreatorParameter; }
66    }
67    public ValueParameter<ITSPEvaluator> EvaluatorParameter {
68      get { return (ValueParameter<ITSPEvaluator>)Parameters["Evaluator"]; }
69    }
70    IParameter IProblem.EvaluatorParameter {
71      get { return EvaluatorParameter; }
72    }
73    public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
74      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
75    }
76    IParameter ISingleObjectiveProblem.BestKnownQualityParameter {
77      get { return BestKnownQualityParameter; }
78    }
79    public OptionalValueParameter<Permutation> BestKnownSolutionParameter {
80      get { return (OptionalValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
81    }
82    #endregion
83
84    #region Properties
85    public DoubleMatrix Coordinates {
86      get { return CoordinatesParameter.Value; }
87      set { CoordinatesParameter.Value = value; }
88    }
89    public DoubleMatrix DistanceMatrix {
90      get { return DistanceMatrixParameter.Value; }
91      set { DistanceMatrixParameter.Value = value; }
92    }
93    public BoolValue UseDistanceMatrix {
94      get { return UseDistanceMatrixParameter.Value; }
95      set { UseDistanceMatrixParameter.Value = value; }
96    }
97    public IPermutationCreator SolutionCreator {
98      get { return SolutionCreatorParameter.Value; }
99      set { SolutionCreatorParameter.Value = value; }
100    }
101    ISolutionCreator IProblem.SolutionCreator {
102      get { return SolutionCreatorParameter.Value; }
103    }
104    public ITSPEvaluator Evaluator {
105      get { return EvaluatorParameter.Value; }
106      set { EvaluatorParameter.Value = value; }
107    }
108    ISingleObjectiveEvaluator ISingleObjectiveProblem.Evaluator {
109      get { return EvaluatorParameter.Value; }
110    }
111    IEvaluator IProblem.Evaluator {
112      get { return EvaluatorParameter.Value; }
113    }
114    public DoubleValue BestKnownQuality {
115      get { return BestKnownQualityParameter.Value; }
116      set { BestKnownQualityParameter.Value = value; }
117    }
118    public Permutation BestKnownSolution {
119      get { return BestKnownSolutionParameter.Value; }
120      set { BestKnownSolutionParameter.Value = value; }
121    }
122    public IEnumerable<IOperator> Operators {
123      get { return operators; }
124    }
125    private BestTSPSolutionAnalyzer BestTSPSolutionAnalyzer {
126      get { return operators.OfType<BestTSPSolutionAnalyzer>().FirstOrDefault(); }
127    }
128    private TSPPopulationDiversityAnalyzer TSPPopulationDiversityAnalyzer {
129      get { return operators.OfType<TSPPopulationDiversityAnalyzer>().FirstOrDefault(); }
130    }
131    #endregion
132
133    [Storable]
134    private List<IOperator> operators;
135
136    [StorableConstructor]
137    private TravelingSalesmanProblem(bool deserializing) : base(deserializing) { }
138    public TravelingSalesmanProblem()
139      : base() {
140      RandomPermutationCreator creator = new RandomPermutationCreator();
141      TSPRoundedEuclideanPathEvaluator evaluator = new TSPRoundedEuclideanPathEvaluator();
142
143      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Traveling Salesman Problem is a minimization problem.", new BoolValue(false)));
144      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
145      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
146      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
147      Parameters.Add(new ValueParameter<IPermutationCreator>("SolutionCreator", "The operator which should be used to create new TSP solutions.", creator));
148      Parameters.Add(new ValueParameter<ITSPEvaluator>("Evaluator", "The operator which should be used to evaluate TSP solutions.", evaluator));
149      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this TSP instance."));
150      Parameters.Add(new OptionalValueParameter<Permutation>("BestKnownSolution", "The best known solution of this TSP instance."));
151
152      Coordinates = new DoubleMatrix(new double[,] {
153        { 100, 100 }, { 100, 200 }, { 100, 300 }, { 100, 400 },
154        { 200, 100 }, { 200, 200 }, { 200, 300 }, { 200, 400 },
155        { 300, 100 }, { 300, 200 }, { 300, 300 }, { 300, 400 },
156        { 400, 100 }, { 400, 200 }, { 400, 300 }, { 400, 400 }
157      });
158
159      creator.PermutationParameter.ActualName = "TSPTour";
160      evaluator.QualityParameter.ActualName = "TSPTourLength";
161      ParameterizeSolutionCreator();
162      ParameterizeEvaluator();
163
164      InitializeOperators();
165      AttachEventHandlers();
166    }
167
168    public override IDeepCloneable Clone(Cloner cloner) {
169      TravelingSalesmanProblem clone = (TravelingSalesmanProblem)base.Clone(cloner);
170      clone.operators = operators.Select(x => (IOperator)cloner.Clone(x)).ToList();
171      clone.DistanceMatrixParameter.Value = DistanceMatrixParameter.Value;
172      clone.AttachEventHandlers();
173      return clone;
174    }
175
176    #region Events
177    public event EventHandler SolutionCreatorChanged;
178    private void OnSolutionCreatorChanged() {
179      EventHandler handler = SolutionCreatorChanged;
180      if (handler != null) handler(this, EventArgs.Empty);
181    }
182    public event EventHandler EvaluatorChanged;
183    private void OnEvaluatorChanged() {
184      EventHandler handler = EvaluatorChanged;
185      if (handler != null) handler(this, EventArgs.Empty);
186    }
187    public event EventHandler OperatorsChanged;
188    private void OnOperatorsChanged() {
189      EventHandler handler = OperatorsChanged;
190      if (handler != null) handler(this, EventArgs.Empty);
191    }
192    public event EventHandler Reset;
193    private void OnReset() {
194      EventHandler handler = Reset;
195      if (handler != null) handler(this, EventArgs.Empty);
196    }
197
198    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
199      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
200      Coordinates.Reset += new EventHandler(Coordinates_Reset);
201      ParameterizeSolutionCreator();
202      ClearDistanceMatrix();
203    }
204    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
205      ClearDistanceMatrix();
206    }
207    private void Coordinates_Reset(object sender, EventArgs e) {
208      ParameterizeSolutionCreator();
209      ClearDistanceMatrix();
210    }
211    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
212      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
213      ParameterizeSolutionCreator();
214      ParameterizeEvaluator();
215      ParameterizeAnalyzers();
216      ParameterizeOperators();
217      OnSolutionCreatorChanged();
218    }
219    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
220      ParameterizeEvaluator();
221      ParameterizeAnalyzers();
222      ParameterizeOperators();
223    }
224    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
225      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
226      ParameterizeEvaluator();
227      UpdateMoveEvaluators();
228      ParameterizeAnalyzers();
229      ClearDistanceMatrix();
230      OnEvaluatorChanged();
231    }
232    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
233      ParameterizeAnalyzers();
234    }
235    private void MoveGenerator_InversionMoveParameter_ActualNameChanged(object sender, EventArgs e) {
236      string name = ((ILookupParameter<InversionMove>)sender).ActualName;
237      foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>()) {
238        op.InversionMoveParameter.ActualName = name;
239      }
240    }
241    private void MoveGenerator_TranslocationMoveParameter_ActualNameChanged(object sender, EventArgs e) {
242      string name = ((ILookupParameter<TranslocationMove>)sender).ActualName;
243      foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>()) {
244        op.TranslocationMoveParameter.ActualName = name;
245      }
246    }
247    #endregion
248
249    #region Helpers
250    [StorableHook(HookType.AfterDeserialization)]
251    private void AfterDeserializationHook() {
252      // BackwardsCompatibility3.3
253      #region Backwards compatible code (remove with 3.4)
254      if (operators == null) InitializeOperators();
255      #endregion
256      AttachEventHandlers();
257    }
258
259    private void AttachEventHandlers() {
260      CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
261      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
262      Coordinates.Reset += new EventHandler(Coordinates_Reset);
263      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
264      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
265      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
266      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
267    }
268
269    private void InitializeOperators() {
270      operators = new List<IOperator>();
271      operators.Add(new BestTSPSolutionAnalyzer());
272      operators.Add(new TSPPopulationDiversityAnalyzer());
273      ParameterizeAnalyzers();
274      operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>().Cast<IOperator>());
275      ParameterizeOperators();
276      UpdateMoveEvaluators();
277      InitializeMoveGenerators();
278    }
279    private void InitializeMoveGenerators() {
280      foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>()) {
281        if (op is IMoveGenerator) {
282          op.InversionMoveParameter.ActualNameChanged += new EventHandler(MoveGenerator_InversionMoveParameter_ActualNameChanged);
283        }
284      }
285      foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>()) {
286        if (op is IMoveGenerator) {
287          op.TranslocationMoveParameter.ActualNameChanged += new EventHandler(MoveGenerator_TranslocationMoveParameter_ActualNameChanged);
288        }
289      }
290    }
291    private void UpdateMoveEvaluators() {
292      operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
293      foreach (ITSPPathMoveEvaluator op in ApplicationManager.Manager.GetInstances<ITSPPathMoveEvaluator>())
294        if (op.EvaluatorType == Evaluator.GetType()) {
295          operators.Add(op);
296        }
297      ParameterizeOperators();
298      OnOperatorsChanged();
299    }
300    private void ParameterizeSolutionCreator() {
301      SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
302      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.RelativeUndirected);
303    }
304    private void ParameterizeEvaluator() {
305      if (Evaluator is ITSPPathEvaluator)
306        ((ITSPPathEvaluator)Evaluator).PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
307      if (Evaluator is ITSPCoordinatesPathEvaluator) {
308        ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
309        evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
310        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
311        evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
312      }
313    }
314    private void ParameterizeAnalyzers() {
315      BestTSPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
316      BestTSPSolutionAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
317      BestTSPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
318      BestTSPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
319      BestTSPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
320      BestTSPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
321      BestTSPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
322      TSPPopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
323      TSPPopulationDiversityAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
324    }
325    private void ParameterizeOperators() {
326      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
327        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
328        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
329      }
330      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
331        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
332      }
333      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
334        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
335      }
336      foreach (ITSPPathMoveEvaluator op in Operators.OfType<ITSPPathMoveEvaluator>()) {
337        op.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
338        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
339        op.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
340        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
341        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
342      }
343      string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
344      foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
345        op.InversionMoveParameter.ActualName = inversionMove;
346      string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
347      foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
348        op.TranslocationMoveParameter.ActualName = translocationMove;
349    }
350
351    private void ClearDistanceMatrix() {
352      DistanceMatrixParameter.Value = null;
353    }
354    #endregion
355
356    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName) {
357      TSPLIBParser tspParser = new TSPLIBParser(tspFileName);
358      tspParser.Parse();
359      Name = tspParser.Name + " TSP (imported from TSPLIB)";
360      if (!string.IsNullOrEmpty(tspParser.Comment)) Description = tspParser.Comment;
361      Coordinates = new DoubleMatrix(tspParser.Vertices);
362      if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D) {
363        TSPRoundedEuclideanPathEvaluator evaluator = new TSPRoundedEuclideanPathEvaluator();
364        evaluator.QualityParameter.ActualName = "TSPTourLength";
365        Evaluator = evaluator;
366      } else if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.GEO) {
367        TSPGeoPathEvaluator evaluator = new TSPGeoPathEvaluator();
368        evaluator.QualityParameter.ActualName = "TSPTourLength";
369        Evaluator = evaluator;
370      }
371      BestKnownQuality = null;
372      BestKnownSolution = null;
373
374      if (!string.IsNullOrEmpty(optimalTourFileName)) {
375        TSPLIBTourParser tourParser = new TSPLIBTourParser(optimalTourFileName);
376        tourParser.Parse();
377        if (tourParser.Tour.Length != Coordinates.Rows) throw new InvalidDataException("Length of optimal tour is not equal to number of cities.");
378        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, tourParser.Tour);
379      }
380      OnReset();
381    }
382    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName, double bestKnownQuality) {
383      ImportFromTSPLIB(tspFileName, optimalTourFileName);
384      BestKnownQuality = new DoubleValue(bestKnownQuality);
385    }
386  }
387}
Note: See TracBrowser for help on using the repository browser.