Free cookie consent management tool by TermsFeed Policy Generator

Changeset 7423


Ignore:
Timestamp:
01/27/12 16:32:30 (13 years ago)
Author:
abeham
Message:

#1614

  • worked on path relinking operator
Location:
branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Analyzers/BestGQAPSolutionAnalyzer.cs

    r7419 r7423  
    113113    public BestGQAPSolutionAnalyzer()
    114114      : base() {
    115       Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
    116       Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances between the locations."));
    117       Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights between the equipments."));
    118       Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The cost of installing equipment x at location y."));
    119       Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands of the equipments."));
    120       Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities at the locations."));
    121       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."));
    122       Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
    123       Parameters.Add(new ScopeTreeLookupParameter<IntegerVector>("Assignment", "The GQAP solutions from which the best solution should be analyzed."));
    124       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the GQAP solutions which should be analyzed."));
    125       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", "The flow-distance qualities of the GQAP solutions which should be analyzed."));
    126       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", "The installation qualities of the GQAP solutions which should be analyzed."));
    127       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", "The overbooked capacities of the GQAP solutions which should be analyzed."));
    128       Parameters.Add(new LookupParameter<GQAPAssignment>("BestSolution", "The best GQAP solution."));
     115      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
     116      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
     117      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
     118      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
     119      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
     120      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
     121      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
     122      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
     123      Parameters.Add(new ScopeTreeLookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
     124      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
     125      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
     126      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
     127      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
     128      Parameters.Add(new LookupParameter<StringArray>("EquipmentNames", GeneralizedQuadraticAssignmentProblem.EquipmentNamesDescription));
     129      Parameters.Add(new LookupParameter<StringArray>("LocationNames", GeneralizedQuadraticAssignmentProblem.LocationNamesDescription));
     130      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", GeneralizedQuadraticAssignmentProblem.BestKnownQualityDescription));
     131      Parameters.Add(new LookupParameter<IntegerVector>("BestKnownSolution", GeneralizedQuadraticAssignmentProblem.BestKnownSolutionDescription));
     132      Parameters.Add(new LookupParameter<GQAPAssignment>("BestSolution", "The best GQAP solution found so far."));
    129133      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best GQAP solution should be stored."));
    130       Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this GQAP instance."));
    131       Parameters.Add(new LookupParameter<IntegerVector>("BestKnownSolution", "The best known solution of this GQAP instance."));
    132       Parameters.Add(new LookupParameter<StringArray>("EquipmentNames", "A list of names that describes the equipments."));
    133       Parameters.Add(new LookupParameter<StringArray>("LocationNames", "A list of names that describes the locations."));
    134134    }
    135135

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Analyzers/GQAPSolutionArchiveAnalyzer.cs

    r7419 r7423  
    9696      get { return (ILookupParameter<IntegerVector>)Parameters["BestKnownSolution"]; }
    9797    }
    98     public ILookupParameter<GQAPAssignment> BestSolutionParameter {
    99       get { return (ILookupParameter<GQAPAssignment>)Parameters["BestSolution"]; }
    100     }
    10198    public IValueLookupParameter<ResultCollection> ResultsParameter {
    10299      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
    … …  
    111108    public GQAPSolutionArchiveAnalyzer()
    112109      : base() {
    113       Parameters.Add(new LookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem."));
    114       Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances between the locations."));
    115       Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights between the equipments."));
    116       Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The cost of installing equipment x at location y."));
    117       Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands of the equipments."));
    118       Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities at the locations."));
    119       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."));
    120       Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
    121       Parameters.Add(new ScopeTreeLookupParameter<IntegerVector>("Assignment", "The GQAP solutions from which the best solution should be analyzed."));
    122       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The qualities of the GQAP solutions which should be analyzed."));
    123       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", "The flow-distance qualities of the GQAP solutions which should be analyzed."));
    124       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", "The installation qualities of the GQAP solutions which should be analyzed."));
    125       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", "The overbooked capacities of the GQAP solutions which should be analyzed."));
    126       Parameters.Add(new LookupParameter<GQAPAssignment>("BestSolution", "The best GQAP solution."));
     110      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
     111      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
     112      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
     113      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
     114      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
     115      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
     116      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
     117      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
     118      Parameters.Add(new ScopeTreeLookupParameter<IntegerVector>("Assignment", GQAPSolutionCreator.AssignmentDescription));
     119      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
     120      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
     121      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
     122      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
     123      Parameters.Add(new LookupParameter<StringArray>("EquipmentNames", GeneralizedQuadraticAssignmentProblem.EquipmentNamesDescription));
     124      Parameters.Add(new LookupParameter<StringArray>("LocationNames", GeneralizedQuadraticAssignmentProblem.LocationNamesDescription));
     125      Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", GeneralizedQuadraticAssignmentProblem.BestKnownQualityDescription));
     126      Parameters.Add(new LookupParameter<IntegerVector>("BestKnownSolution", GeneralizedQuadraticAssignmentProblem.BestKnownSolutionDescription));
    127127      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the best GQAP solution should be stored."));
    128       Parameters.Add(new LookupParameter<DoubleValue>("BestKnownQuality", "The quality of the best known solution of this GQAP instance."));
    129       Parameters.Add(new LookupParameter<IntegerVector>("BestKnownSolution", "The best known solution of this GQAP instance."));
    130       Parameters.Add(new LookupParameter<StringArray>("EquipmentNames", "A list of names that describes the equipments."));
    131       Parameters.Add(new LookupParameter<StringArray>("LocationNames", "A list of names that describes the locations."));
    132128    }
    133129

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAPIntegerVectorProximityCalculator.cs

    r7412 r7423  
    2020#endregion
    2121
     22using System.Collections.Generic;
    2223using HeuristicLab.Encodings.IntegerVectorEncoding;
    2324
    … …  
    3536      return 1.0 - CalculateGenotypeSimilarity(a, b);
    3637    }
     38
     39    public static IEnumerable<int> GetDifference(IntegerVector a, IntegerVector b) {
     40      for (int i = 0; i < a.Length; i++)
     41        if (a[i] != b[i]) yield return i;
     42    }
    3743  }
    3844}

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GeneralizedQuadraticAssignmentProblem.cs

    r7419 r7423  
    5353    public static readonly string TransportationCostsDescription = "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.";
    5454    public static readonly string OverbookedCapacityPenaltyDescription = "The multiplier for the constraint violation when added to the quality.";
    55     public static readonly string BestKnownSolutionDescription = "The best known solution (if available)";
     55    public static readonly string BestKnownQualityDescription = "The best known quality (if available).";
     56    public static readonly string BestKnownSolutionDescription = "The best known solution (if available).";
    5657    public static readonly string EquipmentNamesDescription = "Optional: A list of names that describes the equipments.";
    5758    public static readonly string LocationNamesDescription = "Optional: A list of names that describes the locations.";

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

    r7419 r7423  
    2121
    2222using System;
     23using System.Collections.Generic;
     24using System.Linq;
    2325using HeuristicLab.Common;
    2426using HeuristicLab.Core;
     27using HeuristicLab.Data;
    2528using HeuristicLab.Encodings.IntegerVectorEncoding;
     29using HeuristicLab.Parameters;
    2630using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2731
    2832namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
    29   [Item("GQAPPathRelinking", "Operator that performs path relinking between two solutions.")]
     33  [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.")]
    3034  [StorableClass]
    31   public class GQAPPathRelinking : GQAPCrossover {
     35  public class GQAPPathRelinking : GQAPCrossover, IQualitiesAwareGQAPOperator, IDemandsAwareGQAPOperator, ICapacitiesAwareGQAPOperator,
     36  IWeightsAwareGQAPOperator, IDistancesAwareGQAPOperator, IInstallationCostsAwareGQAPOperator, ITransportationCostsAwareGQAPOperator,
     37  IOverbookedCapacityPenaltyAwareGQAPOperator {
     38
     39    public ILookupParameter<BoolValue> MaximizationParameter {
     40      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
     41    }
     42    public IScopeTreeLookupParameter<DoubleValue> QualityParameter {
     43      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
     44    }
     45    public IScopeTreeLookupParameter<DoubleValue> FlowDistanceQualityParameter {
     46      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
     47    }
     48    public IScopeTreeLookupParameter<DoubleValue> InstallationQualityParameter {
     49      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
     50    }
     51    public IScopeTreeLookupParameter<DoubleValue> OverbookedCapacityParameter {
     52      get { return (IScopeTreeLookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
     53    }
     54    public ILookupParameter<DoubleArray> DemandsParameter {
     55      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
     56    }
     57    public ILookupParameter<DoubleArray> CapacitiesParameter {
     58      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
     59    }
     60    public ILookupParameter<DoubleMatrix> WeightsParameter {
     61      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
     62    }
     63    public ILookupParameter<DoubleMatrix> DistancesParameter {
     64      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
     65    }
     66    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
     67      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
     68    }
     69    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
     70      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
     71    }
     72    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
     73      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
     74    }
    3275
    3376    [StorableConstructor]
    … …  
    3679    public GQAPPathRelinking()
    3780      : base() {
     81      Parameters.Add(new LookupParameter<BoolValue>("Maximization", GeneralizedQuadraticAssignmentProblem.MaximizationDescription));
     82      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", GQAPEvaluator.QualityDescription));
     83      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("FlowDistanceQuality", GQAPEvaluator.FlowDistanceQualityDescription));
     84      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("InstallationQuality", GQAPEvaluator.InstallationQualityDescription));
     85      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("OverbookedCapacity", GQAPEvaluator.OverbookedCapacityDescription));
     86      Parameters.Add(new LookupParameter<DoubleArray>("Demands", GeneralizedQuadraticAssignmentProblem.DemandsDescription));
     87      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", GeneralizedQuadraticAssignmentProblem.CapacitiesDescription));
     88      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", GeneralizedQuadraticAssignmentProblem.WeightsDescription));
     89      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", GeneralizedQuadraticAssignmentProblem.DistancesDescription));
     90      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", GeneralizedQuadraticAssignmentProblem.InstallationCostsDescription));
     91      Parameters.Add(new ValueLookupParameter<DoubleValue>("TransportationCosts", GeneralizedQuadraticAssignmentProblem.TransportationCostsDescription));
     92      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", GeneralizedQuadraticAssignmentProblem.OverbookedCapacityPenaltyDescription));
    3893    }
    3994
    … …  
    4297    }
    4398
     99    public static IntegerVector Apply(IRandom random, ItemArray<IntegerVector> parents, ItemArray<DoubleValue> qualities, DoubleArray demands,
     100      DoubleArray capacities, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts, DoubleValue transportationCosts,
     101      DoubleValue overbookedCapacityPenalty) {
     102      if (random == null) throw new ArgumentNullException("random", "No IRandom provider is given.");
     103      if (parents == null || !parents.Any()) throw new ArgumentException("No parents given for path relinking.", "parents");
     104      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");
     105      if (parents[0].Length != parents[1].Length) throw new ArgumentException("The length of the parents is not equal.", "parents");
     106      if (qualities == null || qualities.Length == 0) throw new ArgumentException("The qualities are not given.", "qualities");
     107      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()));
     108
     109      var source = parents[0];
     110      var target = parents[1];
     111
     112      var pi_prime = (IntegerVector)source.Clone();
     113      var fix = new HashSet<int>();
     114      var nonFix = new HashSet<int>(Enumerable.Range(0, demands.Length));
     115      var phi = GQAPIntegerVectorProximityCalculator.GetDifference(pi_prime, target);
     116
     117      while (phi.Any()) {
     118        var B = new HashSet<IntegerVector>();
     119        foreach (var v in phi) {
     120          pi_prime[v] = target[v];
     121          var pi2 = makeFeasible(pi_prime, v);
     122
     123          double flowDistanceQuality, installationQuality, overbookedCapacity;
     124          GQAPEvaluator.Evaluate(pi2, weights, distances, installationCosts, demands, capacities,
     125            out flowDistanceQuality, out installationQuality, out overbookedCapacity);
     126        }
     127      }
     128
     129      return pi_prime;
     130    }
     131
    44132    protected override IntegerVector Cross(IRandom random, ItemArray<IntegerVector> parents) {
    45       throw new NotImplementedException();
     133      return Apply(random, parents, QualityParameter.ActualValue, DemandsParameter.ActualValue,
     134        CapacitiesParameter.ActualValue, WeightsParameter.ActualValue, DistancesParameter.ActualValue,
     135        InstallationCostsParameter.ActualValue, TransportationCostsParameter.ActualValue,
     136        OverbookedCapacityPenaltyParameter.ActualValue);
     137    }
     138
     139    private static IntegerVector makeFeasible(IntegerVector assignment, int equipment) {
     140      // TODO: implement
     141      return assignment;
    46142    }
    47143  }
Note: See TracChangeset for help on using the changeset viewer.