sources/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearch.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.Collections.Generic;
  24 using System.Linq;
  25 using HeuristicLab.Analysis;
  26 using HeuristicLab.Common;
  27 using HeuristicLab.Core;
  28 using HeuristicLab.Data;
  29 using HeuristicLab.Operators;
  30 using HeuristicLab.Optimization;
  31 using HeuristicLab.Optimization.Operators;
  32 using HeuristicLab.Parameters;
  33 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
  34 using HeuristicLab.Random;
  35
  36 namespace HeuristicLab.Algorithms.LocalSearch {
  37   [Item("Local Search", "A local search algorithm.")]
  38   [Creatable("Algorithms")]
  39   [StorableClass]
  40   public sealed class LocalSearch : 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 ValueParameter<IntValue> SeedParameter {
  55       get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
  56     }
  57     private ValueParameter<BoolValue> SetSeedRandomlyParameter {
  58       get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
  59     }
  60     public ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
  61       get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
  62     }
  63     public ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
  64       get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
  65     }
  66     public ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
  67       get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
  68     }
  69     private ValueParameter<IntValue> MaximumIterationsParameter {
  70       get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
  71     }
  72     private ValueParameter<IntValue> SampleSizeParameter {
  73       get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
  74     }
  75     private ValueParameter<MultiAnalyzer> AnalyzerParameter {
  76       get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
  77     }
  78     #endregion
  79
  80     #region Properties
  81     public IntValue Seed {
  82       get { return SeedParameter.Value; }
  83       set { SeedParameter.Value = value; }
  84     }
  85     public BoolValue SetSeedRandomly {
  86       get { return SetSeedRandomlyParameter.Value; }
  87       set { SetSeedRandomlyParameter.Value = value; }
  88     }
  89     public IMoveGenerator MoveGenerator {
  90       get { return MoveGeneratorParameter.Value; }
  91       set { MoveGeneratorParameter.Value = value; }
  92     }
  93     public IMoveMaker MoveMaker {
  94       get { return MoveMakerParameter.Value; }
  95       set { MoveMakerParameter.Value = value; }
  96     }
  97     public ISingleObjectiveMoveEvaluator MoveEvaluator {
  98       get { return MoveEvaluatorParameter.Value; }
  99       set { MoveEvaluatorParameter.Value = value; }
 100     }
 101     public IntValue MaximumIterations {
 102       get { return MaximumIterationsParameter.Value; }
 103       set { MaximumIterationsParameter.Value = value; }
 104     }
 105     public IntValue SampleSize {
 106       get { return SampleSizeParameter.Value; }
 107       set { SampleSizeParameter.Value = value; }
 108     }
 109     public MultiAnalyzer Analyzer {
 110       get { return AnalyzerParameter.Value; }
 111       set { AnalyzerParameter.Value = value; }
 112     }
 113     private RandomCreator RandomCreator {
 114       get { return (RandomCreator)OperatorGraph.InitialOperator; }
 115     }
 116     private SolutionsCreator SolutionsCreator {
 117       get { return (SolutionsCreator)RandomCreator.Successor; }
 118     }
 119     private LocalSearchMainLoop MainLoop {
 120       get { return FindMainLoop(SolutionsCreator.Successor); }
 121     }
 122     [Storable]
 123     private BestAverageWorstQualityAnalyzer moveQualityAnalyzer;
 124     #endregion
 125
 126     [StorableConstructor]
 127     private LocalSearch(bool deserializing) : base(deserializing) { }
 128     [StorableHook(HookType.AfterDeserialization)]
 129     private void AfterDeserialization() {
 130       Initialize();
 131     }
 132     private LocalSearch(LocalSearch original, Cloner cloner)
 133       : base(original, cloner) {
 134       moveQualityAnalyzer = cloner.Clone(original.moveQualityAnalyzer);
 135       Initialize();
 136     }
 137     public override IDeepCloneable Clone(Cloner cloner) {
 138       return new LocalSearch(this, cloner);
 139     }
 140     public LocalSearch()
 141       : base() {
 142       Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
 143       Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
 144       Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
 145       Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
 146       Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
 147       Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
 148       Parameters.Add(new ValueParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(100)));
 149       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
 150
 151       RandomCreator randomCreator = new RandomCreator();
 152       SolutionsCreator solutionsCreator = new SolutionsCreator();
 153       VariableCreator variableCreator = new VariableCreator();
 154       ResultsCollector resultsCollector = new ResultsCollector();
 155       LocalSearchMainLoop mainLoop = new LocalSearchMainLoop();
 156       OperatorGraph.InitialOperator = randomCreator;
 157
 158       randomCreator.RandomParameter.ActualName = "Random";
 159       randomCreator.SeedParameter.ActualName = SeedParameter.Name;
 160       randomCreator.SeedParameter.Value = null;
 161       randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
 162       randomCreator.SetSeedRandomlyParameter.Value = null;
 163       randomCreator.Successor = solutionsCreator;
 164
 165       solutionsCreator.NumberOfSolutions = new IntValue(1);
 166       solutionsCreator.Successor = variableCreator;
 167
 168       variableCreator.Name = "Initialize EvaluatedMoves";
 169       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedMoves", new IntValue()));
 170       variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
 171       variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(0)));
 172       variableCreator.Successor = resultsCollector;
 173
 174       resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Moves", null, "EvaluatedMoves"));
 175       resultsCollector.ResultsParameter.ActualName = "Results";
 176       resultsCollector.Successor = mainLoop;
 177
 178       mainLoop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
 179       mainLoop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
 180       mainLoop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
 181       mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
 182       mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
 183       mainLoop.ResultsParameter.ActualName = "Results";
 184       mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
 185       mainLoop.EvaluatedMovesParameter.ActualName = "EvaluatedMoves";
 186       mainLoop.IterationsParameter.ActualName = "Iterations";
 187       mainLoop.BestLocalQualityParameter.ActualName = "BestQuality";
 188
 189       moveQualityAnalyzer = new BestAverageWorstQualityAnalyzer();
 190       ParameterizeAnalyzers();
 191       UpdateAnalyzers();
 192
 193       Initialize();
 194     }
 195
 196     public override void Prepare() {
 197       if (Problem != null && MoveGenerator != null && MoveMaker != null && MoveEvaluator != null)
 198         base.Prepare();
 199     }
 200
 201     #region Events
 202     protected override void OnProblemChanged() {
 203       ParameterizeStochasticOperator(Problem.SolutionCreator);
 204       ParameterizeStochasticOperator(Problem.Evaluator);
 205       foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
 206       foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
 207         op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
 208       }
 209       ParameterizeSolutionsCreator();
 210       ParameterizeMainLoop();
 211       UpdateMoveGenerator();
 212       UpdateMoveParameters();
 213       UpdateAnalyzers();
 214       ParameterizeMoveGenerators();
 215       ParameterizeMoveEvaluators();
 216       ParameterizeMoveMakers();
 217       ParameterizeAnalyzers();
 218       ParameterizeIterationBasedOperators();
 219       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 220       base.OnProblemChanged();
 221     }
 222     protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
 223       ParameterizeStochasticOperator(Problem.SolutionCreator);
 224       ParameterizeSolutionsCreator();
 225       base.Problem_SolutionCreatorChanged(sender, e);
 226     }
 227     protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
 228       ParameterizeStochasticOperator(Problem.Evaluator);
 229       ParameterizeSolutionsCreator();
 230       ParameterizeMainLoop();
 231       ParameterizeMoveEvaluators();
 232       ParameterizeMoveMakers();
 233       ParameterizeAnalyzers();
 234       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 235       base.Problem_EvaluatorChanged(sender, e);
 236     }
 237     protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
 238       foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
 239       // This may seem pointless, but some operators already have the eventhandler registered, others don't
 240       // FIXME: Is there another way to solve this problem?
 241       foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
 242         op.MoveQualityParameter.ActualNameChanged -= new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
 243         op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
 244       }
 245       UpdateMoveGenerator();
 246       UpdateMoveParameters();
 247       UpdateAnalyzers();
 248       ParameterizeMainLoop();
 249       ParameterizeMoveGenerators();
 250       ParameterizeMoveEvaluators();
 251       ParameterizeMoveMakers();
 252       ParameterizeAnalyzers();
 253       ParameterizeIterationBasedOperators();
 254       base.Problem_OperatorsChanged(sender, e);
 255     }
 256     private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
 257       ParameterizeMainLoop();
 258       ParameterizeMoveEvaluators();
 259       ParameterizeMoveMakers();
 260     }
 261     private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
 262       UpdateMoveParameters();
 263     }
 264     private void MoveEvaluatorParameter_ValueChanged(object sender, EventArgs e) {
 265       ParameterizeMainLoop();
 266       ParameterizeMoveEvaluators();
 267       ParameterizeMoveMakers();
 268       ParameterizeAnalyzers();
 269     }
 270     private void MoveEvaluator_MoveQualityParameter_ActualNameChanged(object sender, EventArgs e) {
 271       ParameterizeMainLoop();
 272       ParameterizeMoveEvaluators();
 273       ParameterizeMoveMakers();
 274       ParameterizeAnalyzers();
 275     }
 276     #endregion
 277
 278     #region Helpers
 279     private void Initialize() {
 280       if (Problem != null) {
 281         Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
 282         foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
 283           op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
 284         }
 285       }
 286       MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
 287       MoveEvaluatorParameter.ValueChanged += new EventHandler(MoveEvaluatorParameter_ValueChanged);
 288     }
 289     private void UpdateMoveGenerator() {
 290       IMoveGenerator oldMoveGenerator = MoveGenerator;
 291       MoveGeneratorParameter.ValidValues.Clear();
 292       if (Problem != null) {
 293         foreach (IMoveGenerator generator in Problem.Operators.OfType<IMoveGenerator>().OrderBy(x => x.Name))
 294           MoveGeneratorParameter.ValidValues.Add(generator);
 295       }
 296       if (oldMoveGenerator != null) {
 297         IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
 298         if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
 299       }
 300       if (MoveGenerator == null) {
 301         ClearMoveParameters();
 302       }
 303     }
 304     private void UpdateMoveParameters() {
 305       IMoveMaker oldMoveMaker = MoveMaker;
 306       ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
 307       ClearMoveParameters();
 308       if (MoveGenerator != null) {
 309         List<Type> moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList();
 310         foreach (Type type in moveTypes.ToList()) {
 311           if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t)))
 312             moveTypes.Remove(type);
 313         }
 314         foreach (Type type in moveTypes) {
 315           var operators = Problem.Operators.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
 316           foreach (IMoveMaker moveMaker in operators.OfType<IMoveMaker>())
 317             MoveMakerParameter.ValidValues.Add(moveMaker);
 318           foreach (ISingleObjectiveMoveEvaluator moveEvaluator in operators.OfType<ISingleObjectiveMoveEvaluator>())
 319             MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
 320         }
 321         if (oldMoveMaker != null) {
 322           IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
 323           if (mm != null) MoveMaker = mm;
 324         }
 325         if (oldMoveEvaluator != null) {
 326           ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
 327           if (me != null) MoveEvaluator = me;
 328         }
 329       }
 330     }
 331     private void UpdateAnalyzers() {
 332       Analyzer.Operators.Clear();
 333       if (Problem != null) {
 334         foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
 335           foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
 336             param.Depth = 0;
 337           Analyzer.Operators.Add(analyzer);
 338         }
 339       }
 340       Analyzer.Operators.Add(moveQualityAnalyzer);
 341     }
 342     private void ClearMoveParameters() {
 343       MoveMakerParameter.ValidValues.Clear();
 344       MoveEvaluatorParameter.ValidValues.Clear();
 345     }
 346     private void ParameterizeSolutionsCreator() {
 347       SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
 348       SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
 349     }
 350     private void ParameterizeMainLoop() {
 351       if (Problem != null) {
 352         MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
 353         MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
 354         MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
 355       }
 356       if (MoveEvaluator != null)
 357         MainLoop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
 358     }
 359     private void ParameterizeStochasticOperator(IOperator op) {
 360       if (op is IStochasticOperator) {
 361         IStochasticOperator stOp = (IStochasticOperator)op;
 362         stOp.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
 363         stOp.RandomParameter.Hidden = true;
 364       }
 365     }
 366     private void ParameterizeMoveGenerators() {
 367       if (Problem != null) {
 368         foreach (IMultiMoveGenerator generator in Problem.Operators.OfType<IMultiMoveGenerator>()) {
 369           generator.SampleSizeParameter.ActualName = SampleSizeParameter.Name;
 370           generator.SampleSizeParameter.Hidden = true;
 371         }
 372       }
 373     }
 374     private void ParameterizeMoveEvaluators() {
 375       foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
 376         op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
 377         op.QualityParameter.Hidden = true;
 378       }
 379     }
 380     private void ParameterizeMoveMakers() {
 381       foreach (IMoveMaker op in Problem.Operators.OfType<IMoveMaker>()) {
 382         op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
 383         op.QualityParameter.Hidden = true;
 384         if (MoveEvaluator != null) {
 385           op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
 386           op.MoveQualityParameter.Hidden = true;
 387         } else {
 388           op.MoveQualityParameter.Hidden = false;
 389         }
 390       }
 391     }
 392     private void ParameterizeAnalyzers() {
 393       moveQualityAnalyzer.ResultsParameter.ActualName = "Results";
 394       moveQualityAnalyzer.ResultsParameter.Hidden = true;
 395       if (Problem != null) {
 396         moveQualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
 397         moveQualityAnalyzer.MaximizationParameter.Hidden = true;
 398         if (MoveEvaluator != null) {
 399           moveQualityAnalyzer.QualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
 400           moveQualityAnalyzer.QualityParameter.Hidden = true;
 401         } else moveQualityAnalyzer.QualityParameter.Hidden = false;
 402         moveQualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
 403         moveQualityAnalyzer.BestKnownQualityParameter.Hidden = true;
 404       } else {
 405         moveQualityAnalyzer.MaximizationParameter.Hidden = false;
 406         moveQualityAnalyzer.BestKnownQualityParameter.Hidden = false;
 407       }
 408     }
 409     private void ParameterizeIterationBasedOperators() {
 410       if (Problem != null) {
 411         foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
 412           op.IterationsParameter.ActualName = "Iterations";
 413           op.IterationsParameter.Hidden = true;
 414           op.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
 415           op.MaximumIterationsParameter.Hidden = true;
 416         }
 417       }
 418     }
 419     private LocalSearchMainLoop FindMainLoop(IOperator start) {
 420       IOperator mainLoop = start;
 421       while (mainLoop != null && !(mainLoop is LocalSearchMainLoop))
 422         mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
 423       if (mainLoop == null) return null;
 424       else return (LocalSearchMainLoop)mainLoop;
 425     }
 426     #endregion
 427   }
 428 }