source: branches/histogram/HeuristicLab.Algorithms.SimulatedAnnealing/3.3/SimulatedAnnealingImprovementOperator.cs @ 6055

Last change on this file since 6055 was 6055, checked in by abeham, 8 years ago

#1465

  • updated branch from trunk
File size: 17.1 KB
Line 
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
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, ILocalImprovementOperator, 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    private ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
70      get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
71    }
72    private ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
73      get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
74    }
75    private ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
76      get { return (ConstrainedValueParameter<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    private ConstrainedValueParameter<IDiscreteDoubleValueModifier> AnnealingOperatorParameter {
91      get { return (ConstrainedValueParameter<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 ISingleObjectiveMoveEvaluator MoveEvaluator {
119      get { return MoveEvaluatorParameter.Value; }
120      set { MoveEvaluatorParameter.Value = value; }
121    }
122    public MultiAnalyzer Analyzer {
123      get { return AnalyzerParameter.Value; }
124      set { AnalyzerParameter.Value = value; }
125    }
126    #endregion
127
128    [StorableConstructor]
129    private SimulatedAnnealingImprovementOperator(bool deserializing) : base(deserializing) { }
130    private SimulatedAnnealingImprovementOperator(SimulatedAnnealingImprovementOperator original, Cloner cloner)
131      : base(original, cloner) {
132      this.problem = cloner.Clone(original.problem);
133      this.loop = cloner.Clone(original.loop);
134      this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
135      RegisterEventHandlers();
136    }
137    public SimulatedAnnealingImprovementOperator()
138      : base() {
139      loop = new SimulatedAnnealingMainLoop();
140
141      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
142
143      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
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 ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
148      Parameters.Add(new ValueLookupParameter<IntValue>("InnerIterations", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(1500)));
149      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
150      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
151      Parameters.Add(new ValueParameter<DoubleValue>("StartTemperature", "The initial temperature.", new DoubleValue(100)));
152      Parameters.Add(new ValueParameter<DoubleValue>("EndTemperature", "The final temperature which should be reached when iterations reaches maximum iterations.", new DoubleValue(1e-6)));
153      Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>("AnnealingOperator", "The operator used to modify the temperature."));
154      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The variable where the results are stored."));
155      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality/fitness value of a solution."));
156
157      foreach (IDiscreteDoubleValueModifier op in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
158        AnnealingOperatorParameter.ValidValues.Add(op);
159
160      ParameterizeAnnealingOperators();
161      ParameterizeSAMainLoop();
162
163      RegisterEventHandlers();
164    }
165
166    public override IDeepCloneable Clone(Cloner cloner) {
167      return new SimulatedAnnealingImprovementOperator(this, cloner);
168    }
169
170    [StorableHook(HookType.AfterDeserialization)]
171    private void AfterDeserialization() {
172      RegisterEventHandlers();
173    }
174
175    #region Event Handler Registration
176    private void RegisterEventHandlers() {
177      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
178      if (problem != null)
179        RegisterProblemEventHandlers();
180    }
181
182    private void RegisterProblemEventHandlers() {
183      problem.Reset += new EventHandler(problem_Reset);
184      problem.OperatorsChanged += new EventHandler(problem_OperatorsChanged);
185    }
186
187    private void DeregisterProblemEventHandlers() {
188      problem.Reset -= new EventHandler(problem_Reset);
189      problem.OperatorsChanged -= new EventHandler(problem_OperatorsChanged);
190    }
191    #endregion
192
193    #region Event Handlers
194    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
195      ChooseMoveOperators();
196      ParameterizeSAMainLoop();
197    }
198
199    private void problem_Reset(object sender, EventArgs e) {
200      UpdateProblem();
201    }
202
203    private void problem_OperatorsChanged(object sender, EventArgs e) {
204      UpdateProblem();
205    }
206    #endregion
207
208    private void ParameterizeAnnealingOperators() {
209      foreach (IDiscreteDoubleValueModifier op in AnnealingOperatorParameter.ValidValues) {
210        op.IndexParameter.ActualName = "LocalIterations";
211        op.StartIndexParameter.Value = new IntValue(0);
212        op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name;
213        op.ValueParameter.ActualName = "Temperature";
214        op.StartValueParameter.ActualName = StartTemperatureParameter.Name;
215        op.EndValueParameter.ActualName = EndTemperatureParameter.Name;
216      }
217    }
218
219    public void UpdateProblem() {
220      UpdateMoveOperators();
221      ChooseMoveOperators();
222
223      ParameterizeMoveGenerators();
224
225      ParameterizeSAMainLoop();
226      ParameterizeAnalyzers();
227      UpdateAnalyzers();
228    }
229
230    private void ParameterizeAnalyzers() {
231      qualityAnalyzer.ResultsParameter.ActualName = "Results";
232      if (problem != null) {
233        qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
234        qualityAnalyzer.QualityParameter.ActualName = problem.Evaluator.QualityParameter.Name;
235        qualityAnalyzer.QualityParameter.Depth = 0;
236        qualityAnalyzer.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
237      }
238    }
239
240    private void ParameterizeSAMainLoop() {
241      loop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
242      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.Name;
243      loop.IterationsParameter.ActualName = "LocalIterations";
244      loop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
245      loop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
246      loop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
247      loop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
248      loop.QualityParameter.ActualName = QualityParameter.Name;
249      loop.RandomParameter.ActualName = RandomParameter.Name;
250      loop.ResultsParameter.ActualName = ResultsParameter.Name;
251
252      if (problem != null) {
253        loop.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
254        loop.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
255      }
256      if (MoveEvaluator != null) {
257        loop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
258      }
259    }
260
261    private bool IsSubclassOfGeneric(Type generic, Type toCheck) {
262      while (toCheck != typeof(object)) {
263        var cur = toCheck.IsGenericType ? toCheck.GetGenericTypeDefinition() : toCheck;
264        if (generic == cur) {
265          return true;
266        }
267        toCheck = toCheck.BaseType;
268      }
269      return false;
270    }
271
272    private void UpdateAnalyzers() {
273      Analyzer.Operators.Clear();
274      if (problem != null) {
275        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
276          if (!IsSubclassOfGeneric(typeof(AlleleFrequencyAnalyzer<>), analyzer.GetType()) &&
277              !IsSubclassOfGeneric(typeof(PopulationDiversityAnalyzer<>), analyzer.GetType())) {
278            IAnalyzer clone = analyzer.Clone() as IAnalyzer;
279            foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
280              param.Depth = 0;
281            Analyzer.Operators.Add(clone);
282          }
283        }
284      }
285      Analyzer.Operators.Add(qualityAnalyzer);
286    }
287
288    private void UpdateMoveOperators() {
289      IMoveGenerator oldMoveGenerator = MoveGenerator;
290      IMoveMaker oldMoveMaker = MoveMaker;
291      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
292
293      ClearMoveParameters();
294
295      if (problem != null) {
296        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
297          MoveGeneratorParameter.ValidValues.Add(generator);
298        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
299          MoveGeneratorParameter.ValidValues.Add(generator);
300
301        if (oldMoveGenerator != null) {
302          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
303          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
304        }
305
306        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
307      }
308    }
309
310    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
311      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
312      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
313      MoveMakerParameter.ValidValues.Clear();
314      MoveEvaluatorParameter.ValidValues.Clear();
315
316      if (MoveGenerator != null) {
317        IMoveGenerator generator = MoveGeneratorParameter.Value;
318        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators).OrderBy(x => x.Name))
319          MoveMakerParameter.ValidValues.Add(moveMaker);
320        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators).OrderBy(x => x.Name))
321          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
322
323        if (oldMoveMaker != null) {
324          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
325          if (mm != null) MoveMaker = mm;
326        }
327        if (oldMoveEvaluator != null) {
328          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
329          if (me != null) MoveEvaluator = me;
330        }
331      }
332    }
333
334    private void ClearMoveParameters() {
335      MoveGeneratorParameter.ValidValues.Clear();
336      MoveMakerParameter.ValidValues.Clear();
337      MoveEvaluatorParameter.ValidValues.Clear();
338    }
339
340    private void ParameterizeMoveGenerators() {
341      if (problem != null) {
342        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
343          generator.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
344      }
345    }
346
347    public override IOperation Apply() {
348      IScope currentScope = ExecutionContext.Scope;
349
350      Scope localScope = new Scope();
351      Scope individual = new Scope();
352
353      foreach (IVariable var in currentScope.Variables)
354        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
355
356      localScope.SubScopes.Add(individual);
357      currentScope.SubScopes.Add(localScope);
358      int index = currentScope.SubScopes.Count - 1;
359
360      SubScopesProcessor processor = new SubScopesProcessor();
361      SubScopesRemover remover = new SubScopesRemover();
362
363      remover.RemoveAllSubScopes = false;
364      remover.SubScopeIndexParameter.Value = new IntValue(index);
365
366      if (index > 0) {
367        EmptyOperator eo = new EmptyOperator();
368        for (int i = 0; i < index - 1; i++) {
369          processor.Operators.Add(eo);
370        }
371      }
372
373      VariableCreator variableCreator = new VariableCreator();
374      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
375
376      variableCreator.Successor = loop;
377
378      processor.Operators.Add(variableCreator);
379      processor.Successor = remover;
380
381      OperationCollection next = new OperationCollection(base.Apply());
382      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
383
384      return next;
385    }
386  }
387}
Note: See TracBrowser for help on using the repository browser.