Free cookie consent management tool by TermsFeed Policy Generator

source: branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 5641

Last change on this file since 5641 was 5641, checked in by abeham, 12 years ago

#1330

  • worked on visualization (and MDS)
File size: 15.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 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 System.Reflection;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Data;
31using HeuristicLab.Encodings.PermutationEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.PluginInfrastructure;
36
37namespace HeuristicLab.Problems.QuadraticAssignment {
38  [Item("Quadratic Assignment Problem", "The Quadratic Assignment Problem (QAP) is the problem of assigning N facilities to N fixed locations such that there is exactly one facility in each location and that the distances multiplied by the connection strength between the facilities becomes minimal.")]
39  [Creatable("Problems")]
40  [StorableClass]
41  public sealed class QuadraticAssignmentProblem : SingleObjectiveProblem<IQAPEvaluator, IPermutationCreator> {
42    private static string InstancePrefix = "HeuristicLab.Problems.QuadraticAssignment.Data.";
43
44    public override Image ItemImage {
45      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
46    }
47
48    #region Parameter Properties
49    public IValueParameter<Permutation> BestKnownSolutionParameter {
50      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
51    }
52    public IValueParameter<DoubleMatrix> CoordinatesParameter {
53      get { return (IValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
54    }
55    public IValueParameter<DoubleMatrix> WeightsParameter {
56      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
57    }
58    public IValueParameter<DoubleMatrix> DistanceMatrixParameter {
59      get { return (IValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
60    }
61    #endregion
62
63    #region Properties
64    public Permutation BestKnownSolution {
65      get { return BestKnownSolutionParameter.Value; }
66      set { BestKnownSolutionParameter.Value = value; }
67    }
68    public DoubleMatrix Coordinates {
69      get { return CoordinatesParameter.Value; }
70      set { CoordinatesParameter.Value = value; }
71    }
72    public DoubleMatrix Weights {
73      get { return WeightsParameter.Value; }
74      set { WeightsParameter.Value = value; }
75    }
76    public DoubleMatrix DistanceMatrix {
77      get { return DistanceMatrixParameter.Value; }
78      set { DistanceMatrixParameter.Value = value; }
79    }
80
81    public IEnumerable<string> EmbeddedInstances {
82      get {
83        return Assembly.GetExecutingAssembly()
84          .GetManifestResourceNames()
85          .Where(x => x.EndsWith(".dat"))
86          .OrderBy(x => x)
87          .Select(x => x.Replace(".dat", String.Empty))
88          .Select(x => x.Replace(InstancePrefix, String.Empty));
89      }
90    }
91
92    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
93      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
94    }
95    #endregion
96
97    [StorableConstructor]
98    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
99    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
100      : base(original, cloner) {
101      AttachEventHandlers();
102    }
103    public QuadraticAssignmentProblem()
104      : base() {
105      Parameters.Add(new ValueParameter<Permutation>("BestKnownSolution", "The best known solution which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
106      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the locations. If this is changed the distance matrix is calculated automatically using the euclidean distance."));
107      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
108      Parameters.Add(new ValueParameter<DoubleMatrix>("DistanceMatrix", "The distance matrix which can either be specified directly without the coordinates, or can be calculated automatically from the coordinates.", new DoubleMatrix(5, 5)));
109
110      Maximization = new BoolValue(false);
111
112      Coordinates = new DoubleMatrix(new double[,] {
113        { 294.000,   3.000 },
114        { 585.246, 214.603 },
115        { 474.000, 556.983 },
116        { 114.000, 556.983 },
117        {   2.754, 214.603 }
118      });
119
120      Weights = new DoubleMatrix(new double[,] {
121        { 0, 1, 0, 0, 1 },
122        { 1, 0, 1, 0, 0 },
123        { 0, 1, 0, 1, 0 },
124        { 0, 0, 1, 0, 1 },
125        { 1, 0, 0, 1, 0 }
126      });
127
128      DistanceMatrix = new DoubleMatrix(new double[,] {
129        {   0, 360, 582, 582, 360 },
130        { 360,   0, 360, 582, 582 },
131        { 582, 360,   0, 360, 582 },
132        { 582, 582, 360,   0, 360 },
133        { 360, 582, 582, 360,   0 }
134      });
135
136      RandomPermutationCreator solutionCreator = new RandomPermutationCreator();
137      solutionCreator.LengthParameter.Value = new IntValue(5);
138      solutionCreator.PermutationParameter.ActualName = "Assignment";
139      QAPEvaluator evaluator = new QAPEvaluator();
140
141      SolutionCreatorParameter.Value = solutionCreator;
142      EvaluatorParameter.Value = evaluator;
143
144      InitializeOperators();
145      AttachEventHandlers();
146    }
147
148    public override IDeepCloneable Clone(Cloner cloner) {
149      return new QuadraticAssignmentProblem(this, cloner);
150    }
151
152    #region Events
153    protected override void OnSolutionCreatorChanged() {
154      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
155      ParameterizeSolutionCreator();
156      ParameterizeEvaluator();
157      ParameterizeAnalyzers();
158      ParameterizeOperators();
159      base.OnSolutionCreatorChanged();
160    }
161    protected override void OnEvaluatorChanged() {
162      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
163      ParameterizeEvaluator();
164      ParameterizeAnalyzers();
165      ParameterizeOperators();
166      base.OnEvaluatorChanged();
167    }
168
169    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
170      ParameterizeEvaluator();
171      ParameterizeAnalyzers();
172      ParameterizeOperators();
173    }
174    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
175      ParameterizeAnalyzers();
176      ParameterizeOperators();
177    }
178    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
179      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
180      ParameterizeSolutionCreator();
181      ParameterizeEvaluator();
182      ParameterizeOperators();
183    }
184    private void Weights_RowsChanged(object sender, EventArgs e) {
185      ParameterizeSolutionCreator();
186      ParameterizeEvaluator();
187      ParameterizeOperators();
188    }
189    private void CoordinatesParameter_ValueChanged(object sender, EventArgs e) {
190      Coordinates.Reset += new EventHandler(Coordinates_Reset);
191      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
192      UpdateDistanceMatrix();
193    }
194    private void Coordinates_ItemChanged(object sender, EventArgs<int, int> e) {
195      UpdateDistanceMatrix();
196    }
197    private void Coordinates_Reset(object sender, EventArgs e) {
198      UpdateDistanceMatrix();
199    }
200    #endregion
201
202    #region Helpers
203    [StorableHook(HookType.AfterDeserialization)]
204    private void AfterDeserializationHook() {
205      AttachEventHandlers();
206    }
207
208    private void AttachEventHandlers() {
209      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
210      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
211      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
212      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
213      CoordinatesParameter.ValueChanged += new EventHandler(CoordinatesParameter_ValueChanged);
214      Coordinates.Reset += new EventHandler(Coordinates_Reset);
215      Coordinates.ItemChanged += new EventHandler<EventArgs<int, int>>(Coordinates_ItemChanged);
216    }
217
218    private void InitializeOperators() {
219      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
220      Operators.Add(new BestQAPSolutionAnalyzer());
221      ParameterizeAnalyzers();
222      ParameterizeOperators();
223    }
224    private void ParameterizeSolutionCreator() {
225      if (SolutionCreator != null) {
226        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
227        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
228      }
229    }
230    private void ParameterizeEvaluator() {
231      if (Evaluator != null) {
232        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
233        Evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
234        Evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
235        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
236      }
237    }
238    private void ParameterizeAnalyzers() {
239      if (BestQAPSolutionAnalyzer != null) {
240        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
241        BestQAPSolutionAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
242        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistanceMatrixParameter.Name;
243        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
244        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
245        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
246        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
247        BestQAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
248        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
249      }
250    }
251    private void ParameterizeOperators() {
252      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
253        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
254        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
255      }
256      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
257        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
258      }
259      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
260        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
261      }
262      if (Operators.OfType<IMoveGenerator>().Any()) {
263        string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
264        foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
265          op.InversionMoveParameter.ActualName = inversionMove;
266        string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
267        foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
268          op.TranslocationMoveParameter.ActualName = translocationMove;
269      }
270    }
271
272    private void UpdateDistanceMatrix() {
273      if (Coordinates != null && Coordinates.Columns == 2 && Coordinates.Rows > 1) {
274        DistanceMatrix = new DoubleMatrix(Coordinates.Rows, Coordinates.Rows);
275        for (int i = 0; i < Coordinates.Rows - 1; i++) {
276          for (int j = i + 1; j < Coordinates.Rows; j++) {
277            double dx = Coordinates[i, 0] - Coordinates[j, 0];
278            double dy = Coordinates[i, 1] - Coordinates[j, 1];
279            DistanceMatrix[i, j] = Math.Sqrt(dx * dx + dy * dy);
280            DistanceMatrix[j, i] = DistanceMatrix[i, j];
281          }
282        }
283      }
284    }
285    #endregion
286
287    public void ImportFileInstance(string filename) {
288      QAPLIBParser parser = new QAPLIBParser();
289      parser.Parse(filename);
290      if (parser.Error != null) throw parser.Error;
291      Coordinates = new DoubleMatrix();
292      DistanceMatrix = new DoubleMatrix(parser.Distances);
293      Weights = new DoubleMatrix(parser.Weights);
294      Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(filename) + ")";
295      Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
296      BestKnownQuality = null;
297      BestKnownSolution = null;
298      OnReset();
299    }
300
301    public void LoadEmbeddedInstance(string instance) {
302      using (Stream stream = Assembly.GetExecutingAssembly()
303        .GetManifestResourceStream(InstancePrefix + instance + ".dat")) {
304        QAPLIBParser parser = new QAPLIBParser();
305        parser.Parse(stream);
306        if (parser.Error != null) throw parser.Error;
307        Coordinates = new DoubleMatrix();
308        DistanceMatrix = new DoubleMatrix(parser.Distances);
309        Weights = new DoubleMatrix(parser.Weights);
310        Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
311        Description = "Loaded embedded problem data of instance " + instance + ".";
312        OnReset();
313      }
314      bool solutionExists = Assembly.GetExecutingAssembly()
315          .GetManifestResourceNames()
316          .Where(x => x.EndsWith(instance + ".sln"))
317          .Any();
318      if (solutionExists) {
319        using (Stream solStream = Assembly.GetExecutingAssembly()
320          .GetManifestResourceStream(InstancePrefix + instance + ".sln")) {
321          QAPLIBSolutionParser solParser = new QAPLIBSolutionParser();
322          solParser.Parse(solStream);
323          if (solParser.Error != null) throw solParser.Error;
324          BestKnownQuality = new DoubleValue(solParser.Qualiy);
325          BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
326        }
327      } else {
328        BestKnownQuality = null;
329        BestKnownSolution = null;
330      }
331    }
332  }
333}
Note: See TracBrowser for help on using the repository browser.