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

Last change on this file since 17544 was 17544, checked in by abeham, 7 weeks ago

#2521: worked on refactoring, worked a lot on binary encoding / problems

File size: 17.2 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    }
105    public QuadraticAssignmentProblem()
106      : base(new PermutationEncoding("Assignment") { Length = 5 }) {
107      Maximization = false;
108      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));
109      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));
110      Parameters.Add(WeightsParameter = new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities."));
111      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."));
112      Parameters.Add(LowerBoundParameter = new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
113      Parameters.Add(AverageQualityParameter = new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
114
115      WeightsParameter.GetsCollected = false;
116      Weights = new DoubleMatrix(new double[,] {
117        { 0, 1, 0, 0, 1 },
118        { 1, 0, 1, 0, 0 },
119        { 0, 1, 0, 1, 0 },
120        { 0, 0, 1, 0, 1 },
121        { 1, 0, 0, 1, 0 }
122      }, @readonly: true);
123
124      DistancesParameter.GetsCollected = false;
125      Distances = new DoubleMatrix(new double[,] {
126        {   0, 360, 582, 582, 360 },
127        { 360,   0, 360, 582, 582 },
128        { 582, 360,   0, 360, 582 },
129        { 582, 582, 360,   0, 360 },
130        { 360, 582, 582, 360,   0 }
131      }, @readonly: true);
132
133      InitializeOperators();
134    }
135
136    public override ISingleObjectiveEvaluationResult Evaluate(Permutation assignment, IRandom random, CancellationToken cancellationToken) {
137      var quality = Evaluate(assignment, cancellationToken);
138      return new SingleObjectiveEvaluationResult(quality);
139    }
140
141    public double Evaluate(Permutation assignment, CancellationToken cancellationToken) {
142      double quality = 0;
143      for (int i = 0; i < assignment.Length; i++) {
144        for (int j = 0; j < assignment.Length; j++) {
145          quality += Weights[i, j] * Distances[assignment[i], assignment[j]];
146        }
147      }
148      return quality;
149    }
150
151    public override IDeepCloneable Clone(Cloner cloner) {
152      return new QuadraticAssignmentProblem(this, cloner);
153    }
154
155    #region Events
156    protected override void OnEncodingChanged() {
157      base.OnEncodingChanged();
158      Dimension = Weights.Rows;
159      Parameterize();
160    }
161    protected override void OnEvaluatorChanged() {
162      Evaluator.QualityParameter.ActualNameChanged += Evaluator_QualityParameter_ActualNameChanged;
163      Parameterize();
164      base.OnEvaluatorChanged();
165    }
166    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
167      Parameterize();
168    }
169    #endregion
170
171    protected override void DimensionOnChanged() {
172      base.DimensionOnChanged();
173      if (Dimension != Weights.Rows) Dimension = Weights.Rows;
174    }
175
176    #region Helpers
177    private void InitializeOperators() {
178      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
179      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPLocalImprovementOperator>());
180      Operators.Add(new BestQAPSolutionAnalyzer());
181      Operators.Add(new QAPAlleleFrequencyAnalyzer());
182
183      Operators.Add(new QAPSimilarityCalculator());
184      Parameterize();
185    }
186    private void Parameterize() {
187      var operators = new List<IItem>();
188      if (BestQAPSolutionAnalyzer != null) {
189        operators.Add(BestQAPSolutionAnalyzer);
190        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
191        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
192        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
193        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
194        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
195        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
196      }
197      if (QAPAlleleFrequencyAnalyzer != null) {
198        operators.Add(QAPAlleleFrequencyAnalyzer);
199        QAPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
200        QAPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
201        QAPAlleleFrequencyAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
202        QAPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
203        QAPAlleleFrequencyAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
204      }
205      foreach (var localOpt in Operators.OfType<IQAPLocalImprovementOperator>()) {
206        operators.Add(localOpt);
207        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
208        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
209        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
210        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
211      }
212
213      foreach (var moveOp in Operators.OfType<IQAPMoveEvaluator>()) {
214        operators.Add(moveOp);
215        moveOp.DistancesParameter.ActualName = DistancesParameter.Name;
216        moveOp.WeightsParameter.ActualName = WeightsParameter.Name;
217        moveOp.QualityParameter.ActualName = Evaluator.QualityParameter.Name;
218
219        var swaMoveOp = moveOp as QAPSwap2MoveEvaluator;
220        if (swaMoveOp != null) {
221          var moveQualityName = swaMoveOp.MoveQualityParameter.ActualName;
222          foreach (var o in Encoding.Operators.OfType<IPermutationSwap2MoveQualityOperator>())
223            o.MoveQualityParameter.ActualName = moveQualityName;
224        }
225        var invMoveOp = moveOp as QAPInversionMoveEvaluator;
226        if (invMoveOp != null) {
227          var moveQualityName = invMoveOp.MoveQualityParameter.ActualName;
228          foreach (var o in Encoding.Operators.OfType<IPermutationInversionMoveQualityOperator>())
229            o.MoveQualityParameter.ActualName = moveQualityName;
230        }
231        var traMoveOp = moveOp as QAPTranslocationMoveEvaluator;
232        if (traMoveOp != null) {
233          var moveQualityName = traMoveOp.MoveQualityParameter.ActualName;
234          foreach (var o in Encoding.Operators.OfType<IPermutationTranslocationMoveQualityOperator>())
235            o.MoveQualityParameter.ActualName = moveQualityName;
236        }
237        var scrMoveOp = moveOp as QAPScrambleMoveEvaluator;
238        if (scrMoveOp != null) {
239          var moveQualityName = scrMoveOp.MoveQualityParameter.ActualName;
240          foreach (var o in Encoding.Operators.OfType<IPermutationScrambleMoveQualityOperator>())
241            o.MoveQualityParameter.ActualName = moveQualityName;
242        }
243      }
244      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
245        operators.Add(similarityCalculator);
246        similarityCalculator.SolutionVariableName = Encoding.Name;
247        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
248        var qapsimcalc = similarityCalculator as QAPSimilarityCalculator;
249        if (qapsimcalc != null) {
250          qapsimcalc.Weights = Weights;
251          qapsimcalc.Distances = Distances;
252        }
253      }
254
255      if (operators.Count > 0) Encoding.ConfigureOperators(operators);
256    }
257
258    private void UpdateParameterValues() {
259      Permutation lbSolution;
260      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
261      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
262      // evaluate the LAP optimal solution as if it was a QAP solution
263      var lbSolutionQuality = Evaluate(lbSolution, CancellationToken.None);
264      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
265      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
266        BestKnownSolution = lbSolution;
267        BestKnownQuality = LowerBound.Value;
268      }
269      AverageQuality = new DoubleValue(ComputeAverageQuality());
270    }
271
272    private double ComputeAverageQuality() {
273      double rt = 0, rd = 0, wt = 0, wd = 0;
274      int n = Weights.Rows;
275      for (int i = 0; i < n; i++)
276        for (int j = 0; j < n; j++) {
277          if (i == j) {
278            rd += Distances[i, i];
279            wd += Weights[i, i];
280          } else {
281            rt += Distances[i, j];
282            wt += Weights[i, j];
283          }
284        }
285
286      return rt * wt / (n * (n - 1)) + rd * wd / n;
287    }
288    #endregion
289
290    public void Load(QAPData data) {
291      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) + "!");
292      var weights = new DoubleMatrix(data.Weights, @readonly: true);
293      var distances = new DoubleMatrix(data.Distances, @readonly: true);
294      Name = data.Name;
295      Description = data.Description;
296      Load(weights, distances);
297      if (data.BestKnownQuality.HasValue) BestKnownQuality = data.BestKnownQuality.Value;
298      EvaluateAndLoadAssignment(data.BestKnownAssignment);
299      OnReset();
300    }
301
302    public void Load(TSPData data) {
303      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) + "!");
304      var w = new double[data.Dimension, data.Dimension];
305      for (int i = 0; i < data.Dimension; i++)
306        w[i, (i + 1) % data.Dimension] = 1;
307      var weights = new DoubleMatrix(w, @readonly: true);
308      var distances = new DoubleMatrix(data.GetDistanceMatrix(), @readonly: true);
309      Name = data.Name;
310      Description = data.Description;
311      Load(weights, distances);
312      if (data.BestKnownQuality.HasValue) BestKnownQuality = data.BestKnownQuality.Value;
313      EvaluateAndLoadAssignment(data.BestKnownTour);
314      OnReset();
315    }
316
317    public void Load(DoubleMatrix weights, DoubleMatrix distances) {
318      if (weights == null || weights.Rows == 0)
319        throw new System.IO.InvalidDataException("The given instance does not contain weights!");
320      if (weights.Rows != weights.Columns)
321        throw new System.IO.InvalidDataException("The weights matrix is not a square matrix!");
322      if (distances == null || distances.Rows == 0)
323        throw new System.IO.InvalidDataException("The given instance does not contain distances!");
324      if (distances.Rows != distances.Columns)
325        throw new System.IO.InvalidDataException("The distances matrix is not a square matrix!");
326      if (weights.Rows != distances.Columns)
327        throw new System.IO.InvalidDataException("The weights matrix and the distance matrix are not of equal size!");
328
329      Weights = weights;
330      Distances = distances;
331      Dimension = weights.Rows;
332
333      BestKnownQualityParameter.Value = null;
334      BestKnownSolution = null;
335      BestKnownSolutions = null;
336      UpdateParameterValues();
337    }
338
339    public void EvaluateAndLoadAssignment(int[] assignment) {
340      if (assignment == null || assignment.Length == 0) return;
341      var vector = new Permutation(PermutationTypes.Absolute, assignment);
342      var result = Evaluate(vector, CancellationToken.None);
343      BestKnownQuality = result;
344      BestKnownSolution = vector;
345      BestKnownSolutions = new ItemSet<Permutation> { (Permutation)vector.Clone() };
346    }
347
348    public QAPData Export() {
349      return new QAPData() {
350        Name = Name,
351        Description = Description,
352        Dimension = Weights.Rows,
353        Weights = Weights.CloneAsMatrix(),
354        Distances = Distances.CloneAsMatrix(),
355        BestKnownAssignment = BestKnownSolution?.ToArray(),
356        BestKnownQuality = !double.IsNaN(BestKnownQuality) ? BestKnownQuality : (double?)null
357      };
358    }
359  }
360}
Note: See TracBrowser for help on using the repository browser.