Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 5949

Last change on this file since 5949 was 5949, checked in by abeham, 13 years ago

#1330

  • some remaining problems with benchmark data, two instances had quality values and solutions that did not go together
File size: 16.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) can be described as the problem of assigning N facilities to N fixed locations such that there is exactly one facility in each location and that the sum of the distances multiplied by the connection strength between the facilities becomes minimal.")]
39  [Creatable("Problems")]
40  [StorableClass]
41  public sealed class QuadraticAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<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> WeightsParameter {
53      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
54    }
55    public IValueParameter<DoubleMatrix> DistancesParameter {
56      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
57    }
58    #endregion
59
60    #region Properties
61    public Permutation BestKnownSolution {
62      get { return BestKnownSolutionParameter.Value; }
63      set { BestKnownSolutionParameter.Value = value; }
64    }
65    public DoubleMatrix Weights {
66      get { return WeightsParameter.Value; }
67      set { WeightsParameter.Value = value; }
68    }
69    public DoubleMatrix Distances {
70      get { return DistancesParameter.Value; }
71      set { DistancesParameter.Value = value; }
72    }
73
74    public IEnumerable<string> EmbeddedInstances {
75      get {
76        return Assembly.GetExecutingAssembly()
77          .GetManifestResourceNames()
78          .Where(x => x.EndsWith(".dat"))
79          .OrderBy(x => x)
80          .Select(x => x.Replace(".dat", String.Empty))
81          .Select(x => x.Replace(InstancePrefix, String.Empty));
82      }
83    }
84
85    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
86      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
87    }
88    #endregion
89
90    [StorableConstructor]
91    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
92    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
93      : base(original, cloner) {
94      AttachEventHandlers();
95    }
96    public QuadraticAssignmentProblem()
97      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
98      Parameters.Add(new OptionalValueParameter<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));
99      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
100      Parameters.Add(new ValueParameter<DoubleMatrix>("Distances", "The distance matrix which can either be specified directly without the coordinates, or can be calculated automatically from the coordinates.", new DoubleMatrix(5, 5)));
101
102      Maximization = new BoolValue(false);
103
104      Weights = new DoubleMatrix(new double[,] {
105        { 0, 1, 0, 0, 1 },
106        { 1, 0, 1, 0, 0 },
107        { 0, 1, 0, 1, 0 },
108        { 0, 0, 1, 0, 1 },
109        { 1, 0, 0, 1, 0 }
110      });
111
112      Distances = new DoubleMatrix(new double[,] {
113        {   0, 360, 582, 582, 360 },
114        { 360,   0, 360, 582, 582 },
115        { 582, 360,   0, 360, 582 },
116        { 582, 582, 360,   0, 360 },
117        { 360, 582, 582, 360,   0 }
118      });
119
120      SolutionCreator.PermutationParameter.ActualName = "Assignment";
121      ParameterizeSolutionCreator();
122      ParameterizeEvaluator();
123
124      InitializeOperators();
125      AttachEventHandlers();
126    }
127
128    public override IDeepCloneable Clone(Cloner cloner) {
129      return new QuadraticAssignmentProblem(this, cloner);
130    }
131
132    #region Events
133    protected override void OnSolutionCreatorChanged() {
134      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
135      ParameterizeSolutionCreator();
136      ParameterizeEvaluator();
137      ParameterizeAnalyzers();
138      ParameterizeOperators();
139      base.OnSolutionCreatorChanged();
140    }
141    protected override void OnEvaluatorChanged() {
142      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
143      ParameterizeEvaluator();
144      ParameterizeAnalyzers();
145      ParameterizeOperators();
146      base.OnEvaluatorChanged();
147    }
148
149    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
150      ParameterizeEvaluator();
151      ParameterizeAnalyzers();
152      ParameterizeOperators();
153    }
154    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
155      ParameterizeAnalyzers();
156      ParameterizeOperators();
157    }
158    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
159      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
160      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
161      ParameterizeSolutionCreator();
162      ParameterizeEvaluator();
163      ParameterizeOperators();
164      AdjustDistanceMatrix();
165    }
166    private void Weights_RowsChanged(object sender, EventArgs e) {
167      if (Weights.Rows != Weights.Columns)
168        ((IStringConvertibleMatrix)Weights).Columns = Weights.Rows;
169      else {
170        ParameterizeSolutionCreator();
171        ParameterizeEvaluator();
172        ParameterizeOperators();
173        AdjustDistanceMatrix();
174      }
175    }
176    private void Weights_ColumnsChanged(object sender, EventArgs e) {
177      if (Weights.Rows != Weights.Columns)
178        ((IStringConvertibleMatrix)Weights).Rows = Weights.Columns;
179      else {
180        ParameterizeSolutionCreator();
181        ParameterizeEvaluator();
182        ParameterizeOperators();
183        AdjustDistanceMatrix();
184      }
185    }
186    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
187      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
188      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
189      ParameterizeSolutionCreator();
190      ParameterizeEvaluator();
191      ParameterizeOperators();
192      AdjustWeightsMatrix();
193    }
194    private void Distances_RowsChanged(object sender, EventArgs e) {
195      if (Distances.Rows != Distances.Columns)
196        ((IStringConvertibleMatrix)Distances).Columns = Distances.Rows;
197      else {
198        ParameterizeSolutionCreator();
199        ParameterizeEvaluator();
200        ParameterizeOperators();
201        AdjustWeightsMatrix();
202      }
203    }
204    private void Distances_ColumnsChanged(object sender, EventArgs e) {
205      if (Distances.Rows != Distances.Columns)
206        ((IStringConvertibleMatrix)Distances).Rows = Distances.Columns;
207      else {
208        ParameterizeSolutionCreator();
209        ParameterizeEvaluator();
210        ParameterizeOperators();
211        AdjustWeightsMatrix();
212      }
213    }
214    #endregion
215
216    #region Helpers
217    [StorableHook(HookType.AfterDeserialization)]
218    private void AfterDeserializationHook() {
219      AttachEventHandlers();
220    }
221
222    private void AttachEventHandlers() {
223      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
224      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
225      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
226      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
227      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
228      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
229      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
230      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
231    }
232
233    private void InitializeOperators() {
234      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
235      Operators.Add(new BestQAPSolutionAnalyzer());
236      ParameterizeAnalyzers();
237      ParameterizeOperators();
238    }
239    private void ParameterizeSolutionCreator() {
240      if (SolutionCreator != null) {
241        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
242        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
243      }
244    }
245    private void ParameterizeEvaluator() {
246      if (Evaluator != null) {
247        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
248        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
249        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
250      }
251    }
252    private void ParameterizeAnalyzers() {
253      if (BestQAPSolutionAnalyzer != null) {
254        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
255        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
256        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
257        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
258        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
259        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
260        BestQAPSolutionAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
261        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
262      }
263    }
264    private void ParameterizeOperators() {
265      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
266        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
267        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
268      }
269      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
270        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
271      }
272      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
273        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
274      }
275      if (Operators.OfType<IMoveGenerator>().Any()) {
276        string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
277        foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
278          op.InversionMoveParameter.ActualName = inversionMove;
279        string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
280        foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
281          op.TranslocationMoveParameter.ActualName = translocationMove;
282        string swapMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationSwap2MoveOperator>().First().Swap2MoveParameter.ActualName;
283        foreach (IPermutationSwap2MoveOperator op in Operators.OfType<IPermutationSwap2MoveOperator>()) {
284          op.Swap2MoveParameter.ActualName = swapMove;
285        }
286      }
287    }
288
289    private void AdjustDistanceMatrix() {
290      if (Distances.Rows != Weights.Rows || Distances.Columns != Weights.Columns) {
291        ((IStringConvertibleMatrix)Distances).Rows = Weights.Rows;
292      }
293    }
294
295    private void AdjustWeightsMatrix() {
296      if (Weights.Rows != Distances.Rows || Weights.Columns != Distances.Columns) {
297        ((IStringConvertibleMatrix)Weights).Rows = Distances.Rows;
298      }
299    }
300    #endregion
301
302    public void ImportFileInstance(string filename) {
303      QAPLIBParser parser = new QAPLIBParser();
304      parser.Parse(filename);
305      if (parser.Error != null) throw parser.Error;
306      Distances = new DoubleMatrix(parser.Distances);
307      Weights = new DoubleMatrix(parser.Weights);
308      Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(filename) + ")";
309      Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
310      BestKnownQuality = null;
311      BestKnownSolution = null;
312      OnReset();
313    }
314
315    public void LoadEmbeddedInstance(string instance) {
316      using (Stream stream = Assembly.GetExecutingAssembly()
317        .GetManifestResourceStream(InstancePrefix + instance + ".dat")) {
318        QAPLIBParser parser = new QAPLIBParser();
319        parser.Parse(stream);
320        if (parser.Error != null) throw parser.Error;
321        Distances = new DoubleMatrix(parser.Distances);
322        Weights = new DoubleMatrix(parser.Weights);
323        Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
324        Description = "Loaded embedded problem data of instance " + instance + ".";
325        OnReset();
326      }
327      bool solutionExists = Assembly.GetExecutingAssembly()
328          .GetManifestResourceNames()
329          .Where(x => x.EndsWith(instance + ".sln"))
330          .Any();
331      if (solutionExists) {
332        using (Stream solStream = Assembly.GetExecutingAssembly()
333          .GetManifestResourceStream(InstancePrefix + instance + ".sln")) {
334          QAPLIBSolutionParser solParser = new QAPLIBSolutionParser();
335          solParser.Parse(solStream, true); // most sln's seem to be of the type index = "facility" => value = "location"
336          if (solParser.Error != null) throw solParser.Error;
337          if (!solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, Distances))) {
338            solStream.Seek(0, SeekOrigin.Begin);
339            solParser.Reset();
340            solParser.Parse(solStream, false); // some sln's seem to be of the type index = "location" => value = "facility"
341            if (solParser.Error != null) throw solParser.Error;
342            if (solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, Distances))) {
343              BestKnownQuality = new DoubleValue(solParser.Quality);
344              BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
345            } else {
346              BestKnownQuality = new DoubleValue(solParser.Quality);
347              BestKnownSolution = null;
348            }
349          } else {
350            BestKnownQuality = new DoubleValue(solParser.Quality);
351            BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
352          }
353        }
354      } else {
355        BestKnownQuality = null;
356        BestKnownSolution = null;
357      }
358    }
359  }
360}
Note: See TracBrowser for help on using the repository browser.