#region License Information
/* HeuristicLab
* Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
*
* This file is part of HeuristicLab.
*
* HeuristicLab is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* HeuristicLab is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with HeuristicLab. If not, see .
*/
#endregion
using System.Linq;
using HEAL.Attic;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Parameters;
namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
[Item("GQAP Instance", "Instance of a generalized quadratic assignment problem.")]
[StorableType("54208525-4EF6-404F-AF4A-52927104C563")]
public class GQAPInstance : ParameterizedNamedItem {
public static readonly string WeightsDescription = "The weights matrix describes the flows between the equipments.";
public static readonly string DistancesDescription = "The distances matrix describes the distances between the locations at which the equipment can be installed.";
public static readonly string InstallationCostsDescription = "The installation costs matrix describes the installation costs of installing equipment i at location j";
public static readonly string DemandsDescription = "The demands vector describes the space requirements of the equipments.";
public static readonly string CapacitiesDescription = "The capacities vector describes the available space at the locations.";
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.";
public static readonly string EquipmentNamesDescription = "Optional: A list of names that describes the equipments.";
public static readonly string LocationNamesDescription = "Optional: A list of names that describes the locations.";
public static readonly string PenaltyLevelDescription = "The quality that an infeasible solution cannot surpass.";
#region Parameter Properties
[Storable]
private ValueParameter weightsParam;
public IValueParameter WeightsParameter {
get { return weightsParam; }
}
[Storable]
private ValueParameter distancesParam;
public IValueParameter DistancesParameter {
get { return distancesParam; }
}
[Storable]
private ValueParameter installCostsParam;
public IValueParameter InstallationCostsParameter {
get { return installCostsParam; }
}
[Storable]
private ValueParameter demandsParam;
public IValueParameter DemandsParameter {
get { return demandsParam; }
}
[Storable]
private ValueParameter capacitiesParam;
public IValueParameter CapacitiesParameter {
get { return capacitiesParam; }
}
[Storable]
private FixedValueParameter transportationCostsParam;
public IFixedValueParameter TransportationCostsParameter {
get { return transportationCostsParam; }
}
[Storable]
private FixedValueParameter penaltyLevelParam;
public IFixedValueParameter PenaltyLevelParameter {
get { return penaltyLevelParam; }
}
[Storable]
private OptionalValueParameter equipmentNamesParam;
public OptionalValueParameter EquipmentNamesParameter {
get { return equipmentNamesParam; }
}
[Storable]
private OptionalValueParameter locationNamesParam;
public OptionalValueParameter LocationNamesParameter {
get { return locationNamesParam; }
}
#endregion
#region Properties
public DoubleMatrix Weights {
get { return WeightsParameter.Value; }
set { WeightsParameter.Value = value; }
}
public DoubleMatrix Distances {
get { return DistancesParameter.Value; }
set { DistancesParameter.Value = value; }
}
public DoubleMatrix InstallationCosts {
get { return InstallationCostsParameter.Value; }
set { InstallationCostsParameter.Value = value; }
}
public DoubleArray Demands {
get { return DemandsParameter.Value; }
set { DemandsParameter.Value = value; }
}
public DoubleArray Capacities {
get { return CapacitiesParameter.Value; }
set { CapacitiesParameter.Value = value; }
}
public double TransportationCosts {
get { return TransportationCostsParameter.Value.Value; }
set { TransportationCostsParameter.Value.Value = value; }
}
public double PenaltyLevel {
get { return PenaltyLevelParameter.Value.Value; }
set { PenaltyLevelParameter.Value.Value = value; }
}
public StringArray EquipmentNames {
get { return EquipmentNamesParameter.Value; }
set { EquipmentNamesParameter.Value = value; }
}
public StringArray LocationNames {
get { return LocationNamesParameter.Value; }
set { LocationNamesParameter.Value = value; }
}
#endregion
[StorableConstructor]
protected GQAPInstance(StorableConstructorFlag _) : base(_) { }
protected GQAPInstance(GQAPInstance original, Cloner cloner)
: base(original, cloner) {
weightsParam = cloner.Clone(original.weightsParam);
distancesParam = cloner.Clone(original.distancesParam);
installCostsParam = cloner.Clone(original.installCostsParam);
transportationCostsParam = cloner.Clone(original.transportationCostsParam);
penaltyLevelParam = cloner.Clone(original.penaltyLevelParam);
demandsParam = cloner.Clone(original.demandsParam);
capacitiesParam = cloner.Clone(original.capacitiesParam);
equipmentNamesParam = cloner.Clone(original.equipmentNamesParam);
locationNamesParam = cloner.Clone(original.locationNamesParam);
}
public GQAPInstance() {
Parameters.Add(weightsParam = new ValueParameter("Weights", WeightsDescription, new DoubleMatrix()) { GetsCollected = false });
Parameters.Add(distancesParam = new ValueParameter("Distances", DistancesDescription, new DoubleMatrix()) { GetsCollected = false });
Parameters.Add(installCostsParam = new ValueParameter("InstallationCosts", InstallationCostsDescription, new DoubleMatrix()) { GetsCollected = false });
Parameters.Add(transportationCostsParam = new FixedValueParameter("TransportationCosts", TransportationCostsDescription, new DoubleValue(1)));
Parameters.Add(penaltyLevelParam = new FixedValueParameter("PenaltyLevel", PenaltyLevelDescription, new DoubleValue(0)));
Parameters.Add(demandsParam = new ValueParameter("Demands", DemandsDescription, new DoubleArray()) { GetsCollected = false });
Parameters.Add(capacitiesParam = new ValueParameter("Capacities", CapacitiesDescription, new DoubleArray()) { GetsCollected = false });
Parameters.Add(equipmentNamesParam = new OptionalValueParameter("EquipmentNames", EquipmentNamesDescription, null) { GetsCollected = false });
Parameters.Add(locationNamesParam = new OptionalValueParameter("LocationNames", LocationNamesDescription, null) { GetsCollected = false });
weightsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
distancesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
installCostsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
demandsParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
capacitiesParam.ReactOnValueToStringChangedAndValueItemImageChanged = false;
Weights = new DoubleMatrix(5, 5);
Weights[0, 0] = Weights[1, 1] = Weights[2, 2] = Weights[3, 3] = Weights[4, 4] = 0;
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;
Weights[1, 2] = Weights[2, 1] = Weights[1, 3] = Weights[3, 1] = Weights[1, 4] = Weights[4, 1] = 5;
Weights[2, 3] = Weights[3, 2] = Weights[2, 4] = Weights[4, 2] = 7.5;
Weights[3, 4] = Weights[4, 3] = 2.5;
Distances = new DoubleMatrix(3, 3);
Distances[0, 0] = Distances[1, 1] = Distances[2, 2] = 0;
Distances[0, 1] = Distances[1, 0] = Distances[1, 2] = Distances[2, 1] = 1;
Distances[0, 2] = Distances[2, 0] = 2;
InstallationCosts = new DoubleMatrix(5, 3);
Demands = new DoubleArray(5);
Demands[0] = 2; Demands[1] = 1; Demands[2] = 3; Demands[3] = 1; Demands[4] = 1;
Capacities = new DoubleArray(3);
Capacities[0] = 4; Capacities[1] = 1; Capacities[2] = 4;
TransportationCosts = 1;
CalculatePenaltyLevel();
}
public override IDeepCloneable Clone(Cloner cloner) {
return new GQAPInstance(this, cloner);
}
public Evaluation Evaluate(IntegerVector assignment) {
var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
InstallationCosts, Weights, Distances);
return evaluation;
}
public double EvaluateSingleObjective(IntegerVector assignment) {
return ToSingleObjective(Evaluate(assignment));
}
public static Evaluation EvaluateIntegerVector(IntegerVector assignment,
DoubleArray demands, DoubleArray capacities, DoubleMatrix installCosts,
DoubleMatrix weights, DoubleMatrix distances) {
var flowDistanceQuality = 0.0;
var installationQuality = 0.0;
var overbookedCapacity = 0.0;
int len = assignment.Length;
var slack = capacities.ToArray();
for (int i = 0; i < len; i++) {
var assignI = assignment[i];
installationQuality += installCosts[i, assignI];
for (int j = 0; j < len; j++) {
flowDistanceQuality += weights[i, j] * distances[assignI, assignment[j]];
}
if (slack[assignI] < 0) overbookedCapacity += demands[i];
else if (slack[assignI] < demands[i]) overbookedCapacity += (demands[i] - slack[assignI]);
slack[assignI] -= demands[i];
}
return new Evaluation(flowDistanceQuality, installationQuality, overbookedCapacity, slack);
}
public GQAPSolution ToEvaluatedSolution(IntegerVector assignment) {
var evaluation = EvaluateIntegerVector(assignment, Demands, Capacities,
InstallationCosts, Weights, Distances);
return new GQAPSolution(assignment, evaluation);
}
public bool IsFeasible(IntegerVector assignment) {
int len = assignment.Length;
var utilization = new double[Capacities.Length];
for (var equip = 0; equip < len; equip++) {
var loc = assignment[equip];
utilization[loc] += Demands[equip];
if (utilization[loc] > Capacities[loc])
return false;
}
return true;
}
public double ToSingleObjective(Evaluation fitness) {
return fitness.IsFeasible
? fitness.InstallationCosts + TransportationCosts * fitness.FlowCosts
: PenaltyLevel + fitness.ExcessDemand;
}
public double[] ToMultiObjectiveStrict(Evaluation fitness) {
return fitness.IsFeasible
? new double[] { fitness.InstallationCosts, TransportationCosts * fitness.FlowCosts }
: new double[] { PenaltyLevel + fitness.ExcessDemand, PenaltyLevel + fitness.ExcessDemand };
}
public double[] ToMultiObjectiveRelaxed(Evaluation fitness) {
return new double[] {
fitness.InstallationCosts,
TransportationCosts * fitness.FlowCosts,
fitness.ExcessDemand };
}
public bool IsValid() {
return Weights != null && Distances != null && Demands != null && Capacities != null && InstallationCosts != null
&& Weights.Rows == Weights.Columns && Weights.Rows == InstallationCosts.Rows
&& Distances.Rows == Distances.Columns && Distances.Rows == InstallationCosts.Columns
&& Demands.Length == Weights.Rows && Capacities.Length == Distances.Rows;
}
public void CalculatePenaltyLevel() {
var flowQuality = Distances.Max() * Weights.Max() * Demands.Length * Demands.Length;
var installQuality = InstallationCosts.Max() * Demands.Length;
PenaltyLevel = installQuality + TransportationCosts * flowQuality;
}
}
}