Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2457_ExpertSystem/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAP.cs @ 17175

Last change on this file since 17175 was 17175, checked in by abeham, 5 years ago

#2457: branched integer encoding, some changes

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