Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
01/25/12 18:32:44 (13 years ago)
Author:
abeham
Message:

#1614: worked on GQAP and GRASP+PR

Location:
branches/GeneralizedQAP
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • branches/GeneralizedQAP

    • Property svn:ignore

      •  

        old new  
        11*.suo
         2TestResults

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

    r7407 r7412  
    3838      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    3939    }
    40     public ILookupParameter<DoubleValue> InfeasibilityParameter {
    41       get { return (ILookupParameter<DoubleValue>)Parameters["Infeasibility"]; }
     40    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
     41      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
    4242    }
    43     public IValueLookupParameter<DoubleValue> PenaltyParameter {
    44       get { return (IValueLookupParameter<DoubleValue>)Parameters["Penalty"]; }
     43    public ILookupParameter<DoubleValue> InstallationQualityParameter {
     44      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
     45    }
     46    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
     47      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
     48    }
     49    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
     50      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
     51    }
     52    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
     53      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
    4554    }
    4655    public ILookupParameter<DoubleMatrix> WeightsParameter {
    … …  
    5261    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
    5362      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
    54     }
    55     public ILookupParameter<DoubleValue> TransportationCostsParameter {
    56       get { return (ILookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
    5763    }
    5864    public ILookupParameter<DoubleArray> DemandsParameter {
    … …  
    7177    public GQAPEvaluator()
    7278      : base() {
    73       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality a.k.a. fitness of the solution."));
    74       Parameters.Add(new LookupParameter<DoubleValue>("Infeasibility", "The infeasibility describes the sum of the overbooked capacities."));
    75       Parameters.Add(new ValueLookupParameter<DoubleValue>("Penalty", "The multiplier for the constraint violation when added to the quality.", new DoubleValue(1000)));
     79      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of the solution."));
     80      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", "The quality regarding the flow-distance criteria."));
     81      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", "The quality regarding the installation costs."));
     82      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", "The sum of the overbooked capacities relative to the capacity of each location."));
     83      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."));
     84      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
    7685      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix describes the flows between the equipments."));
    7786      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix describes the distances between the locations at which the equipment can be installed."));
    7887      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The installation costs matrix describes the installation costs of installing equipment i at location j"));
    79       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."));
    8088      Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands vector describes the space requirements of the equipments."));
    8189      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities vector describes the available space at the locations."));
    … …  
    8795    }
    8896
    89     public static DoubleValue Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
    90       DoubleMatrix installCosts, double transportCosts, DoubleArray demands, DoubleArray capacities,
    91       out double infeasibility) {
    92       double quality = 0;
     97    public static double Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
     98                                  DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
     99                                  DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
     100      double flowDistanceQuality, installationQuality, overbookedCapacity;
     101      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
     102        out flowDistanceQuality, out installationQuality, out overbookedCapacity);
     103      return GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity,
     104        transportationCosts.Value, overbookedCapacityPenalty.Value);
     105    }
     106
     107    public static void Evaluate(IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances,
     108                                DoubleMatrix installCosts, DoubleArray demands, DoubleArray capacities,
     109                                out double flowDistanceQuality, out double installationQuality, out double overbookedCapacity) {
     110      flowDistanceQuality = 0;
     111      installationQuality = 0;
    93112      int len = assignment.Length;
    94113      var slack = (DoubleArray)capacities.Clone();
    95114      for (int i = 0; i < len; i++) {
    96         quality += installCosts[i, assignment[i]];
     115        installationQuality += installCosts[i, assignment[i]];
    97116        for (int j = 0; j < len; j++) {
    98           quality += transportCosts * weights[i, j] * distances[assignment[i], assignment[j]];
     117          flowDistanceQuality += weights[i, j] * distances[assignment[i], assignment[j]];
    99118        }
    100119        slack[assignment[i]] -= demands[i];
    101120      }
     121      overbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
     122    }
    102123
    103       infeasibility = -slack.Where(x => x < 0).Sum();
    104       return new DoubleValue(quality);
     124    public static double GetCombinedQuality(double flowDistanceQuality, double installationQuality, double overbookedCapacity,
     125      double transportationCosts, double overbookedCapacityPenalty) {
     126      return installationQuality
     127        + transportationCosts * flowDistanceQuality
     128        + overbookedCapacityPenalty * overbookedCapacity;
    105129    }
    106130
    107131    public override IOperation Apply() {
    108       IntegerVector assignment = AssignmentParameter.ActualValue;
    109       DoubleMatrix weights = WeightsParameter.ActualValue;
    110       DoubleMatrix distances = DistancesParameter.ActualValue;
    111       DoubleMatrix installCosts = InstallationCostsParameter.ActualValue;
    112       double transportCosts = TransportationCostsParameter.ActualValue.Value;
    113       DoubleArray demands = DemandsParameter.ActualValue;
    114       DoubleArray capacities = (DoubleArray)CapacitiesParameter.ActualValue.Clone();
    115       double penalty = PenaltyParameter.ActualValue.Value;
     132      var assignment = AssignmentParameter.ActualValue;
     133      var weights = WeightsParameter.ActualValue;
     134      var distances = DistancesParameter.ActualValue;
     135      var installCosts = InstallationCostsParameter.ActualValue;
     136      var demands = DemandsParameter.ActualValue;
     137      var capacities = CapacitiesParameter.ActualValue;
     138      var transportCosts = TransportationCostsParameter.ActualValue.Value;
     139      double penalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
    116140
    117141      if (weights.Rows != weights.Columns || distances.Rows != distances.Columns
    … …  
    120144        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.");
    121145
    122       double infeasibility;
    123       var quality = Evaluate(assignment, weights, distances, installCosts, transportCosts, demands, capacities, out infeasibility);
     146      double flowDistanceQuality, installationQuality, overbookedCapacity;
     147      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
     148        out flowDistanceQuality, out installationQuality, out overbookedCapacity);
    124149
    125       InfeasibilityParameter.ActualValue = new DoubleValue(infeasibility);
    126       QualityParameter.ActualValue = new DoubleValue(quality.Value + penalty * infeasibility);
     150      FlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality);
     151      InstallationQualityParameter.ActualValue = new DoubleValue(installationQuality);
     152      OverbookedCapacityParameter.ActualValue = new DoubleValue(overbookedCapacity);
     153
     154      QualityParameter.ActualValue = new DoubleValue(GetCombinedQuality(flowDistanceQuality, installationQuality, overbookedCapacity, transportCosts, penalty));
    127155      return base.Apply();
    128156    }

  • branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPNMoveEvaluator.cs

    r7407 r7412  
    4444      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    4545    }
     46    public ILookupParameter<DoubleValue> FlowDistanceQualityParameter {
     47      get { return (ILookupParameter<DoubleValue>)Parameters["FlowDistanceQuality"]; }
     48    }
     49    public ILookupParameter<DoubleValue> InstallationQualityParameter {
     50      get { return (ILookupParameter<DoubleValue>)Parameters["InstallationQuality"]; }
     51    }
     52    public ILookupParameter<DoubleValue> OverbookedCapacityParameter {
     53      get { return (ILookupParameter<DoubleValue>)Parameters["OverbookedCapacity"]; }
     54    }
    4655    public ILookupParameter<DoubleValue> MoveQualityParameter {
    4756      get { return (ILookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
    4857    }
    49     public ILookupParameter<DoubleValue> MoveInfeasibilityParameter {
    50       get { return (ILookupParameter<DoubleValue>)Parameters["MoveInfeasibility"]; }
     58    public ILookupParameter<DoubleValue> MoveFlowDistanceQualityParameter {
     59      get { return (ILookupParameter<DoubleValue>)Parameters["MoveFlowDistanceQuality"]; }
     60    }
     61    public ILookupParameter<DoubleValue> MoveInstallationQualityParameter {
     62      get { return (ILookupParameter<DoubleValue>)Parameters["MoveInstallationQuality"]; }
     63    }
     64    public ILookupParameter<DoubleValue> MoveOverbookedCapacityParameter {
     65      get { return (ILookupParameter<DoubleValue>)Parameters["MoveOverbookedCapacity"]; }
     66    }
     67    public IValueLookupParameter<DoubleValue> TransportationCostsParameter {
     68      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
     69    }
     70    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
     71      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
    5172    }
    5273    public ILookupParameter<DoubleMatrix> WeightsParameter {
    … …  
    5879    public ILookupParameter<DoubleMatrix> InstallationCostsParameter {
    5980      get { return (ILookupParameter<DoubleMatrix>)Parameters["InstallationCosts"]; }
    60     }
    61     public ILookupParameter<DoubleValue> TransportationCostsParameter {
    62       get { return (ILookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
    6381    }
    6482    public ILookupParameter<DoubleArray> DemandsParameter {
    … …  
    7795      Parameters.Add(new LookupParameter<NMove>("Move", "The move to perform."));
    7896      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The solution quality."));
     97      Parameters.Add(new LookupParameter<DoubleValue>("FlowDistanceQuality", "The quality regarding the flow-distance criteria."));
     98      Parameters.Add(new LookupParameter<DoubleValue>("InstallationQuality", "The quality regarding the installation costs."));
     99      Parameters.Add(new LookupParameter<DoubleValue>("OverbookedCapacity", "The sum of the overbooked capacities relative to the capacity of each location."));
    79100      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The quality of the move if it would be applied."));
    80       Parameters.Add(new LookupParameter<DoubleValue>("MoveInfeasibility", "The infeasibility of the move if it would be applied."));
     101      Parameters.Add(new LookupParameter<DoubleValue>("MoveFlowDistanceQuality", "The quality of the move regarding the flow-distance criteria."));
     102      Parameters.Add(new LookupParameter<DoubleValue>("MoveInstallationQuality", "The quality of the move regarding the installation costs."));
     103      Parameters.Add(new LookupParameter<DoubleValue>("MoveOverbookedCapacity", "The sum of the overbooked capacities of the move relative to the capacity of each location."));
     104      Parameters.Add(new ValueLookupParameter<DoubleValue>("OverbookedCapacityPenalty", "The multiplier for the constraint violation when added to the quality."));
     105      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."));
    81106      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix describes the flows between the equipments."));
    82107      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix describes the distances between the locations at which the equipment can be installed."));
    83108      Parameters.Add(new LookupParameter<DoubleMatrix>("InstallationCosts", "The installation costs matrix describes the installation costs of installing equipment i at location j"));
    84       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."));
    85109      Parameters.Add(new LookupParameter<DoubleArray>("Demands", "The demands vector describes the space requirements of the equipments."));
    86110      Parameters.Add(new LookupParameter<DoubleArray>("Capacities", "The capacities vector describes the available space at the locations."));
    … …  
    91115    }
    92116
    93     public static DoubleValue Evaluate(NMove move, IntegerVector assignment, DoubleValue quality,
    94                                   DoubleArray demands, DoubleArray capacities,
    95                                   DoubleMatrix weights, DoubleMatrix distances,
    96                                   DoubleMatrix installationCosts,
    97                                   DoubleValue transportationCosts,
    98                                   out DoubleValue moveInfeasibility) {
    99       double moveQuality = quality.Value;
     117    public static double Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
     118      DoubleArray demands, DoubleArray capacities, DoubleValue transportationCosts, DoubleValue overbookedCapacityPenalty) {
     119      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
     120      Evaluate(move, assignment, weights, distances, installationCosts, demands, capacities,
     121        out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
     122      return GQAPEvaluator.GetCombinedQuality(moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity,
     123        transportationCosts.Value, overbookedCapacityPenalty.Value);
     124    }
     125
     126    public static void Evaluate(NMove move, IntegerVector assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
     127      DoubleArray demands, DoubleArray capacities, out double moveFlowDistanceQuality, out double moveInstallationQuality, out double moveOverbookedCapacity) {
     128      moveFlowDistanceQuality = moveInstallationQuality = moveOverbookedCapacity = 0.0;
    100129      int moves = move.N;
    101130      var slack = (DoubleArray)capacities.Clone();
     131      var oldSlack = (DoubleArray)slack.Clone();
    102132      Dictionary<int, int> moving = new Dictionary<int, int>();
    103133      for (int i = 0; i < moves; i++) moving.Add(move.Equipments[i], move.Locations[i]);
    … …  
    106136        int equip = move.Equipments[i];
    107137        int newLoc = move.Locations[i];
    108         moveQuality -= installationCosts[equip, assignment[equip]];
    109         moveQuality += installationCosts[equip, newLoc];
     138        moveInstallationQuality -= installationCosts[equip, assignment[equip]];
     139        moveInstallationQuality += installationCosts[equip, newLoc];
    110140        for (int j = 0; j < assignment.Length; j++) {
    111141          if (!moving.ContainsKey(j)) {
    112             moveQuality += transportationCosts.Value * weights[equip, j] * (distances[newLoc, assignment[j]] - distances[assignment[equip], assignment[j]]);
    113             moveQuality += transportationCosts.Value * weights[j, equip] * (distances[assignment[j], newLoc] - distances[assignment[j], assignment[equip]]);
     142            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, assignment[j]];
     143            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
     144            moveFlowDistanceQuality += weights[j, equip] * distances[assignment[j], newLoc];
     145            moveFlowDistanceQuality -= weights[j, equip] * distances[assignment[j], assignment[equip]];
    114146            if (i == 0) { // only once for each untouched equipment deduct the demand from the capacity
    115147              slack[assignment[j]] -= demands[j];
     148              oldSlack[assignment[j]] -= demands[j];
    116149            }
    117150          } else {
    118             moveQuality += transportationCosts.Value * weights[equip, j] * (distances[newLoc, moving[j]] - distances[assignment[equip], assignment[j]]);
    119             moveQuality += transportationCosts.Value * weights[j, equip] * (distances[moving[j], newLoc] - distances[assignment[j], assignment[equip]]);
     151            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, moving[j]];
     152            moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
    120153          }
    121154        }
    122155        slack[newLoc] -= demands[equip];
     156        oldSlack[assignment[equip]] -= demands[equip];
    123157      }
    124158
    125       moveInfeasibility = new DoubleValue(-slack.Where(x => x < 0).Sum());
    126       return new DoubleValue(moveQuality);
    127 
     159      moveOverbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum()
     160                               - oldSlack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
    128161    }
    129162
    130163    public override IOperation Apply() {
    131       DoubleValue moveInfeasibility;
    132       MoveQualityParameter.ActualValue = Evaluate(MoveParameter.ActualValue,
    133                  AssignmentParameter.ActualValue, QualityParameter.ActualValue,
    134                  DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
    135                  WeightsParameter.ActualValue, DistancesParameter.ActualValue,
    136                  InstallationCostsParameter.ActualValue,
    137                  TransportationCostsParameter.ActualValue, out moveInfeasibility);
    138       MoveInfeasibilityParameter.ActualValue = moveInfeasibility;
     164      double moveFlowDistanceQuality, moveInstallationQuality, moveOverbookedCapacity;
     165      double quality = QualityParameter.ActualValue.Value;
     166      double transportationCosts = TransportationCostsParameter.ActualValue.Value;
     167      double overbookedCapacityPenalty = OverbookedCapacityPenaltyParameter.ActualValue.Value;
     168
     169      double flowDistanceQuality = FlowDistanceQualityParameter.ActualValue.Value;
     170      double installationQuality = InstallationQualityParameter.ActualValue.Value;
     171      double overbookedCapacity = OverbookedCapacityParameter.ActualValue.Value;
     172
     173      Evaluate(MoveParameter.ActualValue,
     174               AssignmentParameter.ActualValue,
     175               WeightsParameter.ActualValue, DistancesParameter.ActualValue,
     176               InstallationCostsParameter.ActualValue,
     177               DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
     178               out moveFlowDistanceQuality, out moveInstallationQuality, out moveOverbookedCapacity);
     179
     180      MoveFlowDistanceQualityParameter.ActualValue = new DoubleValue(flowDistanceQuality + moveFlowDistanceQuality);
     181      MoveInstallationQualityParameter.ActualValue = new DoubleValue(installationQuality + moveInstallationQuality);
     182      MoveOverbookedCapacityParameter.ActualValue = new DoubleValue(moveOverbookedCapacity);
     183
     184      MoveQualityParameter.ActualValue = new DoubleValue(GQAPEvaluator.GetCombinedQuality(
     185        flowDistanceQuality + moveFlowDistanceQuality,
     186        installationQuality + moveInstallationQuality,
     187        moveOverbookedCapacity,
     188        transportationCosts,
     189        overbookedCapacityPenalty));
    139190      return base.Apply();
    140191    }
Note: See TracChangeset for help on using the changeset viewer.