source: branches/ProblemRefactoring/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 13396

Last change on this file since 13396 was 13396, checked in by abeham, 4 years ago

#2521:

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