source: branches/2936_GQAPIntegration/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPInstance.cs @ 16077

Last change on this file since 16077 was 16077, checked in by abeham, 12 months ago

#2936: Added integration branch

File size: 12.8 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.Linq;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.IntegerVectorEncoding;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29
30namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
31  [Item("GQAP Instance", "Instance of a generalized quadratic assignment problem.")]
32  [StorableClass]
33  public class GQAPInstance : ParameterizedNamedItem {
34    public static readonly string WeightsDescription = "The weights matrix describes the flows between the equipments.";
35    public static readonly string DistancesDescription = "The distances matrix describes the distances between the locations at which the equipment can be installed.";
36    public static readonly string InstallationCostsDescription = "The installation costs matrix describes the installation costs of installing equipment i at location j";
37    public static readonly string DemandsDescription = "The demands vector describes the space requirements of the equipments.";
38    public static readonly string CapacitiesDescription = "The capacities vector describes the available space at the locations.";
39    public static readonly string TransportationCostsDescription = "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.";
40    public static readonly string EquipmentNamesDescription = "Optional: A list of names that describes the equipments.";
41    public static readonly string LocationNamesDescription = "Optional: A list of names that describes the locations.";
42    public static readonly string PenaltyLevelDescription = "The quality that an infeasible solution cannot surpass.";
43
44
45    #region Parameter Properties
46    [Storable]
47    private ValueParameter<DoubleMatrix> weightsParam;
48    public IValueParameter<DoubleMatrix> WeightsParameter {
49      get { return weightsParam; }
50    }
51    [Storable]
52    private ValueParameter<DoubleMatrix> distancesParam;
53    public IValueParameter<DoubleMatrix> DistancesParameter {
54      get { return distancesParam; }
55    }
56    [Storable]
57    private ValueParameter<DoubleMatrix> installCostsParam;
58    public IValueParameter<DoubleMatrix> InstallationCostsParameter {
59      get { return installCostsParam; }
60    }
61    [Storable]
62    private ValueParameter<DoubleArray> demandsParam;
63    public IValueParameter<DoubleArray> DemandsParameter {
64      get { return demandsParam; }
65    }
66    [Storable]
67    private ValueParameter<DoubleArray> capacitiesParam;
68    public IValueParameter<DoubleArray> CapacitiesParameter {
69      get { return capacitiesParam; }
70    }
71    [Storable]
72    private FixedValueParameter<DoubleValue> transportationCostsParam;
73    public IFixedValueParameter<DoubleValue> TransportationCostsParameter {
74      get { return transportationCostsParam; }
75    }
76    [Storable]
77    private FixedValueParameter<DoubleValue> penaltyLevelParam;
78    public IFixedValueParameter<DoubleValue> PenaltyLevelParameter {
79      get { return penaltyLevelParam; }
80    }
81    [Storable]
82    private OptionalValueParameter<StringArray> equipmentNamesParam;
83    public OptionalValueParameter<StringArray> EquipmentNamesParameter {
84      get { return equipmentNamesParam; }
85    }
86    [Storable]
87    private OptionalValueParameter<StringArray> locationNamesParam;
88    public OptionalValueParameter<StringArray> LocationNamesParameter {
89      get { return locationNamesParam; }
90    }
91    #endregion
92
93    #region Properties
94    public DoubleMatrix Weights {
95      get { return WeightsParameter.Value; }
96      set { WeightsParameter.Value = value; }
97    }
98    public DoubleMatrix Distances {
99      get { return DistancesParameter.Value; }
100      set { DistancesParameter.Value = value; }
101    }
102    public DoubleMatrix InstallationCosts {
103      get { return InstallationCostsParameter.Value; }
104      set { InstallationCostsParameter.Value = value; }
105    }
106    public DoubleArray Demands {
107      get { return DemandsParameter.Value; }
108      set { DemandsParameter.Value = value; }
109    }
110    public DoubleArray Capacities {
111      get { return CapacitiesParameter.Value; }
112      set { CapacitiesParameter.Value = value; }
113    }
114    public double TransportationCosts {
115      get { return TransportationCostsParameter.Value.Value; }
116      set { TransportationCostsParameter.Value.Value = value; }
117    }
118    public double PenaltyLevel {
119      get { return PenaltyLevelParameter.Value.Value; }
120      set { PenaltyLevelParameter.Value.Value = value; }
121    }
122    public StringArray EquipmentNames {
123      get { return EquipmentNamesParameter.Value; }
124      set { EquipmentNamesParameter.Value = value; }
125    }
126    public StringArray LocationNames {
127      get { return LocationNamesParameter.Value; }
128      set { LocationNamesParameter.Value = value; }
129    }
130    #endregion
131
132    [StorableConstructor]
133    protected GQAPInstance(bool deserializing) : base(deserializing) { }
134    protected GQAPInstance(GQAPInstance original, Cloner cloner)
135      : base(original, cloner) {
136      weightsParam = cloner.Clone(original.weightsParam);
137      distancesParam = cloner.Clone(original.distancesParam);
138      installCostsParam = cloner.Clone(original.installCostsParam);
139      transportationCostsParam = cloner.Clone(original.transportationCostsParam);
140      penaltyLevelParam = cloner.Clone(original.penaltyLevelParam);
141      demandsParam = cloner.Clone(original.demandsParam);
142      capacitiesParam = cloner.Clone(original.capacitiesParam);
143      equipmentNamesParam = cloner.Clone(original.equipmentNamesParam);
144      locationNamesParam = cloner.Clone(original.locationNamesParam);
145    }
146    public GQAPInstance() {
147      Parameters.Add(weightsParam = new ValueParameter<DoubleMatrix>("Weights", WeightsDescription, new DoubleMatrix(), false));
148      Parameters.Add(distancesParam = new ValueParameter<DoubleMatrix>("Distances", DistancesDescription, new DoubleMatrix(), false));
149      Parameters.Add(installCostsParam = new ValueParameter<DoubleMatrix>("InstallationCosts", InstallationCostsDescription, new DoubleMatrix(), false));
150      Parameters.Add(transportationCostsParam = new FixedValueParameter<DoubleValue>("TransportationCosts", TransportationCostsDescription, new DoubleValue(1)));
151      Parameters.Add(penaltyLevelParam = new FixedValueParameter<DoubleValue>("PenaltyLevel", PenaltyLevelDescription, new DoubleValue(0), true));
152      Parameters.Add(demandsParam = new ValueParameter<DoubleArray>("Demands", DemandsDescription, new DoubleArray(), false));
153      Parameters.Add(capacitiesParam = new ValueParameter<DoubleArray>("Capacities", CapacitiesDescription, new DoubleArray(), false));
154      Parameters.Add(equipmentNamesParam = new OptionalValueParameter<StringArray>("EquipmentNames", EquipmentNamesDescription, null, false));
155      Parameters.Add(locationNamesParam = new OptionalValueParameter<StringArray>("LocationNames", LocationNamesDescription, null, false));
156
157      weightsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
158      distancesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
159      installCostsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
160      demandsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
161      capacitiesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
162
163      Weights = new DoubleMatrix(5, 5);
164      Weights[0, 0] = Weights[1, 1] = Weights[2, 2] = Weights[3, 3] = Weights[4, 4] = 0;
165      Weights[0, 1] = Weights[1, 0] = Weights[0, 2] = Weights[2, 0] = Weights[0, 3] = Weights[3, 0] = Weights[0, 4] = Weights[4, 0] = 10;
166      Weights[1, 2] = Weights[2, 1] = Weights[1, 3] = Weights[3, 1] = Weights[1, 4] = Weights[4, 1] = 5;
167      Weights[2, 3] = Weights[3, 2] = Weights[2, 4] = Weights[4, 2] = 7.5;
168      Weights[3, 4] = Weights[4, 3] = 2.5;
169
170      Distances = new DoubleMatrix(3, 3);
171      Distances[0, 0] = Distances[1, 1] = Distances[2, 2] = 0;
172      Distances[0, 1] = Distances[1, 0] = Distances[1, 2] = Distances[2, 1] = 1;
173      Distances[0, 2] = Distances[2, 0] = 2;
174
175      InstallationCosts = new DoubleMatrix(5, 3);
176
177      Demands = new DoubleArray(5);
178      Demands[0] = 2; Demands[1] = 1; Demands[2] = 3; Demands[3] = 1; Demands[4] = 1;
179
180      Capacities = new DoubleArray(3);
181      Capacities[0] = 4; Capacities[1] = 1; Capacities[2] = 4;
182
183      TransportationCosts = 1;
184
185      CalculatePenaltyLevel();
186    }
187
188    public override IDeepCloneable Clone(Cloner cloner) {
189      return new GQAPInstance(this, cloner);
190    }
191
192    public Evaluation Evaluate(IntegerVector assignment) {
193      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
194        InstallationCosts, Weights, Distances);
195      return evaluation;
196    }
197
198    public double EvaluateSingleObjective(IntegerVector assignment) {
199      return ToSingleObjective(Evaluate(assignment));
200    }
201
202    public static Evaluation EvaluateIntegerVector(IntegerVector assignment,
203      DoubleArray demands, DoubleArray capacities, DoubleMatrix installCosts,
204      DoubleMatrix weights, DoubleMatrix distances) {
205      var flowDistanceQuality = 0.0;
206      var installationQuality = 0.0;
207      var overbookedCapacity = 0.0;
208      int len = assignment.Length;
209      var slack = capacities.ToArray();
210
211      for (int i = 0; i < len; i++) {
212        var assignI = assignment[i];
213        installationQuality += installCosts[i, assignI];
214        for (int j = 0; j < len; j++) {
215          flowDistanceQuality += weights[i, j] * distances[assignI, assignment[j]];
216        }
217        if (slack[assignI] < 0) overbookedCapacity += demands[i];
218        else if (slack[assignI] < demands[i]) overbookedCapacity += (demands[i] - slack[assignI]);
219        slack[assignI] -= demands[i];
220      }
221      return new Evaluation(flowDistanceQuality, installationQuality, overbookedCapacity, slack);
222    }
223
224    public GQAPSolution ToEvaluatedSolution(IntegerVector assignment) {
225      var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
226InstallationCosts, Weights, Distances);
227      return new GQAPSolution(assignment, evaluation);
228    }
229
230    public bool IsFeasible(IntegerVector assignment) {
231      int len = assignment.Length;
232      var utilization = new double[Capacities.Length];
233      for (var equip = 0; equip < len; equip++) {
234        var loc = assignment[equip];
235        utilization[loc] += Demands[equip];
236        if (utilization[loc] > Capacities[loc])
237          return false;
238      }
239      return true;
240    }
241
242    public double ToSingleObjective(Evaluation fitness) {
243      return fitness.IsFeasible
244        ? fitness.InstallationCosts + TransportationCosts * fitness.FlowCosts
245        : PenaltyLevel + fitness.ExcessDemand;
246    }
247
248    public double[] ToMultiObjectiveStrict(Evaluation fitness) {
249      return fitness.IsFeasible
250        ? new double[] { fitness.InstallationCosts, TransportationCosts * fitness.FlowCosts }
251        : new double[] { PenaltyLevel + fitness.ExcessDemand, PenaltyLevel + fitness.ExcessDemand };
252    }
253
254    public double[] ToMultiObjectiveRelaxed(Evaluation fitness) {
255      return new double[] {
256        fitness.InstallationCosts,
257        TransportationCosts * fitness.FlowCosts,
258        fitness.ExcessDemand };
259    }
260
261    public bool IsValid() {
262      return Weights != null && Distances != null && Demands != null && Capacities != null && InstallationCosts != null
263        && Weights.Rows == Weights.Columns && Weights.Rows == InstallationCosts.Rows
264        && Distances.Rows == Distances.Columns && Distances.Rows == InstallationCosts.Columns
265        && Demands.Length == Weights.Rows && Capacities.Length == Distances.Rows;
266    }
267
268    public void CalculatePenaltyLevel() {
269      var flowQuality = Distances.Max() * Weights.Max() * Demands.Length * Demands.Length;
270      var installQuality = InstallationCosts.Max() * Demands.Length;
271      PenaltyLevel = installQuality + TransportationCosts * flowQuality;
272    }
273  }
274}
Note: See TracBrowser for help on using the repository browser.