Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1663

  • Added hiding of Maximization parameter
  • Fixed AfterDeserializationHook in KnapsackProblem
  • Ported ArtificialAntProblem to use the SingleObjectiveHeuristicOptimizationProblem base class
File size: 20.9 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.Drawing;
24using System.IO;
25using System.Linq;
26using System.Reflection;
27using HeuristicLab.Collections;
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>, IStorableContent {
42    private static string InstancePrefix = "HeuristicLab.Problems.QuadraticAssignment.Data.";
43
44    public string Filename { get; set; }
45
46    public override Image ItemImage {
47      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
48    }
49
50    #region Parameter Properties
51    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
52      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
53    }
54    public IValueParameter<Permutation> BestKnownSolutionParameter {
55      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
56    }
57    public IValueParameter<DoubleMatrix> WeightsParameter {
58      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
59    }
60    public IValueParameter<DoubleMatrix> DistancesParameter {
61      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
62    }
63    #endregion
64
65    #region Properties
66    public ItemSet<Permutation> BestKnownSolutions {
67      get { return BestKnownSolutionsParameter.Value; }
68      set { BestKnownSolutionsParameter.Value = value; }
69    }
70    public Permutation BestKnownSolution {
71      get { return BestKnownSolutionParameter.Value; }
72      set { BestKnownSolutionParameter.Value = value; }
73    }
74    public DoubleMatrix Weights {
75      get { return WeightsParameter.Value; }
76      set { WeightsParameter.Value = value; }
77    }
78    public DoubleMatrix Distances {
79      get { return DistancesParameter.Value; }
80      set { DistancesParameter.Value = value; }
81    }
82
83    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
84      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
85    }
86
87    private QAPAlleleFrequencyAnalyzer QAPAlleleFrequencyAnalyzer {
88      get { return Operators.OfType<QAPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
89    }
90
91    private QAPPopulationDiversityAnalyzer QAPPopulationDiversityAnalyzer {
92      get { return Operators.OfType<QAPPopulationDiversityAnalyzer>().FirstOrDefault(); }
93    }
94
95    private ObservableList<string> instances = new ObservableList<string>();
96    public ObservableList<string> Instances {
97      get { return instances; }
98    }
99    #endregion
100
101    [StorableConstructor]
102    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
103    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
104      : base(original, cloner) {
105      instances = new ObservableList<string>(original.instances);
106      AttachEventHandlers();
107    }
108    public QuadraticAssignmentProblem()
109      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
110      Parameters.Add(new OptionalValueParameter<ItemSet<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
111      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));
112      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
113      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)));
114
115      Maximization.Value = false;
116      MaximizationParameter.Hidden = true;
117
118      Weights = new DoubleMatrix(new double[,] {
119        { 0, 1, 0, 0, 1 },
120        { 1, 0, 1, 0, 0 },
121        { 0, 1, 0, 1, 0 },
122        { 0, 0, 1, 0, 1 },
123        { 1, 0, 0, 1, 0 }
124      });
125
126      Distances = new DoubleMatrix(new double[,] {
127        {   0, 360, 582, 582, 360 },
128        { 360,   0, 360, 582, 582 },
129        { 582, 360,   0, 360, 582 },
130        { 582, 582, 360,   0, 360 },
131        { 360, 582, 582, 360,   0 }
132      });
133
134      SolutionCreator.PermutationParameter.ActualName = "Assignment";
135      ParameterizeSolutionCreator();
136      ParameterizeEvaluator();
137
138      InitializeOperators();
139      AttachEventHandlers();
140    }
141
142    public override IDeepCloneable Clone(Cloner cloner) {
143      return new QuadraticAssignmentProblem(this, cloner);
144    }
145
146    [StorableHook(HookType.AfterDeserialization)]
147    private void AfterDeserialization() {
148      // BackwardsCompatibility3.3
149      #region Backwards compatible code, remove with 3.4
150      if (!Parameters.ContainsKey("BestKnownSolutions")) {
151        Parameters.Add(new OptionalValueParameter<ItemSet<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", null));
152      } else if (Parameters["BestKnownSolutions"].GetType().Equals(typeof(OptionalValueParameter<ItemList<Permutation>>))) {
153        ItemList<Permutation> list = ((OptionalValueParameter<ItemList<Permutation>>)Parameters["BestKnownSolutions"]).Value;
154        Parameters.Remove("BestKnownSolutions");
155        Parameters.Add(new OptionalValueParameter<ItemSet<Permutation>>("BestKnownSolutions", "The list of best known solutions which is updated whenever a new better solution is found or may be the optimal solution if it is known beforehand.", (list != null ? new ItemSet<Permutation>(list) : null)));
156      }
157      if (Parameters.ContainsKey("DistanceMatrix")) {
158        DoubleMatrix d = ((ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]).Value;
159        Parameters.Remove("DistanceMatrix");
160        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.", d));
161      }
162      AttachEventHandlers();
163      #endregion
164    }
165
166    #region Events
167    protected override void OnSolutionCreatorChanged() {
168      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
169      ParameterizeSolutionCreator();
170      ParameterizeEvaluator();
171      ParameterizeAnalyzers();
172      ParameterizeOperators();
173      base.OnSolutionCreatorChanged();
174    }
175    protected override void OnEvaluatorChanged() {
176      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
177      ParameterizeEvaluator();
178      ParameterizeAnalyzers();
179      ParameterizeOperators();
180      base.OnEvaluatorChanged();
181    }
182
183    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
184      ParameterizeEvaluator();
185      ParameterizeAnalyzers();
186      ParameterizeOperators();
187    }
188    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
189      ParameterizeAnalyzers();
190      ParameterizeOperators();
191    }
192    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
193      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
194      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
195      ParameterizeSolutionCreator();
196      ParameterizeEvaluator();
197      ParameterizeOperators();
198      AdjustDistanceMatrix();
199    }
200    private void Weights_RowsChanged(object sender, EventArgs e) {
201      if (Weights.Rows != Weights.Columns)
202        ((IStringConvertibleMatrix)Weights).Columns = Weights.Rows;
203      else {
204        ParameterizeSolutionCreator();
205        ParameterizeEvaluator();
206        ParameterizeOperators();
207        AdjustDistanceMatrix();
208      }
209    }
210    private void Weights_ColumnsChanged(object sender, EventArgs e) {
211      if (Weights.Rows != Weights.Columns)
212        ((IStringConvertibleMatrix)Weights).Rows = Weights.Columns;
213      else {
214        ParameterizeSolutionCreator();
215        ParameterizeEvaluator();
216        ParameterizeOperators();
217        AdjustDistanceMatrix();
218      }
219    }
220    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
221      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
222      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
223      ParameterizeSolutionCreator();
224      ParameterizeEvaluator();
225      ParameterizeOperators();
226      AdjustWeightsMatrix();
227    }
228    private void Distances_RowsChanged(object sender, EventArgs e) {
229      if (Distances.Rows != Distances.Columns)
230        ((IStringConvertibleMatrix)Distances).Columns = Distances.Rows;
231      else {
232        ParameterizeSolutionCreator();
233        ParameterizeEvaluator();
234        ParameterizeOperators();
235        AdjustWeightsMatrix();
236      }
237    }
238    private void Distances_ColumnsChanged(object sender, EventArgs e) {
239      if (Distances.Rows != Distances.Columns)
240        ((IStringConvertibleMatrix)Distances).Rows = Distances.Columns;
241      else {
242        ParameterizeSolutionCreator();
243        ParameterizeEvaluator();
244        ParameterizeOperators();
245        AdjustWeightsMatrix();
246      }
247    }
248    #endregion
249
250    #region Helpers
251    private void AttachEventHandlers() {
252      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
253      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
254      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
255      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
256      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
257      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
258      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
259      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
260    }
261
262    private void InitializeOperators() {
263      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>());
264      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
265      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
266      Operators.Add(new BestQAPSolutionAnalyzer());
267      Operators.Add(new QAPAlleleFrequencyAnalyzer());
268      Operators.Add(new QAPPopulationDiversityAnalyzer());
269      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
270      ParameterizeAnalyzers();
271      ParameterizeOperators();
272    }
273    private void ParameterizeSolutionCreator() {
274      if (SolutionCreator != null) {
275        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
276        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
277      }
278    }
279    private void ParameterizeEvaluator() {
280      if (Evaluator != null) {
281        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
282        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
283        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
284      }
285    }
286    private void ParameterizeAnalyzers() {
287      if (BestQAPSolutionAnalyzer != null) {
288        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
289        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
290        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
291        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
292        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
293        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
294        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
295        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
296      }
297      if (QAPAlleleFrequencyAnalyzer != null) {
298        QAPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
299        QAPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
300        QAPAlleleFrequencyAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
301        QAPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
302        QAPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
303        QAPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
304        QAPAlleleFrequencyAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
305      }
306      if (QAPPopulationDiversityAnalyzer != null) {
307        QAPPopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
308        QAPPopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
309        QAPPopulationDiversityAnalyzer.ResultsParameter.ActualName = "Results";
310        QAPPopulationDiversityAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
311      }
312    }
313    private void ParameterizeOperators() {
314      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
315        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
316        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
317      }
318      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
319        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
320      }
321      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
322        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
323      }
324      if (Operators.OfType<IMoveGenerator>().Any()) {
325        string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
326        foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
327          op.InversionMoveParameter.ActualName = inversionMove;
328        string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
329        foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
330          op.TranslocationMoveParameter.ActualName = translocationMove;
331        string swapMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationSwap2MoveOperator>().First().Swap2MoveParameter.ActualName;
332        foreach (IPermutationSwap2MoveOperator op in Operators.OfType<IPermutationSwap2MoveOperator>()) {
333          op.Swap2MoveParameter.ActualName = swapMove;
334        }
335      }
336      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
337        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
338
339      QAPExhaustiveSwap2LocalImprovement localOpt = Operators.OfType<QAPExhaustiveSwap2LocalImprovement>().SingleOrDefault();
340      if (localOpt != null) {
341        localOpt.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
342        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
343        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
344        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
345        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
346      }
347    }
348
349    private void AdjustDistanceMatrix() {
350      if (Distances.Rows != Weights.Rows || Distances.Columns != Weights.Columns) {
351        ((IStringConvertibleMatrix)Distances).Rows = Weights.Rows;
352      }
353    }
354
355    private void AdjustWeightsMatrix() {
356      if (Weights.Rows != Distances.Rows || Weights.Columns != Distances.Columns) {
357        ((IStringConvertibleMatrix)Weights).Rows = Distances.Rows;
358      }
359    }
360    #endregion
361
362    public void LoadInstanceFromFile(string filename) {
363      QAPLIBParser parser = new QAPLIBParser();
364      parser.Parse(filename);
365      if (parser.Error != null) throw parser.Error;
366      Distances = new DoubleMatrix(parser.Distances);
367      Weights = new DoubleMatrix(parser.Weights);
368      Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(filename) + ")";
369      Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
370      BestKnownQuality = null;
371      BestKnownSolution = null;
372      BestKnownSolutions = null;
373      OnReset();
374    }
375
376    public void LoadInstanceFromFile(string datFilename, string slnFilename) {
377      QAPLIBParser datParser = new QAPLIBParser();
378      datParser.Parse(datFilename);
379      if (datParser.Error != null) throw datParser.Error;
380      Distances = new DoubleMatrix(datParser.Distances);
381      Weights = new DoubleMatrix(datParser.Weights);
382      Name = "Quadratic Assignment Problem (imported from " + Path.GetFileNameWithoutExtension(datFilename) + ")";
383      Description = "Imported problem data using QAPLIBParser " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().FirstOrDefault().Version + ".";
384
385      QAPLIBSolutionParser slnParser = new QAPLIBSolutionParser();
386      slnParser.Parse(slnFilename, true);
387      if (slnParser.Error != null) throw slnParser.Error;
388
389      BestKnownQuality = new DoubleValue(slnParser.Quality);
390      BestKnownSolution = new Permutation(PermutationTypes.Absolute, slnParser.Assignment);
391      BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
392      BestKnownSolutions.Add((Permutation)BestKnownSolution.Clone());
393
394      if (!BestKnownQuality.Value.IsAlmost(QAPEvaluator.Apply(BestKnownSolution, Weights, Distances))) {
395        // the solution doesn't result in the given quality, maybe indices and values are inverted
396        // try parsing again, this time inverting them
397        slnParser.Reset();
398        slnParser.Parse(slnFilename, false);
399        if (slnParser.Error != null) throw slnParser.Error;
400
401        BestKnownQuality = new DoubleValue(slnParser.Quality);
402        BestKnownSolution = new Permutation(PermutationTypes.Absolute, slnParser.Assignment);
403        BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
404        BestKnownSolutions.Add((Permutation)BestKnownSolution.Clone());
405
406        if (!BestKnownQuality.Value.IsAlmost(QAPEvaluator.Apply(BestKnownSolution, Weights, Distances))) {
407          // if the solution still doesn't result in the given quality, remove it and only take the quality
408          BestKnownSolution = null;
409          BestKnownSolutions = new ItemSet<Permutation>(new PermutationEqualityComparer());
410        }
411      }
412      OnReset();
413    }
414  }
415}
Note: See TracBrowser for help on using the repository browser.