Changeset 7412 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs

Timestamp:

01/25/12 18:32:44 (12 years ago)

Author:

abeham

Message:

#1614: worked on GQAP and GRASP+PR

Location:

branches/GeneralizedQAP

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs (modified) (5 diffs)

branches/GeneralizedQAP

@@ -1 +1 @@
 *.suo
+TestResults

@@ -1 +1 @@
 *.suo
+TestResults

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs

@@ -38 +38 @@
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
     }
-    public ILookupParameter<DoubleValue> InfeasibilityParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["Infeasibility"]; }
+    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
     }
-    public IValueLookupParameter<DoubleValue> PenaltyParameter {
-      get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
+    public ILookupParameter<DoubleValue> InstallationQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
+    }
+    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
+    }
+    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
+    }
+    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
     }
     public ILookupParameter<DoubleMatrix> WeightsParameter {
@@ -52 +61 @@
     public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
       get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
-    }
-    public ILookupParameter<DoubleValue> TransportationCostsParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
     }
     public ILookupParameter<DoubleArray> DemandsParameter {
@@ -71 +77 @@
     public GQAPEvaluator()
       : base() {
-      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality a.k.a. fitness of the solution."));
-      Parameters.Add(new LookupParameter<DoubleValue>("Infeasibility", "The infeasibility describes the sum of the overbooked capacities."));
-      Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty", "The multiplier for the constraint violation when added to the quality.", new DoubleValue(1000)));
+      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the solution."));
+      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", "The quality regarding the flow-distance criteria."));
+      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", "The quality regarding the installation costs."));
+      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", "The sum of the overbooked capacities relative to the capacity of each location."));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", "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 or distance matrix already."));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix describes the flows between the equipments."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix describes the distances between the locations at which the equipment can be installed."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The installation costs matrix describes the installation costs of installing equipment i at location j"));
-      Parameters.Add(new LookupParameter<DoubleValue>("TransportationCosts", "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."));
       Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands vector describes the space requirements of the equipments."));
       Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities vector describes the available space at the locations."));
@@ -87 +95 @@
     }
 
-    public static DoubleValue Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
-      DoubleMatrix installCosts, double transportCosts, DoubleArray demands, DoubleArray capacities,
-      out double infeasibility) {
-      double quality = 0;
+    public static double Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
+                                  DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
+                                  DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
+      double flowDistanceQuality, installationQuality, overbookedCapacity;
+      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
+        out flowDistanceQuality, out installationQuality, out overbookedCapacity);
+      return GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity,
+        transportationCosts.Value, overbookedCapacityPenalty.Value);
+    }
+
+    public static void Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
+                                DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
+                                out double flowDistanceQuality, out double installationQuality, out double overbookedCapacity) {
+      flowDistanceQuality = 0;
+      installationQuality = 0;
       int len = assignment.Length;
       var slack = (DoubleArray)capacities.Clone();
       for (int i = 0; i < len; i++) {
-        quality += installCosts[i, assignment[i]];
+        installationQuality += installCosts[i, assignment[i]];
         for (int j = 0; j < len; j++) {
-          quality += transportCosts * weights[i, j] * distances[assignment[i], assignment[j]];
+          flowDistanceQuality += weights[i, j] * distances[assignment[i], assignment[j]];
         }
         slack[assignment[i]] -= demands[i];
       }
+      overbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
+    }
 
-      infeasibility = -slack.Where(x => x < 0).Sum();
-      return new DoubleValue(quality);
+    public static double GetCombinedQuality(double flowDistanceQuality, double installationQuality, double overbookedCapacity,
+      double transportationCosts, double overbookedCapacityPenalty) {
+      return installationQuality
+        + transportationCosts * flowDistanceQuality
+        + overbookedCapacityPenalty * overbookedCapacity;
     }
 
     public override IOperation Apply() {
-      IntegerVector assignment = AssignmentParameter.ActualValue;
-      DoubleMatrix weights = WeightsParameter.ActualValue;
-      DoubleMatrix distances = DistancesParameter.ActualValue;
-      DoubleMatrix installCosts = InstallationCostsParameter.ActualValue;
-      double transportCosts = TransportationCostsParameter.ActualValue.Value;
-      DoubleArray demands = DemandsParameter.ActualValue;
-      DoubleArray capacities = (DoubleArray)CapacitiesParameter.ActualValue.Clone();
-      double penalty = PenaltyParameter.ActualValue.Value;
+      var assignment = AssignmentParameter.ActualValue;
+      var weights = WeightsParameter.ActualValue;
+      var distances = DistancesParameter.ActualValue;
+      var installCosts = InstallationCostsParameter.ActualValue;
+      var demands = DemandsParameter.ActualValue;
+      var capacities = CapacitiesParameter.ActualValue;
+      var transportCosts = TransportationCostsParameter.ActualValue.Value;
+      double penalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
 
       if (weights.Rows != weights.Columns || distances.Rows != distances.Columns
@@ -120 +144 @@
         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.");
 
-      double infeasibility;
-      var quality = Evaluate(assignment, weights, distances, installCosts, transportCosts, demands, capacities, out infeasibility);
+      double flowDistanceQuality, installationQuality, overbookedCapacity;
+      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
+        out flowDistanceQuality, out installationQuality, out overbookedCapacity);
 
-      InfeasibilityParameter.ActualValue = new DoubleValue(infeasibility);
-      QualityParameter.ActualValue = new DoubleValue(quality.Value + penalty * infeasibility);
+      FlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality);
+      InstallationQualityParameter.ActualValue = new DoubleValue(installationQuality);
+      OverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity);
+
+      QualityParameter.ActualValue = new DoubleValue(GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity, transportCosts, penalty));
       return base.Apply();
     }

@@ -1 +1 @@
 *.suo
+TestResults