source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs @ 7412

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
  [Item("GQAPEvaluator", "Evaluates solutions to the generalized quadratic assignment problem.")]
  [StorableClass]
  public class GQAPEvaluator : SingleSuccessorOperator, IGQAPEvaluator {

    public ILookupParameter<DoubleValue> QualityParameter {
      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
    }
    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 IValueLookupParameter<DoubleValue> TransportationCostsParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters["TransportationCosts"]; }
    }
    public IValueLookupParameter<DoubleValue> OverbookedCapacityPenaltyParameter {
      get { return (IValueLookupParameter<DoubleValue>)Parameters["OverbookedCapacityPenalty"]; }
    }
    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 ILookupParameter<DoubleArray> DemandsParameter {
      get { return (ILookupParameter<DoubleArray>)Parameters["Demands"]; }
    }
    public ILookupParameter<DoubleArray> CapacitiesParameter {
      get { return (ILookupParameter<DoubleArray>)Parameters["Capacities"]; }
    }
    public ILookupParameter<IntegerVector> AssignmentParameter {
      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
    }

    [StorableConstructor]
    protected GQAPEvaluator(bool deserializing) : base(deserializing) { }
    protected GQAPEvaluator(GQAPEvaluator original, Cloner cloner) : base(original, cloner) { }
    public GQAPEvaluator()
      : base() {
      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<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 LookupParameter<IntegerVector>("Assignment", "The vector that encodes the assignment."));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new GQAPEvaluator(this, cloner);
    }

    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++) {
        installationQuality += installCosts[i, assignment[i]];
        for (int j = 0; j < len; 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();
    }

    public static double GetCombinedQuality(double flowDistanceQuality, double installationQuality, double overbookedCapacity,
      double transportationCosts, double overbookedCapacityPenalty) {
      return installationQuality
        + transportationCosts * flowDistanceQuality
        + overbookedCapacityPenalty * overbookedCapacity;
    }

    public override IOperation Apply() {
      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
        || weights.Rows != installCosts.Rows || distances.Rows != installCosts.Columns
        || demands.Length != weights.Rows || capacities.Length != distances.Rows)
        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 flowDistanceQuality, installationQuality, overbookedCapacity;
      Evaluate(assignment, weights, distances, installCosts, demands, capacities,
        out flowDistanceQuality, out installationQuality, out overbookedCapacity);

      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();
    }
  }
}