Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Hive.Azure/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 7871

Last change on this file since 7871 was 7669, checked in by spimming, 13 years ago

#1680: merged changes from trunk into branch
File size: 20.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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    #endregion
63
64    #region Properties
65    public ItemSet<Permutation> BestKnownSolutions {
66      get { return BestKnownSolutionsParameter.Value; }
67      set { BestKnownSolutionsParameter.Value = value; }
68    }
69    public Permutation BestKnownSolution {
70      get { return BestKnownSolutionParameter.Value; }
71      set { BestKnownSolutionParameter.Value = value; }
72    }
73    public DoubleMatrix Weights {
74      get { return WeightsParameter.Value; }
75      set { WeightsParameter.Value = value; }
76    }
77    public DoubleMatrix Distances {
78      get { return DistancesParameter.Value; }
79      set { DistancesParameter.Value = value; }
80    }
81
82    private BestQAPSolutionAnalyzer BestQAPSolutionAnalyzer {
83      get { return Operators.OfType<BestQAPSolutionAnalyzer>().FirstOrDefault(); }
84    }
85
86    private QAPAlleleFrequencyAnalyzer QAPAlleleFrequencyAnalyzer {
87      get { return Operators.OfType<QAPAlleleFrequencyAnalyzer>().FirstOrDefault(); }
88    }
89
90    private QAPPopulationDiversityAnalyzer QAPPopulationDiversityAnalyzer {
91      get { return Operators.OfType<QAPPopulationDiversityAnalyzer>().FirstOrDefault(); }
92    }
93    #endregion
94
95    [StorableConstructor]
96    private QuadraticAssignmentProblem(bool deserializing) : base(deserializing) { }
97    private QuadraticAssignmentProblem(QuadraticAssignmentProblem original, Cloner cloner)
98      : base(original, cloner) {
99      RegisterEventHandlers();
100    }
101    public QuadraticAssignmentProblem()
102      : base(new QAPEvaluator(), new RandomPermutationCreator()) {
103      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));
104      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));
105      Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
106      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)));
107
108      Maximization.Value = false;
109      MaximizationParameter.Hidden = true;
110
111      Weights = new DoubleMatrix(new double[,] {
112        { 0, 1, 0, 0, 1 },
113        { 1, 0, 1, 0, 0 },
114        { 0, 1, 0, 1, 0 },
115        { 0, 0, 1, 0, 1 },
116        { 1, 0, 0, 1, 0 }
117      });
118
119      Distances = new DoubleMatrix(new double[,] {
120        {   0, 360, 582, 582, 360 },
121        { 360,   0, 360, 582, 582 },
122        { 582, 360,   0, 360, 582 },
123        { 582, 582, 360,   0, 360 },
124        { 360, 582, 582, 360,   0 }
125      });
126
127      SolutionCreator.PermutationParameter.ActualName = "Assignment";
128      ParameterizeSolutionCreator();
129      ParameterizeEvaluator();
130
131      InitializeOperators();
132      RegisterEventHandlers();
133    }
134
135    public override IDeepCloneable Clone(Cloner cloner) {
136      return new QuadraticAssignmentProblem(this, cloner);
137    }
138
139    [StorableHook(HookType.AfterDeserialization)]
140    private void AfterDeserialization() {
141      // BackwardsCompatibility3.3
142      #region Backwards compatible code, remove with 3.4
143      if (!Parameters.ContainsKey("BestKnownSolutions")) {
144        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));
145      } else if (Parameters["BestKnownSolutions"].GetType().Equals(typeof(OptionalValueParameter<ItemList<Permutation>>))) {
146        ItemList<Permutation> list = ((OptionalValueParameter<ItemList<Permutation>>)Parameters["BestKnownSolutions"]).Value;
147        Parameters.Remove("BestKnownSolutions");
148        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)));
149      }
150      if (Parameters.ContainsKey("DistanceMatrix")) {
151        DoubleMatrix d = ((ValueParameter<DoubleMatrix>)Parameters["DistanceMatrix"]).Value;
152        Parameters.Remove("DistanceMatrix");
153        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));
154      }
155      RegisterEventHandlers();
156      #endregion
157    }
158
159    #region Events
160    protected override void OnSolutionCreatorChanged() {
161      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
162      ParameterizeSolutionCreator();
163      ParameterizeEvaluator();
164      ParameterizeAnalyzers();
165      ParameterizeOperators();
166      base.OnSolutionCreatorChanged();
167    }
168    protected override void OnEvaluatorChanged() {
169      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
170      ParameterizeEvaluator();
171      ParameterizeAnalyzers();
172      ParameterizeOperators();
173      base.OnEvaluatorChanged();
174    }
175
176    private void SolutionCreator_PermutationParameter_ActualNameChanged(object sender, EventArgs e) {
177      ParameterizeEvaluator();
178      ParameterizeAnalyzers();
179      ParameterizeOperators();
180    }
181    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
182      ParameterizeAnalyzers();
183      ParameterizeOperators();
184    }
185    private void WeightsParameter_ValueChanged(object sender, EventArgs e) {
186      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
187      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
188      ParameterizeSolutionCreator();
189      ParameterizeEvaluator();
190      ParameterizeOperators();
191      AdjustDistanceMatrix();
192    }
193    private void Weights_RowsChanged(object sender, EventArgs e) {
194      if (Weights.Rows != Weights.Columns)
195        ((IStringConvertibleMatrix)Weights).Columns = Weights.Rows;
196      else {
197        ParameterizeSolutionCreator();
198        ParameterizeEvaluator();
199        ParameterizeOperators();
200        AdjustDistanceMatrix();
201      }
202    }
203    private void Weights_ColumnsChanged(object sender, EventArgs e) {
204      if (Weights.Rows != Weights.Columns)
205        ((IStringConvertibleMatrix)Weights).Rows = Weights.Columns;
206      else {
207        ParameterizeSolutionCreator();
208        ParameterizeEvaluator();
209        ParameterizeOperators();
210        AdjustDistanceMatrix();
211      }
212    }
213    private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
214      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
215      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
216      ParameterizeSolutionCreator();
217      ParameterizeEvaluator();
218      ParameterizeOperators();
219      AdjustWeightsMatrix();
220    }
221    private void Distances_RowsChanged(object sender, EventArgs e) {
222      if (Distances.Rows != Distances.Columns)
223        ((IStringConvertibleMatrix)Distances).Columns = Distances.Rows;
224      else {
225        ParameterizeSolutionCreator();
226        ParameterizeEvaluator();
227        ParameterizeOperators();
228        AdjustWeightsMatrix();
229      }
230    }
231    private void Distances_ColumnsChanged(object sender, EventArgs e) {
232      if (Distances.Rows != Distances.Columns)
233        ((IStringConvertibleMatrix)Distances).Rows = Distances.Columns;
234      else {
235        ParameterizeSolutionCreator();
236        ParameterizeEvaluator();
237        ParameterizeOperators();
238        AdjustWeightsMatrix();
239      }
240    }
241    #endregion
242
243    #region Helpers
244    private void RegisterEventHandlers() {
245      SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
246      Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
247      WeightsParameter.ValueChanged += new EventHandler(WeightsParameter_ValueChanged);
248      Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
249      Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
250      DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
251      Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
252      Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
253    }
254
255    private void InitializeOperators() {
256      var defaultOperators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
257        new PartiallyMatchedCrossover(),
258        new Swap2Manipulator(),
259        new ExhaustiveSwap2MoveGenerator()
260      });
261      Operators.AddRange(defaultOperators);
262      Operators.AddRange(ApplicationManager.Manager.GetInstances<IPermutationOperator>().Except(defaultOperators, new TypeEqualityComparer<IPermutationOperator>()));
263      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
264      Operators.AddRange(ApplicationManager.Manager.GetInstances<IQAPMoveEvaluator>());
265      Operators.Add(new BestQAPSolutionAnalyzer());
266      Operators.Add(new QAPAlleleFrequencyAnalyzer());
267      Operators.Add(new QAPPopulationDiversityAnalyzer());
268      Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
269      ParameterizeAnalyzers();
270      ParameterizeOperators();
271    }
272    private void ParameterizeSolutionCreator() {
273      if (SolutionCreator != null) {
274        SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.Absolute);
275        SolutionCreator.LengthParameter.Value = new IntValue(Weights.Rows);
276      }
277    }
278    private void ParameterizeEvaluator() {
279      if (Evaluator != null) {
280        Evaluator.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
281        Evaluator.DistancesParameter.ActualName = DistancesParameter.Name;
282        Evaluator.WeightsParameter.ActualName = WeightsParameter.Name;
283      }
284    }
285    private void ParameterizeAnalyzers() {
286      if (BestQAPSolutionAnalyzer != null) {
287        BestQAPSolutionAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
288        BestQAPSolutionAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
289        BestQAPSolutionAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
290        BestQAPSolutionAnalyzer.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
291        BestQAPSolutionAnalyzer.ResultsParameter.ActualName = "Results";
292        BestQAPSolutionAnalyzer.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
293        BestQAPSolutionAnalyzer.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
294        BestQAPSolutionAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
295      }
296      if (QAPAlleleFrequencyAnalyzer != null) {
297        QAPAlleleFrequencyAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
298        QAPAlleleFrequencyAnalyzer.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
299        QAPAlleleFrequencyAnalyzer.DistancesParameter.ActualName = DistancesParameter.Name;
300        QAPAlleleFrequencyAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
301        QAPAlleleFrequencyAnalyzer.ResultsParameter.ActualName = "Results";
302        QAPAlleleFrequencyAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
303        QAPAlleleFrequencyAnalyzer.WeightsParameter.ActualName = WeightsParameter.Name;
304      }
305      if (QAPPopulationDiversityAnalyzer != null) {
306        QAPPopulationDiversityAnalyzer.MaximizationParameter.ActualName = MaximizationParameter.Name;
307        QAPPopulationDiversityAnalyzer.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
308        QAPPopulationDiversityAnalyzer.ResultsParameter.ActualName = "Results";
309        QAPPopulationDiversityAnalyzer.SolutionParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
310      }
311    }
312    private void ParameterizeOperators() {
313      foreach (IPermutationCrossover op in Operators.OfType<IPermutationCrossover>()) {
314        op.ParentsParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
315        op.ChildParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
316      }
317      foreach (IPermutationManipulator op in Operators.OfType<IPermutationManipulator>()) {
318        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
319      }
320      foreach (IPermutationMoveOperator op in Operators.OfType<IPermutationMoveOperator>()) {
321        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
322      }
323      if (Operators.OfType<IMoveGenerator>().Any()) {
324        string inversionMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationInversionMoveOperator>().First().InversionMoveParameter.ActualName;
325        foreach (IPermutationInversionMoveOperator op in Operators.OfType<IPermutationInversionMoveOperator>())
326          op.InversionMoveParameter.ActualName = inversionMove;
327        string translocationMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationTranslocationMoveOperator>().First().TranslocationMoveParameter.ActualName;
328        foreach (IPermutationTranslocationMoveOperator op in Operators.OfType<IPermutationTranslocationMoveOperator>())
329          op.TranslocationMoveParameter.ActualName = translocationMove;
330        string swapMove = Operators.OfType<IMoveGenerator>().OfType<IPermutationSwap2MoveOperator>().First().Swap2MoveParameter.ActualName;
331        foreach (IPermutationSwap2MoveOperator op in Operators.OfType<IPermutationSwap2MoveOperator>()) {
332          op.Swap2MoveParameter.ActualName = swapMove;
333        }
334      }
335      foreach (var op in Operators.OfType<IPermutationMultiNeighborhoodShakingOperator>())
336        op.PermutationParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
337
338      QAPExhaustiveSwap2LocalImprovement localOpt = Operators.OfType<QAPExhaustiveSwap2LocalImprovement>().SingleOrDefault();
339      if (localOpt != null) {
340        localOpt.AssignmentParameter.ActualName = SolutionCreator.PermutationParameter.ActualName;
341        localOpt.DistancesParameter.ActualName = DistancesParameter.Name;
342        localOpt.MaximizationParameter.ActualName = MaximizationParameter.Name;
343        localOpt.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
344        localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
345      }
346    }
347
348    private void AdjustDistanceMatrix() {
349      if (Distances.Rows != Weights.Rows || Distances.Columns != Weights.Columns) {
350        ((IStringConvertibleMatrix)Distances).Rows = Weights.Rows;
351      }
352    }
353
354    private void AdjustWeightsMatrix() {
355      if (Weights.Rows != Distances.Rows || Weights.Columns != Distances.Columns) {
356        ((IStringConvertibleMatrix)Weights).Rows = Distances.Rows;
357      }
358    }
359    #endregion
360
361    public void Load(QAPData data) {
362      var weights = new DoubleMatrix(data.Weights);
363      var distances = new DoubleMatrix(data.Distances);
364      Name = data.Name;
365      Description = data.Description;
366      Load(weights, distances);
367      EvaluateAndLoadAssignment(data.BestKnownAssignment);
368      OnReset();
369    }
370
371    public void Load(TSPData data) {
372      if (data.Dimension > 1000)
373        throw new System.IO.InvalidDataException("Instances with more than 1000 customers are not supported by the QAP.");
374      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
375      for (int i = 0; i < data.Dimension; i++)
376        weights[i, (i + 1) % data.Dimension] = 1;
377      var distances = new DoubleMatrix(data.GetDistanceMatrix());
378      Name = data.Name;
379      Description = data.Description;
380      Load(weights, distances);
381      EvaluateAndLoadAssignment(data.BestKnownTour);
382      OnReset();
383    }
384
385    public void Load(DoubleMatrix weights, DoubleMatrix distances) {
386      if (weights == null || weights.Rows == 0)
387        throw new System.IO.InvalidDataException("The given instance does not contain weights!");
388      if (weights.Rows != weights.Columns)
389        throw new System.IO.InvalidDataException("The weights matrix is not a square matrix!");
390      if (distances == null || distances.Rows == 0)
391        throw new System.IO.InvalidDataException("The given instance does not contain distances!");
392      if (distances.Rows != distances.Columns)
393        throw new System.IO.InvalidDataException("The distances matrix is not a square matrix!");
394      if (weights.Rows != distances.Columns)
395        throw new System.IO.InvalidDataException("The weights matrix and the distance matrix are not of equal size!");
396
397      Weights = weights;
398      Distances = distances;
399
400      BestKnownQuality = null;
401      BestKnownSolution = null;
402      BestKnownSolutions = null;
403    }
404
405    public void EvaluateAndLoadAssignment(int[] assignment) {
406      if (assignment == null || assignment.Length == 0) return;
407      var vector = new Permutation(PermutationTypes.Absolute, assignment);
408      var result = QAPEvaluator.Apply(vector, Weights, Distances);
409      BestKnownQuality = new DoubleValue(result);
410      BestKnownSolution = vector;
411      BestKnownSolutions = new ItemSet<Permutation>();
412      BestKnownSolutions.Add((Permutation)vector.Clone());
413    }
414  }
415}
Note: See TracBrowser for help on using the repository browser.