1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Threading;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Optimization;


28  using HeuristicLab.Parameters;


29  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


30 


31  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSearch {


32  [Item("Iterated Local Search (GQAP)", "Iterated local search for the GQAP.")]


33  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms)]


34  [StorableClass]


35  public sealed class IteratedLS : StochasticAlgorithm<LocalSearchContext> {


36 


37  public override bool SupportsPause {


38  get { return true; }


39  }


40 


41  public override Type ProblemType {


42  get { return typeof(GQAP); }


43  }


44 


45  public new GQAP Problem {


46  get { return (GQAP)base.Problem; }


47  set { base.Problem = value; }


48  }


49 


50  [Storable]


51  private IFixedValueParameter<PercentValue> perturbationStrengthParameter;


52  public IFixedValueParameter<PercentValue> PerturbationStrengthParameter {


53  get { return perturbationStrengthParameter; }


54  }


55 


56  public double PerturbationStrength {


57  get { return perturbationStrengthParameter.Value.Value; }


58  set { perturbationStrengthParameter.Value.Value = value; }


59  }


60 


61  [StorableConstructor]


62  private IteratedLS(bool deserializing) : base(deserializing) { }


63  private IteratedLS(IteratedLS original, Cloner cloner)


64  : base(original, cloner) {


65  }


66  public IteratedLS() {


67  Parameters.Add(perturbationStrengthParameter = new FixedValueParameter<PercentValue>("PerturbationStrength", "The expected length of the random walk relative to the size of the solution vector.", new PercentValue(0.5)));


68 


69  Problem = new GQAP();


70  }


71 


72  public override IDeepCloneable Clone(Cloner cloner) {


73  return new IteratedLS(this, cloner);


74  }


75 


76  protected override void Initialize(CancellationToken token) {


77  base.Initialize(token);


78 


79  Context.Problem = Problem;


80  Context.BestQuality = double.NaN;


81  Context.BestSolution = null;


82 


83  var assign = GreedyRandomizedSolutionCreator.CreateSolution(Context.Random, Problem.ProblemInstance, 10, true, token);


84  var eval = Problem.ProblemInstance.Evaluate(assign);


85  var fit = Problem.ProblemInstance.ToSingleObjective(eval);


86  Context.EvaluatedSolutions++;


87 


88  var candidate = new GQAPSolution(assign, eval);


89  var lsevaluations = 0;


90  OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);


91  Context.EvaluatedSolutions += lsevaluations;


92 


93  Context.ReplaceIncumbent(Context.ToScope(candidate, fit));


94  Context.BestQuality = fit;


95  Context.BestSolution = (GQAPSolution)candidate.Clone();


96 


97  Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));


98  Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));


99  Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));


100  Results.Add(new Result("BestSolution", Context.BestSolution));


101 


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


103  }


104 


105  protected override void Run(CancellationToken cancellationToken) {


106  var lastUpdate = ExecutionTime;


107 


108  while (!StoppingCriterion()) {


109  var lsevaluations = 0;


110  var candidate = (GQAPSolution)Context.Incumbent.Solution.Clone();


111  RelocateEquipmentManipluator.Apply(Context.Random, candidate.Assignment, Problem.ProblemInstance.Capacities.Length, 1.0 / (PerturbationStrength * candidate.Assignment.Length));


112  candidate.Evaluation = Problem.ProblemInstance.Evaluate(candidate.Assignment);


113  Context.EvaluatedSolutions++;


114  OneOptLocalSearch.Apply(Context.Random, candidate, Problem.ProblemInstance, out lsevaluations);


115  Context.EvaluatedSolutions += lsevaluations;


116 


117  var candidateFit = Problem.ProblemInstance.ToSingleObjective(candidate.Evaluation);


118  if (candidateFit < Context.Incumbent.Fitness) {


119  Context.ReplaceIncumbent(Context.ToScope(candidate, candidateFit));


120  Context.BestQuality = candidateFit;


121  Context.BestSolution = (GQAPSolution)candidate.Clone();


122  }


123 


124  IResult result;


125  if (ExecutionTime  lastUpdate > TimeSpan.FromSeconds(1)) {


126  if (Results.TryGetValue("Iterations", out result))


127  ((IntValue)result.Value).Value = Context.Iterations;


128  else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));


129  if (Results.TryGetValue("EvaluatedSolutions", out result))


130  ((IntValue)result.Value).Value = Context.EvaluatedSolutions;


131  else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));


132  lastUpdate = ExecutionTime;


133  }


134  if (Results.TryGetValue("BestQuality", out result))


135  ((DoubleValue)result.Value).Value = Context.BestQuality;


136  else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));


137  if (Results.TryGetValue("BestSolution", out result))


138  result.Value = Context.BestSolution;


139  else Results.Add(new Result("BestSolution", Context.BestSolution));


140 


141  try {


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


143  } catch (OperationCanceledException) { }


144 


145  Context.Iterations++;


146  if (cancellationToken.IsCancellationRequested) break;


147  }


148  IResult result2;


149  if (Results.TryGetValue("Iterations", out result2))


150  ((IntValue)result2.Value).Value = Context.Iterations;


151  else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));


152  if (Results.TryGetValue("EvaluatedSolutions", out result2))


153  ((IntValue)result2.Value).Value = Context.EvaluatedSolutions;


154  else Results.Add(new Result("EvaluatedSolutions", new IntValue(Context.EvaluatedSolutions)));


155  }


156  }


157  }

