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

Last change on this file since 15510 was 15510, checked in by abeham, 20 months ago

#1614:

  • Fixed bugs in view
  • Made Evaluation object immutable
  • Fixed bug in Analyze
  • Fixed operators
File size: 22.4 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) {
157        archive = new GQAPAssignmentArchive(ProblemInstance);
158        archiveResult.Value = archive;
159      } else archive.ProblemInstance = ProblemInstance;
160     
161      var combinedArchive = solutions
162        .Select(x => new GQAPSolution(x.Item1, x.Item2))
163        .Concat(archive.Solutions);
164      archive.Solutions = GetFeasibleParetoFront(combinedArchive);
165     
166      if (BestKnownSolutions == null) {
167        BestKnownSolutions = archive;
168      } else {
169        var combinedArchive2 = solutions
170        .Select(x => new GQAPSolution(x.Item1, x.Item2))
171        .Concat(BestKnownSolutions.Solutions);
172        BestKnownSolutions.Solutions = GetFeasibleParetoFront(combinedArchive2);
173      }
174    }
175
176    #region Problem Instance Loading
177    public void Load(QAPData data) {
178      Name = data.Name;
179      Description = data.Description;
180
181      var weights = new DoubleMatrix(data.Weights);
182      var distances = new DoubleMatrix(data.Distances);
183      var installationCosts = new DoubleMatrix(weights.Rows, distances.Columns); // all zero
184      var capacities = new DoubleArray(Enumerable.Range(0, distances.Rows).Select(x => 1.0).ToArray());
185      var demands = new DoubleArray(Enumerable.Range(0, weights.Rows).Select(x => 1.0).ToArray());
186
187      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
188      EvaluateAndLoadAssignment(data.BestKnownAssignment);
189    }
190
191    public void Load(CTAPData data) {
192      Name = data.Name;
193      Description = data.Description;
194
195      var capacities = new DoubleArray(data.MemoryCapacities);
196      var demands = new DoubleArray(data.MemoryRequirements);
197      var weights = new DoubleMatrix(data.CommunicationCosts);
198      var installationCosts = new DoubleMatrix(data.ExecutionCosts.Transpose());
199      var distances = new DoubleMatrix(capacities.Length, capacities.Length);
200      for (int i = 0; i < capacities.Length - 1; i++)
201        for (int j = i + 1; j < capacities.Length; j++) {
202          distances[i, j] = 1;
203        }
204
205      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
206      EvaluateAndLoadAssignment(data.BestKnownAssignment);
207    }
208
209    public void Load(TSPData data) {
210      if (data.Dimension > 1000)
211        throw new System.IO.InvalidDataException("Instances with more than 1000 cities are not supported.");
212
213      Name = data.Name;
214      Description = data.Description;
215
216      var capacities = new DoubleArray(data.Dimension);
217      var demands = new DoubleArray(data.Dimension);
218      for (int i = 0; i < data.Dimension; i++) {
219        capacities[i] = 1;
220        demands[i] = 1;
221      }
222      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
223      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
224      for (int i = 0; i < data.Dimension; i++)
225        weights[i, (i + 1) % data.Dimension] = 1;
226      var distances = new DoubleMatrix(data.GetDistanceMatrix());
227
228      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
229      EvaluateAndLoadAssignment(data.BestKnownTour);
230    }
231
232    public void Load(ATSPData data) {
233      Name = data.Name;
234      Description = data.Description;
235
236      var capacities = new DoubleArray(data.Dimension);
237      var demands = new DoubleArray(data.Dimension);
238      for (int i = 0; i < data.Dimension; i++) {
239        capacities[i] = 1;
240        demands[i] = 1;
241      }
242      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
243      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
244      for (int i = 0; i < data.Dimension; i++)
245        weights[i, (i + 1) % data.Dimension] = 1;
246      var distances = new DoubleMatrix(data.Distances);
247
248      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
249      EvaluateAndLoadAssignment(data.BestKnownTour);
250    }
251
252    public void Load(GQAPData data) {
253      Name = data.Name;
254      Description = data.Description;
255
256      var capacities = new DoubleArray(data.Capacities);
257      var demands = new DoubleArray(data.Demands);
258      var installationCosts = new DoubleMatrix(data.InstallationCosts);
259      var weights = new DoubleMatrix(data.Weights);
260      var distances = new DoubleMatrix(data.Distances);
261      var transportationCosts = new DoubleValue(data.TransportationCosts);
262
263      Load(demands, capacities, weights, distances, installationCosts, transportationCosts);
264      EvaluateAndLoadAssignment(data.BestKnownAssignment);
265
266      if (data.BestKnownAssignment == null && data.BestKnownQuality.HasValue) {
267        BestKnownQuality = data.BestKnownQuality.Value;
268      }
269    }
270
271    public void Load(DoubleArray demands, DoubleArray capacities,
272      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
273      DoubleValue transportationCosts) {
274      if (weights == null || weights.Rows == 0)
275        throw new System.IO.InvalidDataException(
276@"The given instance does not contain weights!");
277      if (weights.Rows != weights.Columns)
278        throw new System.IO.InvalidDataException(
279@"The weights matrix of the given instance contains
280an unequal number of rows and columns.");
281      if (distances == null || distances.Rows == 0)
282        throw new System.IO.InvalidDataException(
283@"The given instance does not contain distances!");
284      if (distances.Rows != distances.Columns)
285        throw new System.IO.InvalidDataException(
286@"The distances matrix of the given instance contains
287an unequal number of rows and columns.");
288      if (installationCosts == null || installationCosts.Rows == 0)
289        throw new System.IO.InvalidDataException(
290@"The given instance does not contain installation costs!");
291      if (installationCosts.Rows != weights.Rows
292        || installationCosts.Columns != distances.Columns)
293        throw new System.IO.InvalidDataException(
294@"The installation costs matrix of the given instance
295contains different number of rows than given in the
296weights matrix and a different number of columns than
297given in the distances matrix.");
298      if (capacities == null || capacities.Length == 0)
299        throw new System.IO.InvalidDataException(
300@"The given instance does not contain capacities!");
301      if (capacities.Length != distances.Rows)
302        throw new System.IO.InvalidDataException(
303@"The given instance contains a different number of
304capacities than rows given in the distances matrix.");
305      if (demands == null || demands.Length == 0)
306        throw new System.IO.InvalidDataException(
307@"The given instance does not contain demands!");
308      if (demands.Length != weights.Rows)
309        throw new System.IO.InvalidDataException(
310@"The given instance contains a different number of
311demands than rows given in the weights matrix.");
312      if (transportationCosts == null)
313        throw new System.IO.InvalidDataException(
314@"The given instance does not contain transportation costs.");
315
316      ProblemInstance = new GQAPInstance() {
317        Weights = weights,
318        Distances = distances,
319        InstallationCosts = installationCosts,
320        Capacities = capacities,
321        Demands = demands,
322        TransportationCosts = transportationCosts.Value
323      };
324      BestKnownQualityParameter.Value = null;
325      BestKnownSolution = null;
326      BestKnownSolutions = null;
327      ProblemInstance.CalculatePenaltyLevel();
328    }
329    private void EvaluateAndLoadAssignment(int[] vector) {
330      if (vector == null || vector.Length == 0) return;
331      EvaluateAndLoadAssignment(new IntegerVector(vector));
332    }
333    public void EvaluateAndLoadAssignment(IntegerVector assignment) {
334      if (!ProblemInstance.IsValid()) {
335        BestKnownQualityParameter.Value = null;
336        BestKnownSolution = null;
337        BestKnownSolutions = null;
338        return;
339      }
340      var evaluation = ProblemInstance.Evaluate(assignment);
341      var quality = ProblemInstance.ToSingleObjective(evaluation);
342     
343      BestKnownSolution = new GQAPAssignment((IntegerVector)assignment.Clone(), ProblemInstance, evaluation);
344      BestKnownQuality = quality;
345      BestKnownSolutions = new GQAPAssignmentArchive(ProblemInstance);
346      BestKnownSolutions.Solutions.Add(new GQAPSolution((IntegerVector)assignment.Clone(), evaluation));
347    }
348    #endregion
349
350    #region Events
351    protected override void OnOperatorsChanged() {
352      base.OnOperatorsChanged();
353      if (!initialized) return;
354      Parameterize();
355    }
356    protected override void OnEncodingChanged() {
357      base.OnEncodingChanged();
358      if (!initialized) return;
359      Parameterize();
360    }
361    #endregion
362
363    #region Helpers
364    [StorableHook(HookType.AfterDeserialization)]
365    private void AfterDeserialization() {
366      RegisterEventHandlers();
367    }
368
369    private void RegisterEventHandlers() {
370      ProblemInstanceParameter.ValueChanged += ProblemInstanceParameterOnValueChanged;
371      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
372      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
373      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
374      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
375    }
376
377    private void ProblemInstanceParameterOnValueChanged(object sender, EventArgs e) {
378      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
379      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
380      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
381      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
382      UpdateEncoding();
383    }
384    private void ProblemInstanceCapacitiesParameterOnValueChanged(object sender, EventArgs e) {
385      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
386      UpdateEncoding();
387    }
388    private void ProblemInstanceDemandsParameterOnValueChanged(object sender, EventArgs e) {
389      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
390      UpdateEncoding();
391    }
392    private void ProblemInstanceDemandsOnReset(object sender, EventArgs e) {
393      UpdateEncoding();
394    }
395    private void ProblemInstanceCapacitiesOnReset(object sender, EventArgs e) {
396      UpdateEncoding();
397    }
398
399    private void UpdateEncoding() {
400      Encoding.Length = ProblemInstance.Demands.Length;
401      Encoding.Bounds = new IntMatrix(new int[,] { { 0, ProblemInstance.Capacities.Length } });
402    }
403
404    private void InitializeOperators() {
405      Operators.RemoveAll(x => x is ISingleObjectiveMoveOperator);
406      Operators.RemoveAll(x => x is SingleObjectiveImprover);
407      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPOperator>());
408      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPMoveEvaluator>());
409      Operators.Add(new HammingSimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
410      Operators.Add(new QualitySimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
411     
412      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
413    }
414
415    private void Parameterize() {
416      var operators = Operators.Union(new IOperator[] { SolutionCreator, Evaluator }).ToArray();
417      Encoding.ConfigureOperators(operators.OfType<IOperator>());
418      foreach (var op in operators.OfType<IAssignmentAwareGQAPOperator>()) {
419        op.AssignmentParameter.ActualName = Encoding.Name;
420        op.AssignmentParameter.Hidden = true;
421      }
422      foreach (var op in operators.OfType<IBestKnownQualityAwareGQAPOperator>()) {
423        op.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
424        op.BestKnownQualityParameter.Hidden = true;
425      }
426      foreach (var op in operators.OfType<IBestKnownSolutionAwareGQAPOperator>()) {
427        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
428        op.BestKnownSolutionParameter.Hidden = true;
429      }
430      foreach (var op in operators.OfType<IBestKnownSolutionsAwareGQAPOperator>()) {
431        op.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
432        op.BestKnownSolutionsParameter.Hidden = true;
433      }
434      foreach (var op in operators.OfType<IGQAPCrossover>()) {
435        op.ParentsParameter.ActualName = Encoding.Name;
436        op.ParentsParameter.Hidden = true;
437        op.ChildParameter.ActualName = Encoding.Name;
438        op.ChildParameter.Hidden = true;
439      }
440      var moveEvaluator = operators.OfType<IGQAPMoveEvaluator>().FirstOrDefault();
441      foreach (var op in operators.OfType<IGQAPMoveEvaluator>()) { // synchronize all move evaluators
442        if (moveEvaluator != null) {
443          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
444          op.MoveQualityParameter.Hidden = true;
445          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
446          op.MoveEvaluationParameter.Hidden = true;
447        }
448      }
449      foreach (var op in operators.OfType<IMoveQualityAwareGQAPOperator>()) {
450        if (moveEvaluator != null) {
451          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
452          op.MoveQualityParameter.Hidden = true;
453          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
454          op.MoveEvaluationParameter.Hidden = true;
455        }
456      }
457      foreach (var op in operators.OfType<IProblemInstanceAwareGQAPOperator>()) {
458        op.ProblemInstanceParameter.ActualName = ProblemInstanceParameter.Name;
459        op.ProblemInstanceParameter.Hidden = true;
460      }
461      foreach (var op in operators.OfType<IQualitiesAwareGQAPOperator>()) {
462        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
463        op.QualityParameter.Hidden = true;
464        op.EvaluationParameter.ActualName = "Evaluation";
465        op.EvaluationParameter.Hidden = true;
466      }
467      foreach (var op in operators.OfType<IQualityAwareGQAPOperator>()) {
468        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
469        op.QualityParameter.Hidden = true;
470        op.EvaluationParameter.ActualName = "Evaluation";
471        op.EvaluationParameter.Hidden = true;
472      }
473    }
474    #endregion
475
476    public static ItemList<GQAPSolution> GetFeasibleParetoFront(IEnumerable<GQAPSolution> solutions) {
477      var front = new ItemList<GQAPSolution>(solutions.Where(x => x.Evaluation.IsFeasible));
478
479      for (int i = 0; i < front.Count - 1; i++) {
480        for (int j = i + 1; j < front.Count; j++) {
481          if (front[i].Evaluation.FlowCosts <= front[j].Evaluation.FlowCosts
482            && front[i].Evaluation.InstallationCosts <= front[j].Evaluation.InstallationCosts) {
483            front.RemoveAt(j);
484            j--;
485          } else if (front[i].Evaluation.FlowCosts >= front[j].Evaluation.FlowCosts
486            && front[i].Evaluation.InstallationCosts >= front[j].Evaluation.InstallationCosts) {
487            front.RemoveAt(i);
488            j = i;
489          }
490        }
491      }
492      return front;
493    }
494  }
495}
Note: See TracBrowser for help on using the repository browser.