Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 5809 was 5809, checked in by mkommend, 12 years ago

#1418: Reintegrated branch into trunk.

File size: 15.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.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Operators;
29using HeuristicLab.Common;
30using HeuristicLab.Parameters;
31using HeuristicLab.Algorithms.SimulatedAnnealing;
32using HeuristicLab.Data;
33using HeuristicLab.Optimization;
34using HeuristicLab.Optimization.Operators;
35using HeuristicLab.Analysis;
36using HeuristicLab.PluginInfrastructure;
37
38namespace HeuristicLab.Algorithms.SimulatedAnnealing {
39  /// <summary>
40  /// A simulated annealing improvement operator.
41  /// </summary>
42  [Item("SimulatedAnnealingImprovementOperator", "A simulated annealing improvement operator.")]
43  [StorableClass]
44  public class SimulatedAnnealingImprovementOperator: SingleSuccessorOperator, ILocalImprovementOperator {
45    [Storable]
46    private SimulatedAnnealingMainLoop loop;
47
48    [Storable]
49    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
50   
51    private ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
52      get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
53    }
54    private ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
55      get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
56    }
57    private ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
58      get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
59    }
60    private ValueParameter<IntValue> MaximumIterationsParameter {
61      get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
62    }
63    private ValueParameter<IntValue> InnerIterationsParameter {
64      get { return (ValueParameter<IntValue>)Parameters["InnerIterations"]; }
65    }
66    public LookupParameter<IntValue> EvaluatedSolutionsParameter {
67      get { return (LookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
68    }
69    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
70      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
71    }
72    private ValueParameter<DoubleValue> StartTemperatureParameter {
73      get { return (ValueParameter<DoubleValue>)Parameters["StartTemperature"]; }
74    }
75    private ValueParameter<DoubleValue> EndTemperatureParameter {
76      get { return (ValueParameter<DoubleValue>)Parameters["EndTemperature"]; }
77    }
78    private ConstrainedValueParameter<IDiscreteDoubleValueModifier> AnnealingOperatorParameter {
79      get { return (ConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["AnnealingOperator"]; }
80    }
81
82    public IMoveGenerator MoveGenerator {
83      get { return MoveGeneratorParameter.Value; }
84      set { MoveGeneratorParameter.Value = value; }
85    }
86    public IMoveMaker MoveMaker {
87      get { return MoveMakerParameter.Value; }
88      set { MoveMakerParameter.Value = value; }
89    }
90    public ISingleObjectiveMoveEvaluator MoveEvaluator {
91      get { return MoveEvaluatorParameter.Value; }
92      set { MoveEvaluatorParameter.Value = value; }
93    }
94    public MultiAnalyzer Analyzer {
95      get { return AnalyzerParameter.Value; }
96      set { AnalyzerParameter.Value = value; }
97    }
98
99    [StorableConstructor]
100    protected SimulatedAnnealingImprovementOperator(bool deserializing) : base(deserializing) {}
101    [StorableHook(HookType.AfterDeserialization)]
102    private void AfterDeserialization() {
103      Initialize();
104    }
105    protected SimulatedAnnealingImprovementOperator(SimulatedAnnealingImprovementOperator original, Cloner cloner)
106      : base(original, cloner) {
107        this.loop = cloner.Clone(original.loop);
108        this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
109        Initialize();
110    }
111    public override IDeepCloneable Clone(Cloner cloner) {
112      return new SimulatedAnnealingImprovementOperator(this, cloner);
113    }
114    public SimulatedAnnealingImprovementOperator()
115      : base() {
116        loop = new SimulatedAnnealingMainLoop();
117
118        qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
119
120        Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
121        Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
122        Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
123        Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
124        Parameters.Add(new ValueParameter<IntValue>("InnerIterations", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(1500)));
125        Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
126        Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
127        Parameters.Add(new ValueParameter<DoubleValue>("StartTemperature", "The initial temperature.", new DoubleValue(100)));
128        Parameters.Add(new ValueParameter<DoubleValue>("EndTemperature", "The final temperature which should be reached when iterations reaches maximum iterations.", new DoubleValue(1e-6)));
129        Parameters.Add(new ConstrainedValueParameter<IDiscreteDoubleValueModifier>("AnnealingOperator", "The operator used to modify the temperature."));
130
131        foreach (IDiscreteDoubleValueModifier op in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
132          AnnealingOperatorParameter.ValidValues.Add(op);
133
134        ParameterizeAnnealingOperators();
135
136        Initialize();
137    }
138
139    private void Initialize() {
140      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
141    }
142
143    private void ParameterizeAnnealingOperators() {
144      foreach (IDiscreteDoubleValueModifier op in AnnealingOperatorParameter.ValidValues) {
145        op.IndexParameter.ActualName = "LocalIterations";
146        op.StartIndexParameter.Value = new IntValue(0);
147        op.EndIndexParameter.ActualName = MaximumIterationsParameter.Name;
148        op.ValueParameter.ActualName = "Temperature";
149        op.StartValueParameter.ActualName = StartTemperatureParameter.Name;
150        op.EndValueParameter.ActualName = EndTemperatureParameter.Name;
151      }
152    }
153
154    public void OnProblemChanged(IProblem problem) {
155      UpdateMoveOperators(problem);
156      ChooseMoveOperators();
157
158      ParameterizeMoveGenerators(problem as ISingleObjectiveHeuristicOptimizationProblem);
159      ParameterizeMoveEvaluators(problem as ISingleObjectiveHeuristicOptimizationProblem);
160      ParameterizeMoveMakers(problem as ISingleObjectiveHeuristicOptimizationProblem);
161
162      ParameterizeAnalyzers(problem as ISingleObjectiveHeuristicOptimizationProblem);
163      UpdateAnalyzers(problem as ISingleObjectiveHeuristicOptimizationProblem);
164    }
165
166    void ParameterizeAnalyzers(ISingleObjectiveHeuristicOptimizationProblem problem) {
167      qualityAnalyzer.ResultsParameter.ActualName = "Results";
168      if (problem != null) {
169        qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
170        qualityAnalyzer.QualityParameter.ActualName = problem.Evaluator.QualityParameter.Name;
171        qualityAnalyzer.QualityParameter.Depth = 0;
172        qualityAnalyzer.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
173      }
174    }
175
176    void UpdateAnalyzers(ISingleObjectiveHeuristicOptimizationProblem problem) {
177      Analyzer.Operators.Clear();
178      if (problem != null) {
179        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
180          IAnalyzer clone = analyzer.Clone() as IAnalyzer;
181          foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
182            param.Depth = 0;
183          Analyzer.Operators.Add(clone);
184        }
185      }
186      Analyzer.Operators.Add(qualityAnalyzer);
187    }
188
189    void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
190      ChooseMoveOperators();
191    }
192
193    private void UpdateMoveOperators(IProblem problem) {
194      IMoveGenerator oldMoveGenerator = MoveGenerator;
195      IMoveMaker oldMoveMaker = MoveMaker;
196      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
197
198      ClearMoveParameters();
199
200      if (problem != null) {
201        foreach (IMoveGenerator generator in problem.Operators.OfType<IMoveGenerator>().OrderBy(x => x.Name))
202          MoveGeneratorParameter.ValidValues.Add(generator);
203
204        foreach (IMoveMaker maker in problem.Operators.OfType<IMoveMaker>().OrderBy(x => x.Name))
205          MoveMakerParameter.ValidValues.Add(maker);
206
207        foreach (ISingleObjectiveMoveEvaluator evaluator in problem.Operators.OfType<ISingleObjectiveMoveEvaluator>().OrderBy(x => x.Name))
208          MoveEvaluatorParameter.ValidValues.Add(evaluator);
209      }
210
211      if (oldMoveGenerator != null) {
212        IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
213        if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
214      }
215      if (MoveGenerator == null) {
216        ClearMoveParameters();
217      }
218
219      if (oldMoveMaker != null) {
220        IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
221        if (mm != null) MoveMaker = mm;
222      }
223
224      if (oldMoveEvaluator != null) {
225        ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
226        if (me != null) MoveEvaluator = me;
227      }
228    }
229
230    private void ChooseMoveOperators() {
231      IMoveMaker oldMoveMaker = MoveMaker;
232      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
233
234      if (MoveGenerator != null) {
235        List<Type> moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList();
236        foreach (Type type in moveTypes.ToList()) {
237          if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t)))
238            moveTypes.Remove(type);
239        }
240        List<IMoveMaker> validMoveMakers = new List<IMoveMaker>();
241        List<ISingleObjectiveMoveEvaluator> validMoveEvaluators = new List<ISingleObjectiveMoveEvaluator>();
242
243        foreach (Type type in moveTypes) {
244          var moveMakers = MoveMakerParameter.ValidValues.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
245          foreach (IMoveMaker moveMaker in moveMakers)
246            validMoveMakers.Add(moveMaker);
247
248          var moveEvaluators = MoveEvaluatorParameter.ValidValues.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
249          foreach (ISingleObjectiveMoveEvaluator moveEvaluator in moveEvaluators)
250            validMoveEvaluators.Add(moveEvaluator);
251        }
252        if (oldMoveMaker != null) {
253          IMoveMaker mm = validMoveMakers.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
254          if (mm != null) MoveMaker = mm;
255          else MoveMaker = validMoveMakers.FirstOrDefault();
256        }
257
258        if (oldMoveEvaluator != null) {
259          ISingleObjectiveMoveEvaluator me = validMoveEvaluators.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
260          if (me != null) MoveEvaluator = me;
261          else MoveEvaluator = validMoveEvaluators.FirstOrDefault();
262        }
263      }
264    }
265
266    private void ClearMoveParameters() {
267      MoveGeneratorParameter.ValidValues.Clear();
268      MoveMakerParameter.ValidValues.Clear();
269      MoveEvaluatorParameter.ValidValues.Clear();
270    }
271
272    private void ParameterizeMoveGenerators(ISingleObjectiveHeuristicOptimizationProblem problem) {
273      if (problem != null) {
274        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
275          generator.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
276      }
277    }
278    private void ParameterizeMoveEvaluators(ISingleObjectiveHeuristicOptimizationProblem problem) {
279      foreach (ISingleObjectiveMoveEvaluator op in problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
280        op.QualityParameter.ActualName = problem.Evaluator.QualityParameter.ActualName;
281      }
282    }
283    private void ParameterizeMoveMakers(ISingleObjectiveHeuristicOptimizationProblem problem) {
284      foreach (IMoveMaker op in problem.Operators.OfType<IMoveMaker>()) {
285        op.QualityParameter.ActualName = problem.Evaluator.QualityParameter.ActualName;
286        if (MoveEvaluator != null)
287          op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
288      }
289    }
290
291    public override IOperation Apply() {
292      Scope subScope = new Scope();
293      Scope individual = new Scope();
294
295      foreach (Variable var in ExecutionContext.Scope.Variables) {
296        individual.Variables.Add(var);
297      }
298      subScope.SubScopes.Add(individual);
299
300      ExecutionContext.Scope.SubScopes.Add(subScope);
301      int index = subScope.Parent.SubScopes.IndexOf(subScope);
302
303      SubScopesProcessor processor = new SubScopesProcessor();
304      SubScopesRemover remover = new SubScopesRemover();
305
306      remover.RemoveAllSubScopes = false;
307      remover.SubScopeIndexParameter.Value = new IntValue(index);
308
309      for (int i = 0; i < index; i++) {
310        processor.Operators.Add(new EmptyOperator());
311      }
312
313      VariableCreator variableCreator = new VariableCreator();
314      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("LocalIterations", new IntValue(0)));
315
316      variableCreator.Successor = loop;
317
318      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.ActualName;
319
320      processor.Operators.Add(variableCreator);
321      processor.Successor = remover;
322
323      IOperation next = base.Apply();
324      if (next as ExecutionContext != null) {
325        remover.Successor = (next as ExecutionContext).Operator;
326      }
327
328      return ExecutionContext.CreateChildOperation(processor);
329    }
330  }
331}
Note: See TracBrowser for help on using the repository browser.