source: branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/GQAP.cs @ 17485

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 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 HEAL.Attic;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Optimization.Operators;
using HeuristicLab.Parameters;
using HeuristicLab.PluginInfrastructure;
using HeuristicLab.Problems.Instances;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
  [Item("Generalized Quadratic Assignment Problem (GQAP)", "The Generalized Quadratic Assignment Problem (GQAP) is a generalization of the QAP in that it allows to assign multiple facilities (here called equipment) to a single location. The problem is described in Lee, C.G., and Ma, Z. 2003. The Generalized Quadratic Assignment Problem. Technical Report M5S 3G8, University of Toronto, Canada.")]
  [Creatable(CreatableAttribute.Categories.CombinatorialProblems)]
  [StorableType("20DC9B2F-F667-425E-A235-B0192CCB1BF4")]
  public sealed class GQAP : SingleObjectiveBasicProblem<IntegerVectorEncoding>,
    IProblemInstanceConsumer<QAPData>,
    IProblemInstanceConsumer<CTAPData>,
    IProblemInstanceConsumer<TSPData>,
    IProblemInstanceConsumer<ATSPData>,
    IProblemInstanceConsumer<GQAPData> {

    public override bool Maximization { get { return false; } }

    [Storable]
    private bool initialized; // ABE: helper variable that defines if the constructor has completed

    #region Parameter Descriptions
    public static readonly string BestKnownQualityDescription = "The best known quality (if available).";
    public static readonly string BestKnownSolutionDescription = "The best known solution (if available).";
    public static readonly string BestKnownSolutionsDescription = "Contains an archive of best-known solutions regarding flow-distance quality and installation quality.";
    public static readonly string ProblemInstanceDescription = "The problem instance that is to be solved.";
    public static readonly string EvaluationDescription = "The evaluation result of a solution to the GQAP.";
    #endregion

    #region Parameter Properties
    public OptionalValueParameter<GQAPAssignment> BestKnownSolutionParameter {
      get { return (OptionalValueParameter<GQAPAssignment>)Parameters["BestKnownSolution"]; }
    }
    public OptionalValueParameter<GQAPAssignmentArchive> BestKnownSolutionsParameter {
      get { return (OptionalValueParameter<GQAPAssignmentArchive>)Parameters["BestKnownSolutions"]; }
    }
    public IValueParameter<GQAPInstance> ProblemInstanceParameter {
      get { return (IValueParameter<GQAPInstance>)Parameters["ProblemInstance"]; }
    }
    #endregion

    #region Properties
    public GQAPAssignment BestKnownSolution {
      get { return BestKnownSolutionParameter.Value; }
      set { BestKnownSolutionParameter.Value = value; }
    }
    public GQAPAssignmentArchive BestKnownSolutions {
      get { return BestKnownSolutionsParameter.Value; }
      set { BestKnownSolutionsParameter.Value = value; }
    }
    public GQAPInstance ProblemInstance {
      get { return ProblemInstanceParameter.Value; }
      set { ProblemInstanceParameter.Value = value; }
    }
    #endregion

    [StorableConstructor]
    private GQAP(StorableConstructorFlag _) : base(_) { }
    private GQAP(GQAP original, Cloner cloner)
      : base(original, cloner) {
      RegisterEventHandlers();
      initialized = original.initialized;
    }
    public GQAP() : base() {
      Encoding = new IntegerVectorEncoding("Assignment");
      Parameters.Add(new OptionalValueParameter<GQAPAssignment>("BestKnownSolution", BestKnownSolutionDescription, null) { GetsCollected = false });
      Parameters.Add(new OptionalValueParameter<GQAPAssignmentArchive>("BestKnownSolutions", BestKnownSolutionsDescription, null) { GetsCollected = false });
      Parameters.Add(new ValueParameter<GQAPInstance>("ProblemInstance", "The problem instance that is to be solved.", new GQAPInstance()) { GetsCollected = false });

      InitializeOperators();
      RegisterEventHandlers();
      initialized = true;
      Parameterize();
    }

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

    public override double Evaluate(Individual individual, IRandom random = null) {
      var assignment = individual.IntegerVector();
      var evaluation = ProblemInstance.Evaluate(assignment);
      individual["Evaluation"] = evaluation;
      return ProblemInstance.ToSingleObjective(evaluation);
    }

    public double Evaluate(IntegerVector assignment) {
      var evaluation = ProblemInstance.Evaluate(assignment);
      return ProblemInstance.ToSingleObjective(evaluation);
    }

    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
      AnalyzeBestSolution(results, GetBestIndividual(individuals, qualities));
      AnalyzeParetoArchive(results,
        individuals.Select(i => Tuple.Create((IntegerVector)i.IntegerVector().Clone(),
        (Evaluation)i["Evaluation"])));
    }

    private void AnalyzeBestSolution(ResultCollection results, Tuple<Individual, double> best) {
      var bestVector = best.Item1.IntegerVector();
      var bestEvaluation = (Evaluation)best.Item1["Evaluation"];

      IResult bestResult;
      if (!results.TryGetValue("Best Solution", out bestResult)) {
        bestResult = new Result("Best Solution", typeof(GQAPAssignment));
        results.Add(bestResult);
      }
      var item = bestResult.Value as GQAPAssignment;
      if (item == null) bestResult.Value = new GQAPAssignment((IntegerVector)bestVector.Clone(), ProblemInstance, bestEvaluation);
      else if (ProblemInstance.ToSingleObjective(bestEvaluation)
        < ProblemInstance.ToSingleObjective(item.Solution.Evaluation)) {
        item.ProblemInstance = ProblemInstance;
        item.Solution = new GQAPSolution((IntegerVector)bestVector.Clone(), bestEvaluation);
      }
    }

    private void AnalyzeParetoArchive(ResultCollection results, IEnumerable<Tuple<IntegerVector, Evaluation>> solutions) {
      IResult archiveResult;
      if (!results.TryGetValue("Solution Archive", out archiveResult)) {
        archiveResult = new Result("Solution Archive", typeof(GQAPAssignmentArchive));
        results.Add(archiveResult);
      }
      var archive = archiveResult.Value as GQAPAssignmentArchive;
      if (archive == null) {
        archive = new GQAPAssignmentArchive(ProblemInstance);
        archiveResult.Value = archive;
      } else archive.ProblemInstance = ProblemInstance;
      
      var combinedArchive = solutions
        .Select(x => new GQAPSolution(x.Item1, x.Item2))
        .Concat(archive.Solutions);
      archive.Solutions = GetFeasibleParetoFront(combinedArchive);
      
      if (BestKnownSolutions == null) {
        BestKnownSolutions = archive;
      } else {
        var combinedArchive2 = solutions
        .Select(x => new GQAPSolution(x.Item1, x.Item2))
        .Concat(BestKnownSolutions.Solutions);
        BestKnownSolutions.Solutions = GetFeasibleParetoFront(combinedArchive2);
      }
    }

    #region Problem Instance Loading
    public void Load(QAPData data) {
      Name = data.Name;
      Description = data.Description;

      var weights = new DoubleMatrix(data.Weights);
      var distances = new DoubleMatrix(data.Distances);
      var installationCosts = new DoubleMatrix(weights.Rows, distances.Columns); // all zero
      var capacities = new DoubleArray(Enumerable.Range(0, distances.Rows).Select(x => 1.0).ToArray());
      var demands = new DoubleArray(Enumerable.Range(0, weights.Rows).Select(x => 1.0).ToArray());

      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
      EvaluateAndLoadAssignment(data.BestKnownAssignment);
    }

    public void Load(CTAPData data) {
      Name = data.Name;
      Description = data.Description;

      var capacities = new DoubleArray(data.MemoryCapacities);
      var demands = new DoubleArray(data.MemoryRequirements);
      var weights = new DoubleMatrix(data.CommunicationCosts);
      var installationCosts = new DoubleMatrix(data.ExecutionCosts.Transpose());
      var distances = new DoubleMatrix(capacities.Length, capacities.Length);
      for (int i = 0; i < capacities.Length - 1; i++)
        for (int j = i + 1; j < capacities.Length; j++) {
          distances[i, j] = 1;
        }

      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
      EvaluateAndLoadAssignment(data.BestKnownAssignment);
    }

    public void Load(TSPData data) {
      if (data.Dimension > 1000)
        throw new System.IO.InvalidDataException("Instances with more than 1000 cities are not supported.");

      Name = data.Name;
      Description = data.Description;

      var capacities = new DoubleArray(data.Dimension);
      var demands = new DoubleArray(data.Dimension);
      for (int i = 0; i < data.Dimension; i++) {
        capacities[i] = 1;
        demands[i] = 1;
      }
      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
      for (int i = 0; i < data.Dimension; i++)
        weights[i, (i + 1) % data.Dimension] = 1;
      var distances = new DoubleMatrix(data.GetDistanceMatrix());

      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
      EvaluateAndLoadAssignment(data.BestKnownTour);
    }

    public void Load(ATSPData data) {
      Name = data.Name;
      Description = data.Description;

      var capacities = new DoubleArray(data.Dimension);
      var demands = new DoubleArray(data.Dimension);
      for (int i = 0; i < data.Dimension; i++) {
        capacities[i] = 1;
        demands[i] = 1;
      }
      var installationCosts = new DoubleMatrix(data.Dimension, data.Dimension);
      var weights = new DoubleMatrix(data.Dimension, data.Dimension);
      for (int i = 0; i < data.Dimension; i++)
        weights[i, (i + 1) % data.Dimension] = 1;
      var distances = new DoubleMatrix(data.Distances);

      Load(demands, capacities, weights, distances, installationCosts, new DoubleValue(1));
      EvaluateAndLoadAssignment(data.BestKnownTour);
    }

    public void Load(GQAPData data) {
      Name = data.Name;
      Description = data.Description;

      var capacities = new DoubleArray(data.Capacities);
      var demands = new DoubleArray(data.Demands);
      var installationCosts = new DoubleMatrix(data.InstallationCosts);
      var weights = new DoubleMatrix(data.Weights);
      var distances = new DoubleMatrix(data.Distances);
      var transportationCosts = new DoubleValue(data.TransportationCosts);

      Load(demands, capacities, weights, distances, installationCosts, transportationCosts);
      EvaluateAndLoadAssignment(data.BestKnownAssignment);

      if (data.BestKnownAssignment == null && data.BestKnownQuality.HasValue) {
        BestKnownQuality = data.BestKnownQuality.Value;
      }
    }

    public void Load(DoubleArray demands, DoubleArray capacities,
      DoubleMatrix weights, DoubleMatrix distances, DoubleMatrix installationCosts,
      DoubleValue transportationCosts) {
      if (weights == null || weights.Rows == 0)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain weights!");
      if (weights.Rows != weights.Columns)
        throw new System.IO.InvalidDataException(
@"The weights matrix of the given instance contains
an unequal number of rows and columns.");
      if (distances == null || distances.Rows == 0)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain distances!");
      if (distances.Rows != distances.Columns)
        throw new System.IO.InvalidDataException(
@"The distances matrix of the given instance contains
an unequal number of rows and columns.");
      if (installationCosts == null || installationCosts.Rows == 0)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain installation costs!");
      if (installationCosts.Rows != weights.Rows
        || installationCosts.Columns != distances.Columns)
        throw new System.IO.InvalidDataException(
@"The installation costs matrix of the given instance
contains different number of rows than given in the
weights matrix and a different number of columns than
given in the distances matrix.");
      if (capacities == null || capacities.Length == 0)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain capacities!");
      if (capacities.Length != distances.Rows)
        throw new System.IO.InvalidDataException(
@"The given instance contains a different number of
capacities than rows given in the distances matrix.");
      if (demands == null || demands.Length == 0)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain demands!");
      if (demands.Length != weights.Rows)
        throw new System.IO.InvalidDataException(
@"The given instance contains a different number of
demands than rows given in the weights matrix.");
      if (transportationCosts == null)
        throw new System.IO.InvalidDataException(
@"The given instance does not contain transportation costs.");

      ProblemInstance = new GQAPInstance() {
        Weights = weights,
        Distances = distances,
        InstallationCosts = installationCosts,
        Capacities = capacities,
        Demands = demands,
        TransportationCosts = transportationCosts.Value
      };
      BestKnownQualityParameter.Value = null;
      BestKnownSolution = null;
      BestKnownSolutions = null;
      ProblemInstance.CalculatePenaltyLevel();
    }
    private void EvaluateAndLoadAssignment(int[] vector) {
      if (vector == null || vector.Length == 0) return;
      EvaluateAndLoadAssignment(new IntegerVector(vector));
    }
    public void EvaluateAndLoadAssignment(IntegerVector assignment) {
      if (!ProblemInstance.IsValid()) {
        BestKnownQualityParameter.Value = null;
        BestKnownSolution = null;
        BestKnownSolutions = null;
        return;
      }
      var evaluation = ProblemInstance.Evaluate(assignment);
      var quality = ProblemInstance.ToSingleObjective(evaluation);
      
      BestKnownSolution = new GQAPAssignment((IntegerVector)assignment.Clone(), ProblemInstance, evaluation);
      BestKnownQuality = quality;
      BestKnownSolutions = new GQAPAssignmentArchive(ProblemInstance);
      BestKnownSolutions.Solutions.Add(new GQAPSolution((IntegerVector)assignment.Clone(), evaluation));
    }
    #endregion

    #region Events
    protected override void OnOperatorsChanged() {
      base.OnOperatorsChanged();
      if (!initialized) return;
      Parameterize();
    }
    protected override void OnEncodingChanged() {
      base.OnEncodingChanged();
      if (!initialized) return;
      Parameterize();
    }
    #endregion

    #region Helpers
    [StorableHook(HookType.AfterDeserialization)]
    private void AfterDeserialization() {
      RegisterEventHandlers();
    }

    private void RegisterEventHandlers() {
      ProblemInstanceParameter.ValueChanged += ProblemInstanceParameterOnValueChanged;
      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
    }

    private void ProblemInstanceParameterOnValueChanged(object sender, EventArgs e) {
      ProblemInstance.CapacitiesParameter.ValueChanged += ProblemInstanceCapacitiesParameterOnValueChanged;
      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
      ProblemInstance.DemandsParameter.ValueChanged += ProblemInstanceDemandsParameterOnValueChanged;
      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
      UpdateEncoding();
    }
    private void ProblemInstanceCapacitiesParameterOnValueChanged(object sender, EventArgs e) {
      ProblemInstance.Capacities.Reset += ProblemInstanceCapacitiesOnReset;
      UpdateEncoding();
    }
    private void ProblemInstanceDemandsParameterOnValueChanged(object sender, EventArgs e) {
      ProblemInstance.Demands.Reset += ProblemInstanceDemandsOnReset;
      UpdateEncoding();
    }
    private void ProblemInstanceDemandsOnReset(object sender, EventArgs e) {
      UpdateEncoding();
    }
    private void ProblemInstanceCapacitiesOnReset(object sender, EventArgs e) {
      UpdateEncoding();
    }

    private void UpdateEncoding() {
      Encoding.Length = ProblemInstance.Demands.Length;
      Encoding.Bounds = new IntMatrix(new int[,] { { 0, ProblemInstance.Capacities.Length } });
    }

    private void InitializeOperators() {
      Operators.RemoveAll(x => x is ISingleObjectiveMoveOperator);
      Operators.RemoveAll(x => x is SingleObjectiveImprover);
      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPOperator>());
      Operators.AddRange(ApplicationManager.Manager.GetInstances<IGQAPMoveEvaluator>());
      Operators.Add(new HammingSimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
      Operators.Add(new QualitySimilarityCalculator() { SolutionVariableName = Encoding.Name, QualityVariableName = Evaluator.QualityParameter.ActualName });
      
      Operators.Add(new PopulationSimilarityAnalyzer(Operators.OfType<ISolutionSimilarityCalculator>()));
    }

    private void Parameterize() {
      var operators = Operators.Union(new IOperator[] { SolutionCreator, Evaluator }).ToArray();
      Encoding.ConfigureOperators(operators.OfType<IOperator>());
      foreach (var op in operators.OfType<IAssignmentAwareGQAPOperator>()) {
        op.AssignmentParameter.ActualName = Encoding.Name;
        op.AssignmentParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IBestKnownQualityAwareGQAPOperator>()) {
        op.BestKnownQualityParameter.ActualName = BestKnownQualityParameter.Name;
        op.BestKnownQualityParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IBestKnownSolutionAwareGQAPOperator>()) {
        op.BestKnownSolutionParameter.ActualName = BestKnownSolutionParameter.Name;
        op.BestKnownSolutionParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IBestKnownSolutionsAwareGQAPOperator>()) {
        op.BestKnownSolutionsParameter.ActualName = BestKnownSolutionsParameter.Name;
        op.BestKnownSolutionsParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IGQAPCrossover>()) {
        op.ParentsParameter.ActualName = Encoding.Name;
        op.ParentsParameter.Hidden = true;
        op.ChildParameter.ActualName = Encoding.Name;
        op.ChildParameter.Hidden = true;
      }
      var moveEvaluator = operators.OfType<IGQAPMoveEvaluator>().FirstOrDefault();
      foreach (var op in operators.OfType<IGQAPMoveEvaluator>()) { // synchronize all move evaluators
        if (moveEvaluator != null) {
          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
          op.MoveQualityParameter.Hidden = true;
          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
          op.MoveEvaluationParameter.Hidden = true;
        }
      }
      foreach (var op in operators.OfType<IMoveQualityAwareGQAPOperator>()) {
        if (moveEvaluator != null) {
          op.MoveQualityParameter.ActualName = moveEvaluator.MoveQualityParameter.ActualName;
          op.MoveQualityParameter.Hidden = true;
          op.MoveEvaluationParameter.ActualName = "MoveEvaluation";
          op.MoveEvaluationParameter.Hidden = true;
        }
      }
      foreach (var op in operators.OfType<IProblemInstanceAwareGQAPOperator>()) {
        op.ProblemInstanceParameter.ActualName = ProblemInstanceParameter.Name;
        op.ProblemInstanceParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IQualitiesAwareGQAPOperator>()) {
        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
        op.QualityParameter.Hidden = true;
        op.EvaluationParameter.ActualName = "Evaluation";
        op.EvaluationParameter.Hidden = true;
      }
      foreach (var op in operators.OfType<IQualityAwareGQAPOperator>()) {
        op.QualityParameter.ActualName = Evaluator.QualityParameter.ActualName;
        op.QualityParameter.Hidden = true;
        op.EvaluationParameter.ActualName = "Evaluation";
        op.EvaluationParameter.Hidden = true;
      }
    }
    #endregion

    public static ItemList<GQAPSolution> GetFeasibleParetoFront(IEnumerable<GQAPSolution> solutions) {
      var front = new ItemList<GQAPSolution>(solutions.Where(x => x.Evaluation.IsFeasible));

      for (int i = 0; i < front.Count - 1; i++) {
        for (int j = i + 1; j < front.Count; j++) {
          if (front[i].Evaluation.FlowCosts <= front[j].Evaluation.FlowCosts
            && front[i].Evaluation.InstallationCosts <= front[j].Evaluation.InstallationCosts) {
            front.RemoveAt(j);
            j--;
          } else if (front[i].Evaluation.FlowCosts >= front[j].Evaluation.FlowCosts
            && front[i].Evaluation.InstallationCosts >= front[j].Evaluation.InstallationCosts) {
            front.RemoveAt(i);
            j = i;
          }
        }
      }
      return front;
    }
  }
}