Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPNMoveEvaluator.cs @ 7419

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

#1614

  • reworked parameterization (one interface for every parameter resp. parameter group)
  • unified parameter descriptions
File size: 13.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.Collections.Generic;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Encodings.IntegerVectorEncoding;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
34  [Item("GQAPNMoveEvaluator", "Evaluates an n-move.")]
35  [StorableClass]
36  public class GQAPNMoveEvaluator : SingleSuccessorOperator, IGQAPNMoveEvaluator, IAssignmentAwareGQAPOperator,
37  IQualityAwareGQAPOperator, ITransportationCostsAwareGQAPOperator,
38  IOverbookedCapacityPenaltyAwareGQAPOperator, IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator,
39  IInstallationCostsAwareGQAPOperator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator {
40
41    #region Parameter Descriptions
42    public static readonly string MoveQualityDescription = "The quality of the move if it would be applied.";
43    public static readonly string MoveFlowDistanceQualityDescription = "The quality of the move regarding the flow-distance criteria.";
44    public static readonly string MoveInstallationQualityDescription = "The quality of the move regarding the installation costs.";
45    public static readonly string MoveOverbookedCapacityDescription = "The sum of the overbooked capacities of the move relative to the capacity of each location.";
46    #endregion
47
48    #region Parameter Properties
49    ILookupParameter<BoolValue> IQualityAwareGQAPOperator.MaximizationParameter {
50      get { return MaximizationParameter; }
51    }
52    ILookupParameter<BoolValue> IGQAPMoveEvaluator.MaximizationParameter {
53      get { return MaximizationParameter; }
54    }
55    public ILookupParameter<BoolValue> MaximizationParameter {
56      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
57    }
58    public ILookupParameter<DoubleValue> MoveQualityParameter {
59      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
60    }
61    public ILookupParameter<DoubleValue> MoveFlowDistanceQualityParameter {
62      get { return (ILookupParameter<DoubleValue>)Parameters["MoveFlowDistanceQuality"]; }
63    }
64    public ILookupParameter<DoubleValue> MoveInstallationQualityParameter {
65      get { return (ILookupParameter<DoubleValue>)Parameters["MoveInstallationQuality"]; }
66    }
67    public ILookupParameter<DoubleValue> MoveOverbookedCapacityParameter {
68      get { return (ILookupParameter<DoubleValue>)Parameters["MoveOverbookedCapacity"]; }
69    }
70    public ILookupParameter<NMove> MoveParameter {
71      get { return (ILookupParameter<NMove>)Parameters["Move"]; }
72    }
73    public ILookupParameter<IntegerVector> AssignmentParameter {
74      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
75    }
76    ILookupParameter<DoubleValue> ISingleObjectiveMoveEvaluator.QualityParameter {
77      get { return QualityParameter; }
78    }
79    ILookupParameter<DoubleValue> IQualityAwareGQAPOperator.QualityParameter {
80      get { return QualityParameter; }
81    }
82    public ILookupParameter<DoubleValue> QualityParameter {
83      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
84    }
85    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
86      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
87    }
88    public ILookupParameter<DoubleValue> InstallationQualityParameter {
89      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
90    }
91    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
92      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
93    }
94    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
95      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
96    }
97    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
98      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
99    }
100    public ILookupParameter<DoubleMatrix> WeightsParameter {
101      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
102    }
103    public ILookupParameter<DoubleMatrix> DistancesParameter {
104      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
105    }
106    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
107      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
108    }
109    public ILookupParameter<DoubleArray> DemandsParameter {
110      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
111    }
112    public ILookupParameter<DoubleArray> CapacitiesParameter {
113      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
114    }
115    #endregion
116
117    [StorableConstructor]
118    protected GQAPNMoveEvaluator(bool deserializing) : base(deserializing) { }
119    protected GQAPNMoveEvaluator(GQAPNMoveEvaluator original, Cloner cloner) : base(original, cloner) { }
120    public GQAPNMoveEvaluator()
121      : base() {
122      Parameters.Add(new LookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
123      Parameters.Add(new LookupParameter<NMove>("Move", GQAPNMoveGenerator.MoveDescription));
124      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
125      Parameters.Add(new LookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
126      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
127      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
128      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
129      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", MoveQualityDescription));
130      Parameters.Add(new LookupParameter<DoubleValue>("MoveFlowDistanceQuality", MoveFlowDistanceQualityDescription));
131      Parameters.Add(new LookupParameter<DoubleValue>("MoveInstallationQuality", MoveInstallationQualityDescription));
132      Parameters.Add(new LookupParameter<DoubleValue>("MoveOverbookedCapacity", MoveOverbookedCapacityDescription));
133      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
134      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
135      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
136      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
137      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
138      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
139      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
140    }
141
142    public override IDeepCloneable Clone(Cloner cloner) {
143      return new GQAPNMoveEvaluator(this, cloner);
144    }
145
146    public static double Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
147      DoubleArray demands, DoubleArray capacities, DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
148      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
149      Evaluate(move, assignment, weights, distances, installationCosts, demands, capacities,
150        out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
151      return GQAPEvaluator.GetCombinedQuality(moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity,
152        transportationCosts.Value, overbookedCapacityPenalty.Value);
153    }
154
155    public static void Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
156      DoubleArray demands, DoubleArray capacities, out double moveFlowDistanceQuality, out double moveInstallationQuality, out double moveOverbookedCapacity) {
157      moveFlowDistanceQuality = moveInstallationQuality = moveOverbookedCapacity = 0.0;
158      int moves = move.N;
159      var slack = (DoubleArray)capacities.Clone();
160      var oldSlack = (DoubleArray)slack.Clone();
161      Dictionary<int, int> moving = new Dictionary<int, int>();
162      for (int i = 0; i < moves; i++) moving.Add(move.Equipments[i], move.Locations[i]);
163
164      for (int i = 0; i < moves; i++) {
165        int equip = move.Equipments[i];
166        int newLoc = move.Locations[i];
167        moveInstallationQuality -= installationCosts[equip, assignment[equip]];
168        moveInstallationQuality += installationCosts[equip, newLoc];
169        for (int j = 0; j < assignment.Length; j++) {
170          if (!moving.ContainsKey(j)) {
171            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, assignment[j]];
172            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
173            moveFlowDistanceQuality += weights[j, equip] * distances[assignment[j], newLoc];
174            moveFlowDistanceQuality -= weights[j, equip] * distances[assignment[j], assignment[equip]];
175            if (i == 0) { // only once for each untouched equipment deduct the demand from the capacity
176              slack[assignment[j]] -= demands[j];
177              oldSlack[assignment[j]] -= demands[j];
178            }
179          } else {
180            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, moving[j]];
181            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
182          }
183        }
184        slack[newLoc] -= demands[equip];
185        oldSlack[assignment[equip]] -= demands[equip];
186      }
187
188      moveOverbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum()
189                               - oldSlack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
190    }
191
192    public override IOperation Apply() {
193      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
194      double quality = QualityParameter.ActualValue.Value;
195      double transportationCosts = TransportationCostsParameter.ActualValue.Value;
196      double overbookedCapacityPenalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
197
198      double flowDistanceQuality = FlowDistanceQualityParameter.ActualValue.Value;
199      double installationQuality = InstallationQualityParameter.ActualValue.Value;
200      double overbookedCapacity = OverbookedCapacityParameter.ActualValue.Value;
201
202      Evaluate(MoveParameter.ActualValue,
203               AssignmentParameter.ActualValue,
204               WeightsParameter.ActualValue, DistancesParameter.ActualValue,
205               InstallationCostsParameter.ActualValue,
206               DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
207               out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
208
209      MoveFlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality + moveFlowDistanceQuality);
210      MoveInstallationQualityParameter.ActualValue = new DoubleValue(installationQuality + moveInstallationQuality);
211      MoveOverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity + moveOverbookedCapacity);
212
213      MoveQualityParameter.ActualValue = new DoubleValue(GQAPEvaluator.GetCombinedQuality(
214        flowDistanceQuality + moveFlowDistanceQuality,
215        installationQuality + moveInstallationQuality,
216        overbookedCapacity + moveOverbookedCapacity,
217        transportationCosts,
218        overbookedCapacityPenalty));
219      return base.Apply();
220    }
221  }
222}
Note: See TracBrowser for help on using the repository browser.