1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022018 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.Linq;


23  using HeuristicLab.Common;


24  using HeuristicLab.Core;


25  using HeuristicLab.Data;


26  using HeuristicLab.Encodings.IntegerVectorEncoding;


27  using HeuristicLab.Parameters;


28  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


29 


30  namespace 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 flowunit per distanceunit 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,


226  InstallationCosts, 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  }

