Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 12450

Last change on this file since 12450 was 12012, checked in by ascheibe, 10 years ago

#2212 merged r12008, r12009, r12010 back into trunk

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