| 1 | #region License Information
|
|---|
| 2 | /* HeuristicLab
|
|---|
| 3 | * Copyright (C) 2002-2012 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;
|
|---|
| 23 | using System.Linq;
|
|---|
| 24 | using HeuristicLab.Common;
|
|---|
| 25 | using HeuristicLab.Core;
|
|---|
| 26 | using HeuristicLab.Data;
|
|---|
| 27 | using HeuristicLab.Encodings.IntegerVectorEncoding;
|
|---|
| 28 | using HeuristicLab.Operators;
|
|---|
| 29 | using HeuristicLab.Parameters;
|
|---|
| 30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
|---|
| 31 |
|
|---|
| 32 | namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
|
|---|
| 33 | [Item("GQAPEvaluator", "Evaluates solutions to the generalized quadratic assignment problem.")]
|
|---|
| 34 | [StorableClass]
|
|---|
| 35 | public class GQAPEvaluator : SingleSuccessorOperator, IGQAPEvaluator,
|
|---|
| 36 | IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator, IInstallationCostsAwareGQAPOperator,
|
|---|
| 37 | IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator, IAssignmentAwareGQAPOperator {
|
|---|
| 38 |
|
|---|
| 39 | #region Parameter Descriptions
|
|---|
| 40 | public static readonly string QualityDescription = "The quality of the solution.";
|
|---|
| 41 | public static readonly string FlowDistanceQualityDescription = "The quality regarding the flow-distance criteria.";
|
|---|
| 42 | public static readonly string InstallationQualityDescription = "The quality regarding the installation costs.";
|
|---|
| 43 | public static readonly string OverbookedCapacityDescription = "The sum of the overbooked capacities relative to the capacity of each location.";
|
|---|
| 44 | #endregion
|
|---|
| 45 |
|
|---|
| 46 | public ILookupParameter<BoolValue> MaximizationParameter {
|
|---|
| 47 | get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
|
|---|
| 48 | }
|
|---|
| 49 | public ILookupParameter<DoubleValue> QualityParameter {
|
|---|
| 50 | get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
|
|---|
| 51 | }
|
|---|
| 52 | public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
|
|---|
| 53 | get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
|
|---|
| 54 | }
|
|---|
| 55 | public ILookupParameter<DoubleValue> InstallationQualityParameter {
|
|---|
| 56 | get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
|
|---|
| 57 | }
|
|---|
| 58 | public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
|
|---|
| 59 | get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
|
|---|
| 60 | }
|
|---|
| 61 | public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
|
|---|
| 62 | get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
|
|---|
| 63 | }
|
|---|
| 64 | public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
|
|---|
| 65 | get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
|
|---|
| 66 | }
|
|---|
| 67 | public ILookupParameter<DoubleMatrix> WeightsParameter {
|
|---|
| 68 | get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
|
|---|
| 69 | }
|
|---|
| 70 | public ILookupParameter<DoubleMatrix> DistancesParameter {
|
|---|
| 71 | get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
|
|---|
| 72 | }
|
|---|
| 73 | public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
|
|---|
| 74 | get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
|
|---|
| 75 | }
|
|---|
| 76 | public ILookupParameter<DoubleArray> DemandsParameter {
|
|---|
| 77 | get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
|
|---|
| 78 | }
|
|---|
| 79 | public ILookupParameter<DoubleArray> CapacitiesParameter {
|
|---|
| 80 | get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
|
|---|
| 81 | }
|
|---|
| 82 | public ILookupParameter<IntegerVector> AssignmentParameter {
|
|---|
| 83 | get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
|
|---|
| 84 | }
|
|---|
| 85 |
|
|---|
| 86 | [StorableConstructor]
|
|---|
| 87 | protected GQAPEvaluator(bool deserializing) : base(deserializing) { }
|
|---|
| 88 | protected GQAPEvaluator(GQAPEvaluator original, Cloner cloner) : base(original, cloner) { }
|
|---|
| 89 | public GQAPEvaluator()
|
|---|
| 90 | : base() {
|
|---|
| 91 | Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
|
|---|
| 92 | Parameters.Add(new LookupParameter<DoubleValue>("Quality", QualityDescription));
|
|---|
| 93 | Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", FlowDistanceQualityDescription));
|
|---|
| 94 | Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", InstallationQualityDescription));
|
|---|
| 95 | Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", OverbookedCapacityDescription));
|
|---|
| 96 | Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
|
|---|
| 97 | Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
|
|---|
| 98 | Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
|
|---|
| 99 | Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
|
|---|
| 100 | Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
|
|---|
| 101 | Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
|
|---|
| 102 | Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
|
|---|
| 103 | Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
|
|---|
| 104 | }
|
|---|
| 105 |
|
|---|
| 106 | public override IDeepCloneable Clone(Cloner cloner) {
|
|---|
| 107 | return new GQAPEvaluator(this, cloner);
|
|---|
| 108 | }
|
|---|
| 109 |
|
|---|
| 110 | public static double Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
|
|---|
| 111 | DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
|
|---|
| 112 | DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
|
|---|
| 113 | double flowDistanceQuality, installationQuality, overbookedCapacity;
|
|---|
| 114 | Evaluate(assignment, weights, distances, installCosts, demands, capacities,
|
|---|
| 115 | out flowDistanceQuality, out installationQuality, out overbookedCapacity);
|
|---|
| 116 | return GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity,
|
|---|
| 117 | transportationCosts.Value, overbookedCapacityPenalty.Value);
|
|---|
| 118 | }
|
|---|
| 119 |
|
|---|
| 120 | public static void Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
|
|---|
| 121 | DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
|
|---|
| 122 | out double flowDistanceQuality, out double installationQuality, out double overbookedCapacity) {
|
|---|
| 123 | flowDistanceQuality = 0;
|
|---|
| 124 | installationQuality = 0;
|
|---|
| 125 | int len = assignment.Length;
|
|---|
| 126 | var slack = (DoubleArray)capacities.Clone();
|
|---|
| 127 | for (int i = 0; i < len; i++) {
|
|---|
| 128 | installationQuality += installCosts[i, assignment[i]];
|
|---|
| 129 | for (int j = 0; j < len; j++) {
|
|---|
| 130 | flowDistanceQuality += weights[i, j] * distances[assignment[i], assignment[j]];
|
|---|
| 131 | }
|
|---|
| 132 | slack[assignment[i]] -= demands[i];
|
|---|
| 133 | }
|
|---|
| 134 | overbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
|
|---|
| 135 | }
|
|---|
| 136 |
|
|---|
| 137 | public static double GetCombinedQuality(double flowDistanceQuality, double installationQuality, double overbookedCapacity,
|
|---|
| 138 | double transportationCosts, double overbookedCapacityPenalty) {
|
|---|
| 139 | return installationQuality
|
|---|
| 140 | + transportationCosts * flowDistanceQuality
|
|---|
| 141 | + overbookedCapacityPenalty * overbookedCapacity;
|
|---|
| 142 | }
|
|---|
| 143 |
|
|---|
| 144 | public override IOperation Apply() {
|
|---|
| 145 | var assignment = AssignmentParameter.ActualValue;
|
|---|
| 146 | var weights = WeightsParameter.ActualValue;
|
|---|
| 147 | var distances = DistancesParameter.ActualValue;
|
|---|
| 148 | var installCosts = InstallationCostsParameter.ActualValue;
|
|---|
| 149 | var demands = DemandsParameter.ActualValue;
|
|---|
| 150 | var capacities = CapacitiesParameter.ActualValue;
|
|---|
| 151 | var transportCosts = TransportationCostsParameter.ActualValue.Value;
|
|---|
| 152 | double penalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
|
|---|
| 153 |
|
|---|
| 154 | if (weights.Rows != weights.Columns || distances.Rows != distances.Columns
|
|---|
| 155 | || weights.Rows != installCosts.Rows || distances.Rows != installCosts.Columns
|
|---|
| 156 | || demands.Length != weights.Rows || capacities.Length != distances.Rows)
|
|---|
| 157 | throw new InvalidOperationException("ERROR: The problem configuration is not valid! Check the sizes of the weights (NxN), distances (MxM) and installation costs (NxM) matrices as well as the length of the demand (N) and capacities (M) vectors.");
|
|---|
| 158 |
|
|---|
| 159 | double flowDistanceQuality, installationQuality, overbookedCapacity;
|
|---|
| 160 | Evaluate(assignment, weights, distances, installCosts, demands, capacities,
|
|---|
| 161 | out flowDistanceQuality, out installationQuality, out overbookedCapacity);
|
|---|
| 162 |
|
|---|
| 163 | FlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality);
|
|---|
| 164 | InstallationQualityParameter.ActualValue = new DoubleValue(installationQuality);
|
|---|
| 165 | OverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity);
|
|---|
| 166 |
|
|---|
| 167 | QualityParameter.ActualValue = new DoubleValue(GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity, transportCosts, penalty));
|
|---|
| 168 | return base.Apply();
|
|---|
| 169 | }
|
|---|
| 170 | }
|
|---|
| 171 | }
|
|---|
