Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchImprovementOperator.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: 14.5 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;
32
33namespace HeuristicLab.Algorithms.LocalSearch {
34  /// <summary>
35  /// A local search improvement operator.
36  /// </summary>
37  [Item("LocalSearchImprovementOperator", "A local search improvement operator.")]
38  [StorableClass]
39  public sealed class LocalSearchImprovementOperator : SingleSuccessorOperator, IGenericLocalImprovementOperator, IStochasticOperator {
40    #region IGenericLocalImprovementOperator Properties
41    public Type ProblemType { get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); } }
42    public IProblem Problem {
43      get { return problem; }
44      set {
45        if (problem != value) {
46          if (value != null && !(value is ISingleObjectiveHeuristicOptimizationProblem))
47            throw new ArgumentException("Only problems of type " + ProblemType.ToString() + " can be assigned.");
48          if (problem != null) DeregisterProblemEventHandlers();
49          problem = (ISingleObjectiveHeuristicOptimizationProblem)value;
50          if (problem != null) RegisterProblemEventHandlers();
51          UpdateProblem();
52        }
53      }
54    }
55    #endregion
56
57    [Storable]
58    private ISingleObjectiveHeuristicOptimizationProblem problem;
59    [Storable]
60    private LocalSearchMainLoop loop;
61    [Storable]
62    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
63
64    #region Parameter Properties
65    public ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
66      get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
67    }
68    public ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
69      get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
70    }
71    public ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
72      get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
73    }
74    public IValueLookupParameter<IntValue> SampleSizeParameter {
75      get { return (IValueLookupParameter<IntValue>)Parameters["SampleSize"]; }
76    }
77    public ValueParameter<MultiAnalyzer> AnalyzerParameter {
78      get { return (ValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
79    }
80    public ScopeTreeLookupParameter<DoubleValue> QualityParameter {
81      get { return (ScopeTreeLookupParameter<DoubleValue>)Parameters["Quality"]; }
82    }
83    public ILookupParameter<IRandom> RandomParameter {
84      get { return (ILookupParameter<IRandom>)Parameters["Random"]; }
85    }
86    #region ILocalImprovementOperator Parameters
87    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
88      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
89    }
90    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
91      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
92    }
93    public ILookupParameter<ResultCollection> ResultsParameter {
94      get { return (ILookupParameter<ResultCollection>)Parameters["Results"]; }
95    }
96    #endregion
97    #endregion
98
99    #region Properties
100    public IMoveGenerator MoveGenerator {
101      get { return MoveGeneratorParameter.Value; }
102      set { MoveGeneratorParameter.Value = value; }
103    }
104    public IMoveMaker MoveMaker {
105      get { return MoveMakerParameter.Value; }
106      set { MoveMakerParameter.Value = value; }
107    }
108    public ISingleObjectiveMoveEvaluator MoveEvaluator {
109      get { return MoveEvaluatorParameter.Value; }
110      set { MoveEvaluatorParameter.Value = value; }
111    }
112    public MultiAnalyzer Analyzer {
113      get { return AnalyzerParameter.Value; }
114      set { AnalyzerParameter.Value = value; }
115    }
116    #endregion
117
118    [StorableConstructor]
119    private LocalSearchImprovementOperator(bool deserializing) : base(deserializing) { }
120    private LocalSearchImprovementOperator(LocalSearchImprovementOperator original, Cloner cloner)
121      : base(original, cloner) {
122      this.loop = cloner.Clone(original.loop);
123      this.qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
124      this.problem = cloner.Clone(original.problem);
125      RegisterEventHandlers();
126    }
127    public LocalSearchImprovementOperator()
128      : base() {
129      Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
130      Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
131      Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
132      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(150)));
133      Parameters.Add(new ValueLookupParameter<IntValue>("SampleSize", "Number of moves that MultiMoveGenerators should create. This is ignored for Exhaustive- and SingleMoveGenerators.", new IntValue(300)));
134      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated moves."));
135      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution.", new MultiAnalyzer()));
136      Parameters.Add(new LookupParameter<ResultCollection>("Results", "The name of the collection where the results are stored."));
137      Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("Quality", "The quality/fitness value of a solution."));
138      Parameters.Add(new LookupParameter<IRandom>("Random", "The random number generator to use."));
139
140      loop = new LocalSearchMainLoop();
141      ParameterizeLSMainLoop();
142
143      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
144      Analyzer.Operators.Add(qualityAnalyzer);
145
146      RegisterEventHandlers();
147    }
148
149    public override IDeepCloneable Clone(Cloner cloner) {
150      return new LocalSearchImprovementOperator(this, cloner);
151    }
152
153    [StorableHook(HookType.AfterDeserialization)]
154    private void AfterDeserialization() {
155      RegisterEventHandlers();
156    }
157
158    #region Event Handler Registration
159    private void RegisterEventHandlers() {
160      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
161      if (problem != null)
162        RegisterProblemEventHandlers();
163    }
164
165    private void RegisterProblemEventHandlers() {
166      problem.Reset += new EventHandler(problem_Reset);
167      problem.OperatorsChanged += new EventHandler(problem_OperatorsChanged);
168    }
169
170    private void DeregisterProblemEventHandlers() {
171      problem.Reset -= new EventHandler(problem_Reset);
172      problem.OperatorsChanged -= new EventHandler(problem_OperatorsChanged);
173    }
174    #endregion
175
176    #region Event Handlers
177    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
178      ChooseMoveOperators();
179      ParameterizeLSMainLoop();
180    }
181
182    private void problem_Reset(object sender, EventArgs e) {
183      UpdateProblem();
184    }
185
186    private void problem_OperatorsChanged(object sender, EventArgs e) {
187      UpdateProblem();
188    }
189    #endregion
190
191    #region Parameterize and Update Methods
192    private void UpdateProblem() {
193      UpdateMoveOperators();
194      ChooseMoveOperators();
195
196      ParameterizeMoveGenerators();
197
198      ParameterizeLSMainLoop();
199      ParameterizeAnalyzers();
200    }
201
202    private void ParameterizeLSMainLoop() {
203      loop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
204      loop.BestLocalQualityParameter.ActualName = QualityParameter.Name;
205      loop.EvaluatedMovesParameter.ActualName = EvaluatedSolutionsParameter.Name;
206      loop.IterationsParameter.ActualName = "LocalIterations";
207      loop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
208      loop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
209      loop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
210      loop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
211      loop.QualityParameter.ActualName = QualityParameter.Name;
212      loop.RandomParameter.ActualName = RandomParameter.Name;
213      loop.ResultsParameter.ActualName = ResultsParameter.Name;
214
215      if (problem != null) {
216        loop.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
217        loop.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
218      }
219      if (MoveEvaluator != null) {
220        loop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
221      }
222    }
223
224    private void ParameterizeAnalyzers() {
225      qualityAnalyzer.ResultsParameter.ActualName = ResultsParameter.Name;
226      if (problem != null) {
227        qualityAnalyzer.MaximizationParameter.ActualName = problem.MaximizationParameter.Name;
228        if (MoveEvaluator != null)
229          qualityAnalyzer.QualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
230        qualityAnalyzer.BestKnownQualityParameter.ActualName = problem.BestKnownQualityParameter.Name;
231      }
232    }
233
234    private void UpdateMoveOperators() {
235      IMoveGenerator oldMoveGenerator = MoveGenerator;
236      IMoveMaker oldMoveMaker = MoveMaker;
237      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
238
239      ClearMoveParameters();
240
241      if (problem != null) {
242        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>().OrderBy(x => x.Name))
243          MoveGeneratorParameter.ValidValues.Add(generator);
244        foreach (IExhaustiveMoveGenerator generator in problem.Operators.OfType<IExhaustiveMoveGenerator>().OrderBy(x => x.Name))
245          MoveGeneratorParameter.ValidValues.Add(generator);
246
247        if (oldMoveGenerator != null) {
248          IMoveGenerator newMoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
249          if (newMoveGenerator != null) MoveGenerator = newMoveGenerator;
250        }
251
252        ChooseMoveOperators(oldMoveMaker, oldMoveEvaluator);
253      }
254    }
255
256    private void ChooseMoveOperators(IMoveMaker oldMoveMaker = null, ISingleObjectiveMoveEvaluator oldMoveEvaluator = null) {
257      if (oldMoveMaker == null) oldMoveMaker = MoveMaker;
258      if (oldMoveEvaluator == null) oldMoveEvaluator = MoveEvaluator;
259      MoveMakerParameter.ValidValues.Clear();
260      MoveEvaluatorParameter.ValidValues.Clear();
261
262      if (MoveGenerator != null && Problem != null) {
263        IMoveGenerator generator = MoveGeneratorParameter.Value;
264        foreach (IMoveMaker moveMaker in MoveHelper.GetCompatibleMoveMakers(generator, Problem.Operators).OrderBy(x => x.Name))
265          MoveMakerParameter.ValidValues.Add(moveMaker);
266        foreach (ISingleObjectiveMoveEvaluator moveEvaluator in MoveHelper.GetCompatibleSingleObjectiveMoveEvaluators(generator, Problem.Operators).OrderBy(x => x.Name))
267          MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
268
269        if (oldMoveMaker != null) {
270          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
271          if (mm != null) MoveMaker = mm;
272        }
273        if (oldMoveEvaluator != null) {
274          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
275          if (me != null) MoveEvaluator = me;
276        }
277      }
278    }
279
280    private void ClearMoveParameters() {
281      MoveGeneratorParameter.ValidValues.Clear();
282      MoveMakerParameter.ValidValues.Clear();
283      MoveEvaluatorParameter.ValidValues.Clear();
284    }
285
286    private void ParameterizeMoveGenerators() {
287      if (problem != null) {
288        foreach (IMultiMoveGenerator generator in problem.Operators.OfType<IMultiMoveGenerator>())
289          generator.SampleSizeParameter.ActualName = SampleSizeParameter.Name;
290      }
291    }
292    #endregion
293
294    public override IOperation Apply() {
295      IScope currentScope = ExecutionContext.Scope;
296
297      Scope localScope = new Scope();
298      Scope individual = new Scope();
299
300      foreach (IVariable var in currentScope.Variables)
301        individual.Variables.Add(var); // add reference to variable otherwise the analyzer fails (it's looking down the tree)
302
303      localScope.SubScopes.Add(individual);
304      currentScope.SubScopes.Add(localScope);
305      int index = currentScope.SubScopes.Count - 1;
306
307      SubScopesProcessor processor = new SubScopesProcessor();
308      SubScopesRemover remover = new SubScopesRemover();
309
310      remover.RemoveAllSubScopes = false;
311      remover.SubScopeIndexParameter.Value = new IntValue(index);
312
313      if (index > 0) {
314        EmptyOperator eo = new EmptyOperator();
315        for (int i = 0; i < index - 1; i++) {
316          processor.Operators.Add(eo);
317        }
318      }
319
320      VariableCreator variableCreator = new VariableCreator();
321      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(loop.IterationsParameter.ActualName, new IntValue(0)));
322      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>(loop.BestLocalQualityParameter.ActualName, new DoubleValue(0)));
323
324      variableCreator.Successor = loop;
325
326      processor.Operators.Add(variableCreator);
327      processor.Successor = remover;
328
329      OperationCollection next = new OperationCollection(base.Apply());
330      next.Insert(0, ExecutionContext.CreateChildOperation(processor));
331
332      return next;
333    }
334  }
335}
Note: See TracBrowser for help on using the repository browser.