Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17382 was 17382, checked in by mkommend, 4 years ago

#2521: Refactored single-objective problems to use EvaluationResult instead of double as return type from Evaluate.

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