sources/HeuristicLab.Algorithms.VariableNeighborhoodSearch/3.3/VariableNeighborhoodSearch.cs

   1 #region License Information
   2 /* HeuristicLab
   3  * Copyright (C) 2002-2011 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.Linq;
  24 using HeuristicLab.Analysis;
  25 using HeuristicLab.Common;
  26 using HeuristicLab.Core;
  27 using HeuristicLab.Data;
  28 using HeuristicLab.Operators;
  29 using HeuristicLab.Optimization;
  30 using HeuristicLab.Optimization.Operators;
  31 using HeuristicLab.Parameters;
  32 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  33 using HeuristicLab.PluginInfrastructure;
  34 using HeuristicLab.Random;
  35
  36 namespace HeuristicLab.Algorithms.VariableNeighborhoodSearch {
  37   [Item("Variable Neighborhood Search", "A variable neighborhood search algorithm based on the description in Mladenovic, N. and Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research Volume 24, Issue 11, pp. 1097-1100.")]
  38   [Creatable("Algorithms")]
  39   [StorableClass]
  40   public sealed class VariableNeighborhoodSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent {
  41     public string Filename { get; set; }
  42
  43     #region Problem Properties
  44     public override Type ProblemType {
  45       get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
  46     }
  47     public new ISingleObjectiveHeuristicOptimizationProblem Problem {
  48       get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
  49       set { base.Problem = value; }
  50     }
  51     #endregion
  52
  53     #region Parameter Properties
  54     private FixedValueParameter<IntValue> SeedParameter {
  55       get { return (FixedValueParameter<IntValue>)Parameters["Seed"]; }
  56     }
  57     private FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
  58       get { return (FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
  59     }
  60     public ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
  61       get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
  62     }
  63     public ConstrainedValueParameter<IMultiNeighborhoodShakingOperator> ShakingOperatorParameter {
  64       get { return (ConstrainedValueParameter<IMultiNeighborhoodShakingOperator>)Parameters["ShakingOperator"]; }
  65     }
  66     private FixedValueParameter<IntValue> MaximumIterationsParameter {
  67       get { return (FixedValueParameter<IntValue>)Parameters["MaximumIterations"]; }
  68     }
  69     private ValueParameter<MultiAnalyzer> AnalyzerParameter {
  70       get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
  71     }
  72     public FixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
  73       get { return (FixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
  74     }
  75     #endregion
  76
  77     #region Properties
  78     private RandomCreator RandomCreator {
  79       get { return (RandomCreator)OperatorGraph.InitialOperator; }
  80     }
  81     public MultiAnalyzer Analyzer {
  82       get { return AnalyzerParameter.Value; }
  83       set { AnalyzerParameter.Value = value; }
  84     }
  85     private SolutionsCreator SolutionsCreator {
  86       get { return (SolutionsCreator)RandomCreator.Successor; }
  87     }
  88     private VariableNeighborhoodSearchMainLoop MainLoop {
  89       get { return FindMainLoop(SolutionsCreator.Successor); }
  90     }
  91     public int Seed {
  92       get { return SeedParameter.Value.Value; }
  93       set { SeedParameter.Value.Value = value; }
  94     }
  95     public bool SetSeedRandomly {
  96       get { return SetSeedRandomlyParameter.Value.Value; }
  97       set { SetSeedRandomlyParameter.Value.Value = value; }
  98     }
  99     public ILocalImprovementOperator LocalImprovement {
 100       get { return LocalImprovementParameter.Value; }
 101       set { LocalImprovementParameter.Value = value; }
 102     }
 103     public IMultiNeighborhoodShakingOperator ShakingOperator {
 104       get { return ShakingOperatorParameter.Value; }
 105       set { ShakingOperatorParameter.Value = value; }
 106     }
 107     public int MaximumIterations {
 108       get { return MaximumIterationsParameter.Value.Value; }
 109       set { MaximumIterationsParameter.Value.Value = value; }
 110     }
 111     public int LocalImprovementMaximumIterations {
 112       get { return LocalImprovementMaximumIterationsParameter.Value.Value; }
 113       set { LocalImprovementMaximumIterationsParameter.Value.Value = value; }
 114     }
 115     #endregion
 116
 117     [Storable]
 118     private BestAverageWorstQualityAnalyzer qualityAnalyzer;
 119
 120     [StorableConstructor]
 121     private VariableNeighborhoodSearch(bool deserializing) : base(deserializing) { }
 122     private VariableNeighborhoodSearch(VariableNeighborhoodSearch original, Cloner cloner)
 123       : base(original, cloner) {
 124       qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
 125       RegisterEventHandlers();
 126     }
 127     public VariableNeighborhoodSearch()
 128       : base() {
 129       Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
 130       Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
 131       Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation"));
 132       Parameters.Add(new ConstrainedValueParameter<IMultiNeighborhoodShakingOperator>("ShakingOperator", "The operator that performs the shaking of solutions."));
 133       Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations which should be processed.", new IntValue(50)));
 134       Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations which should be performed in the local improvement phase.", new IntValue(50)));
 135       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
 136
 137       RandomCreator randomCreator = new RandomCreator();
 138       SolutionsCreator solutionsCreator = new SolutionsCreator();
 139       VariableCreator variableCreator = new VariableCreator();
 140       ResultsCollector resultsCollector = new ResultsCollector();
 141       VariableNeighborhoodSearchMainLoop mainLoop = new VariableNeighborhoodSearchMainLoop();
 142       OperatorGraph.InitialOperator = randomCreator;
 143
 144       randomCreator.RandomParameter.ActualName = "Random";
 145       randomCreator.SeedParameter.ActualName = SeedParameter.Name;
 146       randomCreator.SeedParameter.Value = null;
 147       randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
 148       randomCreator.SetSeedRandomlyParameter.Value = null;
 149       randomCreator.Successor = solutionsCreator;
 150
 151       solutionsCreator.NumberOfSolutions = new IntValue(1);
 152       solutionsCreator.Successor = variableCreator;
 153
 154       variableCreator.Name = "Initialize Evaluated Solutions";
 155
 156       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
 157       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
 158       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("CurrentNeighborhoodIndex", new IntValue(0)));
 159       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("NeighborhoodCount", new IntValue(0)));
 160       variableCreator.Successor = resultsCollector;
 161
 162       resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Solutions", null, "EvaluatedSolutions"));
 163       resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
 164       resultsCollector.ResultsParameter.ActualName = "Results";
 165       resultsCollector.Successor = mainLoop;
 166
 167       mainLoop.IterationsParameter.ActualName = "Iterations";
 168       mainLoop.CurrentNeighborhoodIndexParameter.ActualName = "CurrentNeighborhoodIndex";
 169       mainLoop.NeighborhoodCountParameter.ActualName = "NeighborhoodCount";
 170       mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
 171       mainLoop.ShakingOperatorParameter.ActualName = ShakingOperatorParameter.Name;
 172       mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
 173       mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
 174       mainLoop.ResultsParameter.ActualName = "Results";
 175       mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
 176       mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
 177
 178       InitializeLocalImprovementOperators();
 179       qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
 180       ParameterizeAnalyzers();
 181       UpdateAnalyzers();
 182
 183       RegisterEventHandlers();
 184     }
 185
 186     public override IDeepCloneable Clone(Cloner cloner) {
 187       return new VariableNeighborhoodSearch(this, cloner);
 188     }
 189
 190     [StorableHook(HookType.AfterDeserialization)]
 191     private void AfterDeserialization() {
 192       RegisterEventHandlers();
 193     }
 194
 195     public override void Prepare() {
 196       if (Problem != null) base.Prepare();
 197     }
 198
 199     private void RegisterEventHandlers() {
 200       LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
 201       if (Problem != null) {
 202         Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 203       }
 204     }
 205
 206     #region Events
 207     protected override void OnProblemChanged() {
 208       InitializeLocalImprovementOperators();
 209       UpdateShakingOperators();
 210       UpdateAnalyzers();
 211
 212       ParameterizeStochasticOperator(Problem.SolutionCreator);
 213       ParameterizeStochasticOperator(Problem.Evaluator);
 214       foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
 215       ParameterizeSolutionsCreator();
 216       ParameterizeMainLoop();
 217       ParameterizeAnalyzers();
 218       ParameterizeIterationBasedOperators();
 219       ParameterizeLocalImprovementOperators();
 220       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 221       base.OnProblemChanged();
 222     }
 223     protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
 224       ParameterizeStochasticOperator(Problem.SolutionCreator);
 225       ParameterizeSolutionsCreator();
 226       base.Problem_SolutionCreatorChanged(sender, e);
 227     }
 228     protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
 229       ParameterizeStochasticOperator(Problem.Evaluator);
 230       ParameterizeSolutionsCreator();
 231       ParameterizeMainLoop();
 232       ParameterizeAnalyzers();
 233       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 234       base.Problem_EvaluatorChanged(sender, e);
 235     }
 236     protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
 237       UpdateShakingOperators();
 238       UpdateAnalyzers();
 239       foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
 240       ParameterizeIterationBasedOperators();
 241       base.Problem_OperatorsChanged(sender, e);
 242     }
 243     private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
 244       ParameterizeMainLoop();
 245       ParameterizeAnalyzers();
 246     }
 247     private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
 248       ParameterizeLocalImprovementOperators();
 249     }
 250     #endregion
 251
 252     #region Helpers
 253     private void ParameterizeSolutionsCreator() {
 254       SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
 255       SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
 256     }
 257     private void ParameterizeStochasticOperator(IOperator op) {
 258       if (op is IStochasticOperator)
 259         ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
 260     }
 261     private void ParameterizeMainLoop() {
 262       MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
 263       MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
 264       MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
 265     }
 266     private void ParameterizeAnalyzers() {
 267       qualityAnalyzer.ResultsParameter.ActualName = "Results";
 268       if (Problem != null) {
 269         qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
 270         qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
 271         qualityAnalyzer.QualityParameter.Depth = 1;
 272         qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
 273       }
 274     }
 275     private void ParameterizeIterationBasedOperators() {
 276       if (Problem != null) {
 277         foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
 278           op.IterationsParameter.ActualName = "Iterations";
 279           op.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
 280         }
 281       }
 282     }
 283     private void ParameterizeLocalImprovementOperators() {
 284       foreach (ILocalImprovementOperator op in LocalImprovementParameter.ValidValues) {
 285         if (op != LocalImprovementParameter.Value) op.Problem = null;
 286         op.MaximumIterationsParameter.Value = null;
 287         op.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
 288       }
 289       if (LocalImprovementParameter.Value != null)
 290         LocalImprovementParameter.Value.Problem = Problem;
 291     }
 292     private void InitializeLocalImprovementOperators() {
 293       if (Problem == null) {
 294         LocalImprovementParameter.ValidValues.Clear();
 295       } else {
 296         LocalImprovementParameter.ValidValues.RemoveWhere(x => !x.ProblemType.IsAssignableFrom(Problem.GetType()));
 297         foreach (ILocalImprovementOperator op in ApplicationManager.Manager.GetInstances<ILocalImprovementOperator>().Where(x => x.ProblemType.IsAssignableFrom(Problem.GetType()))) {
 298           if (!LocalImprovementParameter.ValidValues.Any(x => x.GetType() == op.GetType()))
 299             LocalImprovementParameter.ValidValues.Add(op);
 300         }
 301       }
 302     }
 303     private void UpdateShakingOperators() {
 304       ShakingOperatorParameter.ValidValues.Clear();
 305       foreach (IMultiNeighborhoodShakingOperator op in Problem.Operators.OfType<IMultiNeighborhoodShakingOperator>()) {
 306         ShakingOperatorParameter.ValidValues.Add(op);
 307         op.CurrentNeighborhoodIndexParameter.ActualName = "CurrentNeighborhoodIndex";
 308         op.NeighborhoodCountParameter.ActualName = "NeighborhoodCount";
 309       }
 310     }
 311     private void UpdateAnalyzers() {
 312       Analyzer.Operators.Clear();
 313       if (Problem != null) {
 314         foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
 315           foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
 316             param.Depth = 1;
 317           Analyzer.Operators.Add(analyzer);
 318         }
 319       }
 320       Analyzer.Operators.Add(qualityAnalyzer);
 321     }
 322     private VariableNeighborhoodSearchMainLoop FindMainLoop(IOperator start) {
 323       IOperator mainLoop = start;
 324       while (mainLoop != null && !(mainLoop is VariableNeighborhoodSearchMainLoop))
 325         mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
 326       if (mainLoop == null) return null;
 327       else return (VariableNeighborhoodSearchMainLoop)mainLoop;
 328     }
 329     #endregion
 330   }
 331 }