#region License Information /* HeuristicLab * Copyright (C) 2002-2017 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 HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Parameters; using HeuristicLab.Persistence.Default.CompositeSerializers.Storable; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment { [Item("GQAP Instance", "Instance of a generalized quadratic assignment problem.")] [StorableClass] 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(bool deserializing) : base(deserializing) { } 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(), false)); Parameters.Add(distancesParam = new ValueParameter("Distances", DistancesDescription, new DoubleMatrix(), false)); Parameters.Add(installCostsParam = new ValueParameter("InstallationCosts", InstallationCostsDescription, new DoubleMatrix(), false)); Parameters.Add(transportationCostsParam = new FixedValueParameter("TransportationCosts", TransportationCostsDescription, new DoubleValue(1))); Parameters.Add(penaltyLevelParam = new FixedValueParameter("PenaltyLevel", PenaltyLevelDescription, new DoubleValue(0), true)); Parameters.Add(demandsParam = new ValueParameter("Demands", DemandsDescription, new DoubleArray(), false)); Parameters.Add(capacitiesParam = new ValueParameter("Capacities", CapacitiesDescription, new DoubleArray(), false)); Parameters.Add(equipmentNamesParam = new OptionalValueParameter("EquipmentNames", EquipmentNamesDescription, null, false)); Parameters.Add(locationNamesParam = new OptionalValueParameter("LocationNames", LocationNamesDescription, null, 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 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; } } }