#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 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 System.Threading;
using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.IntegerVectorEncoding;
using HeuristicLab.Optimization;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.GRASP {

  /// <summary>
  /// This is an implementation of the algorithm described in Mateus, G.R., Resende, M.G.C. & Silva, R.M.A. J Heuristics (2011) 17: 527. https://doi.org/10.1007/s10732-010-9144-0
  /// </summary>
  [Item("GRASP+PR (GQAP)", "The algorithm implements the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking as 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.")]
  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
  [StorableClass]
  public class GRASP : BasicAlgorithm {

    public override bool SupportsPause {
      get { return true; }
    }

    public override Type ProblemType {
      get { return typeof(GQAP); }
    }

    public new GQAP Problem {
      get { return (GQAP)base.Problem; }
      set { base.Problem = value; }
    }

    [Storable]
    private ValueParameter<IAnalyzer> analyzerParameter;
    public IValueParameter<IAnalyzer> AnalyzerParameter {
      get { return analyzerParameter; }
    }

    [Storable]
    private FixedValueParameter<BoolValue> setSeedRandomlyParameter;
    private IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
      get { return setSeedRandomlyParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> seedParameter;
    private IFixedValueParameter<IntValue> SeedParameter {
      get { return seedParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> eliteSetSizeParameter;
    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
      get { return eliteSetSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> minimiumEliteSetSizeParameter;
    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
      get { return minimiumEliteSetSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> maximumIterationsParameter;
    public IFixedValueParameter<IntValue> MaximumIterationsParameter {
      get { return maximumIterationsParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> maximumLocalSearchIterationsParameter;
    public IFixedValueParameter<IntValue> MaximumLocalSearchIterationsParameter {
      get { return maximumIterationsParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> candidateSizeFactorParameter;
    public IFixedValueParameter<PercentValue> CandidateSizeFactorParameter {
      get { return candidateSizeFactorParameter; }
    }
    [Storable]
    private FixedValueParameter<IntValue> maximumCandidateListSizeParameter;
    public IFixedValueParameter<IntValue> MaximumCandidateListSizeParameter {
      get { return maximumCandidateListSizeParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> oneMoveProbabilityParameter;
    public IFixedValueParameter<PercentValue> OneMoveProbabilityParameter {
      get { return oneMoveProbabilityParameter; }
    }
    [Storable]
    private FixedValueParameter<PercentValue> minimumDifferenceParameter;
    public IFixedValueParameter<PercentValue> MinimumDifferenceParameter {
      get { return minimumDifferenceParameter; }
    }
    
    public bool SetSeedRandomly {
      get { return setSeedRandomlyParameter.Value.Value; }
      set { setSeedRandomlyParameter.Value.Value = value; }
    }
    public int Seed {
      get { return seedParameter.Value.Value; }
      set { seedParameter.Value.Value = value; }
    }
    public int MinimumEliteSetSize {
      get { return minimiumEliteSetSizeParameter.Value.Value; }
      set { minimiumEliteSetSizeParameter.Value.Value = value; }
    }
    public int EliteSetSize {
      get { return eliteSetSizeParameter.Value.Value; }
      set { eliteSetSizeParameter.Value.Value = value; }
    }
    public double CandidateSizeFactor {
      get { return candidateSizeFactorParameter.Value.Value; }
      set { candidateSizeFactorParameter.Value.Value = value; }
    }
    public int MaximumCandidateListSize {
      get { return maximumCandidateListSizeParameter.Value.Value; }
      set { maximumCandidateListSizeParameter.Value.Value = value; }
    }
    public double OneMoveProbability {
      get { return oneMoveProbabilityParameter.Value.Value; }
      set { oneMoveProbabilityParameter.Value.Value = value; }
    }
    public double MinimumDifference {
      get { return minimumDifferenceParameter.Value.Value; }
      set { minimumDifferenceParameter.Value.Value = value; }
    }

    [StorableConstructor]
    protected GRASP(bool deserializing) : base(deserializing) { }
    protected GRASP(GRASP original, Cloner cloner)
      : base(original, cloner) {
      setSeedRandomlyParameter = cloner.Clone(original.setSeedRandomlyParameter);
      seedParameter = cloner.Clone(original.seedParameter);
      analyzerParameter = cloner.Clone(original.analyzerParameter);
      eliteSetSizeParameter = cloner.Clone(original.eliteSetSizeParameter);
      minimiumEliteSetSizeParameter = cloner.Clone(original.minimiumEliteSetSizeParameter);
      maximumIterationsParameter = cloner.Clone(original.maximumIterationsParameter);
      maximumLocalSearchIterationsParameter = cloner.Clone(original.maximumLocalSearchIterationsParameter);
      candidateSizeFactorParameter = cloner.Clone(original.candidateSizeFactorParameter);
      maximumCandidateListSizeParameter = cloner.Clone(original.maximumCandidateListSizeParameter);
      oneMoveProbabilityParameter = cloner.Clone(original.oneMoveProbabilityParameter);
      minimumDifferenceParameter = cloner.Clone(original.minimumDifferenceParameter);
      context = cloner.Clone(original.context);
    }
    public GRASP() {
      Parameters.Add(setSeedRandomlyParameter = new FixedValueParameter<BoolValue>("SetSeedRandomly", "Whether to overwrite the seed with a random value each time the algorithm is run.", new BoolValue(true)));
      Parameters.Add(seedParameter = new FixedValueParameter<IntValue>("Seed", "The random seed that is used in the stochastic algorithm", new IntValue(0)));
      Parameters.Add(analyzerParameter = new ValueParameter<IAnalyzer>("Analyzer", "The analyzers that are used to perform an analysis of the solutions.", new MultiAnalyzer()));
      Parameters.Add(eliteSetSizeParameter = new FixedValueParameter<IntValue>("EliteSetSize", "The (maximum) size of the elite set.", new IntValue(10)));
      Parameters.Add(minimiumEliteSetSizeParameter = new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimal size of the elite set, before local search and path relinking are applied.", new IntValue(2)));
      Parameters.Add(maximumIterationsParameter = new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(1000)));
      Parameters.Add(maximumLocalSearchIterationsParameter = new FixedValueParameter<IntValue>("MaximumLocalSearchIteration", "The maximum number of iterations that the approximate local search should run", new IntValue(100)));
      Parameters.Add(candidateSizeFactorParameter = new FixedValueParameter<PercentValue>("CandidateSizeFactor", "(η) Determines the size of the set of feasible moves in each path - relinking step relative to the maximum size.A value of 50 % means that only half of all possible moves are considered each step.", new PercentValue(0.5)));
      Parameters.Add(maximumCandidateListSizeParameter = new FixedValueParameter<IntValue>("MaximumCandidateListSize", "The maximum number of candidates that should be found in each step.", new IntValue(10)));
      Parameters.Add(oneMoveProbabilityParameter = new FixedValueParameter<PercentValue>("OneMoveProbability", "The probability for performing a 1-move, which is the opposite of performing a 2-move.", new PercentValue(.5)));
      Parameters.Add(minimumDifferenceParameter = new FixedValueParameter<PercentValue>("MinimumDifference", "The minimum amount of difference between two solutions so that they are both accepted in the elite set.", new PercentValue(1e-7)));
      Problem = new GQAP();
    }

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

    public override void Prepare() {
      base.Prepare();
      Results.Clear();
      context = null;
    }

    [Storable]
    private GRASPContext context;

    protected override void Initialize(CancellationToken cancellationToken) {
      base.Initialize(cancellationToken);
      context = new GRASPContext();
      context.Problem = Problem;
      context.Scope.Variables.Add(new Variable("Results", Results));

      IExecutionContext ctxt = null;
      foreach (var item in Problem.ExecutionContextItems)
        ctxt = new Core.ExecutionContext(ctxt, item, context.Scope);
      ctxt = new Core.ExecutionContext(ctxt, this, context.Scope);
      context.Parent = ctxt;

      if (SetSeedRandomly) {
        var rnd = new System.Random();
        Seed = rnd.Next();
      }
      context.Random = new MersenneTwister((uint)Seed);
      context.Iterations = 0;
      context.EvaluatedSolutions = 0;
      context.BestQuality = double.NaN;
      context.BestSolution = null;

      context.Initialized = true;

      Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
      Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
      Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
      Results.Add(new Result("BestSolution", typeof(GQAPSolution)));

      context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
    }

    protected override void Run(CancellationToken cancellationToken) {
      var eq = new IntegerVectorEqualityComparer();
      while (!StoppingCriterion()) { // line 2 in Algorithm 1
        // next: line 3 in Algorithm 1
        var pi_prime_vec = GreedyRandomizedSolutionCreator.CreateSolution(context.Random, Problem.ProblemInstance, 1000, false, cancellationToken);
        if (context.PopulationCount >= MinimumEliteSetSize) { // line 4 in Algorithm 1
          GQAPSolution pi_prime;
          if (!Problem.ProblemInstance.IsFeasible(pi_prime_vec)) // line 5 in Algorithm 1
            pi_prime = context.AtPopulation(context.Random.Next(context.PopulationCount)).Solution; // line 6 in Algorithm 1
          else {
            // This is necessary, because pi_prime has not been evaluated yet and such details are not covered in Algorithm 1
            pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
            context.EvaluatedSolutions++;
          }

          ApproxLocalSearch(pi_prime); // line 8 in Algorithm 1
          var pi_plus = context.AtPopulation(context.Random.Next(context.PopulationCount)); // line 9 in Algorithm 1
          pi_prime = PathRelinking(pi_prime, pi_plus.Solution); // line 10 in Algorithm 1
          ApproxLocalSearch(pi_prime); // line 11 in Algorithm 1
          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
          // Book-keeping
          if (context.BestQuality > fitness) {
            context.BestQuality = fitness;
            context.BestSolution = (GQAPSolution)pi_prime.Clone();
          }

          if (context.PopulationCount == EliteSetSize) { // line 12 in Algorithm 1
            var fit = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
            double[] similarities = context.Population.Select(x => HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, pi_prime.Assignment)).ToArray();
            if (similarities.Max() <= 1.0 - MinimumDifference) { // cond. 2 of line 13 in Algorithm 1
              var replacement = context.Population.Select((v, i) => new { V = v, Index = i })
                                          .Where(x => x.V.Fitness >= fit).ToArray();
              if (replacement.Length > 0) { // cond. 1 of line 13 in Algorithm 1
                // next two lines: line 14 in Algorithm 1
                replacement = replacement.OrderBy(x => similarities[x.Index]).ToArray();
                context.ReplaceAtPopulation(replacement.Last().Index, context.ToScope(pi_prime, fit));
              }
            }
          } else if (IsSufficientlyDifferent(pi_prime.Assignment)) { // line 17 in Algorithm 1
            context.AddToPopulation(context.ToScope(pi_prime, Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation))); // line 18 in Algorithm 1
          }
        } else if (Problem.ProblemInstance.IsFeasible(pi_prime_vec) /* cond. 1 of line 21 in Algorithm 1 */
          && IsSufficientlyDifferent(pi_prime_vec))  /* cond. 2 of line 21 in Algorithm 1 */ {
          var pi_prime = Problem.ProblemInstance.ToEvaluatedSolution(pi_prime_vec);
          context.EvaluatedSolutions++;
          var fitness = Problem.ProblemInstance.ToSingleObjective(pi_prime.Evaluation);
          context.AddToPopulation(context.ToScope(pi_prime, fitness)); /* line 22 in Algorithm 1 */
          // Book-keeping
          if (context.PopulationCount == 1 || context.BestQuality > fitness) {
            context.BestQuality = fitness;
            context.BestSolution = (GQAPSolution)pi_prime.Clone();
          }
        }

        context.Iterations++;

        IResult result;
        if (Results.TryGetValue("Iterations", out result))
          ((IntValue)result.Value).Value = context.Iterations;
        else Results.Add(new Result("Iterations", new IntValue(context.Iterations)));
        if (Results.TryGetValue("EvaluatedSolutions", out result))
          ((IntValue)result.Value).Value = context.EvaluatedSolutions;
        else Results.Add(new Result("EvaluatedSolutions", new IntValue(context.EvaluatedSolutions)));
        if (Results.TryGetValue("BestQuality", out result))
          ((DoubleValue)result.Value).Value = context.BestQuality;
        else Results.Add(new Result("BestQuality", new DoubleValue(context.BestQuality)));
        if (Results.TryGetValue("BestSolution", out result))
          result.Value = context.BestSolution;
        else Results.Add(new Result("BestSolution", context.BestSolution));

        context.RunOperator(analyzerParameter.Value, context.Scope, cancellationToken);
      }
    }

    private bool IsSufficientlyDifferent(IntegerVector vec) {
      return context.Population.All(x =>
        HammingSimilarityCalculator.CalculateSimilarity(x.Solution.Assignment, vec) <= 1.0 - MinimumDifference
      );
    }

    private GQAPSolution PathRelinking(GQAPSolution pi_prime, GQAPSolution pi_plus) {
      // Following code represents line 1 of Algorithm 4
      IntegerVector source = pi_prime.Assignment, target = pi_plus.Assignment;
      Evaluation sourceEval = pi_prime.Evaluation, targetEval = pi_plus.Evaluation;
      var sourceFit = Problem.ProblemInstance.ToSingleObjective(sourceEval);
      var targetFit = Problem.ProblemInstance.ToSingleObjective(targetEval);
      if (targetFit < sourceFit) {
        var h = source;
        source = target;
        target = h;
        var hh = sourceEval;
        sourceEval = targetEval;
        targetEval = hh;
      }
      int evaluatedSolutions;
      // lines 2-36 of Algorithm 4 are implemented in the following call
      var pi_star = GQAPPathRelinking.Apply(context.Random, source, sourceEval,
        target, targetEval, Problem.ProblemInstance, CandidateSizeFactor,
        out evaluatedSolutions);
      context.EvaluatedSolutions += evaluatedSolutions;
      return pi_star;
    }

    private void ApproxLocalSearch(GQAPSolution pi_prime) {
      var localSearchEvaluations = 0;
      ApproximateLocalSearch.Apply(context.Random, pi_prime, MaximumCandidateListSize,
        OneMoveProbability, 1000, Problem.ProblemInstance, out localSearchEvaluations);
      context.EvaluatedSolutions += localSearchEvaluations;
    }

    private bool StoppingCriterion() {
      return context.Iterations > MaximumIterationsParameter.Value.Value;
    }
  }
}