Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceOverhaul/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 14711

Last change on this file since 14711 was 14711, checked in by gkronber, 7 years ago

#2520

  • renamed StorableClass -> StorableType
  • changed persistence to use GUIDs instead of type names
File size: 25.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.PermutationEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.PluginInfrastructure;
34using HeuristicLab.Problems.Instances;
35
36namespace HeuristicLab.Problems.QuadraticAssignment {
37  [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.")]
38  [Creatable(CreatableAttribute.Categories.CombinatorialProblems, Priority = 140)]
39  [StorableType("5B77ECCC-8A58-471C-82FF-AC71126E8337")]
40  public sealed class QuadraticAssignmentProblem : SingleObjectiveHeuristicOptimizationProblem<IQAPEvaluator, IPermutationCreator>, IStorableContent,
41    IProblemInstanceConsumer<QAPData>,
42    IProblemInstanceConsumer<TSPData> {
43    public string Filename { get; set; }
44
45    public static new Image StaticItemImage {
46      get { return HeuristicLab.Common.Resources.VSImageLibrary.Type; }
47    }
48
49    #region Parameter Properties
50    public IValueParameter<ItemSet<Permutation>> BestKnownSolutionsParameter {
51      get { return (IValueParameter<ItemSet<Permutation>>)Parameters["BestKnownSolutions"]; }
52    }
53    public IValueParameter<Permutation> BestKnownSolutionParameter {
54      get { return (IValueParameter<Permutation>)Parameters["BestKnownSolution"]; }
55    }
56    public IValueParameter<DoubleMatrix> WeightsParameter {
57      get { return (IValueParameter<DoubleMatrix>)Parameters["Weights"]; }
58    }
59    public IValueParameter<DoubleMatrix> DistancesParameter {
60      get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
61    }
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    }
68    #endregion
69
70    #region Properties
71    public ItemSet<Permutation> BestKnownSolutions {
72      get { return BestKnownSolutionsParameter.Value; }
73      set { BestKnownSolutionsParameter.Value = value; }
74    }
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    }
83    public DoubleMatrix Distances {
84      get { return DistancesParameter.Value; }
85      set { DistancesParameter.Value = value; }
86    }
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    }
95
96    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
97      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
98    }
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    }
107    #endregion
108
109    [StorableConstructor]
110    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
111    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
112      : base(original, cloner) {
113      RegisterEventHandlers();
114    }
115    public QuadraticAssignmentProblem()
116      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
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));
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));
119      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
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)));
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."));
123
124      Maximization.Value = false;
125      MaximizationParameter.Hidden = true;
126
127      WeightsParameter.GetsCollected = false;
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
136      DistancesParameter.GetsCollected = false;
137      Distances = new DoubleMatrix(new double[,] {
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
145      SolutionCreator.PermutationParameter.ActualName = "Assignment";
146      ParameterizeSolutionCreator();
147      ParameterizeEvaluator();
148
149      InitializeOperators();
150      RegisterEventHandlers();
151    }
152
153    public override IDeepCloneable Clone(Cloner cloner) {
154      return new QuadraticAssignmentProblem(this, cloner);
155    }
156
157    [StorableHook(HookType.AfterDeserialization)]
158    private void AfterDeserialization() {
159      // BackwardsCompatibility3.3
160      #region Backwards compatible code, remove with 3.4
161      if (!Parameters.ContainsKey("BestKnownSolutions")) {
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;
165        Parameters.Remove("BestKnownSolutions");
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)));
167      }
168      if (Parameters.ContainsKey("DistanceMatrix")) {
169        DoubleMatrix d = ((ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]).Value;
170        Parameters.Remove("DistanceMatrix");
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));
172      }
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."));
179        AverageQuality = new DoubleValue(ComputeAverageQuality());
180      }
181      #endregion
182      RegisterEventHandlers();
183    }
184
185    #region Events
186    protected override void OnSolutionCreatorChanged() {
187      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
188      ParameterizeSolutionCreator();
189      ParameterizeEvaluator();
190      ParameterizeAnalyzers();
191      ParameterizeOperators();
192      base.OnSolutionCreatorChanged();
193    }
194    protected override void OnEvaluatorChanged() {
195      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
196      ParameterizeEvaluator();
197      ParameterizeAnalyzers();
198      ParameterizeOperators();
199      base.OnEvaluatorChanged();
200    }
201
202    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
203      ParameterizeEvaluator();
204      ParameterizeAnalyzers();
205      ParameterizeOperators();
206    }
207    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
208      ParameterizeAnalyzers();
209      ParameterizeOperators();
210    }
211    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
212      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
213      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
214      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
215      ParameterizeSolutionCreator();
216      ParameterizeEvaluator();
217      ParameterizeOperators();
218      AdjustDistanceMatrix();
219    }
220    private void Weights_RowsChanged(object sender, EventArgs e) {
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    }
240    private void Weights_ToStringChanged(object sender, EventArgs e) {
241      UpdateParameterValues();
242    }
243    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
244      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
245      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
246      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
247      ParameterizeSolutionCreator();
248      ParameterizeEvaluator();
249      ParameterizeOperators();
250      AdjustWeightsMatrix();
251    }
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    }
272    private void Distances_ToStringChanged(object sender, EventArgs e) {
273      UpdateParameterValues();
274    }
275    #endregion
276
277    private void RegisterEventHandlers() {
278      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
279      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
280      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
281      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
282      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
283      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
284      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
285      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
286      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
287      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
288    }
289
290    #region Helpers
291    private void InitializeOperators() {
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>()));
299      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
300      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
301      Operators.Add(new BestQAPSolutionAnalyzer());
302      Operators.Add(new QAPAlleleFrequencyAnalyzer());
303      Operators.Add(new QAPPopulationDiversityAnalyzer());
304
305      Operators.Add(new QAPExhaustiveInsertionLocalImprovement());
306      Operators.Add(new QAPExhaustiveInversionLocalImprovement());
307      Operators.Add(new QAPStochasticScrambleLocalImprovement());
308      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
309
310      Operators.Add(new QAPSimilarityCalculator());
311      ParameterizeAnalyzers();
312      ParameterizeOperators();
313    }
314    private void ParameterizeSolutionCreator() {
315      if (SolutionCreator != null) {
316        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
317        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
318      }
319    }
320    private void ParameterizeEvaluator() {
321      if (Evaluator != null) {
322        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
323        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
324        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
325      }
326    }
327    private void ParameterizeAnalyzers() {
328      if (BestQAPSolutionAnalyzer != null) {
329        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
330        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
331        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
332        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
333        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
334        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
335        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
336        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
337      }
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      }
353    }
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      }
365      if (Operators.OfType<IMoveGenerator>().Any()) {
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;
370        }
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        }
382      }
383      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
384        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
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      }
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      }
400    }
401
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    }
413
414    private void UpdateParameterValues() {
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());
426    }
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    }
444    #endregion
445
446    public void Load(QAPData data) {
447      var weights = new DoubleMatrix(data.Weights);
448      var distances = new DoubleMatrix(data.Distances);
449      Name = data.Name;
450      Description = data.Description;
451      Load(weights, distances);
452      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
453      EvaluateAndLoadAssignment(data.BestKnownAssignment);
454      OnReset();
455    }
456
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());
464      Name = data.Name;
465      Description = data.Description;
466      Load(weights, distances);
467      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
468      EvaluateAndLoadAssignment(data.BestKnownTour);
469      OnReset();
470    }
471
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!");
483
484      Weights = weights;
485      Distances = distances;
486
487      BestKnownQuality = null;
488      BestKnownSolution = null;
489      BestKnownSolutions = null;
490      UpdateParameterValues();
491    }
492
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());
501    }
502  }
503}
Note: See TracBrowser for help on using the repository browser.