source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAP.cs @ 15504

Last change on this file since 15504 was 15504, checked in by abeham, 2 years ago

#1614: refactored code

  • change problem to derive from basic problem
  • using a combined instance class instead of individual parameters
File size: 21.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Linq;
25using HeuristicLab.Analysis;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Encodings.IntegerVectorEncoding;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Problems.Instances;
36
37namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
38  [Item("Generalized Quadratic Assignment Problem (GQAP)", "The Generalized Quadratic Assignment Problem (GQAP) is a generalization of the QAP in that it allows to assign multiple facilities (here called equipment) to a single location. The problem is described in Lee, C.G., and Ma, Z. 2003. The Generalized Quadratic Assignment Problem. Technical Report M5S 3G8, University of Toronto, Canada.")]
39  [Creatable("Problems")]
40  [StorableClass]
41  public sealed class GQAP : SingleObjectiveBasicProblem<IntegerVectorEncoding>,
42    IProblemInstanceConsumer<QAPData>,
43    IProblemInstanceConsumer<CTAPData>,
44    IProblemInstanceConsumer<TSPData>,
45    IProblemInstanceConsumer<ATSPData>,
46    IProblemInstanceConsumer<GQAPData> {
47
48    public override bool Maximization { get { return false; } }
49
50    #region Parameter Descriptions
51    public static readonly string BestKnownQualityDescription = "The best known quality (if available).";
52    public static readonly string BestKnownSolutionDescription = "The best known solution (if available).";
53    public static readonly string BestKnownSolutionsDescription = "Contains an archive of best-known solutions regarding flow-distance quality and installation quality.";
54    public static readonly string ProblemInstanceDescription = "The problem instance that is to be solved.";
55    public static readonly string EvaluationDescription = "The evaluation result of a solution to the GQAP.";
56    #endregion
57
58    #region Parameter Properties
59    public OptionalValueParameter<GQAPAssignment> BestKnownSolutionParameter {
60      get { return (OptionalValueParameter<GQAPAssignment>)Parameters["BestKnownSolution"]; }
61    }
62    public OptionalValueParameter<GQAPAssignmentArchive> BestKnownSolutionsParameter {
63      get { return (OptionalValueParameter<GQAPAssignmentArchive>)Parameters["BestKnownSolutions"]; }
64    }
65    public IValueParameter<GQAPInstance> ProblemInstanceParameter {
66      get { return (IValueParameter<GQAPInstance>)Parameters["ProblemInstance"]; }
67    }
68    #endregion
69
70    #region Properties
71    public GQAPAssignment BestKnownSolution {
72      get { return BestKnownSolutionParameter.Value; }
73      set { BestKnownSolutionParameter.Value = value; }
74    }
75    public GQAPAssignmentArchive BestKnownSolutions {
76      get { return BestKnownSolutionsParameter.Value; }
77      set { BestKnownSolutionsParameter.Value = value; }
78    }
79    public GQAPInstance ProblemInstance {
80      get { return ProblemInstanceParameter.Value; }
81      set { ProblemInstanceParameter.Value = value; }
82    }
83    #endregion
84
85    [StorableConstructor]
86    private GQAP(bool deserializing) : base(deserializing) { }
87    private GQAP(GQAP original, Cloner cloner)
88      : base(original, cloner) {
89      RegisterEventHandlers();
90    }
91    public GQAP() : base() {
92      Encoding = new IntegerVectorEncoding("Assignment");
93      Parameters.Add(new OptionalValueParameter<GQAPAssignment>("BestKnownSolution", BestKnownSolutionDescription, null, false));
94      Parameters.Add(new OptionalValueParameter<GQAPAssignmentArchive>("BestKnownSolutions", BestKnownSolutionsDescription, null, false));
95      Parameters.Add(new ValueParameter<GQAPInstance>("ProblemInstance", "The problem instance that is to be solved.", new GQAPInstance(), false));
96
97      InitializeOperators();
98      RegisterEventHandlers();
99    }
100
101    public override IDeepCloneable Clone(Cloner cloner) {
102      return new GQAP(this, cloner);
103    }
104
105    public override double Evaluate(Individual individual, IRandom random = null) {
106      var assignment = individual.IntegerVector();
107      var evaluation = ProblemInstance.Evaluate(assignment);
108      individual["Evaluation"] = evaluation;
109      return ProblemInstance.ToSingleObjective(evaluation);
110    }
111
112    public double Evaluate(IntegerVector assignment) {
113      var evaluation = ProblemInstance.Evaluate(assignment);
114      return ProblemInstance.ToSingleObjective(evaluation);
115    }
116
117    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
118      AnalyzeBestSolution(results, GetBestIndividual(individuals, qualities));
119      AnalyzeParetoArchive(results,
120        individuals.Select(i => Tuple.Create((IntegerVector)i.IntegerVector().Clone(),
121        (Evaluation)i["Evaluation"])));
122    }
123
124    private void AnalyzeBestSolution(ResultCollection results, Tuple<Individual, double> best) {
125      var bestVector = best.Item1.IntegerVector();
126      var bestEvaluation = (Evaluation)best.Item1["Evaluation"];
127
128      IResult bestResult;
129      if (!results.TryGetValue("Best Solution", out bestResult)) {
130        bestResult = new Result("Best Solution", typeof(GQAPAssignment));
131        results.Add(bestResult);
132      }
133      var item = bestResult.Value as GQAPAssignment;
134      if (item == null) bestResult.Value = new GQAPAssignment((IntegerVector)bestVector.Clone(), ProblemInstance, bestEvaluation);
135      else if (ProblemInstance.ToSingleObjective(bestEvaluation)
136        < ProblemInstance.ToSingleObjective(item.Evaluation)) {
137        item.ProblemInstance = ProblemInstance;
138        item.Assignment = (IntegerVector)bestVector.Clone();
139        item.Evaluation = bestEvaluation;
140      }
141    }
142
143    private void AnalyzeParetoArchive(ResultCollection results, IEnumerable<Tuple<IntegerVector, Evaluation>> solutions) {
144      IResult archiveResult;
145      if (!results.TryGetValue("Solution Archive", out archiveResult)) {
146        archiveResult = new Result("Solution Archive", typeof(GQAPAssignmentArchive));
147        results.Add(archiveResult);
148      }
149      var archive = archiveResult.Value as GQAPAssignmentArchive;
150      if (archive == null) archive = new GQAPAssignmentArchive(ProblemInstance);
151      else archive.ProblemInstance = ProblemInstance;
152     
153      var combinedArchive = solutions
154        .Select(x => new GQAPSolution(x.Item1, x.Item2))
155        .Concat(archive.Solutions);
156      archive.Solutions = GetFeasibleParetoFront(combinedArchive);
157     
158      if (BestKnownSolutions == null) {
159        BestKnownSolutions = archive;
160      } else {
161        var combinedArchive2 = solutions
162        .Select(x => new GQAPSolution(x.Item1, x.Item2))
163        .Concat(BestKnownSolutions.Solutions);
164        BestKnownSolutions.Solutions = GetFeasibleParetoFront(combinedArchive2);
165      }
166    }
167
168    #region Problem Instance Loading
169    public void Load(QAPData data) {
170      Name = data.Name;
171      Description = data.Description;
172
173      var weights = new DoubleMatrix(data.Weights);
174      var distances = new DoubleMatrix(data.Distances);
175      var installationCosts = new DoubleMatrix(weights.Rows, distances.Columns); // all zero
176      var capacities = new DoubleArray(Enumerable.Range(0, distances.Rows).Select(x => 1.0).ToArray());
177      var demands = new DoubleArray(Enumerable.Range(0, weights.Rows).Select(x => 1.0).ToArray());
178
179      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
180      EvaluateAndLoadAssignment(data.BestKnownAssignment);
181    }
182
183    public void Load(CTAPData data) {
184      Name = data.Name;
185      Description = data.Description;
186
187      var capacities = new DoubleArray(data.MemoryCapacities);
188      var demands = new DoubleArray(data.MemoryRequirements);
189      var weights = new DoubleMatrix(data.CommunicationCosts);
190      var installationCosts = new DoubleMatrix(data.ExecutionCosts.Transpose());
191      var distances = new DoubleMatrix(capacities.Length, capacities.Length);
192      for (int i = 0; i < capacities.Length - 1; i++)
193        for (int j = i + 1; j < capacities.Length; j++) {
194          distances[i, j] = 1;
195        }
196
197      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
198      EvaluateAndLoadAssignment(data.BestKnownAssignment);
199    }
200
201    public void Load(TSPData data) {
202      if (data.Dimension > 1000)
203        throw new System.IO.InvalidDataException("Instances with more than 1000 cities are not supported.");
204
205      Name = data.Name;
206      Description = data.Description;
207
208      var capacities = new DoubleArray(data.Dimension);
209      var demands = new DoubleArray(data.Dimension);
210      for (int i = 0; i < data.Dimension; i++) {
211        capacities[i] = 1;
212        demands[i] = 1;
213      }
214      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
215      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
216      for (int i = 0; i < data.Dimension; i++)
217        weights[i, (i + 1) % data.Dimension] = 1;
218      var distances = new DoubleMatrix(data.GetDistanceMatrix());
219
220      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
221      EvaluateAndLoadAssignment(data.BestKnownTour);
222    }
223
224    public void Load(ATSPData data) {
225      Name = data.Name;
226      Description = data.Description;
227
228      var capacities = new DoubleArray(data.Dimension);
229      var demands = new DoubleArray(data.Dimension);
230      for (int i = 0; i < data.Dimension; i++) {
231        capacities[i] = 1;
232        demands[i] = 1;
233      }
234      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
235      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
236      for (int i = 0; i < data.Dimension; i++)
237        weights[i, (i + 1) % data.Dimension] = 1;
238      var distances = new DoubleMatrix(data.Distances);
239
240      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
241      EvaluateAndLoadAssignment(data.BestKnownTour);
242    }
243
244    public void Load(GQAPData data) {
245      Name = data.Name;
246      Description = data.Description;
247
248      var capacities = new DoubleArray(data.Capacities);
249      var demands = new DoubleArray(data.Demands);
250      var installationCosts = new DoubleMatrix(data.InstallationCosts);
251      var weights = new DoubleMatrix(data.Weights);
252      var distances = new DoubleMatrix(data.Distances);
253      var transportationCosts = new DoubleValue(data.TransportationCosts);
254
255      Load(demands, capacities, weights, distances, installationCosts, transportationCosts);
256      EvaluateAndLoadAssignment(data.BestKnownAssignment);
257
258      if (data.BestKnownAssignment == null && data.BestKnownQuality.HasValue) {
259        BestKnownQuality = data.BestKnownQuality.Value;
260      }
261    }
262
263    public void Load(DoubleArray demands, DoubleArray capacities,
264      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
265      DoubleValue transportationCosts) {
266      if (weights == null || weights.Rows == 0)
267        throw new System.IO.InvalidDataException(
268@"The given instance does not contain weights!");
269      if (weights.Rows != weights.Columns)
270        throw new System.IO.InvalidDataException(
271@"The weights matrix of the given instance contains
272an unequal number of rows and columns.");
273      if (distances == null || distances.Rows == 0)
274        throw new System.IO.InvalidDataException(
275@"The given instance does not contain distances!");
276      if (distances.Rows != distances.Columns)
277        throw new System.IO.InvalidDataException(
278@"The distances matrix of the given instance contains
279an unequal number of rows and columns.");
280      if (installationCosts == null || installationCosts.Rows == 0)
281        throw new System.IO.InvalidDataException(
282@"The given instance does not contain installation costs!");
283      if (installationCosts.Rows != weights.Rows
284        || installationCosts.Columns != distances.Columns)
285        throw new System.IO.InvalidDataException(
286@"The installation costs matrix of the given instance
287contains different number of rows than given in the
288weights matrix and a different number of columns than
289given in the distances matrix.");
290      if (capacities == null || capacities.Length == 0)
291        throw new System.IO.InvalidDataException(
292@"The given instance does not contain capacities!");
293      if (capacities.Length != distances.Rows)
294        throw new System.IO.InvalidDataException(
295@"The given instance contains a different number of
296capacities than rows given in the distances matrix.");
297      if (demands == null || demands.Length == 0)
298        throw new System.IO.InvalidDataException(
299@"The given instance does not contain demands!");
300      if (demands.Length != weights.Rows)
301        throw new System.IO.InvalidDataException(
302@"The given instance contains a different number of
303demands than rows given in the weights matrix.");
304      if (transportationCosts == null)
305        throw new System.IO.InvalidDataException(
306@"The given instance does not contain transportation costs.");
307
308      ProblemInstance = new GQAPInstance() {
309        Weights = weights,
310        Distances = distances,
311        InstallationCosts = installationCosts,
312        Capacities = capacities,
313        Demands = demands,
314        TransportationCosts = transportationCosts.Value
315      };
316      BestKnownQualityParameter.Value = null;
317      BestKnownSolution = null;
318      BestKnownSolutions = null;
319      ProblemInstance.CalculatePenaltyLevel();
320    }
321    private void EvaluateAndLoadAssignment(int[] vector) {
322      if (vector == null || vector.Length == 0) return;
323      EvaluateAndLoadAssignment(new IntegerVector(vector));
324    }
325    public void EvaluateAndLoadAssignment(IntegerVector assignment) {
326      if (!ProblemInstance.IsValid()) {
327        BestKnownQualityParameter.Value = null;
328        BestKnownSolution = null;
329        BestKnownSolutions = null;
330        return;
331      }
332      var evaluation = ProblemInstance.Evaluate(assignment);
333      var quality = ProblemInstance.ToSingleObjective(evaluation);
334     
335      BestKnownSolution = new GQAPAssignment((IntegerVector)assignment.Clone(), ProblemInstance, evaluation);
336      BestKnownQuality = quality;
337      BestKnownSolutions = new GQAPAssignmentArchive(ProblemInstance);
338      BestKnownSolutions.Solutions.Add(new GQAPSolution((IntegerVector)assignment.Clone(), evaluation));
339    }
340    #endregion
341
342    #region Events
343    protected override void OnOperatorsChanged() {
344      base.OnOperatorsChanged();
345      Parameterize();
346    }
347    protected override void OnEncodingChanged() {
348      base.OnEncodingChanged();
349      Parameterize();
350    }
351    #endregion
352
353    #region Helpers
354    [StorableHook(HookType.AfterDeserialization)]
355    private void AfterDeserialization() {
356      RegisterEventHandlers();
357    }
358
359    private void RegisterEventHandlers() {
360      ProblemInstanceParameter.ValueChanged += ProblemInstanceParameterOnValueChanged;
361      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
362      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
363      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
364      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
365    }
366
367    private void ProblemInstanceParameterOnValueChanged(object sender, EventArgs e) {
368      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
369      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
370      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
371      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
372      UpdateEncoding();
373    }
374    private void ProblemInstanceCapacitiesParameterOnValueChanged(object sender, EventArgs e) {
375      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
376      UpdateEncoding();
377    }
378    private void ProblemInstanceDemandsParameterOnValueChanged(object sender, EventArgs e) {
379      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
380      UpdateEncoding();
381    }
382    private void ProblemInstanceDemandsOnReset(object sender, EventArgs e) {
383      UpdateEncoding();
384    }
385    private void ProblemInstanceCapacitiesOnReset(object sender, EventArgs e) {
386      UpdateEncoding();
387    }
388
389    private void UpdateEncoding() {
390      Encoding.Length = ProblemInstance.Demands.Length;
391      Encoding.Bounds = new IntMatrix(new int[,] { { 0, ProblemInstance.Capacities.Length } });
392    }
393
394    private void InitializeOperators() {
395      Operators.Clear();
396      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPOperator>());
397      Operators.RemoveAll(x => x is ISingleObjectiveMoveEvaluator);
398      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPMoveEvaluator>());
399      Operators.Add(new HammingSimilarityCalculator());
400      Operators.Add(new QualitySimilarityCalculator());
401     
402      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
403      Parameterize();
404    }
405
406    private void Parameterize() {
407      var operators = Operators.Union(new IOperator[] { SolutionCreator, Evaluator }).ToArray();
408     
409      foreach (var op in operators.OfType<IBestKnownQualityAwareGQAPOperator>()) {
410        op.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
411        op.BestKnownQualityParameter.Hidden = true;
412      }
413      foreach (var op in operators.OfType<IBestKnownSolutionAwareGQAPOperator>()) {
414        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
415        op.BestKnownSolutionParameter.Hidden = true;
416      }
417      foreach (var op in operators.OfType<IBestKnownSolutionsAwareGQAPOperator>()) {
418        op.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
419        op.BestKnownSolutionsParameter.Hidden = true;
420      }
421      foreach (var op in operators.OfType<IGQAPCrossover>()) {
422        op.ParentsParameter.ActualName = Encoding.Name;
423        op.ParentsParameter.Hidden = true;
424        op.ChildParameter.ActualName = Encoding.Name;
425        op.ChildParameter.Hidden = true;
426      }
427      var moveEvaluator = operators.OfType<IGQAPMoveEvaluator>().FirstOrDefault();
428      foreach (var op in operators.OfType<IGQAPMoveEvaluator>()) { // synchronize all move evaluators
429        if (moveEvaluator != null) {
430          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
431          op.MoveQualityParameter.Hidden = true;
432          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
433          op.MoveEvaluationParameter.Hidden = true;
434        }
435      }
436      foreach (var op in operators.OfType<IMoveQualityAwareGQAPOperator>()) {
437        if (moveEvaluator != null) {
438          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
439          op.MoveQualityParameter.Hidden = true;
440          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
441          op.MoveEvaluationParameter.Hidden = true;
442        }
443      }
444      foreach (var op in operators.OfType<IProblemInstanceAwareGQAPOperator>()) {
445        op.ProblemInstanceParameter.ActualName = ProblemInstanceParameter.Name;
446        op.ProblemInstanceParameter.Hidden = true;
447      }
448      foreach (var op in operators.OfType<IQualitiesAwareGQAPOperator>()) {
449        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
450        op.QualityParameter.Hidden = true;
451        op.EvaluationParameter.ActualName = "Evaluation";
452        op.EvaluationParameter.Hidden = true;
453      }
454      foreach (var op in operators.OfType<IQualityAwareGQAPOperator>()) {
455        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
456        op.QualityParameter.Hidden = true;
457        op.EvaluationParameter.ActualName = "Evaluation";
458        op.EvaluationParameter.Hidden = true;
459      }
460    }
461    #endregion
462
463    public static ItemList<GQAPSolution> GetFeasibleParetoFront(IEnumerable<GQAPSolution> solutions) {
464      var front = new ItemList<GQAPSolution>(solutions.Where(x => x.Evaluation.IsFeasible));
465
466      for (int i = 0; i < front.Count - 1; i++) {
467        for (int j = i + 1; j < front.Count; j++) {
468          if (front[i].Evaluation.FlowCosts <= front[j].Evaluation.FlowCosts
469            && front[i].Evaluation.InstallationCosts <= front[j].Evaluation.InstallationCosts) {
470            front.RemoveAt(j);
471            j--;
472          } else if (front[i].Evaluation.FlowCosts >= front[j].Evaluation.FlowCosts
473            && front[i].Evaluation.InstallationCosts >= front[j].Evaluation.InstallationCosts) {
474            front.RemoveAt(i);
475            j = i;
476          }
477        }
478      }
479      return front;
480    }
481  }
482}
Note: See TracBrowser for help on using the repository browser.