Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingImprovementOperator.cs @ 13745

Last change on this file since 13745 was 12069, checked in by jkarder, 10 years ago

#2332: refactored operators and analyzers

  • removed quality and maximization parameters in SingleObjectivePopulationDiversityAnalyzer
  • renamed SingleObjectivePopulationDiversityAnalyzer to PopulationSimilarityAnalyzer
  • added ConstrainedValueParameter for similarity calculators of analyzer
  • added ValueLookupParameter for similarity calculator of the following operators:
    • DuplicatesSelector, ProgressiveOffspringPreserver, ReferenceSetUpdateMethod, SolutionPoolUpdateMethod
  • removed some wiring code in specific problems
File size: 17.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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, ISingleObjectiveOperator {
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 PopulationSimilarityAnalyzer)) {
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.