Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.VariableNeighborhoodSearch/3.3/VariableNeighborhoodSearchMainLoop.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.3 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 HeuristicLab.Common;
23using HeuristicLab.Core;
24using HeuristicLab.Data;
25using HeuristicLab.Operators;
26using HeuristicLab.Optimization;
27using HeuristicLab.Optimization.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Selection;
31
32namespace HeuristicLab.Algorithms.VariableNeighborhoodSearch {
33  /// <summary>
34  /// An operator which represents a variable neighborhood search.
35  /// </summary>
36  [Item("VariableNeighborhoodSearchMainLoop", "An operator which represents the main loop of a variable neighborhood search.")]
37  [StorableClass]
38  public sealed class VariableNeighborhoodSearchMainLoop : AlgorithmOperator {
39    #region Parameter properties
40    public IValueLookupParameter<IRandom> RandomParameter {
41      get { return (IValueLookupParameter<IRandom>)Parameters["Random"]; }
42    }
43    public IValueLookupParameter<BoolValue> MaximizationParameter {
44      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
45    }
46    public ILookupParameter<DoubleValue> QualityParameter {
47      get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
48    }
49    public IValueLookupParameter<DoubleValue> BestKnownQualityParameter {
50      get { return (IValueLookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
51    }
52    public IValueLookupParameter<IOperator> EvaluatorParameter {
53      get { return (IValueLookupParameter<IOperator>)Parameters["Evaluator"]; }
54    }
55    public ILookupParameter<IntValue> IterationsParameter {
56      get { return (ILookupParameter<IntValue>)Parameters["Iterations"]; }
57    }
58    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
59      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
60    }
61    public IValueLookupParameter<VariableCollection> ResultsParameter {
62      get { return (IValueLookupParameter<VariableCollection>)Parameters["Results"]; }
63    }
64    public IValueLookupParameter<IOperator> AnalyzerParameter {
65      get { return (IValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
66    }
67    public ILookupParameter<IntValue> EvaluatedSolutionsParameter {
68      get { return (ILookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
69    }
70    public ILookupParameter<IntValue> CurrentNeighborhoodIndexParameter {
71      get { return (ILookupParameter<IntValue>)Parameters["CurrentNeighborhoodIndex"]; }
72    }
73    public ILookupParameter<IntValue> NeighborhoodCountParameter {
74      get { return (ILookupParameter<IntValue>)Parameters["NeighborhoodCount"]; }
75    }
76    public IValueLookupParameter<ILocalImprovementOperator> LocalImprovementParameter {
77      get { return (IValueLookupParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
78    }
79    public IValueLookupParameter<IMultiNeighborhoodShakingOperator> ShakingOperatorParameter {
80      get { return (IValueLookupParameter<IMultiNeighborhoodShakingOperator>)Parameters["ShakingOperator"]; }
81    }
82    #endregion
83
84    [StorableConstructor]
85    private VariableNeighborhoodSearchMainLoop(bool deserializing) : base(deserializing) { }
86    public VariableNeighborhoodSearchMainLoop()
87      : base() {
88      Initialize();
89    }
90    private VariableNeighborhoodSearchMainLoop(VariableNeighborhoodSearchMainLoop original, Cloner cloner)
91      : base(original, cloner) {
92    }
93    public override IDeepCloneable Clone(Cloner cloner) {
94      return new VariableNeighborhoodSearchMainLoop(this, cloner);
95    }
96
97    private void Initialize() {
98      #region Create parameters
99      Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
100      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
101      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The value which represents the quality of a solution."));
102      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality", "The best known quality value found so far."));
103      Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The operator used to evaluate solutions. This operator is executed in parallel, if an engine is used which supports parallelization."));
104      Parameters.Add(new LookupParameter<IntValue>("Iterations", "The iterations to count."));
105      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed."));
106      Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
107      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze the solution."));
108      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
109      Parameters.Add(new ValueLookupParameter<ILocalImprovementOperator>("LocalImprovement", "The local improvement operation."));
110      Parameters.Add(new ValueLookupParameter<IMultiNeighborhoodShakingOperator>("ShakingOperator", "The shaking operation."));
111      Parameters.Add(new LookupParameter<IntValue>("CurrentNeighborhoodIndex", "The index of the current shaking operation that should be applied."));
112      Parameters.Add(new LookupParameter<IntValue>("NeighborhoodCount", "The number of neighborhood operators used for shaking."));
113      #endregion
114
115      #region Create operators
116      VariableCreator variableCreator = new VariableCreator();
117      SubScopesProcessor subScopesProcessor0 = new SubScopesProcessor();
118      Assigner bestQualityInitializer = new Assigner();
119      Placeholder analyzer1 = new Placeholder();
120      ResultsCollector resultsCollector1 = new ResultsCollector();
121
122      CombinedOperator iteration = new CombinedOperator();
123      Assigner iterationInit = new Assigner();
124
125      SubScopesCloner createChild = new SubScopesCloner();
126      SubScopesProcessor childProcessor = new SubScopesProcessor();
127
128      Assigner qualityAssigner = new Assigner();
129      Placeholder shaking = new Placeholder();
130      Placeholder localImprovement = new Placeholder();
131      Placeholder evaluator = new Placeholder();
132      IntCounter evalCounter = new IntCounter();
133
134      QualityComparator qualityComparator = new QualityComparator();
135      ConditionalBranch improvesQualityBranch = new ConditionalBranch();
136
137      Assigner bestQualityUpdater = new Assigner();
138
139      BestSelector bestSelector = new BestSelector();
140      RightReducer rightReducer = new RightReducer();
141
142      IntCounter indexCounter = new IntCounter();
143      Assigner indexResetter = new Assigner();
144
145      Placeholder analyzer2 = new Placeholder();
146
147      Comparator indexComparator = new Comparator();
148      ConditionalBranch indexTermination = new ConditionalBranch();
149
150      IntCounter iterationsCounter = new IntCounter();
151      Comparator iterationsComparator = new Comparator();
152      ConditionalBranch iterationsTermination = new ConditionalBranch();
153
154      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("IsBetter", new BoolValue(false)));
155      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("BestQuality", new DoubleValue(0)));
156
157      bestQualityInitializer.Name = "Initialize BestQuality";
158      bestQualityInitializer.LeftSideParameter.ActualName = "BestQuality";
159      bestQualityInitializer.RightSideParameter.ActualName = QualityParameter.Name;
160
161      analyzer1.Name = "Analyzer (placeholder)";
162      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
163
164      resultsCollector1.CopyValue = new BoolValue(false);
165      resultsCollector1.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Quality", null, "BestQuality"));
166      resultsCollector1.ResultsParameter.ActualName = ResultsParameter.Name;
167
168      iteration.Name = "MainLoop Body";
169
170      iterationInit.Name = "Init k = 0";
171      iterationInit.LeftSideParameter.ActualName = CurrentNeighborhoodIndexParameter.Name;
172      iterationInit.RightSideParameter.Value = new IntValue(0);
173
174      createChild.Name = "Clone solution";
175
176      qualityAssigner.Name = "Assign quality";
177      qualityAssigner.LeftSideParameter.ActualName = "OriginalQuality";
178      qualityAssigner.RightSideParameter.ActualName = QualityParameter.Name;
179
180      shaking.Name = "Shaking operator (placeholder)";
181      shaking.OperatorParameter.ActualName = ShakingOperatorParameter.Name;
182
183      localImprovement.Name = "Local improvement operator (placeholder)";
184      localImprovement.OperatorParameter.ActualName = LocalImprovementParameter.Name;
185
186      evaluator.Name = "Evaluation operator (placeholder)";
187      evaluator.OperatorParameter.ActualName = EvaluatorParameter.Name;
188
189      evalCounter.Name = "Count evaluations";
190      evalCounter.Increment.Value = 1;
191      evalCounter.ValueParameter.ActualName = EvaluatedSolutionsParameter.ActualName;
192
193      qualityComparator.LeftSideParameter.ActualName = QualityParameter.Name;
194      qualityComparator.RightSideParameter.ActualName = "OriginalQuality";
195      qualityComparator.ResultParameter.ActualName = "IsBetter";
196
197      improvesQualityBranch.ConditionParameter.ActualName = "IsBetter";
198
199      bestQualityUpdater.Name = "Update BestQuality";
200      bestQualityUpdater.LeftSideParameter.ActualName = "BestQuality";
201      bestQualityUpdater.RightSideParameter.ActualName = QualityParameter.Name;
202
203      bestSelector.CopySelected = new BoolValue(false);
204      bestSelector.MaximizationParameter.ActualName = MaximizationParameter.Name;
205      bestSelector.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
206      bestSelector.QualityParameter.ActualName = QualityParameter.Name;
207
208      indexCounter.Name = "Count neighborhood index";
209      indexCounter.Increment.Value = 1;
210      indexCounter.ValueParameter.ActualName = CurrentNeighborhoodIndexParameter.Name;
211
212      indexResetter.Name = "Reset neighborhood index";
213      indexResetter.LeftSideParameter.ActualName = CurrentNeighborhoodIndexParameter.Name;
214      indexResetter.RightSideParameter.Value = new IntValue(0);
215
216      analyzer2.Name = "Analyzer (placeholder)";
217      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
218
219      iterationsCounter.Name = "Iterations Counter";
220      iterationsCounter.Increment = new IntValue(1);
221      iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
222
223      iterationsComparator.Name = "Iterations >= MaximumIterations";
224      iterationsComparator.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
225      iterationsComparator.LeftSideParameter.ActualName = IterationsParameter.Name;
226      iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
227      iterationsComparator.ResultParameter.ActualName = "Terminate";
228
229      iterationsTermination.Name = "Iterations Termination Condition";
230      iterationsTermination.ConditionParameter.ActualName = "Terminate";
231
232      indexComparator.Name = "k < k_max (index condition)";
233      indexComparator.LeftSideParameter.ActualName = CurrentNeighborhoodIndexParameter.Name;
234      indexComparator.RightSideParameter.ActualName = NeighborhoodCountParameter.Name;
235      indexComparator.Comparison = new Comparison(ComparisonType.Less);
236      indexComparator.ResultParameter.ActualName = "ContinueIteration";
237
238      indexTermination.Name = "Index Termination Condition";
239      indexTermination.ConditionParameter.ActualName = "ContinueIteration";
240      #endregion
241
242      #region Create operator graph
243      OperatorGraph.InitialOperator = variableCreator;
244      variableCreator.Successor = subScopesProcessor0;
245      subScopesProcessor0.Operators.Add(bestQualityInitializer);
246      subScopesProcessor0.Successor = analyzer1;
247      analyzer1.Successor = resultsCollector1;
248      /////////
249      resultsCollector1.Successor = iteration;
250
251      iteration.OperatorGraph.InitialOperator = iterationInit;
252      iteration.Successor = iterationsCounter;
253      iterationInit.Successor = createChild;
254
255      createChild.Successor = childProcessor;
256      childProcessor.Operators.Add(new EmptyOperator());
257      childProcessor.Operators.Add(qualityAssigner);
258      childProcessor.Successor = bestSelector;
259      /////////
260      qualityAssigner.Successor = shaking;
261      shaking.Successor = evaluator;
262      evaluator.Successor = evalCounter;
263      evalCounter.Successor = localImprovement;
264      localImprovement.Successor = qualityComparator;
265      qualityComparator.Successor = improvesQualityBranch;
266      improvesQualityBranch.TrueBranch = bestQualityUpdater;
267      improvesQualityBranch.FalseBranch = indexCounter;
268
269      bestQualityUpdater.Successor = indexResetter;
270      indexResetter.Successor = null;
271
272      indexCounter.Successor = null;
273      /////////
274      bestSelector.Successor = rightReducer;
275      rightReducer.Successor = analyzer2;
276      analyzer2.Successor = indexComparator;
277      indexComparator.Successor = indexTermination;
278      indexTermination.TrueBranch = createChild;
279      indexTermination.FalseBranch = null;
280
281      iterationsCounter.Successor = iterationsComparator;
282      iterationsComparator.Successor = iterationsTermination;
283      iterationsTermination.TrueBranch = null;
284      iterationsTermination.FalseBranch = iteration;
285      #endregion
286    }
287
288    public override IOperation Apply() {
289      if (LocalImprovementParameter.ActualValue == null || ShakingOperatorParameter.ActualValue == null)
290        return null;
291      return base.Apply();
292    }
293  }
294}
Note: See TracBrowser for help on using the repository browser.