Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 17218 was 17180, checked in by swagner, 5 years ago

#2875: Removed years in copyrights

File size: 25.3 KB
RevLine 
[5558]1#region License Information
2/* HeuristicLab
[17180]3 * Copyright (C) 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;
[15069]26using HeuristicLab.Analysis;
[5558]27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.PermutationEncoding;
31using HeuristicLab.Optimization;
[15069]32using HeuristicLab.Optimization.Operators;
[5558]33using HeuristicLab.Parameters;
[16565]34using HEAL.Attic;
[5562]35using HeuristicLab.PluginInfrastructure;
[7558]36using HeuristicLab.Problems.Instances;
[5558]37
38namespace HeuristicLab.Problems.QuadraticAssignment {
[13173]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.")]
[12504]40  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 140)]
[16565]41  [StorableType("A86B1F49-D8E6-45E4-8EFB-8F5CCA2F9DC7")]
[7558]42  public sealed class QuadraticAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<IQAPEvaluator, IPermutationCreator>, IStorableContent,
43    IProblemInstanceConsumer<QAPData>,
44    IProblemInstanceConsumer<TSPData> {
[5953]45    public string Filename { get; set; }
46
[7201]47    public static new Image StaticItemImage {
[5558]48      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
49    }
50
51    #region Parameter Properties
[6525]52    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
53      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
[6342]54    }
[5641]55    public IValueParameter<Permutation> BestKnownSolutionParameter {
56      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
[5558]57    }
[5641]58    public IValueParameter<DoubleMatrix> WeightsParameter {
59      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
[5558]60    }
[5838]61    public IValueParameter<DoubleMatrix> DistancesParameter {
62      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
[5558]63    }
[7877]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    }
[5558]70    #endregion
71
72    #region Properties
[6525]73    public ItemSet<Permutation> BestKnownSolutions {
[6342]74      get { return BestKnownSolutionsParameter.Value; }
75      set { BestKnownSolutionsParameter.Value = value; }
76    }
[5558]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    }
[5838]85    public DoubleMatrix Distances {
86      get { return DistancesParameter.Value; }
87      set { DistancesParameter.Value = value; }
[5558]88    }
[7877]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    }
[5563]97
[5583]98    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
99      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
100    }
[6342]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    }
[5558]109    #endregion
110
111    [StorableConstructor]
[16565]112    private QuadraticAssignmentProblem(StorableConstructorFlag _) : base(_) { }
[5562]113    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
[5558]114      : base(original, cloner) {
[7351]115      RegisterEventHandlers();
[5558]116    }
117    public QuadraticAssignmentProblem()
[5931]118      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
[6525]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));
[5648]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));
[5558]121      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
[5838]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)));
[7877]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."));
[5558]125
[6939]126      Maximization.Value = false;
127      MaximizationParameter.Hidden = true;
[5563]128
[7877]129      WeightsParameter.GetsCollected = false;
[5558]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
[7877]138      DistancesParameter.GetsCollected = false;
[5838]139      Distances = new DoubleMatrix(new double[,] {
[5558]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
[5931]147      SolutionCreator.PermutationParameter.ActualName = "Assignment";
148      ParameterizeSolutionCreator();
149      ParameterizeEvaluator();
[5558]150
151      InitializeOperators();
[7351]152      RegisterEventHandlers();
[5558]153    }
154
155    public override IDeepCloneable Clone(Cloner cloner) {
156      return new QuadraticAssignmentProblem(this, cloner);
157    }
158
[6342]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")) {
[6525]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;
[6540]167        Parameters.Remove("BestKnownSolutions");
[6571]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)));
[6342]169      }
170      if (Parameters.ContainsKey("DistanceMatrix")) {
[6525]171        DoubleMatrix d = ((ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]).Value;
[6342]172        Parameters.Remove("DistanceMatrix");
[6525]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));
[6342]174      }
[7877]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."));
[8910]181        AverageQuality = new DoubleValue(ComputeAverageQuality());
[7877]182      }
183      #endregion
[7351]184      RegisterEventHandlers();
[6342]185    }
186
[5558]187    #region Events
[5562]188    protected override void OnSolutionCreatorChanged() {
189      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
190      ParameterizeSolutionCreator();
191      ParameterizeEvaluator();
[5583]192      ParameterizeAnalyzers();
[5562]193      ParameterizeOperators();
194      base.OnSolutionCreatorChanged();
[5558]195    }
[5562]196    protected override void OnEvaluatorChanged() {
[5583]197      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
[5562]198      ParameterizeEvaluator();
[5583]199      ParameterizeAnalyzers();
[5562]200      ParameterizeOperators();
201      base.OnEvaluatorChanged();
[5558]202    }
[5562]203
204    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
205      ParameterizeEvaluator();
[5583]206      ParameterizeAnalyzers();
[5562]207      ParameterizeOperators();
[5558]208    }
[5583]209    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
210      ParameterizeAnalyzers();
211      ParameterizeOperators();
212    }
[5562]213    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
214      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
[5855]215      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
[7877]216      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
[5562]217      ParameterizeSolutionCreator();
218      ParameterizeEvaluator();
219      ParameterizeOperators();
[5855]220      AdjustDistanceMatrix();
[5558]221    }
[5562]222    private void Weights_RowsChanged(object sender, EventArgs e) {
[5855]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    }
[7877]242    private void Weights_ToStringChanged(object sender, EventArgs e) {
243      UpdateParameterValues();
244    }
[5855]245    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
246      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
247      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
[7877]248      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
[5562]249      ParameterizeSolutionCreator();
250      ParameterizeEvaluator();
251      ParameterizeOperators();
[5855]252      AdjustWeightsMatrix();
[5562]253    }
[5855]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    }
[7877]274    private void Distances_ToStringChanged(object sender, EventArgs e) {
275      UpdateParameterValues();
276    }
[5558]277    #endregion
278
[7351]279    private void RegisterEventHandlers() {
[5598]280      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
281      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
[5562]282      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
283      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
[5855]284      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
[7877]285      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
[5855]286      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
287      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
288      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
[7877]289      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
[5558]290    }
291
[7877]292    #region Helpers
[5558]293    private void InitializeOperators() {
[7626]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>()));
[6088]301      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
302      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
[5583]303      Operators.Add(new BestQAPSolutionAnalyzer());
[6342]304      Operators.Add(new QAPAlleleFrequencyAnalyzer());
[11300]305
306      Operators.Add(new QAPExhaustiveInsertionLocalImprovement());
307      Operators.Add(new QAPExhaustiveInversionLocalImprovement());
308      Operators.Add(new QAPStochasticScrambleLocalImprovement());
[6342]309      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
[11300]310
[15069]311      Operators.Add(new HammingSimilarityCalculator());
[9029]312      Operators.Add(new QAPSimilarityCalculator());
[15069]313      Operators.Add(new QualitySimilarityCalculator());
314      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
315
[5583]316      ParameterizeAnalyzers();
[5563]317      ParameterizeOperators();
[5558]318    }
319    private void ParameterizeSolutionCreator() {
[5563]320      if (SolutionCreator != null) {
321        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
322        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
323      }
[5558]324    }
325    private void ParameterizeEvaluator() {
[5563]326      if (Evaluator != null) {
327        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
[5838]328        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
[5563]329        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
330      }
[5558]331    }
[5583]332    private void ParameterizeAnalyzers() {
333      if (BestQAPSolutionAnalyzer != null) {
334        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
[5838]335        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
[5583]336        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
337        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
338        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
339        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
[6342]340        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
[5583]341        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
342      }
[6342]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      }
[5583]358    }
[5562]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      }
[5563]370      if (Operators.OfType<IMoveGenerator>().Any()) {
[7768]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;
[5785]375        }
[7768]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        }
[5563]387      }
[6042]388      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
389        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
[6342]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      }
[9029]399
[15069]400      foreach (var similarityCalculator in Operators.OfType<ISolutionSimilarityCalculator>()) {
[9029]401        similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
402        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
[15069]403        var qapsimcalc = similarityCalculator as QAPSimilarityCalculator;
404        if (qapsimcalc != null) {
405          qapsimcalc.Weights = Weights;
406          qapsimcalc.Distances = Distances;
407        }
[9029]408      }
[5562]409    }
[5598]410
[5855]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    }
[7877]422
423    private void UpdateParameterValues() {
[8910]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());
[7877]435    }
[8910]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    }
[5558]453    #endregion
[5562]454
[7558]455    public void Load(QAPData data) {
456      var weights = new DoubleMatrix(data.Weights);
457      var distances = new DoubleMatrix(data.Distances);
[7641]458      Name = data.Name;
459      Description = data.Description;
[7558]460      Load(weights, distances);
[8553]461      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
[7558]462      EvaluateAndLoadAssignment(data.BestKnownAssignment);
[5562]463      OnReset();
464    }
[5563]465
[7558]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());
[7641]473      Name = data.Name;
474      Description = data.Description;
[7558]475      Load(weights, distances);
[8553]476      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
[7558]477      EvaluateAndLoadAssignment(data.BestKnownTour);
[6891]478      OnReset();
[5563]479    }
[6952]480
[7558]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!");
[6952]492
[7558]493      Weights = weights;
494      Distances = distances;
[6952]495
[7558]496      BestKnownQuality = null;
497      BestKnownSolution = null;
498      BestKnownSolutions = null;
[7877]499      UpdateParameterValues();
[7558]500    }
[6952]501
[7558]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());
[6952]510    }
[5558]511  }
512}
Note: See TracBrowser for help on using the repository browser.