Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.LocalSearch/3.3/LocalSearchMainLoop.cs @ 6042

Last change on this file since 6042 was 6042, checked in by abeham, 13 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: 12.7 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.Operators;
27using HeuristicLab.Parameters;
28using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
29using HeuristicLab.Selection;
30
31namespace HeuristicLab.Algorithms.LocalSearch {
32  /// <summary>
33  /// An operator which represents a local search.
34  /// </summary>
35  [Item("LocalSearchMainLoop", "An operator which represents the main loop of a best improvement local search (if only a single move is generated in each iteration it is a first improvement local search).")]
36  [StorableClass]
37  public sealed class LocalSearchMainLoop : AlgorithmOperator {
38    #region Parameter properties
39    public ValueLookupParameter<IRandom> RandomParameter {
40      get { return (ValueLookupParameter<IRandom>)Parameters["Random"]; }
41    }
42    public ValueLookupParameter<BoolValue> MaximizationParameter {
43      get { return (ValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
44    }
45    public LookupParameter<DoubleValue> QualityParameter {
46      get { return (LookupParameter<DoubleValue>)Parameters["Quality"]; }
47    }
48    public LookupParameter<DoubleValue> BestLocalQualityParameter {
49      get { return (LookupParameter<DoubleValue>)Parameters["BestLocalQuality"]; }
50    }
51    public ValueLookupParameter<DoubleValue> BestKnownQualityParameter {
52      get { return (ValueLookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
53    }
54    public LookupParameter<DoubleValue> MoveQualityParameter {
55      get { return (LookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
56    }
57    public LookupParameter<IntValue> IterationsParameter {
58      get { return (LookupParameter<IntValue>)Parameters["Iterations"]; }
59    }
60    public ValueLookupParameter<IntValue> MaximumIterationsParameter {
61      get { return (ValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
62    }
63    public ValueLookupParameter<VariableCollection> ResultsParameter {
64      get { return (ValueLookupParameter<VariableCollection>)Parameters["Results"]; }
65    }
66    public ValueLookupParameter<IOperator> MoveGeneratorParameter {
67      get { return (ValueLookupParameter<IOperator>)Parameters["MoveGenerator"]; }
68    }
69    public ValueLookupParameter<IOperator> MoveEvaluatorParameter {
70      get { return (ValueLookupParameter<IOperator>)Parameters["MoveEvaluator"]; }
71    }
72    public ValueLookupParameter<IOperator> MoveMakerParameter {
73      get { return (ValueLookupParameter<IOperator>)Parameters["MoveMaker"]; }
74    }
75    public ValueLookupParameter<IOperator> AnalyzerParameter {
76      get { return (ValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
77    }
78    public LookupParameter<IntValue> EvaluatedMovesParameter {
79      get { return (LookupParameter<IntValue>)Parameters["EvaluatedMoves"]; }
80    }
81    #endregion
82
83    [StorableConstructor]
84    private LocalSearchMainLoop(bool deserializing) : base(deserializing) { }
85    public LocalSearchMainLoop()
86      : base() {
87      Initialize();
88    }
89    private LocalSearchMainLoop(LocalSearchMainLoop original, Cloner cloner)
90      : base(original, cloner) {
91    }
92    public override IDeepCloneable Clone(Cloner cloner) {
93      return new LocalSearchMainLoop(this, cloner);
94    }
95
96    private void Initialize() {
97      #region Create parameters
98      Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
99      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
100      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The value which represents the quality of a solution."));
101      Parameters.Add(new LookupParameter<DoubleValue>("BestLocalQuality", "The value which represents the best quality found so far."));
102      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality", "The problem's best known quality value found so far."));
103      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The value which represents the quality of a move."));
104      Parameters.Add(new LookupParameter<IntValue>("Iterations", "The number of iterations performed."));
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
108      Parameters.Add(new ValueLookupParameter<IOperator>("MoveGenerator", "The operator that generates the moves."));
109      Parameters.Add(new ValueLookupParameter<IOperator>("MoveMaker", "The operator that performs a move and updates the quality."));
110      Parameters.Add(new ValueLookupParameter<IOperator>("MoveEvaluator", "The operator that evaluates a move."));
111
112      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The operator used to analyze the solution and moves."));
113      Parameters.Add(new LookupParameter<IntValue>("EvaluatedMoves", "The number of evaluated moves."));
114      #endregion
115
116      #region Create operators
117      SubScopesProcessor subScopesProcessor0 = new SubScopesProcessor();
118      Assigner bestQualityInitializer = new Assigner();
119      Placeholder analyzer1 = new Placeholder();
120      ResultsCollector resultsCollector1 = new ResultsCollector();
121      SubScopesProcessor mainProcessor = new SubScopesProcessor();
122      Placeholder moveGenerator = new Placeholder();
123      UniformSubScopesProcessor moveEvaluationProcessor = new UniformSubScopesProcessor();
124      Placeholder moveEvaluator = new Placeholder();
125      SubScopesCounter subScopesCounter = new SubScopesCounter();
126      BestSelector bestSelector = new BestSelector();
127      SubScopesProcessor moveMakingProcessor = new SubScopesProcessor();
128      UniformSubScopesProcessor selectedMoveMakingProcessor = new UniformSubScopesProcessor();
129      QualityComparator qualityComparator = new QualityComparator();
130      ConditionalBranch improvesQualityBranch = new ConditionalBranch();
131      Placeholder moveMaker = new Placeholder();
132      Assigner bestQualityUpdater = new Assigner();
133      ResultsCollector resultsCollector2 = new ResultsCollector();
134      MergingReducer mergingReducer = new MergingReducer();
135      Placeholder analyzer2 = new Placeholder();
136      SubScopesRemover subScopesRemover = new SubScopesRemover();
137      IntCounter iterationsCounter = new IntCounter();
138      Comparator iterationsComparator = new Comparator();
139      ConditionalBranch iterationsTermination = new ConditionalBranch();
140
141      bestQualityInitializer.Name = "Initialize BestQuality";
142      bestQualityInitializer.LeftSideParameter.ActualName = BestLocalQualityParameter.Name;
143      bestQualityInitializer.RightSideParameter.ActualName = QualityParameter.Name;
144
145      analyzer1.Name = "Analyzer (placeholder)";
146      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
147
148      resultsCollector1.CopyValue = new BoolValue(false);
149      resultsCollector1.CollectedValues.Add(new LookupParameter<IntValue>(IterationsParameter.Name));
150      resultsCollector1.CollectedValues.Add(new LookupParameter<DoubleValue>(BestLocalQualityParameter.Name, null, BestLocalQualityParameter.Name));
151      resultsCollector1.ResultsParameter.ActualName = ResultsParameter.Name;
152
153      moveGenerator.Name = "MoveGenerator (placeholder)";
154      moveGenerator.OperatorParameter.ActualName = MoveGeneratorParameter.Name;
155
156      moveEvaluationProcessor.Parallel = new BoolValue(true);
157
158      moveEvaluator.Name = "MoveEvaluator (placeholder)";
159      moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
160
161      subScopesCounter.Name = "Increment EvaluatedMoves";
162      subScopesCounter.ValueParameter.ActualName = EvaluatedMovesParameter.Name;
163
164      bestSelector.CopySelected = new BoolValue(false);
165      bestSelector.MaximizationParameter.ActualName = MaximizationParameter.Name;
166      bestSelector.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
167      bestSelector.QualityParameter.ActualName = MoveQualityParameter.Name;
168
169      qualityComparator.LeftSideParameter.ActualName = MoveQualityParameter.Name;
170      qualityComparator.RightSideParameter.ActualName = QualityParameter.Name;
171      qualityComparator.ResultParameter.ActualName = "IsBetter";
172
173      improvesQualityBranch.ConditionParameter.ActualName = "IsBetter";
174
175      moveMaker.Name = "MoveMaker (placeholder)";
176      moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
177
178      bestQualityUpdater.Name = "Update BestQuality";
179      bestQualityUpdater.LeftSideParameter.ActualName = BestLocalQualityParameter.Name;
180      bestQualityUpdater.RightSideParameter.ActualName = QualityParameter.Name;
181
182      resultsCollector2.CopyValue = new BoolValue(false);
183      resultsCollector2.CollectedValues.Add(new LookupParameter<DoubleValue>(BestLocalQualityParameter.Name, null, BestLocalQualityParameter.Name));
184      resultsCollector2.ResultsParameter.ActualName = ResultsParameter.Name;
185
186      analyzer2.Name = "Analyzer (placeholder)";
187      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
188
189      subScopesRemover.RemoveAllSubScopes = true;
190
191      iterationsCounter.Name = "Iterations Counter";
192      iterationsCounter.Increment = new IntValue(1);
193      iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
194
195      iterationsComparator.Name = "Iterations >= MaximumIterations";
196      iterationsComparator.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
197      iterationsComparator.LeftSideParameter.ActualName = IterationsParameter.Name;
198      iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
199      iterationsComparator.ResultParameter.ActualName = "Terminate";
200
201      iterationsTermination.Name = "Iterations Termination Condition";
202      iterationsTermination.ConditionParameter.ActualName = "Terminate";
203      #endregion
204
205      #region Create operator graph
206      OperatorGraph.InitialOperator = subScopesProcessor0;
207      subScopesProcessor0.Operators.Add(bestQualityInitializer);
208      subScopesProcessor0.Successor = resultsCollector1;
209      bestQualityInitializer.Successor = analyzer1;
210      analyzer1.Successor = null;
211      resultsCollector1.Successor = mainProcessor;
212      mainProcessor.Operators.Add(moveGenerator);
213      mainProcessor.Successor = iterationsCounter;
214      moveGenerator.Successor = moveEvaluationProcessor;
215      moveEvaluationProcessor.Operator = moveEvaluator;
216      moveEvaluationProcessor.Successor = subScopesCounter;
217      moveEvaluator.Successor = null;
218      subScopesCounter.Successor = bestSelector;
219      bestSelector.Successor = moveMakingProcessor;
220      moveMakingProcessor.Operators.Add(new EmptyOperator());
221      moveMakingProcessor.Operators.Add(selectedMoveMakingProcessor);
222      moveMakingProcessor.Successor = mergingReducer;
223      selectedMoveMakingProcessor.Operator = qualityComparator;
224      qualityComparator.Successor = improvesQualityBranch;
225      improvesQualityBranch.TrueBranch = moveMaker;
226      improvesQualityBranch.FalseBranch = null;
227      improvesQualityBranch.Successor = null;
228      moveMaker.Successor = bestQualityUpdater;
229      bestQualityUpdater.Successor = null;
230      mergingReducer.Successor = analyzer2;
231      analyzer2.Successor = subScopesRemover;
232      subScopesRemover.Successor = null;
233      iterationsCounter.Successor = iterationsComparator;
234      iterationsComparator.Successor = iterationsTermination;
235      iterationsTermination.TrueBranch = null;
236      iterationsTermination.FalseBranch = mainProcessor;
237      #endregion
238    }
239
240    public override IOperation Apply() {
241      if (MoveGeneratorParameter.ActualValue == null || MoveEvaluatorParameter.ActualValue == null || MoveMakerParameter.ActualValue == null)
242        return null;
243      return base.Apply();
244    }
245  }
246}
Note: See TracBrowser for help on using the repository browser.