Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2645_ContextAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 15904

Last change on this file since 15904 was 15583, checked in by swagner, 7 years ago

#2640: Updated year of copyrights in license headers
File size: 25.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Optimization.Operators;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
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  [StorableClass]
42  public sealed class QuadraticAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<IQAPEvaluator, IPermutationCreator>, IStorableContent,
43    IProblemInstanceConsumer<QAPData>,
44    IProblemInstanceConsumer<TSPData> {
45    public string Filename { get; set; }
46
47    public static new Image StaticItemImage {
48      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
49    }
50
51    #region Parameter Properties
52    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
53      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
54    }
55    public IValueParameter<Permutation> BestKnownSolutionParameter {
56      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
57    }
58    public IValueParameter<DoubleMatrix> WeightsParameter {
59      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
60    }
61    public IValueParameter<DoubleMatrix> DistancesParameter {
62      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
63    }
64    public IValueParameter<DoubleValue> LowerBoundParameter {
65      get { return (IValueParameter<DoubleValue>)Parameters["LowerBound"]; }
66    }
67    public IValueParameter<DoubleValue> AverageQualityParameter {
68      get { return (IValueParameter<DoubleValue>)Parameters["AverageQuality"]; }
69    }
70    #endregion
71
72    #region Properties
73    public ItemSet<Permutation> BestKnownSolutions {
74      get { return BestKnownSolutionsParameter.Value; }
75      set { BestKnownSolutionsParameter.Value = value; }
76    }
77    public Permutation BestKnownSolution {
78      get { return BestKnownSolutionParameter.Value; }
79      set { BestKnownSolutionParameter.Value = value; }
80    }
81    public DoubleMatrix Weights {
82      get { return WeightsParameter.Value; }
83      set { WeightsParameter.Value = value; }
84    }
85    public DoubleMatrix Distances {
86      get { return DistancesParameter.Value; }
87      set { DistancesParameter.Value = value; }
88    }
89    public DoubleValue LowerBound {
90      get { return LowerBoundParameter.Value; }
91      set { LowerBoundParameter.Value = value; }
92    }
93    public DoubleValue AverageQuality {
94      get { return AverageQualityParameter.Value; }
95      set { AverageQualityParameter.Value = value; }
96    }
97
98    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
99      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
100    }
101
102    private QAPAlleleFrequencyAnalyzer QAPAlleleFrequencyAnalyzer {
103      get { return Operators.OfType<QAPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
104    }
105
106    private QAPPopulationDiversityAnalyzer QAPPopulationDiversityAnalyzer {
107      get { return Operators.OfType<QAPPopulationDiversityAnalyzer>().FirstOrDefault(); }
108    }
109    #endregion
110
111    [StorableConstructor]
112    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
113    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
114      : base(original, cloner) {
115      RegisterEventHandlers();
116    }
117    public QuadraticAssignmentProblem()
118      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
119      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));
120      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));
121      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
122      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)));
123      Parameters.Add(new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
124      Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
125
126      Maximization.Value = false;
127      MaximizationParameter.Hidden = true;
128
129      WeightsParameter.GetsCollected = false;
130      Weights = new DoubleMatrix(new double[,] {
131        { 0, 1, 0, 0, 1 },
132        { 1, 0, 1, 0, 0 },
133        { 0, 1, 0, 1, 0 },
134        { 0, 0, 1, 0, 1 },
135        { 1, 0, 0, 1, 0 }
136      });
137
138      DistancesParameter.GetsCollected = false;
139      Distances = new DoubleMatrix(new double[,] {
140        {   0, 360, 582, 582, 360 },
141        { 360,   0, 360, 582, 582 },
142        { 582, 360,   0, 360, 582 },
143        { 582, 582, 360,   0, 360 },
144        { 360, 582, 582, 360,   0 }
145      });
146
147      SolutionCreator.PermutationParameter.ActualName = "Assignment";
148      ParameterizeSolutionCreator();
149      ParameterizeEvaluator();
150
151      InitializeOperators();
152      RegisterEventHandlers();
153    }
154
155    public override IDeepCloneable Clone(Cloner cloner) {
156      return new QuadraticAssignmentProblem(this, cloner);
157    }
158
159    [StorableHook(HookType.AfterDeserialization)]
160    private void AfterDeserialization() {
161      // BackwardsCompatibility3.3
162      #region Backwards compatible code, remove with 3.4
163      if (!Parameters.ContainsKey("BestKnownSolutions")) {
164        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));
165      } else if (Parameters["BestKnownSolutions"].GetType().Equals(typeof(OptionalValueParameter<ItemList<Permutation>>))) {
166        ItemList<Permutation> list = ((OptionalValueParameter<ItemList<Permutation>>)Parameters["BestKnownSolutions"]).Value;
167        Parameters.Remove("BestKnownSolutions");
168        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.", (list != null ? new ItemSet<Permutation>(list) : null)));
169      }
170      if (Parameters.ContainsKey("DistanceMatrix")) {
171        DoubleMatrix d = ((ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]).Value;
172        Parameters.Remove("DistanceMatrix");
173        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.", d));
174      }
175      if (!Parameters.ContainsKey("LowerBound")) {
176        Parameters.Add(new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
177        LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
178      }
179      if (!Parameters.ContainsKey("AverageQuality")) {
180        Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
181        AverageQuality = new DoubleValue(ComputeAverageQuality());
182      }
183      #endregion
184      RegisterEventHandlers();
185    }
186
187    #region Events
188    protected override void OnSolutionCreatorChanged() {
189      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
190      ParameterizeSolutionCreator();
191      ParameterizeEvaluator();
192      ParameterizeAnalyzers();
193      ParameterizeOperators();
194      base.OnSolutionCreatorChanged();
195    }
196    protected override void OnEvaluatorChanged() {
197      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
198      ParameterizeEvaluator();
199      ParameterizeAnalyzers();
200      ParameterizeOperators();
201      base.OnEvaluatorChanged();
202    }
203
204    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
205      ParameterizeEvaluator();
206      ParameterizeAnalyzers();
207      ParameterizeOperators();
208    }
209    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
210      ParameterizeAnalyzers();
211      ParameterizeOperators();
212    }
213    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
214      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
215      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
216      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
217      ParameterizeSolutionCreator();
218      ParameterizeEvaluator();
219      ParameterizeOperators();
220      AdjustDistanceMatrix();
221    }
222    private void Weights_RowsChanged(object sender, EventArgs e) {
223      if (Weights.Rows != Weights.Columns)
224        ((IStringConvertibleMatrix)Weights).Columns = Weights.Rows;
225      else {
226        ParameterizeSolutionCreator();
227        ParameterizeEvaluator();
228        ParameterizeOperators();
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        ParameterizeSolutionCreator();
237        ParameterizeEvaluator();
238        ParameterizeOperators();
239        AdjustDistanceMatrix();
240      }
241    }
242    private void Weights_ToStringChanged(object sender, EventArgs e) {
243      UpdateParameterValues();
244    }
245    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
246      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
247      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
248      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
249      ParameterizeSolutionCreator();
250      ParameterizeEvaluator();
251      ParameterizeOperators();
252      AdjustWeightsMatrix();
253    }
254    private void Distances_RowsChanged(object sender, EventArgs e) {
255      if (Distances.Rows != Distances.Columns)
256        ((IStringConvertibleMatrix)Distances).Columns = Distances.Rows;
257      else {
258        ParameterizeSolutionCreator();
259        ParameterizeEvaluator();
260        ParameterizeOperators();
261        AdjustWeightsMatrix();
262      }
263    }
264    private void Distances_ColumnsChanged(object sender, EventArgs e) {
265      if (Distances.Rows != Distances.Columns)
266        ((IStringConvertibleMatrix)Distances).Rows = Distances.Columns;
267      else {
268        ParameterizeSolutionCreator();
269        ParameterizeEvaluator();
270        ParameterizeOperators();
271        AdjustWeightsMatrix();
272      }
273    }
274    private void Distances_ToStringChanged(object sender, EventArgs e) {
275      UpdateParameterValues();
276    }
277    #endregion
278
279    private void RegisterEventHandlers() {
280      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
281      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
282      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
283      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
284      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
285      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
286      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
287      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
288      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
289      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
290    }
291
292    #region Helpers
293    private void InitializeOperators() {
294      var defaultOperators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
295        new PartiallyMatchedCrossover(),
296        new Swap2Manipulator(),
297        new ExhaustiveSwap2MoveGenerator()
298      });
299      Operators.AddRange(defaultOperators);
300      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>().Except(defaultOperators, new TypeEqualityComparer<IPermutationOperator>()));
301      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
302      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
303      Operators.Add(new BestQAPSolutionAnalyzer());
304      Operators.Add(new QAPAlleleFrequencyAnalyzer());
305
306      Operators.Add(new QAPExhaustiveInsertionLocalImprovement());
307      Operators.Add(new QAPExhaustiveInversionLocalImprovement());
308      Operators.Add(new QAPStochasticScrambleLocalImprovement());
309      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
310
311      Operators.Add(new HammingSimilarityCalculator());
312      Operators.Add(new QAPSimilarityCalculator());
313      Operators.Add(new QualitySimilarityCalculator());
314      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
315
316      ParameterizeAnalyzers();
317      ParameterizeOperators();
318    }
319    private void ParameterizeSolutionCreator() {
320      if (SolutionCreator != null) {
321        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
322        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
323      }
324    }
325    private void ParameterizeEvaluator() {
326      if (Evaluator != null) {
327        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
328        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
329        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
330      }
331    }
332    private void ParameterizeAnalyzers() {
333      if (BestQAPSolutionAnalyzer != null) {
334        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
335        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
336        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
337        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
338        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
339        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
340        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
341        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
342      }
343      if (QAPAlleleFrequencyAnalyzer != null) {
344        QAPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
345        QAPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
346        QAPAlleleFrequencyAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
347        QAPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
348        QAPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
349        QAPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
350        QAPAlleleFrequencyAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
351      }
352      if (QAPPopulationDiversityAnalyzer != null) {
353        QAPPopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
354        QAPPopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
355        QAPPopulationDiversityAnalyzer.ResultsParameter.ActualName = "Results";
356        QAPPopulationDiversityAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
357      }
358    }
359    private void ParameterizeOperators() {
360      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
361        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
362        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
363      }
364      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
365        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
366      }
367      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
368        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
369      }
370      if (Operators.OfType<IMoveGenerator>().Any()) {
371        if (Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().Any()) {
372          string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
373          foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
374            op.InversionMoveParameter.ActualName = inversionMove;
375        }
376        if (Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().Any()) {
377          string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
378          foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
379            op.TranslocationMoveParameter.ActualName = translocationMove;
380        }
381        if (Operators.OfType<IMoveGenerator>().OfType<IPermutationSwap2MoveOperator>().Any()) {
382          string swapMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationSwap2MoveOperator>().First().Swap2MoveParameter.ActualName;
383          foreach (IPermutationSwap2MoveOperator op in Operators.OfType<IPermutationSwap2MoveOperator>()) {
384            op.Swap2MoveParameter.ActualName = swapMove;
385          }
386        }
387      }
388      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
389        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
390
391      QAPExhaustiveSwap2LocalImprovement localOpt = Operators.OfType<QAPExhaustiveSwap2LocalImprovement>().SingleOrDefault();
392      if (localOpt != null) {
393        localOpt.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
394        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
395        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
396        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
397        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
398      }
399
400      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
401        similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
402        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
403        var qapsimcalc = similarityCalculator as QAPSimilarityCalculator;
404        if (qapsimcalc != null) {
405          qapsimcalc.Weights = Weights;
406          qapsimcalc.Distances = Distances;
407        }
408      }
409    }
410
411    private void AdjustDistanceMatrix() {
412      if (Distances.Rows != Weights.Rows || Distances.Columns != Weights.Columns) {
413        ((IStringConvertibleMatrix)Distances).Rows = Weights.Rows;
414      }
415    }
416
417    private void AdjustWeightsMatrix() {
418      if (Weights.Rows != Distances.Rows || Weights.Columns != Distances.Columns) {
419        ((IStringConvertibleMatrix)Weights).Rows = Distances.Rows;
420      }
421    }
422
423    private void UpdateParameterValues() {
424      Permutation lbSolution;
425      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
426      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
427      // evalute the LAP optimal solution as if it was a QAP solution
428      var lbSolutionQuality = QAPEvaluator.Apply(lbSolution, Weights, Distances);
429      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
430      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
431        BestKnownSolution = lbSolution;
432        BestKnownQuality = new DoubleValue(LowerBound.Value);
433      }
434      AverageQuality = new DoubleValue(ComputeAverageQuality());
435    }
436
437    private double ComputeAverageQuality() {
438      double rt = 0, rd = 0, wt = 0, wd = 0;
439      int n = Weights.Rows;
440      for (int i = 0; i < n; i++)
441        for (int j = 0; j < n; j++) {
442          if (i == j) {
443            rd += Distances[i, i];
444            wd += Weights[i, i];
445          } else {
446            rt += Distances[i, j];
447            wt += Weights[i, j];
448          }
449        }
450
451      return rt * wt / (n * (n - 1)) + rd * wd / n;
452    }
453    #endregion
454
455    public void Load(QAPData data) {
456      var weights = new DoubleMatrix(data.Weights);
457      var distances = new DoubleMatrix(data.Distances);
458      Name = data.Name;
459      Description = data.Description;
460      Load(weights, distances);
461      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
462      EvaluateAndLoadAssignment(data.BestKnownAssignment);
463      OnReset();
464    }
465
466    public void Load(TSPData data) {
467      if (data.Dimension > 1000)
468        throw new System.IO.InvalidDataException("Instances with more than 1000 customers are not supported by the QAP.");
469      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
470      for (int i = 0; i < data.Dimension; i++)
471        weights[i, (i + 1) % data.Dimension] = 1;
472      var distances = new DoubleMatrix(data.GetDistanceMatrix());
473      Name = data.Name;
474      Description = data.Description;
475      Load(weights, distances);
476      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
477      EvaluateAndLoadAssignment(data.BestKnownTour);
478      OnReset();
479    }
480
481    public void Load(DoubleMatrix weights, DoubleMatrix distances) {
482      if (weights == null || weights.Rows == 0)
483        throw new System.IO.InvalidDataException("The given instance does not contain weights!");
484      if (weights.Rows != weights.Columns)
485        throw new System.IO.InvalidDataException("The weights matrix is not a square matrix!");
486      if (distances == null || distances.Rows == 0)
487        throw new System.IO.InvalidDataException("The given instance does not contain distances!");
488      if (distances.Rows != distances.Columns)
489        throw new System.IO.InvalidDataException("The distances matrix is not a square matrix!");
490      if (weights.Rows != distances.Columns)
491        throw new System.IO.InvalidDataException("The weights matrix and the distance matrix are not of equal size!");
492
493      Weights = weights;
494      Distances = distances;
495
496      BestKnownQuality = null;
497      BestKnownSolution = null;
498      BestKnownSolutions = null;
499      UpdateParameterValues();
500    }
501
502    public void EvaluateAndLoadAssignment(int[] assignment) {
503      if (assignment == null || assignment.Length == 0) return;
504      var vector = new Permutation(PermutationTypes.Absolute, assignment);
505      var result = QAPEvaluator.Apply(vector, Weights, Distances);
506      BestKnownQuality = new DoubleValue(result);
507      BestKnownSolution = vector;
508      BestKnownSolutions = new ItemSet<Permutation>();
509      BestKnownSolutions.Add((Permutation)vector.Clone());
510    }
511  }
512}
Note: See TracBrowser for help on using the repository browser.