source: trunk/sources/HeuristicLab.Problems.TSP/3.3/TSP.cs @ 3147

Last change on this file since 3147 was 3147, checked in by swagner, 12 years ago

Stored name of TSP instance imported from TSPLIB (#924).

File size: 14.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.Linq;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34
35namespace HeuristicLab.Problems.TSP {
36  [Item("TSP", "Represents a symmetric Traveling Salesman Problem.")]
37  [Creatable("Problems")]
38  [StorableClass]
39  public sealed class TSP : ParameterizedNamedItem, ISingleObjectiveProblem {
40    public override Image ItemImage {
41      get { return HeuristicLab.Common.Resources.VS2008ImageLibrary.Type; }
42    }
43
44    #region Parameter Properties
45    public ValueParameter<BoolValue> MaximizationParameter {
46      get { return (ValueParameter<BoolValue>)Parameters["Maximization"]; }
47    }
48    IParameter ISingleObjectiveProblem.MaximizationParameter {
49      get { return MaximizationParameter; }
50    }
51    public ValueParameter<DoubleMatrix> CoordinatesParameter {
52      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
53    }
54    public OptionalValueParameter<DoubleMatrix> DistanceMatrixParameter {
55      get { return (OptionalValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
56    }
57    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
58      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
59    }
60    public ValueParameter<IPermutationCreator> SolutionCreatorParameter {
61      get { return (ValueParameter<IPermutationCreator>)Parameters["SolutionCreator"]; }
62    }
63    IParameter IProblem.SolutionCreatorParameter {
64      get { return SolutionCreatorParameter; }
65    }
66    public ValueParameter<ITSPEvaluator> EvaluatorParameter {
67      get { return (ValueParameter<ITSPEvaluator>)Parameters["Evaluator"]; }
68    }
69    IParameter IProblem.EvaluatorParameter {
70      get { return EvaluatorParameter; }
71    }
72    public OptionalValueParameter<ITSPSolutionsVisualizer> VisualizerParameter {
73      get { return (OptionalValueParameter<ITSPSolutionsVisualizer>)Parameters["Visualizer"]; }
74    }
75    IParameter IProblem.VisualizerParameter {
76      get { return VisualizerParameter; }
77    }
78    public OptionalValueParameter<DoubleValue> BestKnownQualityParameter {
79      get { return (OptionalValueParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
80    }
81    IParameter ISingleObjectiveProblem.BestKnownQualityParameter {
82      get { return BestKnownQualityParameter; }
83    }
84    #endregion
85
86    #region Properties
87    public DoubleMatrix Coordinates {
88      get { return CoordinatesParameter.Value; }
89      set { CoordinatesParameter.Value = value; }
90    }
91    public DoubleMatrix DistanceMatrix {
92      get { return DistanceMatrixParameter.Value; }
93      set { DistanceMatrixParameter.Value = value; }
94    }
95    public BoolValue UseDistanceMatrix {
96      get { return UseDistanceMatrixParameter.Value; }
97      set { UseDistanceMatrixParameter.Value = value; }
98    }
99    public IPermutationCreator SolutionCreator {
100      get { return SolutionCreatorParameter.Value; }
101      set { SolutionCreatorParameter.Value = value; }
102    }
103    ISolutionCreator IProblem.SolutionCreator {
104      get { return SolutionCreatorParameter.Value; }
105    }
106    public ITSPEvaluator Evaluator {
107      get { return EvaluatorParameter.Value; }
108      set { EvaluatorParameter.Value = value; }
109    }
110    ISingleObjectiveEvaluator ISingleObjectiveProblem.Evaluator {
111      get { return EvaluatorParameter.Value; }
112    }
113    IEvaluator IProblem.Evaluator {
114      get { return EvaluatorParameter.Value; }
115    }
116    public ITSPSolutionsVisualizer Visualizer {
117      get { return VisualizerParameter.Value; }
118      set { VisualizerParameter.Value = value; }
119    }
120    ISolutionsVisualizer IProblem.Visualizer {
121      get { return VisualizerParameter.Value; }
122    }
123    public DoubleValue BestKnownQuality {
124      get { return BestKnownQualityParameter.Value; }
125      set { BestKnownQualityParameter.Value = value; }
126    }
127    private List<IPermutationOperator> operators;
128    public IEnumerable<IOperator> Operators {
129      get { return operators.Cast<IOperator>(); }
130    }
131    #endregion
132
133    public TSP()
134      : base() {
135      RandomPermutationCreator creator = new RandomPermutationCreator();
136      TSPRoundedEuclideanPathEvaluator evaluator = new TSPRoundedEuclideanPathEvaluator();
137      BestPathTSPTourVisualizer visualizer = new BestPathTSPTourVisualizer();
138
139      Parameters.Add(new ValueParameter<BoolValue>("Maximization", "Set to false as the Traveling Salesman Problem is a minimization problem.", new BoolValue(false)));
140      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities.", new DoubleMatrix(0, 0)));
141      Parameters.Add(new OptionalValueParameter<DoubleMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
142      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "True if a distance matrix should be calculated and used for evaluation, otherwise false.", new BoolValue(true)));
143      Parameters.Add(new ValueParameter<IPermutationCreator>("SolutionCreator", "The operator which should be used to create new TSP solutions.", creator));
144      Parameters.Add(new ValueParameter<ITSPEvaluator>("Evaluator", "The operator which should be used to evaluate TSP solutions.", evaluator));
145      Parameters.Add(new OptionalValueParameter<ITSPSolutionsVisualizer>("Visualizer", "The operator which should be used to visualize TSP solutions.", visualizer));
146      Parameters.Add(new OptionalValueParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this TSP instance."));
147
148      creator.PermutationParameter.ActualName = "TSPTour";
149      evaluator.QualityParameter.ActualName = "TSPTourLength";
150      ParameterizeSolutionCreator();
151      ParameterizeEvaluator();
152      ParameterizeVisualizer();
153
154      Initialize();
155    }
156    [StorableConstructor]
157    private TSP(bool deserializing) : base() { }
158
159    public override IDeepCloneable Clone(Cloner cloner) {
160      TSP clone = (TSP)base.Clone(cloner);
161      clone.Initialize();
162      return clone;
163    }
164
165    public void ImportFromTSPLIB(string filename) {
166      TSPLIBParser parser = new TSPLIBParser(filename);
167      parser.Parse();
168      Name = parser.Name + " TSP (imported from TSPLIB)";
169      Coordinates = new DoubleMatrix(parser.Vertices);
170    }
171
172    #region Events
173    public event EventHandler SolutionCreatorChanged;
174    private void OnSolutionCreatorChanged() {
175      if (SolutionCreatorChanged != null)
176        SolutionCreatorChanged(this, EventArgs.Empty);
177    }
178    public event EventHandler EvaluatorChanged;
179    private void OnEvaluatorChanged() {
180      if (EvaluatorChanged != null)
181        EvaluatorChanged(this, EventArgs.Empty);
182    }
183    public event EventHandler VisualizerChanged;
184    private void OnVisualizerChanged() {
185      if (VisualizerChanged != null)
186        VisualizerChanged(this, EventArgs.Empty);
187    }
188    public event EventHandler OperatorsChanged;
189    private void OnOperatorsChanged() {
190      if (OperatorsChanged != null)
191        OperatorsChanged(this, EventArgs.Empty);
192    }
193
194    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
195      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
196      Coordinates.Reset += new EventHandler(Coordinates_Reset);
197      ParameterizeSolutionCreator();
198      ClearDistanceMatrix();
199    }
200    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
201      ClearDistanceMatrix();
202    }
203    private void Coordinates_Reset(object sender, EventArgs e) {
204      ParameterizeSolutionCreator();
205      ClearDistanceMatrix();
206    }
207    private void SolutionCreatorParameter_ValueChanged(object sender, EventArgs e) {
208      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
209      ParameterizeSolutionCreator();
210      ParameterizeEvaluator();
211      ParameterizeVisualizer();
212      ParameterizeOperators();
213      OnSolutionCreatorChanged();
214    }
215    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
216      ParameterizeEvaluator();
217      ParameterizeVisualizer();
218      ParameterizeOperators();
219    }
220    private void EvaluatorParameter_ValueChanged(object sender, EventArgs e) {
221      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
222      ParameterizeEvaluator();
223      ParameterizeVisualizer();
224      ClearDistanceMatrix();
225      OnEvaluatorChanged();
226    }
227    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
228      ParameterizeVisualizer();
229    }
230    private void VisualizerParameter_ValueChanged(object sender, EventArgs e) {
231      ParameterizeVisualizer();
232      OnVisualizerChanged();
233    }
234    private void MoveGenerator_TwoOptMoveParameter_ActualNameChanged(object sender, EventArgs e) {
235      string name = ((ILookupParameter<TwoOptMove>)sender).ActualName;
236      foreach (ITwoOptPermutationMoveOperator op in Operators.OfType<ITwoOptPermutationMoveOperator>()) {
237        op.TwoOptMoveParameter.ActualName = name;
238      }
239    }
240    private void MoveGenerator_ThreeOptMoveParameter_ActualNameChanged(object sender, EventArgs e) {
241      string name = ((ILookupParameter<ThreeOptMove>)sender).ActualName;
242      foreach (IThreeOptPermutationMoveOperator op in Operators.OfType<IThreeOptPermutationMoveOperator>()) {
243        op.ThreeOptMoveParameter.ActualName = name;
244      }
245    }
246    #endregion
247
248    #region Helpers
249    [StorableHook(HookType.AfterDeserialization)]
250    private void Initialize() {
251      InitializeOperators();
252      CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
253      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
254      Coordinates.Reset += new EventHandler(Coordinates_Reset);
255      SolutionCreatorParameter.ValueChanged += new EventHandler(SolutionCreatorParameter_ValueChanged);
256      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
257      EvaluatorParameter.ValueChanged += new EventHandler(EvaluatorParameter_ValueChanged);
258      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
259      VisualizerParameter.ValueChanged += new EventHandler(VisualizerParameter_ValueChanged);
260    }
261
262    private void InitializeOperators() {
263      operators = new List<IPermutationOperator>();
264      if (ApplicationManager.Manager != null) {
265        operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
266        ParameterizeOperators();
267      }
268      InitializeMoveGenerators();
269    }
270    private void InitializeMoveGenerators() {
271      foreach (ITwoOptPermutationMoveOperator op in Operators.OfType<ITwoOptPermutationMoveOperator>()) {
272        if (op is IMoveGenerator) {
273          op.TwoOptMoveParameter.ActualNameChanged += new EventHandler(MoveGenerator_TwoOptMoveParameter_ActualNameChanged);
274        }
275      }
276      foreach (IThreeOptPermutationMoveOperator op in Operators.OfType<IThreeOptPermutationMoveOperator>()) {
277        if (op is IMoveGenerator) {
278          op.ThreeOptMoveParameter.ActualNameChanged += new EventHandler(MoveGenerator_ThreeOptMoveParameter_ActualNameChanged);
279        }
280      }
281    }
282    private void ParameterizeSolutionCreator() {
283      SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
284    }
285    private void ParameterizeEvaluator() {
286      if (Evaluator is ITSPPathEvaluator)
287        ((ITSPPathEvaluator)Evaluator).PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
288      if (Evaluator is ITSPCoordinatesPathEvaluator) {
289        ITSPCoordinatesPathEvaluator evaluator = (ITSPCoordinatesPathEvaluator)Evaluator;
290        evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
291        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
292        evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
293      }
294    }
295    private void ParameterizeVisualizer() {
296      if (Visualizer != null) {
297        Visualizer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
298        if (Visualizer is ICoordinatesTSPSolutionsVisualizer)
299          ((ICoordinatesTSPSolutionsVisualizer)Visualizer).CoordinatesParameter.ActualName = CoordinatesParameter.Name;
300        if (Visualizer is IPathCoordinatesTSPSolutionsVisualizer)
301          ((IPathCoordinatesTSPSolutionsVisualizer)Visualizer).PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
302      }
303    }
304    private void ParameterizeOperators() {
305      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
306        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
307        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
308      }
309      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
310        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
311      }
312      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
313        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
314      }
315      foreach (ITSPPathMoveEvaluator op in Operators.OfType<ITSPPathMoveEvaluator>()) {
316        op.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
317        op.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
318        op.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
319      }
320    }
321
322    private void ClearDistanceMatrix() {
323      DistanceMatrixParameter.Value = null;
324    }
325    #endregion
326  }
327}
Note: See TracBrowser for help on using the repository browser.