Changeset 7423 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GQAPPathRelinking.cs

Timestamp:

01/27/12 16:32:30 (12 years ago)

Author:

abeham

Message:

#1614

• worked on path relinking operator

File:

• branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/GQAPPathRelinking.cs (modified) (3 diffs)

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

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Encodings.IntegerVectorEncoding;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
-  [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions.")]
+  [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions. It is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
   [StorableClass]
-  public class GQAPPathRelinking : GQAPCrossover {
+  public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator,
+  IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator, IInstallationCostsAwareGQAPOperator, ITransportationCostsAwareGQAPOperator,
+  IOverbookedCapacityPenaltyAwareGQAPOperator {
+
+    public ILookupParameter<BoolValue> MaximizationParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
+    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public IScopeTreeLookupParameter<DoubleValue> FlowDistanceQualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
+    }
+    public IScopeTreeLookupParameter<DoubleValue> InstallationQualityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
+    }
+    public IScopeTreeLookupParameter<DoubleValue> OverbookedCapacityParameter {
+      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
+    }
+    public ILookupParameter<DoubleArray> DemandsParameter {
+      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
+    }
+    public ILookupParameter<DoubleArray> CapacitiesParameter {
+      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
+    }
+    public ILookupParameter<DoubleMatrix> WeightsParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
+    }
+    public ILookupParameter<DoubleMatrix> DistancesParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
+    }
+    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
+    }
+    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
+    }
+    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
+      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
+    }
 
     [StorableConstructor]
@@ -36 +79 @@
     public GQAPPathRelinking()
       : base() {
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
+      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
+      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
+      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
     }
 
@@ -42 +97 @@
     }
 
+    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, ItemArray<DoubleValue> qualities, DoubleArray demands,
+      DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleValue transportationCosts,
+      DoubleValue overbookedCapacityPenalty) {
+      if (random == null) throw new ArgumentNullException("random", "No IRandom provider is given.");
+      if (parents == null || !parents.Any()) throw new ArgumentException("No parents given for path relinking.", "parents");
+      if (parents.Length != 2) throw new ArgumentException(String.Format("Two parents were expected for path relinking, but {0} was/were given.", parents.Length.ToString()), "parents");
+      if (parents[0].Length != parents[1].Length) throw new ArgumentException("The length of the parents is not equal.", "parents");
+      if (qualities == null || qualities.Length == 0) throw new ArgumentException("The qualities are not given.", "qualities");
+      if (qualities.Length != parents.Length) throw new ArgumentException(String.Format("There are a different number of parents ({0}) than quality values ({1})", parents.Length.ToString(), qualities.Length.ToString()));
+
+      var source = parents[0];
+      var target = parents[1];
+
+      var pi_prime = (IntegerVector)source.Clone();
+      var fix = new HashSet<int>();
+      var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
+      var phi = GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target);
+
+      while (phi.Any()) {
+        var B = new HashSet<IntegerVector>();
+        foreach (var v in phi) {
+          pi_prime[v] = target[v];
+          var pi2 = makeFeasible(pi_prime, v);
+
+          double flowDistanceQuality, installationQuality, overbookedCapacity;
+          GQAPEvaluator.Evaluate(pi2, weights, distances, installationCosts, demands, capacities,
+            out flowDistanceQuality, out installationQuality, out overbookedCapacity);
+        }
+      }
+
+      return pi_prime;
+    }
+
     protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents) {
-      throw new NotImplementedException();
+      return Apply(random, parents, QualityParameter.ActualValue, DemandsParameter.ActualValue,
+        CapacitiesParameter.ActualValue, WeightsParameter.ActualValue, DistancesParameter.ActualValue,
+        InstallationCostsParameter.ActualValue, TransportationCostsParameter.ActualValue,
+        OverbookedCapacityPenaltyParameter.ActualValue);
+    }
+
+    private static IntegerVector makeFeasible(IntegerVector assignment, int equipment) {
+      // TODO: implement
+      return assignment;
     }
   }