Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12011 was 11300, checked in by pfleck, 10 years ago

#2232
Introduced ILocalImprovementAlgorithmOperator to separate single operators for local improvement and operator graphs/algorithms for local improvement.
This way the ILocalImprovementOperator does not have to specify a problem type and does not store a problem any more.

The LocalSearchImprovementOperator and SimulatedAnnealingImprovementOperator implement the new ILocalImprovementAlgorithmOperator as they represent an operator graph for local improvement.
The QAP and VRP local improvement operators implement the ILocalImprovementOperator which does not store a problem anymore.

File size: 24.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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", "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("Problems")]
39  [StorableClass]
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.