source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/ApproximateLocalSearch.cs @ 7413

#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.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Operators;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Operators {
  [Item("ApproximateLocalSearch", @"The approximate local search 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.

The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to the maxItr parameter defined by Mateus et al.")]
  [StorableClass]
  public class ApproximateLocalSearch : SingleSuccessorOperator, IGQAPLocalImprovementOperator, IStochasticOperator {
    public IProblem Problem { get; set; }
    public Type ProblemType {
      get { return typeof(GeneralizedQuadraticAssignmentProblem); }
    }

    public ILookupParameter<IRandom> RandomParameter {
      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
    }
    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
    }
    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
    }
    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 ILookupParameter<ResultCollection> ResultsParameter {
      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
    }
    public IValueLookupParameter<IntValue> MaximumCandidateListSizeParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumCandidateListSize"]; }
    }
    public IValueLookupParameter<IntValue> MaximumSampleSizeParameter {
      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumSampleSize"]; }
    }
    public ILookupParameter<IntegerVector> AssignmentParameter {
      get { return (ILookupParameter<IntegerVector>)Parameters["Assignment"]; }
    }
    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 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]
    protected ApproximateLocalSearch(bool deserializing) : base(deserializing) { }
    protected ApproximateLocalSearch(ApproximateLocalSearch original, Cloner cloner) : base(original, cloner) { }
    public ApproximateLocalSearch()
      : base() {
      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations that should be performed."));
      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>("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)));
      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumSampleSize", "The maximum number of candidates that should be sampled in each step.", new IntValue(100)));
      Parameters.Add(new LookupParameter<IntegerVector>("Assignment", "The equipment-location assignment vector."));
      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 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)));
    }

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

    /// <summary>
    /// The implementation differs slightly from Mateus et al. in that the maximumIterations parameter defines a cap
    /// on the number of steps that the local search can perform. While the maxSampleSize parameter corresponds to
    /// the maxItr parameter defined by Mateus et al.
    /// </summary>
    /// <param name="random">The random number generator to use.</param>
    /// <param name="assignment">The equipment-location assignment vector.</param>
    /// <param name="quality">The solution quality.</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="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>
    /// <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, double, double, double, double>>();
        double sum = 0.0;
        do {
          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
        else {
          var ball = random.NextDouble() * sum;
          var selected = CLS.Last();
          foreach (var candidate in CLS) {
            ball -= 1.0 / candidate.Item2;
            if (ball <= 0.0) {
              selected = candidate;
              break;
            }
          }
          NMoveMaker.Apply(assignment, selected.Item1);
          quality.Value += selected.Item2;
          flowDistanceQuality.Value += selected.Item3;
          installationQuality.Value += selected.Item4;
          overbookedCapacity.Value += selected.Item5;
        }
      }
    }

    public override IOperation Apply() {
      Apply(RandomParameter.ActualValue,
        AssignmentParameter.ActualValue,
        QualityParameter.ActualValue,
        FlowDistanceQualityParameter.ActualValue,
        InstallationQualityParameter.ActualValue,
        OverbookedCapacityParameter.ActualValue,
        MaximumCandidateListSizeParameter.ActualValue,
        MaximumSampleSizeParameter.ActualValue,
        MaximumIterationsParameter.ActualValue,
        WeightsParameter.ActualValue, DistancesParameter.ActualValue,
        InstallationCostsParameter.ActualValue,
        DemandsParameter.ActualValue, CapacitiesParameter.ActualValue,
        TransportationCostsParameter.ActualValue,
        OverbookedCapacityPenaltyParameter.ActualValue,
        OneMoveProbabilityParameter.ActualValue);
      return base.Apply();
    }
  }
}