1 | #region License Information
|
---|
2 | /* HeuristicLab
|
---|
3 | * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
4 | *
|
---|
5 | * This file is part of HeuristicLab.
|
---|
6 | *
|
---|
7 | * HeuristicLab is free software: you can redistribute it and/or modify
|
---|
8 | * it under the terms of the GNU General Public License as published by
|
---|
9 | * the Free Software Foundation, either version 3 of the License, or
|
---|
10 | * (at your option) any later version.
|
---|
11 | *
|
---|
12 | * HeuristicLab is distributed in the hope that it will be useful,
|
---|
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
15 | * GNU General Public License for more details.
|
---|
16 | *
|
---|
17 | * You should have received a copy of the GNU General Public License
|
---|
18 | * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
|
---|
19 | */
|
---|
20 | #endregion
|
---|
21 |
|
---|
22 | using System;
|
---|
23 | using System.Linq;
|
---|
24 | using HeuristicLab.Common;
|
---|
25 | using HeuristicLab.Core;
|
---|
26 | using HeuristicLab.Data;
|
---|
27 | using HeuristicLab.Encodings.IntegerVectorEncoding;
|
---|
28 | using HeuristicLab.Operators;
|
---|
29 | using HeuristicLab.Parameters;
|
---|
30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
31 |
|
---|
32 | namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
|
---|
33 | [Item("GQAPEvaluator", "Evaluates solutions to the generalized quadratic assignment problem.")]
|
---|
34 | [StorableClass]
|
---|
35 | public class GQAPEvaluator : SingleSuccessorOperator, IGQAPEvaluator {
|
---|
36 |
|
---|
37 | public ILookupParameter<DoubleValue> QualityParameter {
|
---|
38 | get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
|
---|
39 | }
|
---|
40 | public ILookupParameter<DoubleValue> InfeasibilityParameter {
|
---|
41 | get { return (ILookupParameter<DoubleValue>)Parameters["Infeasibility"]; }
|
---|
42 | }
|
---|
43 | public IValueLookupParameter<DoubleValue> PenaltyParameter {
|
---|
44 | get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
|
---|
45 | }
|
---|
46 | public ILookupParameter<DoubleMatrix> WeightsParameter {
|
---|
47 | get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
|
---|
48 | }
|
---|
49 | public ILookupParameter<DoubleMatrix> DistancesParameter {
|
---|
50 | get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
|
---|
51 | }
|
---|
52 | public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
|
---|
53 | get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
|
---|
54 | }
|
---|
55 | public ILookupParameter<DoubleValue> TransportationCostsParameter {
|
---|
56 | get { return (ILookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
|
---|
57 | }
|
---|
58 | public ILookupParameter<DoubleArray> DemandsParameter {
|
---|
59 | get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
|
---|
60 | }
|
---|
61 | public ILookupParameter<DoubleArray> CapacitiesParameter {
|
---|
62 | get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
|
---|
63 | }
|
---|
64 | public ILookupParameter<IntegerVector> AssignmentParameter {
|
---|
65 | get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
|
---|
66 | }
|
---|
67 |
|
---|
68 | [StorableConstructor]
|
---|
69 | protected GQAPEvaluator(bool deserializing) : base(deserializing) { }
|
---|
70 | protected GQAPEvaluator(GQAPEvaluator original, Cloner cloner) : base(original, cloner) { }
|
---|
71 | public GQAPEvaluator()
|
---|
72 | : base() {
|
---|
73 | Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality a.k.a. fitness of the solution."));
|
---|
74 | Parameters.Add(new LookupParameter<DoubleValue>("Infeasibility", "The infeasibility describes the sum of the overbooked capacities."));
|
---|
75 | Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty", "The multiplier for the constraint violation when added to the quality.", new DoubleValue(1000)));
|
---|
76 | Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix describes the flows between the equipments."));
|
---|
77 | Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix describes the distances between the locations at which the equipment can be installed."));
|
---|
78 | Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The installation costs matrix describes the installation costs of installing equipment i at location j"));
|
---|
79 | Parameters.Add(new LookupParameter<DoubleValue>("TransportationCosts", "The transportation cost represents the flow-unit per distance-unit cost factor. This value can also be set to 1 if these costs are factored into the weights matrix already."));
|
---|
80 | Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands vector describes the space requirements of the equipments."));
|
---|
81 | Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities vector describes the available space at the locations."));
|
---|
82 | Parameters.Add(new LookupParameter<IntegerVector>("Assignment", "The vector that encodes the assignment."));
|
---|
83 | }
|
---|
84 |
|
---|
85 | public override IDeepCloneable Clone(Cloner cloner) {
|
---|
86 | return new GQAPEvaluator(this, cloner);
|
---|
87 | }
|
---|
88 |
|
---|
89 | public static DoubleValue Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
|
---|
90 | DoubleMatrix installCosts, double transportCosts, DoubleArray demands, DoubleArray capacities,
|
---|
91 | out double infeasibility) {
|
---|
92 | double quality = 0;
|
---|
93 | int len = assignment.Length;
|
---|
94 | var slack = (DoubleArray)capacities.Clone();
|
---|
95 | for (int i = 0; i < len; i++) {
|
---|
96 | quality += installCosts[i, assignment[i]];
|
---|
97 | for (int j = 0; j < len; j++) {
|
---|
98 | quality += transportCosts * weights[i, j] * distances[assignment[i], assignment[j]];
|
---|
99 | }
|
---|
100 | slack[assignment[i]] -= demands[i];
|
---|
101 | }
|
---|
102 |
|
---|
103 | infeasibility = -slack.Where(x => x < 0).Sum();
|
---|
104 | return new DoubleValue(quality);
|
---|
105 | }
|
---|
106 |
|
---|
107 | public override IOperation Apply() {
|
---|
108 | IntegerVector assignment = AssignmentParameter.ActualValue;
|
---|
109 | DoubleMatrix weights = WeightsParameter.ActualValue;
|
---|
110 | DoubleMatrix distances = DistancesParameter.ActualValue;
|
---|
111 | DoubleMatrix installCosts = InstallationCostsParameter.ActualValue;
|
---|
112 | double transportCosts = TransportationCostsParameter.ActualValue.Value;
|
---|
113 | DoubleArray demands = DemandsParameter.ActualValue;
|
---|
114 | DoubleArray capacities = (DoubleArray)CapacitiesParameter.ActualValue.Clone();
|
---|
115 | double penalty = PenaltyParameter.ActualValue.Value;
|
---|
116 |
|
---|
117 | if (weights.Rows != weights.Columns || distances.Rows != distances.Columns
|
---|
118 | || weights.Rows != installCosts.Rows || distances.Rows != installCosts.Columns
|
---|
119 | || demands.Length != weights.Rows || capacities.Length != distances.Rows)
|
---|
120 | throw new InvalidOperationException("ERROR: The problem configuration is not valid! Check the sizes of the weights (NxN), distances (MxM) and installation costs (NxM) matrices as well as the length of the demand (N) and capacities (M) vectors.");
|
---|
121 |
|
---|
122 | double infeasibility;
|
---|
123 | var quality = Evaluate(assignment, weights, distances, installCosts, transportCosts, demands, capacities, out infeasibility);
|
---|
124 |
|
---|
125 | InfeasibilityParameter.ActualValue = new DoubleValue(infeasibility);
|
---|
126 | QualityParameter.ActualValue = new DoubleValue(quality.Value + penalty * infeasibility);
|
---|
127 | return base.Apply();
|
---|
128 | }
|
---|
129 | }
|
---|
130 | }
|
---|