Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 6042 was 6042, checked in by abeham, 12 years ago

#1425

  • Changed LocalImprovementOperators
    • Changed interface (made Problem a property, added a property that denotes the type of the problem that it can be applied on, added some general parameters)
    • Added some parameters and wiring
    • Changed move discovery and parameterization and added a helper class to ease finding compatible move operators
    • Discovering only IMultiMoveOperators and IExhaustiveMoveOperators and putting the multi move ones first
    • Fixed bug in Apply method that could create an endless string of nested execution contexts
    • Removed all problem specific analyzers in the two local improvement operators and only left the BestAverageWorstQualityAnalyzer since it doesn't make any sense to perform diversity or allele analysis during local improvement in the most common case and those analyzers take a lot of time (one can always add them manually should he/she be interested). The analyzers in the VNS's Analyzer parameter are left untouched.
  • Removed shaking operator and interface from VNS plugin and added that to Optimization and Optimization.Operators
  • Changed some ValueParameters to ConstrainedValueParameters and added type discovery to fill them (using the ProblemType property to get compatible local improvement operators)
  • Added missing GPL license headers
  • Changed some ValueParameters to the new FixedValueParameters
  • Added an additional encoding specific ShakingOperator to each encoding and added that to each problem
    • reason is that only the problem/encoding can really decide if a shaking operator is meaningful or not
  • Fixed an unrelated bug in the BestAverageWorstQualityAnalyzer that I encountered (and made the fix backwards compatible)
    • Also added a snippet for creating the backwards compatible comment marker and region
  • Fixed the operator graph of the VNS main loop
    • The condition to continue only when the local search was not successful is not necessary and is not part of the VNS definition as far as I know it (only condition to break the inner loop is when k reaches k_max)
  • Changed the ShakingOperator to input current index and output the maximum number of neighborhoods instead of a boolean that indicates that the last index has been reached since the maximum number is a little more generally useful and equally powerful in modeling
    • Remodeled the VNS main loop to check for k < k_max in order to continue the inner loop
  • other changes that I forgot...

Still necessary

  • test, test, test
  • check for backwards compatible breakers
  • add a maximum evaluated solutions stop criterion
  • optionally: implement fast problem specific local search improvement operators that do not build on the whole generic overhead (e.g. a 2-opt TSP specific local search operator). The idea of VNS is really to converge to a local optimum which is difficult to achieve using the current rather limited termination options
File size: 16.6 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, IGenericLocalImprovementOperator, 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 void UpdateAnalyzers() {
262      Analyzer.Operators.Clear();
263      if (problem != null) {
264        foreach (IAnalyzer analyzer in problem.Operators.OfType<IAnalyzer>()) {
265          IAnalyzer clone = analyzer.Clone() as IAnalyzer;
266          foreach (IScopeTreeLookupParameter param in clone.Parameters.OfType<IScopeTreeLookupParameter>())
267            param.Depth = 0;
268          Analyzer.Operators.Add(clone);
269        }
270      }
271      Analyzer.Operators.Add(qualityAnalyzer);
272    }
273
274    private void UpdateMoveOperators() {
275      IMoveGenerator oldMoveGenerator = MoveGenerator;
276      IMoveMaker oldMoveMaker = MoveMaker;
277      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
278
279      ClearMoveParameters();
280
281      if (problem != null) {
282        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
283          MoveGeneratorParameter.ValidValues.Add(generator);
284        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
285          MoveGeneratorParameter.ValidValues.Add(generator);
286
287        if (oldMoveGenerator != null) {
288          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
289          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
290        }
291
292        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
293      }
294    }
295
296    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
297      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
298      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
299      MoveMakerParameter.ValidValues.Clear();
300      MoveEvaluatorParameter.ValidValues.Clear();
301
302      if (MoveGenerator != null) {
303        IMoveGenerator generator = MoveGeneratorParameter.Value;
304        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators).OrderBy(x => x.Name))
305          MoveMakerParameter.ValidValues.Add(moveMaker);
306        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators).OrderBy(x => x.Name))
307          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
308
309        if (oldMoveMaker != null) {
310          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
311          if (mm != null) MoveMaker = mm;
312        }
313        if (oldMoveEvaluator != null) {
314          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
315          if (me != null) MoveEvaluator = me;
316        }
317      }
318    }
319
320    private void ClearMoveParameters() {
321      MoveGeneratorParameter.ValidValues.Clear();
322      MoveMakerParameter.ValidValues.Clear();
323      MoveEvaluatorParameter.ValidValues.Clear();
324    }
325
326    private void ParameterizeMoveGenerators() {
327      if (problem != null) {
328        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
329          generator.SampleSizeParameter.ActualName = InnerIterationsParameter.Name;
330      }
331    }
332
333    public override IOperation Apply() {
334      IScope currentScope = ExecutionContext.Scope;
335
336      Scope localScope = new Scope();
337      Scope individual = new Scope();
338
339      foreach (IVariable var in currentScope.Variables)
340        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
341
342      localScope.SubScopes.Add(individual);
343      currentScope.SubScopes.Add(localScope);
344      int index = currentScope.SubScopes.Count - 1;
345
346      SubScopesProcessor processor = new SubScopesProcessor();
347      SubScopesRemover remover = new SubScopesRemover();
348
349      remover.RemoveAllSubScopes = false;
350      remover.SubScopeIndexParameter.Value = new IntValue(index);
351
352      if (index > 0) {
353        EmptyOperator eo = new EmptyOperator();
354        for (int i = 0; i < index - 1; i++) {
355          processor.Operators.Add(eo);
356        }
357      }
358
359      VariableCreator variableCreator = new VariableCreator();
360      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
361
362      variableCreator.Successor = loop;
363
364      processor.Operators.Add(variableCreator);
365      processor.Successor = remover;
366
367      OperationCollection next = new OperationCollection(base.Apply());
368      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
369
370      return next;
371    }
372  }
373}
Note: See TracBrowser for help on using the repository browser.