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

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

#1614: finished wiring

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