Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs @ 7593

Last change on this file since 7593 was 7593, checked in by abeham, 12 years ago

#1614

  • Investigation in different solution creator that result in feasible solutions even for 95% fill level instances
  • Added option for all solution creators to produce the least infeasible solution if no feasible solution could be found
  • Added maximum tries parameter to all creators
File size: 10.0 KB
Line 
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
22using System;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31
32namespace 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 = EvaluateOverbooking(slack, capacities);
135    }
136
137    public static double EvaluateOverbooking(DoubleArray slack, DoubleArray capacities) {
138      return slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
139    }
140
141    public static double GetCombinedQuality(double flowDistanceQuality, double installationQuality, double overbookedCapacity,
142      double transportationCosts, double overbookedCapacityPenalty) {
143      return installationQuality
144        + transportationCosts * flowDistanceQuality
145        + overbookedCapacityPenalty * overbookedCapacity;
146    }
147
148    public override IOperation Apply() {
149      var assignment = AssignmentParameter.ActualValue;
150      var weights = WeightsParameter.ActualValue;
151      var distances = DistancesParameter.ActualValue;
152      var installCosts = InstallationCostsParameter.ActualValue;
153      var demands = DemandsParameter.ActualValue;
154      var capacities = CapacitiesParameter.ActualValue;
155      var transportCosts = TransportationCostsParameter.ActualValue.Value;
156      double penalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
157
158      if (weights.Rows != weights.Columns || distances.Rows != distances.Columns
159        || weights.Rows != installCosts.Rows || distances.Rows != installCosts.Columns
160        || demands.Length != weights.Rows || capacities.Length != distances.Rows)
161        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.");
162
163      double flowDistanceQuality, installationQuality, overbookedCapacity;
164      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
165        out flowDistanceQuality, out installationQuality, out overbookedCapacity);
166
167      FlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality);
168      InstallationQualityParameter.ActualValue = new DoubleValue(installationQuality);
169      OverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity);
170
171      QualityParameter.ActualValue = new DoubleValue(GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity, transportCosts, penalty));
172      return base.Apply();
173    }
174  }
175}
Note: See TracBrowser for help on using the repository browser.