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

Last change on this file since 17232 was 17232, checked in by abeham, 2 years ago

#2521: Improve speed of Evaluate() in QuadraticAssignmentProblem

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