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

Last change on this file since 16712 was 16712, checked in by gkronber, 3 months ago

#2936: adapted branch to new persistence (works with HL trunk r16711)

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