#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 . */ #endregion using System; using System.Threading; using HEAL.Attic; using HeuristicLab.Common; using HeuristicLab.Core; using HeuristicLab.Data; using HeuristicLab.Encodings.IntegerVectorEncoding; using HeuristicLab.Optimization; using HeuristicLab.Parameters; namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch { [Item("Iterated Local Search (GQAP)", "Iterated local search for the GQAP.")] [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)] [StorableType("2C8EE433-B133-4382-8B4F-4EFFA536D759")] public sealed class IteratedLS : StochasticAlgorithm { 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 IFixedValueParameter perturbationStrengthParameter; public IFixedValueParameter PerturbationStrengthParameter { get { return perturbationStrengthParameter; } } public double PerturbationStrength { get { return perturbationStrengthParameter.Value.Value; } set { perturbationStrengthParameter.Value.Value = value; } } [StorableConstructor] private IteratedLS(StorableConstructorFlag _) : base(_) { } private IteratedLS(IteratedLS original, Cloner cloner) : base(original, cloner) { perturbationStrengthParameter = cloner.Clone(original.perturbationStrengthParameter); } public IteratedLS() { Parameters.Add(perturbationStrengthParameter = new FixedValueParameter("PerturbationStrength", "The expected length of the random walk relative to the size of the solution vector.", new PercentValue(0.5))); 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.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)); try { Context.RunOperator(Analyzer, token); } catch (OperationCanceledException) { } } protected override void Run(CancellationToken cancellationToken) { base.Run(cancellationToken); var lastUpdate = ExecutionTime; while (!StoppingCriterion()) { var lsevaluations = 0; var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone(); RelocateEquipmentManipluator.Apply(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, 1.0 / (PerturbationStrength * 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)); try { Context.RunOperator(Analyzer, cancellationToken); } catch (OperationCanceledException) { } 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))); } } }