Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.TimeSeries/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs @ 7819

Last change on this file since 7819 was 7615, checked in by gkronber, 13 years ago

#1081 merged r7462:7609 from trunk into time series branch

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