source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSearch/IteratedLS.cs @ 15563

#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.Persistence.Default.CompositeSerializers.Storable;

namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {
  [Item("Iterated Local Search (GQAP)", "Iterated local search for the GQAP.")]
  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]
  [StorableClass]
  public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext> {

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

    [StorableConstructor]
    private IteratedLS(bool deserializing) : base(deserializing) { }
    private IteratedLS(IteratedLS original, Cloner cloner)
      : base(original, cloner) {
    }
    public IteratedLS() {

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

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

      Context.Problem = Problem;
      Context.BestQuality = double.NaN;
      Context.BestSolution = null;

      var assign = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 10, true, token);
      var eval = Problem.ProblemInstance.Evaluate(assign);
      var fit = Problem.ProblemInstance.ToSingleObjective(eval);
      Context.EvaluatedSolutions++;

      var candidate = new GQAPSolution(assign, eval);
      var lsevaluations = 0;
      OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
      Context.EvaluatedSolutions += lsevaluations;

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

      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", Context.BestSolution));

      Context.RunOperator(Analyzer, Context.Scope, token);
    }

    protected override void Run(CancellationToken cancellationToken) {
      var lastUpdate = ExecutionTime;

      while (!StoppingCriterion()) {
        var lsevaluations = 0;
        var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();
        RandomWalk(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, candidate.Assignment.Length);
        candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);
        Context.EvaluatedSolutions++;
        OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);
        Context.EvaluatedSolutions += lsevaluations;

        var candidateFit = Problem.ProblemInstance.ToSingleObjective(candidate.Evaluation);
        if (candidateFit < Context.Incumbent.Fitness) {
          Context.ReplaceIncumbent(Context.ToScope(candidate, candidateFit));
          Context.BestQuality = candidateFit;
          Context.BestSolution = (GQAPSolution)candidate.Clone();
        }

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

        Context.RunOperator(Analyzer, Context.Scope, cancellationToken);

        Context.Iterations++;
        if (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("EvaluatedSolutions", out result2))
        ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;
      else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));
    }

    private static void RandomWalk(IRandom random, IntegerVector assignment, int locations, int walkLength) {
      for (int i = 0; i < walkLength; i++) {
        var equipment = random.Next(assignment.Length);
        assignment[equipment] = random.Next(locations);
        if (random.NextDouble() < 1.0 / walkLength) break;
      }
    }
  }
}