source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LAHC/pLAHC.cs @ 15572

#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.Threading;
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;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LAHC {
  [Item("pLAHC-s (GQAP)", "Parameterless Late-acceptance hill climber for the GQAP.")]
  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
  [StorableClass]
  public sealed class PLAHCS : StochasticAlgorithm<PLAHCContext, IntegerVectorEncoding> {

    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 FixedValueParameter<IntValue> maximumExponentParameter;
    public IFixedValueParameter<IntValue> MaximumExponentParameter {
      get { return maximumExponentParameter; }
    }

    [Storable]
    private FixedValueParameter<IntValue> minimumSprintIterationsParameter;
    public IFixedValueParameter<IntValue> MinimumSprintIterationsParameter {
      get { return minimumSprintIterationsParameter; }
    }

    public int MaximumExponent {
      get { return maximumExponentParameter.Value.Value; }
      set { maximumExponentParameter.Value.Value = value; }
    }

    public int MinimumSprintIterations {
      get { return minimumSprintIterationsParameter.Value.Value; }
      set { minimumSprintIterationsParameter.Value.Value = value; }
    }

    [StorableConstructor]
    private PLAHCS(bool deserializing) : base(deserializing) { }
    private PLAHCS(PLAHCS original, Cloner cloner)
      : base(original, cloner) {
      maximumExponentParameter = cloner.Clone(original.maximumExponentParameter);
      minimumSprintIterationsParameter = cloner.Clone(original.minimumSprintIterationsParameter);
    }
    public PLAHCS() {
      Parameters.Add(maximumExponentParameter = new FixedValueParameter<IntValue>("MaximumExponent", "The maximum power to which memory sizes should be tried (2^x). Do not set higher than 31", new IntValue(24)));
      Parameters.Add(minimumSprintIterationsParameter = new FixedValueParameter<IntValue>("MinimumSprintIterations", "The minimum amount of iterations per sprint.", new IntValue(100000)));

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

    protected override void Initialize(CancellationToken token) {
      base.Initialize(token);

      Context.Problem = Problem;
      Context.LastSuccess = 0;

      var assign = new IntegerVector(Problem.ProblemInstance.Demands.Length, Context.Random, 0, Problem.ProblemInstance.Capacities.Length);
      var eval = Problem.ProblemInstance.Evaluate(assign);
      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
      Context.EvaluatedSolutions++;

      var candidate = new GQAPSolution(assign, eval);

      Context.ReplaceIncumbent(Context.ToScope(candidate, fit));
      Context.BestQuality = fit;
      Context.BestSolution = (GQAPSolution)candidate.Clone();

      Context.BestList = new ItemList<DoubleValue>(new[] { new DoubleValue(Context.BestQuality) });

      Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
      Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
      Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
      Results.Add(new Result("CurrentMemorySize", new IntValue(0)));
    }

    protected override void Run(CancellationToken cancellationToken) {
      var lastUpdate = ExecutionTime;
      for (var i = 0; i <= MaximumExponent; i++) {
        var l = (int)Math.Pow(2, i);
        var memory = new double[l];
        for (var vv = 0; vv < l; vv++)
          memory[vv] = Context.BestList[Context.BestList.Count - 1 - (vv % Context.BestList.Count)].Value;
        Array.Sort(memory);
        Context.Memory = new DoubleArray(memory);
        if (i > 0) Context.ReplaceIncumbent(Context.ToScope((GQAPSolution)Context.BestSolution.Clone(), Context.BestQuality));
        IResult memorySizeResult;
        if (Results.TryGetValue("CurrentMemorySize", out memorySizeResult))
          ((IntValue)memorySizeResult.Value).Value = Context.Memory.Length;
        else Results.Add(new Result("CurrentMemorySize", new IntValue(Context.Memory.Length)));

        Context.SprintIterations = 0;
        while (!StoppingCriterion()
          && (Context.SprintIterations < MinimumSprintIterations
          || (Context.SprintIterations - Context.LastSuccess) < Context.SprintIterations * 0.02)) {

          var move = StochasticNMoveSingleMoveGenerator.GenerateOneMove(Context.Random,
            Context.Incumbent.Solution.Assignment, Problem.ProblemInstance.Capacities);
          var moveEval = GQAPNMoveEvaluator.Evaluate(move,
            Context.Incumbent.Solution.Assignment,
            Context.Incumbent.Solution.Evaluation, Problem.ProblemInstance);
          if (Context.SprintIterations % Problem.ProblemInstance.Demands.Length == 0)
            Context.EvaluatedSolutions++;
          var nextFit = Problem.ProblemInstance.ToSingleObjective(moveEval);
          var nextVec = new IntegerVector(Context.Incumbent.Solution.Assignment);
          NMoveMaker.Apply(nextVec, move);

          var v = Context.Iterations % Context.Memory.Length;
          Context.Iterations++;
          Context.SprintIterations++;
          var prevFit = Context.Memory[v];

          var accept = nextFit <= Context.Incumbent.Fitness
                    || nextFit <= prevFit;

          if (accept && nextFit < Context.Incumbent.Fitness)
            Context.LastSuccess = Context.SprintIterations;

          if (accept) {
            Context.ReplaceIncumbent(Context.ToScope(new GQAPSolution(nextVec, moveEval), nextFit));
            if (nextFit < Context.BestQuality) {
              Context.BestSolution = (GQAPSolution)Context.Incumbent.Solution.Clone();
              Context.BestQuality = nextFit;
              Context.BestList.Add(new DoubleValue(Context.BestQuality));
            }
          }

          if (Context.Incumbent.Fitness < prevFit)
            Context.Memory[v] = Context.Incumbent.Fitness;

          IResult result;
          if (ExecutionTime - lastUpdate > TimeSpan.FromSeconds(1)) {
            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("Sprint Iterations", out result))
              ((IntValue)result.Value).Value = Context.SprintIterations;
            else Results.Add(new Result("Total Iterations", new IntValue(Context.SprintIterations)));
            if (Results.TryGetValue("EvaluatedSolutions", out result))
              ((IntValue)result.Value).Value = Context.EvaluatedSolutions;
            else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
            lastUpdate = ExecutionTime;
          }
          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));

          try {
            Context.RunOperator(Analyzer, Context.Scope, cancellationToken);
          } catch (OperationCanceledException) { }

          if (cancellationToken.IsCancellationRequested) break;
        }
        if (StoppingCriterion() || cancellationToken.IsCancellationRequested) break;
      }

      IResult result2;
      if (Results.TryGetValue("Iterations", out result2))
        ((IntValue)result2.Value).Value = Context.Iterations;
      else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));
      if (Results.TryGetValue("Sprint Iterations", out result2))
        ((IntValue)result2.Value).Value = Context.SprintIterations;
      else Results.Add(new Result("Sprint Iterations", new IntValue(Context.SprintIterations)));
      if (Results.TryGetValue("EvaluatedSolutions", out result2))
        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    }
  }
}