#1553: added remaining unit tests to create and run optimizer samples.
[hl.git] / sources / HeuristicLab.Algorithms.SimulatedAnnealing / 3.3 / SimulatedAnnealing.cs
blob16bf72283ba12c5c363e9c1479eb5ef22bc0ff12
1 #region License Information
2 /* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
5 * This file is part of HeuristicLab.
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.
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.
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/>.
20 #endregion
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.PluginInfrastructure;
35 using HeuristicLab.Random;
37 namespace HeuristicLab.Algorithms.SimulatedAnnealing {
38 [Item("Simulated Annealing", "A simulated annealing algorithm.")]
39 [Creatable("Algorithms")]
40 [StorableClass]
41 public sealed class SimulatedAnnealing : HeuristicOptimizationEngineAlgorithm, IStorableContent {
42 public string Filename { get; set; }
44 #region Problem Properties
45 public override Type ProblemType {
46 get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
48 public new ISingleObjectiveHeuristicOptimizationProblem Problem {
49 get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
50 set { base.Problem = value; }
52 #endregion
54 #region Parameter Properties
55 private ValueParameter<IntValue> SeedParameter {
56 get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
58 private ValueParameter<BoolValue> SetSeedRandomlyParameter {
59 get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
61 public ConstrainedValueParameter<IMultiMoveGenerator> MoveGeneratorParameter {
62 get { return (ConstrainedValueParameter<IMultiMoveGenerator>)Parameters["MoveGenerator"]; }
64 public ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
65 get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
67 public ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
68 get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
70 public ConstrainedValueParameter<IDiscreteDoubleValueModifier> AnnealingOperatorParameter {
71 get { return (ConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["AnnealingOperator"]; }
73 private ValueParameter<IntValue> MaximumIterationsParameter {
74 get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
76 private ValueParameter<IntValue> InnerIterationsParameter {
77 get { return (ValueParameter<IntValue>)Parameters["InnerIterations"]; }
79 private ValueParameter<DoubleValue> StartTemperatureParameter {
80 get { return (ValueParameter<DoubleValue>)Parameters["StartTemperature"]; }
82 private ValueParameter<DoubleValue> EndTemperatureParameter {
83 get { return (ValueParameter<DoubleValue>)Parameters["EndTemperature"]; }
85 private ValueParameter<MultiAnalyzer> AnalyzerParameter {
86 get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
88 #endregion
90 #region Properties
91 public IntValue Seed {
92 get { return SeedParameter.Value; }
93 set { SeedParameter.Value = value; }
95 public BoolValue SetSeedRandomly {
96 get { return SetSeedRandomlyParameter.Value; }
97 set { SetSeedRandomlyParameter.Value = value; }
99 public IMultiMoveGenerator MoveGenerator {
100 get { return MoveGeneratorParameter.Value; }
101 set { MoveGeneratorParameter.Value = value; }
103 public IMoveMaker MoveMaker {
104 get { return MoveMakerParameter.Value; }
105 set { MoveMakerParameter.Value = value; }
107 public ISingleObjectiveMoveEvaluator MoveEvaluator {
108 get { return MoveEvaluatorParameter.Value; }
109 set { MoveEvaluatorParameter.Value = value; }
111 public IDiscreteDoubleValueModifier AnnealingOperator {
112 get { return AnnealingOperatorParameter.Value; }
113 set { AnnealingOperatorParameter.Value = value; }
115 public IntValue MaximumIterations {
116 get { return MaximumIterationsParameter.Value; }
117 set { MaximumIterationsParameter.Value = value; }
119 public IntValue InnerIterations {
120 get { return InnerIterationsParameter.Value; }
121 set { InnerIterationsParameter.Value = value; }
123 public DoubleValue StartTemperature {
124 get { return StartTemperatureParameter.Value; }
125 set { StartTemperatureParameter.Value = value; }
127 public DoubleValue EndTemperature {
128 get { return EndTemperatureParameter.Value; }
129 set { EndTemperatureParameter.Value = value; }
131 public MultiAnalyzer Analyzer {
132 get { return AnalyzerParameter.Value; }
133 set { AnalyzerParameter.Value = value; }
135 private RandomCreator RandomCreator {
136 get { return (RandomCreator)OperatorGraph.InitialOperator; }
138 private SolutionsCreator SolutionsCreator {
139 get { return (SolutionsCreator)RandomCreator.Successor; }
141 private SimulatedAnnealingMainLoop MainLoop {
142 get { return FindMainLoop(SolutionsCreator.Successor); }
144 [Storable]
145 private QualityAnalyzer qualityAnalyzer;
146 #endregion
148 [StorableConstructor]
149 private SimulatedAnnealing(bool deserializing) : base(deserializing) { }
150 [StorableHook(HookType.AfterDeserialization)]
151 private void AfterDeserialization() {
152 Initialize();
154 private SimulatedAnnealing(SimulatedAnnealing original, Cloner cloner)
155 : base(original, cloner) {
156 qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
157 Initialize();
159 public override IDeepCloneable Clone(Cloner cloner) {
160 return new SimulatedAnnealing(this, cloner);
162 public SimulatedAnnealing()
163 : base() {
164 Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
165 Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
166 Parameters.Add(new ConstrainedValueParameter<IMultiMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
167 Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
168 Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
169 Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>("AnnealingOperator", "The operator used to modify the temperature."));
170 Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(100)));
171 Parameters.Add(new ValueParameter<IntValue>("InnerIterations", "The amount of inner iterations (number of moves before temperature is adjusted again).", new IntValue(10)));
172 Parameters.Add(new ValueParameter<DoubleValue>("StartTemperature", "The initial temperature.", new DoubleValue(100)));
173 Parameters.Add(new ValueParameter<DoubleValue>("EndTemperature", "The final temperature which should be reached when iterations reaches maximum iterations.", new DoubleValue(1e-6)));
174 Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each generation.", new MultiAnalyzer()));
176 RandomCreator randomCreator = new RandomCreator();
177 SolutionsCreator solutionsCreator = new SolutionsCreator();
178 VariableCreator variableCreator = new VariableCreator();
179 ResultsCollector resultsCollector = new ResultsCollector();
180 SimulatedAnnealingMainLoop mainLoop = new SimulatedAnnealingMainLoop();
181 OperatorGraph.InitialOperator = randomCreator;
183 randomCreator.RandomParameter.ActualName = "Random";
184 randomCreator.SeedParameter.ActualName = SeedParameter.Name;
185 randomCreator.SeedParameter.Value = null;
186 randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
187 randomCreator.SetSeedRandomlyParameter.Value = null;
188 randomCreator.Successor = solutionsCreator;
190 solutionsCreator.NumberOfSolutions = new IntValue(1);
191 solutionsCreator.Successor = variableCreator;
193 variableCreator.Name = "Initialize EvaluatedMoves";
194 variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedMoves", new IntValue()));
195 variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
196 variableCreator.Successor = resultsCollector;
198 resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Evaluated Moves", null, "EvaluatedMoves"));
199 resultsCollector.ResultsParameter.ActualName = "Results";
200 resultsCollector.Successor = mainLoop;
202 mainLoop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
203 mainLoop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
204 mainLoop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
205 mainLoop.AnnealingOperatorParameter.ActualName = AnnealingOperatorParameter.Name;
206 mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
207 mainLoop.StartTemperatureParameter.ActualName = StartTemperatureParameter.Name;
208 mainLoop.EndTemperatureParameter.ActualName = EndTemperatureParameter.Name;
209 mainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
210 mainLoop.ResultsParameter.ActualName = "Results";
211 mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
212 mainLoop.EvaluatedMovesParameter.ActualName = "EvaluatedMoves";
213 mainLoop.IterationsParameter.ActualName = "Iterations";
215 foreach (IDiscreteDoubleValueModifier op in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
216 AnnealingOperatorParameter.ValidValues.Add(op);
217 ParameterizeAnnealingOperators();
219 qualityAnalyzer = new QualityAnalyzer();
220 ParameterizeAnalyzers();
221 UpdateAnalyzers();
223 Initialize();
226 public override void Prepare() {
227 if (Problem != null && MoveGenerator != null && MoveMaker != null && MoveEvaluator != null)
228 base.Prepare();
231 #region Events
232 protected override void OnProblemChanged() {
233 ParameterizeStochasticOperator(Problem.SolutionCreator);
234 ParameterizeStochasticOperator(Problem.Evaluator);
235 foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
236 foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
237 op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
239 ParameterizeSolutionsCreator();
240 ParameterizeMainLoop();
241 UpdateMoveGenerator();
242 UpdateMoveParameters();
243 UpdateAnalyzers();
244 ParameterizeMoveEvaluators();
245 ParameterizeMoveMakers();
246 ParameterizeMoveGenerators();
247 ParameterizeAnalyzers();
248 ParameterizeIterationBasedOperators();
249 Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
250 base.OnProblemChanged();
252 protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
253 ParameterizeStochasticOperator(Problem.SolutionCreator);
254 ParameterizeSolutionsCreator();
255 base.Problem_SolutionCreatorChanged(sender, e);
257 protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
258 ParameterizeStochasticOperator(Problem.Evaluator);
259 ParameterizeSolutionsCreator();
260 ParameterizeMainLoop();
261 ParameterizeMoveEvaluators();
262 ParameterizeMoveMakers();
263 ParameterizeAnalyzers();
264 Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
265 base.Problem_EvaluatorChanged(sender, e);
267 protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
268 foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
269 // This may seem pointless, but some operators already have the eventhandler registered, others don't
270 // FIXME: Is there another way to solve this problem?
271 foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
272 op.MoveQualityParameter.ActualNameChanged -= new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
273 op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
275 UpdateMoveGenerator();
276 UpdateMoveParameters();
277 UpdateAnalyzers();
278 ParameterizeMainLoop();
279 ParameterizeMoveEvaluators();
280 ParameterizeMoveMakers();
281 ParameterizeMoveGenerators();
282 ParameterizeIterationBasedOperators();
283 base.Problem_OperatorsChanged(sender, e);
285 private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
286 ParameterizeMainLoop();
287 ParameterizeMoveEvaluators();
288 ParameterizeMoveMakers();
289 ParameterizeAnalyzers();
291 private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
292 UpdateMoveParameters();
294 private void MoveEvaluatorParameter_ValueChanged(object sender, EventArgs e) {
295 ParameterizeMainLoop();
296 ParameterizeMoveEvaluators();
297 ParameterizeMoveMakers();
299 private void MoveEvaluator_MoveQualityParameter_ActualNameChanged(object sender, EventArgs e) {
300 ParameterizeMainLoop();
301 ParameterizeMoveEvaluators();
302 ParameterizeMoveMakers();
304 #endregion
306 #region Helpers
307 private void Initialize() {
308 if (Problem != null) {
309 Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
310 foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
311 op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
314 MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
315 MoveEvaluatorParameter.ValueChanged += new EventHandler(MoveEvaluatorParameter_ValueChanged);
317 private void UpdateMoveGenerator() {
318 IMultiMoveGenerator oldMoveGenerator = MoveGenerator;
319 MoveGeneratorParameter.ValidValues.Clear();
320 if (Problem != null) {
321 foreach (IMultiMoveGenerator generator in Problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
322 MoveGeneratorParameter.ValidValues.Add(generator);
324 if (oldMoveGenerator != null) {
325 IMultiMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
326 if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
328 if (MoveGenerator == null) {
329 ClearMoveParameters();
332 private void ParameterizeAnalyzers() {
333 qualityAnalyzer.ResultsParameter.ActualName = "Results";
334 if (Problem != null) {
335 qualityAnalyzer.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
336 qualityAnalyzer.MaximizationParameter.Hidden = true;
337 qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
338 qualityAnalyzer.QualityParameter.Depth = 0;
339 qualityAnalyzer.QualityParameter.Hidden = true;
340 qualityAnalyzer.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
341 qualityAnalyzer.BestKnownQualityParameter.Hidden = true;
342 } else {
343 qualityAnalyzer.MaximizationParameter.Hidden = false;
344 qualityAnalyzer.QualityParameter.Hidden = false;
345 qualityAnalyzer.BestKnownQualityParameter.Hidden = false;
348 private void UpdateMoveParameters() {
349 IMoveMaker oldMoveMaker = MoveMaker;
350 ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
351 ClearMoveParameters();
352 if (MoveGenerator != null) {
353 List<Type> moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList();
354 foreach (Type type in moveTypes.ToList()) {
355 if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t)))
356 moveTypes.Remove(type);
358 foreach (Type type in moveTypes) {
359 var operators = Problem.Operators.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
360 foreach (IMoveMaker moveMaker in operators.OfType<IMoveMaker>())
361 MoveMakerParameter.ValidValues.Add(moveMaker);
362 foreach (ISingleObjectiveMoveEvaluator moveEvaluator in operators.OfType<ISingleObjectiveMoveEvaluator>())
363 MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
365 if (oldMoveMaker != null) {
366 IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
367 if (mm != null) MoveMaker = mm;
369 if (oldMoveEvaluator != null) {
370 ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
371 if (me != null) MoveEvaluator = me;
375 private void ClearMoveParameters() {
376 MoveMakerParameter.ValidValues.Clear();
377 MoveEvaluatorParameter.ValidValues.Clear();
379 private void ParameterizeSolutionsCreator() {
380 SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
381 SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
383 private void ParameterizeMainLoop() {
384 if (Problem != null) {
385 MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
386 MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
387 MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
389 if (MoveEvaluator != null)
390 MainLoop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
392 private void ParameterizeStochasticOperator(IOperator op) {
393 if (op is IStochasticOperator) {
394 IStochasticOperator stOp = (IStochasticOperator)op;
395 stOp.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
396 stOp.RandomParameter.Hidden = true;
399 private void ParameterizeMoveEvaluators() {
400 foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
401 op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
402 op.QualityParameter.Hidden = true;
405 private void ParameterizeMoveMakers() {
406 foreach (IMoveMaker op in Problem.Operators.OfType<IMoveMaker>()) {
407 op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
408 op.QualityParameter.Hidden = true;
409 if (MoveEvaluator != null) {
410 op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
411 op.MoveQualityParameter.Hidden = true;
412 } else {
413 op.MoveQualityParameter.Hidden = false;
417 private void ParameterizeAnnealingOperators() {
418 foreach (IDiscreteDoubleValueModifier op in AnnealingOperatorParameter.ValidValues) {
419 op.IndexParameter.ActualName = "Iterations";
420 op.IndexParameter.Hidden = true;
421 op.StartIndexParameter.Value = new IntValue(0);
422 op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name;
423 op.ValueParameter.ActualName = "Temperature";
424 op.ValueParameter.Hidden = true;
425 op.StartValueParameter.ActualName = StartTemperatureParameter.Name;
426 op.StartValueParameter.Hidden = true;
427 op.EndValueParameter.ActualName = EndTemperatureParameter.Name;
428 op.EndValueParameter.Hidden = true;
429 ParameterizeStochasticOperator(op);
432 private void ParameterizeMoveGenerators() {
433 foreach (IMultiMoveGenerator op in Problem.Operators.OfType<IMultiMoveGenerator>()) {
434 op.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
435 op.SampleSizeParameter.Hidden = true;
438 private void ParameterizeIterationBasedOperators() {
439 if (Problem != null) {
440 foreach (IIterationBasedOperator op in Problem.Operators.OfType<IIterationBasedOperator>()) {
441 op.IterationsParameter.ActualName = "Iterations";
442 op.IterationsParameter.Hidden = true;
443 op.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
444 op.MaximumIterationsParameter.Hidden = true;
448 private void UpdateAnalyzers() {
449 Analyzer.Operators.Clear();
450 if (Problem != null) {
451 foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
452 foreach (IScopeTreeLookupParameter param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
453 param.Depth = 0;
454 Analyzer.Operators.Add(analyzer);
457 Analyzer.Operators.Add(qualityAnalyzer);
459 private SimulatedAnnealingMainLoop FindMainLoop(IOperator start) {
460 IOperator mainLoop = start;
461 while (mainLoop != null && !(mainLoop is SimulatedAnnealingMainLoop))
462 mainLoop = ((SingleSuccessorOperator)mainLoop).Successor;
463 if (mainLoop == null) return null;
464 else return (SimulatedAnnealingMainLoop)mainLoop;
466 #endregion