Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Async/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingImprovementOperator.cs @ 12043

Last change on this file since 12043 was 11300, checked in by pfleck, 10 years ago

#2232
Introduced ILocalImprovementAlgorithmOperator to separate single operators for local improvement and operator graphs/algorithms for local improvement.
This way the ILocalImprovementOperator does not have to specify a problem type and does not store a problem any more.

The LocalSearchImprovementOperator and SimulatedAnnealingImprovementOperator implement the new ILocalImprovementAlgorithmOperator as they represent an operator graph for local improvement.
The QAP and VRP local improvement operators implement the ILocalImprovementOperator which does not store a problem anymore.

File size: 17.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2014 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
22using System;
23using System.Linq;
24using HeuristicLab.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33
34namespace HeuristicLab.Algorithms.SimulatedAnnealing {
35  /// <summary>
36  /// A simulated annealing improvement operator.
37  /// </summary>
38  [Item("SimulatedAnnealingImprovementOperator", "A simulated annealing improvement operator.")]
39  [StorableClass]
40  public sealed class SimulatedAnnealingImprovementOperator : SingleSuccessorOperator, ILocalImprovementAlgorithmOperator, IStochasticOperator {
41    #region IGenericLocalImprovementOperator Properties
42    public Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } }
43    public IProblem Problem {
44      get { return problem; }
45      set {
46        if (problem != value) {
47          if (value != null && !(value is ISingleObjectiveHeuristicOptimizationProblem))
48            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
49          if (problem != null) DeregisterProblemEventHandlers();
50          problem = (ISingleObjectiveHeuristicOptimizationProblem)value;
51          if (problem != null) RegisterProblemEventHandlers();
52          UpdateProblem();
53        }
54      }
55    }
56    #endregion
57
58    [Storable]
59    private ISingleObjectiveHeuristicOptimizationProblem problem;
60    [Storable]
61    private SimulatedAnnealingMainLoop loop;
62    [Storable]
63    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
64
65    #region Parameter Properties
66    public ILookupParameter<IRandom> RandomParameter {
67      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
68    }
69    public IConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
70      get { return (IConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
71    }
72    public IConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
73      get { return (IConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
74    }
75    public IConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
76      get { return (IConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
77    }
78    private IValueLookupParameter<IntValue> InnerIterationsParameter {
79      get { return (IValueLookupParameter<IntValue>)Parameters["InnerIterations"]; }
80    }
81    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
82      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
83    }
84    private ValueParameter<DoubleValue> StartTemperatureParameter {
85      get { return (ValueParameter<DoubleValue>)Parameters["StartTemperature"]; }
86    }
87    private ValueParameter<DoubleValue> EndTemperatureParameter {
88      get { return (ValueParameter<DoubleValue>)Parameters["EndTemperature"]; }
89    }
90    public IConstrainedValueParameter<IDiscreteDoubleValueModifier> AnnealingOperatorParameter {
91      get { return (IConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["AnnealingOperator"]; }
92    }
93    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
94      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
95    }
96    #region ILocalImprovementOperator Parameters
97    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
98      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
99    }
100    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
101      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
102    }
103    public ILookupParameter<ResultCollection> ResultsParameter {
104      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
105    }
106    #endregion
107    #endregion
108
109    #region Properties
110    public IMoveGenerator MoveGenerator {
111      get { return MoveGeneratorParameter.Value; }
112      set { MoveGeneratorParameter.Value = value; }
113    }
114    public IMoveMaker MoveMaker {
115      get { return MoveMakerParameter.Value; }
116      set { MoveMakerParameter.Value = value; }
117    }
118    public IDiscreteDoubleValueModifier AnnealingOperator {
119      get { return AnnealingOperatorParameter.Value; }
120      set { AnnealingOperatorParameter.Value = value; }
121    }
122    public ISingleObjectiveMoveEvaluator MoveEvaluator {
123      get { return MoveEvaluatorParameter.Value; }
124      set { MoveEvaluatorParameter.Value = value; }
125    }
126    public MultiAnalyzer Analyzer {
127      get { return AnalyzerParameter.Value; }
128      set { AnalyzerParameter.Value = value; }
129    }
130    #endregion
131
132    [StorableConstructor]
133    private SimulatedAnnealingImprovementOperator(bool deserializing) : base(deserializing) { }
134    private SimulatedAnnealingImprovementOperator(SimulatedAnnealingImprovementOperator original, Cloner cloner)
135      : base(original, cloner) {
136      this.problem = cloner.Clone(original.problem);
137      this.loop = cloner.Clone(original.loop);
138      this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
139      RegisterEventHandlers();
140    }
141    public SimulatedAnnealingImprovementOperator()
142      : base() {
143      loop = new SimulatedAnnealingMainLoop();
144
145      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
146
147      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
148      Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
149      Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
150      Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
151      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
152      Parameters.Add(new ValueLookupParameter<IntValue>("InnerIterations", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(1500)));
153      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
154      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
155      Parameters.Add(new ValueParameter<DoubleValue>("StartTemperature", "The initial temperature.", new DoubleValue(100)));
156      Parameters.Add(new ValueParameter<DoubleValue>("EndTemperature", "The final temperature which should be reached when iterations reaches maximum iterations.", new DoubleValue(1e-6)));
157      Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>("AnnealingOperator", "The operator used to modify the temperature."));
158      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The variable where the results are stored."));
159      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality/fitness value of a solution."));
160
161      foreach (IDiscreteDoubleValueModifier op in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
162        AnnealingOperatorParameter.ValidValues.Add(op);
163
164      ParameterizeAnnealingOperators();
165      ParameterizeSAMainLoop();
166
167      RegisterEventHandlers();
168    }
169
170    public override IDeepCloneable Clone(Cloner cloner) {
171      return new SimulatedAnnealingImprovementOperator(this, cloner);
172    }
173
174    [StorableHook(HookType.AfterDeserialization)]
175    private void AfterDeserialization() {
176      RegisterEventHandlers();
177    }
178
179    #region Event Handler Registration
180    private void RegisterEventHandlers() {
181      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
182      if (problem != null)
183        RegisterProblemEventHandlers();
184    }
185
186    private void RegisterProblemEventHandlers() {
187      problem.Reset += new EventHandler(problem_Reset);
188      problem.OperatorsChanged += new EventHandler(problem_OperatorsChanged);
189    }
190
191    private void DeregisterProblemEventHandlers() {
192      problem.Reset -= new EventHandler(problem_Reset);
193      problem.OperatorsChanged -= new EventHandler(problem_OperatorsChanged);
194    }
195    #endregion
196
197    #region Event Handlers
198    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
199      ChooseMoveOperators();
200      ParameterizeSAMainLoop();
201    }
202
203    private void problem_Reset(object sender, EventArgs e) {
204      UpdateProblem();
205    }
206
207    private void problem_OperatorsChanged(object sender, EventArgs e) {
208      UpdateProblem();
209    }
210    #endregion
211
212    private void ParameterizeAnnealingOperators() {
213      foreach (IDiscreteDoubleValueModifier op in AnnealingOperatorParameter.ValidValues) {
214        op.IndexParameter.ActualName = "LocalIterations";
215        op.StartIndexParameter.Value = new IntValue(0);
216        op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name;
217        op.ValueParameter.ActualName = "Temperature";
218        op.StartValueParameter.ActualName = StartTemperatureParameter.Name;
219        op.EndValueParameter.ActualName = EndTemperatureParameter.Name;
220      }
221    }
222
223    public void UpdateProblem() {
224      UpdateMoveOperators();
225      ChooseMoveOperators();
226
227      ParameterizeMoveGenerators();
228
229      ParameterizeSAMainLoop();
230      ParameterizeAnalyzers();
231      UpdateAnalyzers();
232    }
233
234    private void ParameterizeAnalyzers() {
235      qualityAnalyzer.ResultsParameter.ActualName = "Results";
236      if (problem != null) {
237        qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
238        qualityAnalyzer.QualityParameter.ActualName = problem.Evaluator.QualityParameter.Name;
239        qualityAnalyzer.QualityParameter.Depth = 0;
240        qualityAnalyzer.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
241      }
242    }
243
244    private void ParameterizeSAMainLoop() {
245      loop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
246      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.Name;
247      loop.IterationsParameter.ActualName = "LocalIterations";
248      loop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
249      loop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
250      loop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
251      loop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
252      loop.QualityParameter.ActualName = QualityParameter.Name;
253      loop.RandomParameter.ActualName = RandomParameter.Name;
254      loop.ResultsParameter.ActualName = ResultsParameter.Name;
255
256      if (problem != null) {
257        loop.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
258        loop.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
259      }
260      if (MoveEvaluator != null) {
261        loop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
262      }
263    }
264
265    private bool IsSubclassOfGeneric(Type generic, Type toCheck) {
266      while (toCheck != typeof(object)) {
267        var cur = toCheck.IsGenericType ? toCheck.GetGenericTypeDefinition() : toCheck;
268        if (generic == cur) {
269          return true;
270        }
271        toCheck = toCheck.BaseType;
272      }
273      return false;
274    }
275
276    private void UpdateAnalyzers() {
277      Analyzer.Operators.Clear();
278      if (problem != null) {
279        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
280          if (!IsSubclassOfGeneric(typeof(AlleleFrequencyAnalyzer<>), analyzer.GetType()) &&
281              !(analyzer is SingleObjectivePopulationDiversityAnalyzer)) {
282            IAnalyzer clone = analyzer.Clone() as IAnalyzer;
283            foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
284              param.Depth = 0;
285            Analyzer.Operators.Add(clone, false);
286          }
287        }
288      }
289      Analyzer.Operators.Add(qualityAnalyzer, false);
290    }
291
292    private void UpdateMoveOperators() {
293      IMoveGenerator oldMoveGenerator = MoveGenerator;
294      IMoveMaker oldMoveMaker = MoveMaker;
295      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
296
297      ClearMoveParameters();
298
299      if (problem != null) {
300        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
301          MoveGeneratorParameter.ValidValues.Add(generator);
302        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
303          MoveGeneratorParameter.ValidValues.Add(generator);
304
305        if (oldMoveGenerator != null) {
306          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
307          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
308        }
309
310        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
311      }
312    }
313
314    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
315      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
316      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
317      MoveMakerParameter.ValidValues.Clear();
318      MoveEvaluatorParameter.ValidValues.Clear();
319
320      if (MoveGenerator != null) {
321        IMoveGenerator generator = MoveGeneratorParameter.Value;
322        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
323          MoveMakerParameter.ValidValues.Add(moveMaker);
324        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators.OfType<IOperator>()).OrderBy(x => x.Name))
325          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
326
327        if (oldMoveMaker != null) {
328          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
329          if (mm != null) MoveMaker = mm;
330        }
331        if (oldMoveEvaluator != null) {
332          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
333          if (me != null) MoveEvaluator = me;
334        }
335      }
336    }
337
338    private void ClearMoveParameters() {
339      MoveGeneratorParameter.ValidValues.Clear();
340      MoveMakerParameter.ValidValues.Clear();
341      MoveEvaluatorParameter.ValidValues.Clear();
342    }
343
344    private void ParameterizeMoveGenerators() {
345      if (problem != null) {
346        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
347          generator.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
348      }
349    }
350
351    public override IOperation Apply() {
352      IScope currentScope = ExecutionContext.Scope;
353
354      Scope localScope = new Scope();
355      Scope individual = new Scope();
356
357      foreach (IVariable var in currentScope.Variables)
358        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
359
360      localScope.SubScopes.Add(individual);
361      currentScope.SubScopes.Add(localScope);
362      int index = currentScope.SubScopes.Count - 1;
363
364      SubScopesProcessor processor = new SubScopesProcessor();
365      SubScopesRemover remover = new SubScopesRemover();
366
367      remover.RemoveAllSubScopes = false;
368      remover.SubScopeIndexParameter.Value = new IntValue(index);
369
370      if (index > 0) {
371        EmptyOperator eo = new EmptyOperator();
372        for (int i = 0; i < index - 1; i++) {
373          processor.Operators.Add(eo);
374        }
375      }
376
377      VariableCreator variableCreator = new VariableCreator();
378      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
379
380      variableCreator.Successor = loop;
381
382      processor.Operators.Add(variableCreator);
383      processor.Successor = remover;
384
385      OperationCollection next = new OperationCollection(base.Apply());
386      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
387
388      return next;
389    }
390  }
391}
Note: See TracBrowser for help on using the repository browser.