Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 5583 was 5583, checked in by abeham, 14 years ago

#1330

  • Worked on QAP
    • Added solution and analyzer
    • Added crude solution view
  • Overwrote instances with those from new QAPLIB site (Pennsylvania)
File size: 13.5 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 ValueParameter<Permutation> BestKnownSolutionParameter {
50      get { return (ValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
51    }
52    public ValueParameter<DoubleMatrix> CoordinatesParameter {
53      get { return (ValueParameter<DoubleMatrix>)Parameters["Coordinates"]; }
54    }
55    public ValueParameter<DoubleMatrix> WeightsParameter {
56      get { return (ValueParameter<DoubleMatrix>)Parameters["Weights"]; }
57    }
58    public ValueParameter<DoubleMatrix> DistanceMatrixParameter {
59      get { return (ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]; }
60    }
61    public ValueParameter<BoolValue> UseDistanceMatrixParameter {
62      get { return (ValueParameter<BoolValue>)Parameters["UseDistanceMatrix"]; }
63    }
64
65    #endregion
66
67    #region Properties
68    public Permutation BestKnownSolution {
69      get { return BestKnownSolutionParameter.Value; }
70      set { BestKnownSolutionParameter.Value = value; }
71    }
72    public DoubleMatrix Coordinates {
73      get { return CoordinatesParameter.Value; }
74      set { CoordinatesParameter.Value = value; }
75    }
76    public DoubleMatrix Weights {
77      get { return WeightsParameter.Value; }
78      set { WeightsParameter.Value = value; }
79    }
80    public DoubleMatrix DistanceMatrix {
81      get { return DistanceMatrixParameter.Value; }
82      set { DistanceMatrixParameter.Value = value; }
83    }
84    public BoolValue UseDistanceMatrix {
85      get { return UseDistanceMatrixParameter.Value; }
86      set { UseDistanceMatrixParameter.Value = value; }
87    }
88
89    public IEnumerable<string> EmbeddedInstances {
90      get {
91        return Assembly.GetExecutingAssembly()
92          .GetManifestResourceNames()
93          .Where(x => x.EndsWith(".dat"))
94          .OrderBy(x => x)
95          .Select(x => x.Replace(".dat", String.Empty))
96          .Select(x => x.Replace(InstancePrefix, String.Empty));
97      }
98    }
99
100    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
101      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
102    }
103    #endregion
104
105    [StorableConstructor]
106    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
107    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
108      : base(original, cloner) {
109      AttachEventHandlers();
110    }
111    public QuadraticAssignmentProblem()
112      : base() {
113      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));
114      Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The coordinates of the locations."));
115      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
116      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)));
117      Parameters.Add(new ValueParameter<BoolValue>("UseDistanceMatrix", "Defaults to true, set to false only when the number of facilities is very high and a distance matrix would become too large (>1000 facilities).", new BoolValue(true)));
118
119      Maximization = new BoolValue(false);
120
121      Coordinates = new DoubleMatrix(new double[,] {
122        { 294.000,   3.000 },
123        { 585.246, 214.603 },
124        { 474.000, 556.983 },
125        { 114.000, 556.983 },
126        {   2.754, 214.603 }
127      });
128
129      Weights = new DoubleMatrix(new double[,] {
130        { 0, 1, 0, 0, 1 },
131        { 1, 0, 1, 0, 0 },
132        { 0, 1, 0, 1, 0 },
133        { 0, 0, 1, 0, 1 },
134        { 1, 0, 0, 1, 0 }
135      });
136
137      DistanceMatrix = new DoubleMatrix(new double[,] {
138        {   0, 360, 582, 582, 360 },
139        { 360,   0, 360, 582, 582 },
140        { 582, 360,   0, 360, 582 },
141        { 582, 582, 360,   0, 360 },
142        { 360, 582, 582, 360,   0 }
143      });
144
145      RandomPermutationCreator solutionCreator = new RandomPermutationCreator();
146      solutionCreator.LengthParameter.Value = new IntValue(5);
147      solutionCreator.PermutationParameter.ActualName = "Assignment";
148      QAPEvaluator evaluator = new QAPEvaluator();
149
150      SolutionCreatorParameter.Value = solutionCreator;
151      EvaluatorParameter.Value = evaluator;
152
153      InitializeOperators();
154      AttachEventHandlers();
155    }
156
157    public override IDeepCloneable Clone(Cloner cloner) {
158      return new QuadraticAssignmentProblem(this, cloner);
159    }
160
161    #region Events
162    protected override void OnSolutionCreatorChanged() {
163      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
164      ParameterizeSolutionCreator();
165      ParameterizeEvaluator();
166      ParameterizeAnalyzers();
167      ParameterizeOperators();
168      base.OnSolutionCreatorChanged();
169    }
170    protected override void OnEvaluatorChanged() {
171      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
172      ParameterizeEvaluator();
173      ParameterizeAnalyzers();
174      ParameterizeOperators();
175      base.OnEvaluatorChanged();
176    }
177
178    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
179      ParameterizeEvaluator();
180      ParameterizeAnalyzers();
181      ParameterizeOperators();
182    }
183    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
184      ParameterizeAnalyzers();
185      ParameterizeOperators();
186    }
187    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
188      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
189      ParameterizeSolutionCreator();
190      ParameterizeEvaluator();
191      ParameterizeOperators();
192    }
193    private void Weights_RowsChanged(object sender, EventArgs e) {
194      ParameterizeSolutionCreator();
195      ParameterizeEvaluator();
196      ParameterizeOperators();
197    }
198    #endregion
199
200    #region Helpers
201    [StorableHook(HookType.AfterDeserialization)]
202    private void AfterDeserializationHook() {
203      AttachEventHandlers();
204    }
205
206    private void AttachEventHandlers() {
207      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
208      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
209      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
210      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
211    }
212
213    private void InitializeOperators() {
214      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
215      Operators.Add(new BestQAPSolutionAnalyzer());
216      ParameterizeAnalyzers();
217      ParameterizeOperators();
218    }
219    private void ParameterizeSolutionCreator() {
220      if (SolutionCreator != null) {
221        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
222        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
223      }
224    }
225    private void ParameterizeEvaluator() {
226      if (Evaluator != null) {
227        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
228        Evaluator.UseDistanceMatrixParameter.ActualName = UseDistanceMatrixParameter.Name;
229        Evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
230        Evaluator.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
231        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
232      }
233    }
234    private void ParameterizeAnalyzers() {
235      if (BestQAPSolutionAnalyzer != null) {
236        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
237        BestQAPSolutionAnalyzer.CoordinatesParameter.ActualName = CoordinatesParameter.Name;
238        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistanceMatrixParameter.Name;
239        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
240        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
241        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
242        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
243        BestQAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
244        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
245      }
246    }
247    private void ParameterizeOperators() {
248      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
249        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
250        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
251      }
252      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
253        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
254      }
255      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
256        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
257      }
258      if (Operators.OfType<IMoveGenerator>().Any()) {
259        string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
260        foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
261          op.InversionMoveParameter.ActualName = inversionMove;
262        string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
263        foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
264          op.TranslocationMoveParameter.ActualName = translocationMove;
265      }
266    }
267    #endregion
268
269    public void ImportFileInstance(string filename) {
270      QAPLIBParser parser = new QAPLIBParser();
271      parser.Parse(filename);
272      Coordinates = new DoubleMatrix();
273      DistanceMatrix = new DoubleMatrix(parser.Distances);
274      Weights = new DoubleMatrix(parser.Weights);
275      UseDistanceMatrix.Value = true;
276      Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(filename) + ")";
277      Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
278      OnReset();
279    }
280
281    public void LoadEmbeddedInstance(string instance) {
282      using (Stream stream = Assembly.GetExecutingAssembly()
283        .GetManifestResourceStream(InstancePrefix + instance + ".dat")) {
284        QAPLIBParser parser = new QAPLIBParser();
285        parser.Parse(stream);
286        Coordinates = new DoubleMatrix();
287        DistanceMatrix = new DoubleMatrix(parser.Distances);
288        Weights = new DoubleMatrix(parser.Weights);
289        UseDistanceMatrix.Value = true;
290        Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
291        Description = "Loaded embedded problem data of instance " + instance + ".";
292        OnReset();
293      }
294    }
295  }
296}
Note: See TracBrowser for help on using the repository browser.