Changeset 7412 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/ApproximateLocalSearch.cs

Timestamp:

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

Author:

abeham

Message:

#1614: worked on GQAP and GRASP+PR

Location:

branches/GeneralizedQAP

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/ApproximateLocalSearch.cs (modified) (8 diffs)

branches/GeneralizedQAP

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

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

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/ApproximateLocalSearch.cs

@@ -55 +55 @@
       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 ILookupParameter<DoubleValue> InstallationQualityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
+    }
+    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
+      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
     }
     public ILookupParameter<ResultCollection> ResultsParameter {
@@ -79 +85 @@
       get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
     }
-    public ILookupParameter<DoubleValue> TransportationCostsParameter {
-      get { return (ILookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
-    }
     public ILookupParameter<DoubleArray> DemandsParameter {
       get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
@@ -88 +91 @@
       get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
     }
-
+    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
+    }
+    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
+    }
+    public IValueLookupParameter<PercentValue> OneMoveProbabilityParameter {
+      get { return (IValueLookupParameter<PercentValue>)Parameters["OneMoveProbability"]; }
+    }
 
     [StorableConstructor]
@@ -99 +110 @@
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solution equivalents."));
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The solution quality."));
-      Parameters.Add(new LookupParameter<DoubleValue>("Infeasibility", "The infeasibility describes the sum of the overbooked capacities."));
+      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 LookupParameter<ResultCollection>("Results", "The result collection that stores the results."));
       Parameters.Add(new ValueLookupParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
@@ -107 +120 @@
       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."));
+      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 matrix already."));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
+      Parameters.Add(new ValueLookupParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
     }
 
@@ -124 +139 @@
     /// <param name="assignment">The equipment-location assignment vector.</param>
     /// <param name="quality">The solution quality.</param>
-    /// <param name="infeasibility">The infeasibility describes the sum of the overbooked capacities.</param>
+    /// <param name="flowDistanceQuality">The quality regarding the flow-distance criteria.</param>
+    /// <param name="installationQuality">The quality regarding the installation costs.</param>
+    /// <param name="overbookedCapacity">The sum of the overbooked capacities relative to the capacity of each location.</param>
     /// <param name="maxCLS">The maximum number of candidates that should be found in each step.</param>
     /// <param name="maxSampleSize">The maximum number of candidates that should be sampled in each step.</param>
     /// <param name="maximumIterations">The maximum number of iterations that should be performed.</param>
-    /// <param name="demands">The demands vector describes the space requirements of the equipments.</param>
-    /// <param name="capacities">The capacities vector describes the available space at the locations.</param>
     /// <param name="weights">The weights matrix describes the flows between the equipments.</param>
     /// <param name="distances">The distances matrix describes the distances between the locations at which the equipment can be installed.</param>
     /// <param name="installationCosts">The installation costs matrix describes the installation costs of installing equipment i at location j</param>
+    /// <param name="demands">The demands vector describes the space requirements of the equipments.</param>
+    /// <param name="capacities">The capacities vector describes the available space at the locations.</param>
     /// <param name="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.</param>
-    public static void Apply(IRandom random, IntegerVector assignment, DoubleValue quality, DoubleValue infeasibility,
-                             IntValue maxCLS, IntValue maxSampleSize, IntValue maximumIterations,
-                             DoubleArray demands, DoubleArray capacities,
-                             DoubleMatrix weights, DoubleMatrix distances,
-                             DoubleMatrix installationCosts,
-                             DoubleValue transportationCosts) {
+    /// <param name="overbookedCapacityPenalty"></param>
+    /// <param name="oneMoveProbability">The probability for performing a 1-move, which is the opposite of performing a 2-move.</param>
+    public static void Apply(IRandom random, IntegerVector assignment,
+      DoubleValue quality, DoubleValue flowDistanceQuality, DoubleValue installationQuality, DoubleValue overbookedCapacity,
+      IntValue maxCLS, IntValue maxSampleSize, IntValue maximumIterations,
+      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleArray demands, DoubleArray capacities,
+      DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty, PercentValue oneMoveProbability) {
+
       for (int i = 0; i < maximumIterations.Value; i++) {
         int count = 0;
-        var CLS = new List<Tuple<NMove, DoubleValue, DoubleValue>>();
+        var CLS = new List<Tuple<NMove, double, double, double, double>>();
         double sum = 0.0;
         do {
-          var move = StochasticNMoveSingleMoveGenerator.Generate(random, assignment, 2, capacities);
-          DoubleValue moveInfeasibility;
-          var moveQuality = GQAPNMoveEvaluator.Evaluate(move, assignment, quality,
-            demands, capacities, weights, distances,
-            installationCosts, transportationCosts, out moveInfeasibility);
-          if (moveInfeasibility.Value <= 0.0 && moveQuality.Value < quality.Value) {
-            CLS.Add(Tuple.Create(move, moveQuality, moveInfeasibility));
-            sum += 1.0 / moveQuality.Value;
+          NMove move;
+          if (random.NextDouble() < oneMoveProbability.Value)
+            move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 1, capacities);
+          else move = StochasticNMoveSingleMoveGenerator.GenerateExactlyN(random, assignment, 2, capacities);
+
+          double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
+          GQAPNMoveEvaluator.Evaluate(move, assignment, weights, distances, installationCosts,
+            demands, capacities, out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
+          double moveQuality = GQAPEvaluator.GetCombinedQuality(moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity,
+            transportationCosts.Value, overbookedCapacityPenalty.Value);
+
+          if (moveOverbookedCapacity <= 0.0 && moveQuality < 0.0) {
+            CLS.Add(Tuple.Create(move, moveQuality, moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity));
+            sum += 1.0 / moveQuality;
           }
           count++;
         } while (CLS.Count < maxCLS.Value && count < maxSampleSize.Value);
-        if (CLS.Count == 0) return; // END
+
+        if (CLS.Count == 0)
+          return; // END
         else {
           var ball = random.NextDouble() * sum;
           var selected = CLS.Last();
           foreach (var candidate in CLS) {
-            ball -= 1.0 / candidate.Item2.Value;
+            ball -= 1.0 / candidate.Item2;
             if (ball <= 0.0) {
               selected = candidate;
@@ -168 +195 @@
           }
           NMoveMaker.Apply(assignment, selected.Item1);
-          quality.Value = selected.Item2.Value;
-          infeasibility.Value = selected.Item3.Value;
+          quality.Value += selected.Item2;
+          flowDistanceQuality.Value += selected.Item3;
+          installationQuality.Value += selected.Item4;
+          overbookedCapacity.Value += selected.Item5;
         }
       }
@@ -178 +207 @@
         AssignmentParameter.ActualValue,
         QualityParameter.ActualValue,
-        InfeasibilityParameter.ActualValue,
+        FlowDistanceQualityParameter.ActualValue,
+        InstallationQualityParameter.ActualValue,
+        OverbookedCapacityParameter.ActualValue,
         MaximumCandidateListSizeParameter.ActualValue,
         MaximumSampleSizeParameter.ActualValue,
         MaximumIterationsParameter.ActualValue,
-        DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
         WeightsParameter.ActualValue, DistancesParameter.ActualValue,
         InstallationCostsParameter.ActualValue,
-        TransportationCostsParameter.ActualValue);
+        DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
+        TransportationCostsParameter.ActualValue,
+        OverbookedCapacityPenaltyParameter.ActualValue,
+        OneMoveProbabilityParameter.ActualValue);
       return base.Apply();
     }

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