source: branches/2521_ProblemRefactoring/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 17226

Last change on this file since 17226 was 17226, checked in by mkommend, 2 years ago

#2521: Merged trunk changes into problem refactoring branch.

File size: 19.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 HEAL.Attic;
27using HeuristicLab.Analysis;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Data;
31using HeuristicLab.Encodings.PermutationEncoding;
32using HeuristicLab.Optimization;
33using HeuristicLab.Optimization.Operators;
34using HeuristicLab.Parameters;
35using HeuristicLab.PluginInfrastructure;
36using HeuristicLab.Problems.Instances;
37
38namespace HeuristicLab.Problems.QuadraticAssignment {
39  [Item("Quadratic Assignment Problem (QAP)", "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.")]
40  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 140)]
41  [StorableType("A86B1F49-D8E6-45E4-8EFB-8F5CCA2F9DC7")]
42  public sealed class QuadraticAssignmentProblem : PermutationProblem,
43    IProblemInstanceConsumer<QAPData>,
44    IProblemInstanceConsumer<TSPData> {
45
46    public static new Image StaticItemImage {
47      get { return Common.Resources.VSImageLibrary.Type; }
48    }
49
50    public override bool Maximization { get { return false; } }
51
52    #region Parameter Properties
53    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
54      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
55    }
56    public IValueParameter<Permutation> BestKnownSolutionParameter {
57      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
58    }
59    public IValueParameter<DoubleMatrix> WeightsParameter {
60      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
61    }
62    public IValueParameter<DoubleMatrix> DistancesParameter {
63      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
64    }
65    public IValueParameter<DoubleValue> LowerBoundParameter {
66      get { return (IValueParameter<DoubleValue>)Parameters["LowerBound"]; }
67    }
68    public IValueParameter<DoubleValue> AverageQualityParameter {
69      get { return (IValueParameter<DoubleValue>)Parameters["AverageQuality"]; }
70    }
71    #endregion
72
73    #region Properties
74    public ItemSet<Permutation> BestKnownSolutions {
75      get { return BestKnownSolutionsParameter.Value; }
76      set { BestKnownSolutionsParameter.Value = value; }
77    }
78    public Permutation BestKnownSolution {
79      get { return BestKnownSolutionParameter.Value; }
80      set { BestKnownSolutionParameter.Value = value; }
81    }
82    public DoubleMatrix Weights {
83      get { return WeightsParameter.Value; }
84      set { WeightsParameter.Value = value; }
85    }
86    public DoubleMatrix Distances {
87      get { return DistancesParameter.Value; }
88      set { DistancesParameter.Value = value; }
89    }
90    public DoubleValue LowerBound {
91      get { return LowerBoundParameter.Value; }
92      set { LowerBoundParameter.Value = value; }
93    }
94    public DoubleValue AverageQuality {
95      get { return AverageQualityParameter.Value; }
96      set { AverageQualityParameter.Value = value; }
97    }
98
99    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
100      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
101    }
102
103    private QAPAlleleFrequencyAnalyzer QAPAlleleFrequencyAnalyzer {
104      get { return Operators.OfType<QAPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
105    }
106
107    private QAPPopulationDiversityAnalyzer QAPPopulationDiversityAnalyzer {
108      get { return Operators.OfType<QAPPopulationDiversityAnalyzer>().FirstOrDefault(); }
109    }
110    #endregion
111
112    [StorableConstructor]
113    private QuadraticAssignmentProblem(StorableConstructorFlag _) : base(_) { }
114    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
115      : base(original, cloner) {
116      RegisterEventHandlers();
117    }
118    public QuadraticAssignmentProblem()
119      : base(new PermutationEncoding("Assignment") { Length = 5 }) {
120      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));
121      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));
122      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
123      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)));
124      Parameters.Add(new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
125      Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
126
127      WeightsParameter.GetsCollected = false;
128      Weights = new DoubleMatrix(new double[,] {
129        { 0, 1, 0, 0, 1 },
130        { 1, 0, 1, 0, 0 },
131        { 0, 1, 0, 1, 0 },
132        { 0, 0, 1, 0, 1 },
133        { 1, 0, 0, 1, 0 }
134      });
135
136      DistancesParameter.GetsCollected = false;
137      Distances = 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      InitializeOperators();
146      RegisterEventHandlers();
147    }
148
149    public override double Evaluate(Permutation assignment, IRandom random) {
150      return Evaluate(assignment);
151    }
152
153    public double Evaluate(Permutation assignment) {
154      double quality = 0;
155      for (int i = 0; i < assignment.Length; i++) {
156        for (int j = 0; j < assignment.Length; j++) {
157          quality += Weights[i, j] * Distances[assignment[i], assignment[j]];
158        }
159      }
160      return quality;
161    }
162
163    public override IDeepCloneable Clone(Cloner cloner) {
164      return new QuadraticAssignmentProblem(this, cloner);
165    }
166
167    [StorableHook(HookType.AfterDeserialization)]
168    private void AfterDeserialization() {
169      RegisterEventHandlers();
170    }
171
172    #region Events
173    //TODO check with abhem if this is necessary
174    //protected override void OnSolutionCreatorChanged() {
175    //  Parameterize();
176    //  base.OnSolutionCreatorChanged();
177    //}
178    protected override void OnEvaluatorChanged() {
179      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
180      Parameterize();
181      base.OnEvaluatorChanged();
182    }
183    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
184      Parameterize();
185    }
186    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
187      Weights.RowsChanged += Weights_RowsChanged;
188      Weights.ColumnsChanged += Weights_ColumnsChanged;
189      Weights.ToStringChanged += Weights_ToStringChanged;
190      AdjustDistanceMatrix();
191    }
192    private void Weights_RowsChanged(object sender, EventArgs e) {
193      if (Weights.Rows != Weights.Columns)
194        ((IStringConvertibleMatrix)Weights).Columns = Weights.Rows;
195      else {
196        AdjustDistanceMatrix();
197      }
198    }
199    private void Weights_ColumnsChanged(object sender, EventArgs e) {
200      if (Weights.Rows != Weights.Columns)
201        ((IStringConvertibleMatrix)Weights).Rows = Weights.Columns;
202      else {
203        AdjustDistanceMatrix();
204      }
205    }
206    private void Weights_ToStringChanged(object sender, EventArgs e) {
207      UpdateParameterValues();
208    }
209    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
210      Distances.RowsChanged += Distances_RowsChanged;
211      Distances.ColumnsChanged += Distances_ColumnsChanged;
212      Distances.ToStringChanged += Distances_ToStringChanged;
213      AdjustWeightsMatrix();
214    }
215    private void Distances_RowsChanged(object sender, EventArgs e) {
216      if (Distances.Rows != Distances.Columns)
217        ((IStringConvertibleMatrix)Distances).Columns = Distances.Rows;
218      else {
219        AdjustWeightsMatrix();
220      }
221    }
222    private void Distances_ColumnsChanged(object sender, EventArgs e) {
223      if (Distances.Rows != Distances.Columns)
224        ((IStringConvertibleMatrix)Distances).Rows = Distances.Columns;
225      else {
226        AdjustWeightsMatrix();
227      }
228    }
229    private void Distances_ToStringChanged(object sender, EventArgs e) {
230      UpdateParameterValues();
231    }
232    #endregion
233
234    private void RegisterEventHandlers() {
235      WeightsParameter.ValueChanged += WeightsParameter_ValueChanged;
236      Weights.RowsChanged += Weights_RowsChanged;
237      Weights.ColumnsChanged += Weights_ColumnsChanged;
238      Weights.ToStringChanged += Weights_ToStringChanged;
239      DistancesParameter.ValueChanged += DistancesParameter_ValueChanged;
240      Distances.RowsChanged += Distances_RowsChanged;
241      Distances.ColumnsChanged += Distances_ColumnsChanged;
242      Distances.ToStringChanged += Distances_ToStringChanged;
243    }
244
245    #region Helpers
246    private void InitializeOperators() {
247      var defaultOperators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
248        new PartiallyMatchedCrossover(),
249        new Swap2Manipulator(),
250        new ExhaustiveSwap2MoveGenerator()
251      });
252      Operators.AddRange(defaultOperators);
253      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
254      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPLocalImprovementOperator>());
255      Operators.Add(new BestQAPSolutionAnalyzer());
256      Operators.Add(new QAPAlleleFrequencyAnalyzer());
257
258      Operators.Add(new HammingSimilarityCalculator());
259      Operators.Add(new QAPSimilarityCalculator());
260      Operators.Add(new QualitySimilarityCalculator());
261      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
262      Parameterize();
263    }
264    private void Parameterize() {
265      var operators = new List<IItem>();
266      if (BestQAPSolutionAnalyzer != null) {
267        operators.Add(BestQAPSolutionAnalyzer);
268        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
269        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
270        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
271        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
272        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
273        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
274      }
275      if (QAPAlleleFrequencyAnalyzer != null) {
276        operators.Add(QAPAlleleFrequencyAnalyzer);
277        QAPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
278        QAPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
279        QAPAlleleFrequencyAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
280        QAPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
281        QAPAlleleFrequencyAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
282      }
283      if (QAPPopulationDiversityAnalyzer != null) {
284        operators.Add(QAPPopulationDiversityAnalyzer);
285        QAPPopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
286        QAPPopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
287      }
288      foreach (var localOpt in Operators.OfType<IQAPLocalImprovementOperator>()) {
289        operators.Add(localOpt);
290        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
291        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
292        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
293        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
294      }
295
296      foreach (var moveOp in Operators.OfType<IQAPMoveEvaluator>()) {
297        operators.Add(moveOp);
298        moveOp.DistancesParameter.ActualName = DistancesParameter.Name;
299        moveOp.WeightsParameter.ActualName = WeightsParameter.Name;
300        moveOp.QualityParameter.ActualName = Evaluator.QualityParameter.Name;
301
302        var swaMoveOp = moveOp as QAPSwap2MoveEvaluator;
303        if (swaMoveOp != null) {
304          var moveQualityName = swaMoveOp.MoveQualityParameter.ActualName;
305          foreach (var o in Encoding.Operators.OfType<IPermutationSwap2MoveQualityOperator>())
306            o.MoveQualityParameter.ActualName = moveQualityName;
307        }
308        var invMoveOp = moveOp as QAPInversionMoveEvaluator;
309        if (invMoveOp != null) {
310          var moveQualityName = invMoveOp.MoveQualityParameter.ActualName;
311          foreach (var o in Encoding.Operators.OfType<IPermutationInversionMoveQualityOperator>())
312            o.MoveQualityParameter.ActualName = moveQualityName;
313        }
314        var traMoveOp = moveOp as QAPTranslocationMoveEvaluator;
315        if (traMoveOp != null) {
316          var moveQualityName = traMoveOp.MoveQualityParameter.ActualName;
317          foreach (var o in Encoding.Operators.OfType<IPermutationTranslocationMoveQualityOperator>())
318            o.MoveQualityParameter.ActualName = moveQualityName;
319        }
320        var scrMoveOp = moveOp as QAPScrambleMoveEvaluator;
321        if (scrMoveOp != null) {
322          var moveQualityName = scrMoveOp.MoveQualityParameter.ActualName;
323          foreach (var o in Encoding.Operators.OfType<IPermutationScrambleMoveQualityOperator>())
324            o.MoveQualityParameter.ActualName = moveQualityName;
325        }
326      }
327      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
328        similarityCalculator.SolutionVariableName = Encoding.Name;
329        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
330        var qapsimcalc = similarityCalculator as QAPSimilarityCalculator;
331        if (qapsimcalc != null) {
332          qapsimcalc.Weights = Weights;
333          qapsimcalc.Distances = Distances;
334        }
335      }
336
337      if (operators.Count > 0) Encoding.ConfigureOperators(operators);
338    }
339
340    private void AdjustDistanceMatrix() {
341      if (Distances.Rows != Weights.Rows || Distances.Columns != Weights.Columns) {
342        ((IStringConvertibleMatrix)Distances).Rows = Weights.Rows;
343        Encoding.Length = Weights.Rows;
344      }
345    }
346
347    private void AdjustWeightsMatrix() {
348      if (Weights.Rows != Distances.Rows || Weights.Columns != Distances.Columns) {
349        ((IStringConvertibleMatrix)Weights).Rows = Distances.Rows;
350        Encoding.Length = Distances.Rows;
351      }
352    }
353
354    private void UpdateParameterValues() {
355      Permutation lbSolution;
356      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
357      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
358      // evalute the LAP optimal solution as if it was a QAP solution
359      var lbSolutionQuality = Evaluate(lbSolution);
360      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
361      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
362        BestKnownSolution = lbSolution;
363        BestKnownQuality = LowerBound.Value;
364      }
365      AverageQuality = new DoubleValue(ComputeAverageQuality());
366    }
367
368    private double ComputeAverageQuality() {
369      double rt = 0, rd = 0, wt = 0, wd = 0;
370      int n = Weights.Rows;
371      for (int i = 0; i < n; i++)
372        for (int j = 0; j < n; j++) {
373          if (i == j) {
374            rd += Distances[i, i];
375            wd += Weights[i, i];
376          } else {
377            rt += Distances[i, j];
378            wt += Weights[i, j];
379          }
380        }
381
382      return rt * wt / (n * (n - 1)) + rd * wd / n;
383    }
384    #endregion
385
386    public void Load(QAPData data) {
387      var weights = new DoubleMatrix(data.Weights);
388      var distances = new DoubleMatrix(data.Distances);
389      Name = data.Name;
390      Description = data.Description;
391      Load(weights, distances);
392      if (data.BestKnownQuality.HasValue) BestKnownQuality = data.BestKnownQuality.Value;
393      EvaluateAndLoadAssignment(data.BestKnownAssignment);
394      OnReset();
395    }
396
397    public void Load(TSPData data) {
398      if (data.Dimension > 1000)
399        throw new System.IO.InvalidDataException("Instances with more than 1000 customers are not supported by the QAP.");
400      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
401      for (int i = 0; i < data.Dimension; i++)
402        weights[i, (i + 1) % data.Dimension] = 1;
403      var distances = new DoubleMatrix(data.GetDistanceMatrix());
404      Name = data.Name;
405      Description = data.Description;
406      Load(weights, distances);
407      if (data.BestKnownQuality.HasValue) BestKnownQuality = data.BestKnownQuality.Value;
408      EvaluateAndLoadAssignment(data.BestKnownTour);
409      OnReset();
410    }
411
412    public void Load(DoubleMatrix weights, DoubleMatrix distances) {
413      if (weights == null || weights.Rows == 0)
414        throw new System.IO.InvalidDataException("The given instance does not contain weights!");
415      if (weights.Rows != weights.Columns)
416        throw new System.IO.InvalidDataException("The weights matrix is not a square matrix!");
417      if (distances == null || distances.Rows == 0)
418        throw new System.IO.InvalidDataException("The given instance does not contain distances!");
419      if (distances.Rows != distances.Columns)
420        throw new System.IO.InvalidDataException("The distances matrix is not a square matrix!");
421      if (weights.Rows != distances.Columns)
422        throw new System.IO.InvalidDataException("The weights matrix and the distance matrix are not of equal size!");
423
424      Weights = weights;
425      Distances = distances;
426      Encoding.Length = weights.Rows;
427
428      BestKnownQualityParameter.Value = null;
429      BestKnownSolution = null;
430      BestKnownSolutions = null;
431      UpdateParameterValues();
432    }
433
434    public void EvaluateAndLoadAssignment(int[] assignment) {
435      if (assignment == null || assignment.Length == 0) return;
436      var vector = new Permutation(PermutationTypes.Absolute, assignment);
437      var result = Evaluate(vector);
438      BestKnownQuality = result;
439      BestKnownSolution = vector;
440      BestKnownSolutions = new ItemSet<Permutation> { (Permutation)vector.Clone() };
441    }
442  }
443}
Note: See TracBrowser for help on using the repository browser.