source: branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearchMainLoop.cs @ 7789

Last change on this file since 7789 was 7789, checked in by jkarder, 8 years ago

#1331:

  • added Scatter Search algorithm
  • added problem specific operators for improvement, path relinking and similarity calculation
  • adjusted event handling
File size: 17.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 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.ScatterSearch {
33  /// <summary>
34  /// An operator which represents a scatter search.
35  /// </summary>
36  [Item("ScatterSearchMainLoop", "An operator which represents a scatter search.")]
37  [StorableClass]
38  public sealed class ScatterSearchMainLoop : AlgorithmOperator {
39    #region Parameter properties
40    public IValueLookupParameter<IMultiAnalyzer> AnalyzerParameter {
41      get { return (IValueLookupParameter<IMultiAnalyzer>)Parameters["Analyzer"]; }
42    }
43    public IValueLookupParameter<DoubleValue> BestKnownQualityParameter {
44      get { return (IValueLookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
45    }
46    public IValueLookupParameter<ICrossover> CrossoverParameter {
47      get { return (IValueLookupParameter<ICrossover>)Parameters["Crossover"]; }
48    }
49    public IValueLookupParameter<IEvaluator> EvaluatorParameter {
50      get { return (IValueLookupParameter<IEvaluator>)Parameters["Evaluator"]; }
51    }
52    public IValueLookupParameter<BoolValue> ExecutePathRelinkingParameter {
53      get { return (IValueLookupParameter<BoolValue>)Parameters["ExecutePathRelinking"]; }
54    }
55    public IValueLookupParameter<IImprovementOperator> ImproverParameter {
56      get { return (IValueLookupParameter<IImprovementOperator>)Parameters["Improver"]; }
57    }
58    public IValueLookupParameter<IntValue> IterationsParameter {
59      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
60    }
61    public IValueLookupParameter<BoolValue> MaximizationParameter {
62      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
63    }
64    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
65      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
66    }
67    public IValueLookupParameter<IntValue> NumberOfHighQualitySolutionsParameter {
68      get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
69    }
70    public IValueLookupParameter<IPathRelinker> PathRelinkerParameter {
71      get { return (IValueLookupParameter<IPathRelinker>)Parameters["PathRelinker"]; }
72    }
73    public IValueLookupParameter<IntValue> PopulationSizeParameter {
74      get { return (IValueLookupParameter<IntValue>)Parameters["PopulationSize"]; }
75    }
76    public IValueLookupParameter<IntValue> ReferenceSetSizeParameter {
77      get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
78    }
79    public IValueLookupParameter<DoubleValue> QualityParameter {
80      get { return (IValueLookupParameter<DoubleValue>)Parameters["Quality"]; }
81    }
82    public IValueLookupParameter<IRandom> RandomParameter {
83      get { return (IValueLookupParameter<IRandom>)Parameters["Random"]; }
84    }
85    public IValueLookupParameter<VariableCollection> ResultsParameter {
86      get { return (IValueLookupParameter<VariableCollection>)Parameters["Results"]; }
87    }
88    public IValueLookupParameter<ISimilarityCalculator> SimilarityCalculatorParameter {
89      get { return (IValueLookupParameter<ISimilarityCalculator>)Parameters["SimilarityCalculator"]; }
90    }
91    public IValueLookupParameter<ISolutionCreator> SolutionCreatorParameter {
92      get { return (IValueLookupParameter<ISolutionCreator>)Parameters["SolutionCreator"]; }
93    }
94    public IValueLookupParameter<IItem> TargetParameter {
95      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
96    }
97    #endregion
98
99    #region Properties
100    private IMultiAnalyzer Analyzer {
101      get { return AnalyzerParameter.ActualValue; }
102      set { AnalyzerParameter.ActualValue = value; }
103    }
104    private DoubleValue BestKnownQuality {
105      get { return BestKnownQualityParameter.ActualValue; }
106      set { BestKnownQualityParameter.ActualValue = value; }
107    }
108    private ICrossover Crossover {
109      get { return CrossoverParameter.ActualValue; }
110      set { CrossoverParameter.ActualValue = value; }
111    }
112    private IEvaluator Evaluator {
113      get { return EvaluatorParameter.ActualValue; }
114      set { EvaluatorParameter.ActualValue = value; }
115    }
116    private BoolValue ExecutePathRelinking {
117      get { return ExecutePathRelinkingParameter.ActualValue; }
118      set { ExecutePathRelinkingParameter.ActualValue = value; }
119    }
120    private IImprovementOperator Improver {
121      get { return ImproverParameter.ActualValue; }
122      set { ImproverParameter.ActualValue = value; }
123    }
124    private IntValue Iterations {
125      get { return IterationsParameter.ActualValue; }
126      set { IterationsParameter.ActualValue = value; }
127    }
128    private BoolValue Maximization {
129      get { return MaximizationParameter.ActualValue; }
130      set { MaximizationParameter.ActualValue = value; }
131    }
132    private IntValue MaximumIterations {
133      get { return MaximumIterationsParameter.ActualValue; }
134      set { MaximumIterationsParameter.ActualValue = value; }
135    }
136    private IntValue NumberOfHighQualitySolutions {
137      get { return NumberOfHighQualitySolutionsParameter.ActualValue; }
138      set { NumberOfHighQualitySolutionsParameter.ActualValue = value; }
139    }
140    private IPathRelinker PathRelinker {
141      get { return PathRelinkerParameter.ActualValue; }
142      set { PathRelinkerParameter.ActualValue = value; }
143    }
144    private IntValue PopulationSize {
145      get { return PopulationSizeParameter.ActualValue; }
146      set { PopulationSizeParameter.ActualValue = value; }
147    }
148    private IntValue ReferenceSetSize {
149      get { return ReferenceSetSizeParameter.ActualValue; }
150      set { ReferenceSetSizeParameter.ActualValue = value; }
151    }
152    private DoubleValue Quality {
153      get { return QualityParameter.ActualValue; }
154      set { QualityParameter.ActualValue = value; }
155    }
156    private IRandom Random {
157      get { return RandomParameter.ActualValue; }
158      set { RandomParameter.ActualValue = value; }
159    }
160    private VariableCollection Results {
161      get { return ResultsParameter.ActualValue; }
162      set { ResultsParameter.ActualValue = value; }
163    }
164    private ISimilarityCalculator SimilarityCalculator {
165      get { return SimilarityCalculatorParameter.ActualValue; }
166      set { SimilarityCalculatorParameter.ActualValue = value; }
167    }
168    private ISolutionCreator SolutionCreator {
169      get { return SolutionCreatorParameter.ActualValue; }
170      set { SolutionCreatorParameter.ActualValue = value; }
171    }
172    private IItem Target {
173      get { return TargetParameter.ActualValue; }
174      set { TargetParameter.ActualValue = value; }
175    }
176    #endregion
177
178    [StorableConstructor]
179    private ScatterSearchMainLoop(bool deserializing) : base(deserializing) { }
180    private ScatterSearchMainLoop(ScatterSearchMainLoop original, Cloner cloner) : base(original, cloner) { }
181    public ScatterSearchMainLoop() : base() { Initialize(); }
182
183    public override IDeepCloneable Clone(Cloner cloner) {
184      return new ScatterSearchMainLoop(this, cloner);
185    }
186
187    private void Initialize() {
188      #region Create parameters
189      Parameters.Add(new ValueLookupParameter<IMultiAnalyzer>("Analyzer"));
190      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality"));
191      Parameters.Add(new ValueLookupParameter<ICrossover>("Crossover"));
192      Parameters.Add(new ValueLookupParameter<IEvaluator>("Evaluator"));
193      Parameters.Add(new ValueLookupParameter<BoolValue>("ExecutePathRelinking"));
194      Parameters.Add(new ValueLookupParameter<IImprovementOperator>("Improver"));
195      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations"));
196      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
197      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations"));
198      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
199      Parameters.Add(new ValueLookupParameter<IPathRelinker>("PathRelinker"));
200      Parameters.Add(new ValueLookupParameter<IntValue>("PopulationSize"));
201      Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
202      Parameters.Add(new ValueLookupParameter<DoubleValue>("Quality"));
203      Parameters.Add(new ValueLookupParameter<IRandom>("Random"));
204      Parameters.Add(new ValueLookupParameter<VariableCollection>("Results"));
205      Parameters.Add(new ValueLookupParameter<ISimilarityCalculator>("SimilarityCalculator"));
206      Parameters.Add(new ValueLookupParameter<ISolutionCreator>("SolutionCreator"));
207      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
208      #endregion
209
210      #region Create operators
211      Placeholder analyzer = new Placeholder();
212      Assigner assigner1 = new Assigner();
213      Assigner assigner2 = new Assigner();
214      ChildrenCreator childrenCreator = new ChildrenCreator();
215      Placeholder crossover = new Placeholder();
216      Comparator iterationsChecker = new Comparator();
217      IntCounter iterationsCounter = new IntCounter();
218      MergingReducer mergingReducer = new MergingReducer();
219      ConditionalBranch executePathRelinkingBranch = new ConditionalBranch();
220      ConditionalBranch newSolutionsBranch = new ConditionalBranch();
221      OffspringProcessor offspringProcessor = new OffspringProcessor();
222      Placeholder pathRelinker = new Placeholder();
223      PopulationRebuildMethod populationRebuildMethod = new PopulationRebuildMethod();
224      ReferenceSetUpdateMethod referenceSetUpdateMethod = new ReferenceSetUpdateMethod();
225      ResultsCollector resultsCollector = new ResultsCollector();
226      RightSelector rightSelector = new RightSelector();
227      Placeholder solutionEvaluator1 = new Placeholder();
228      Placeholder solutionEvaluator2 = new Placeholder();
229      Placeholder solutionImprover1 = new Placeholder();
230      Placeholder solutionImprover2 = new Placeholder();
231      SolutionPoolUpdateMethod solutionPoolUpdateMethod = new SolutionPoolUpdateMethod();
232      SolutionsCreator solutionsCreator = new SolutionsCreator();
233      SubScopesProcessor subScopesProcessor1 = new SubScopesProcessor();
234      SubScopesProcessor subScopesProcessor2 = new SubScopesProcessor();
235      SubScopesProcessor subScopesProcessor3 = new SubScopesProcessor();
236      ConditionalBranch terminateBranch = new ConditionalBranch();
237      UniformSubScopesProcessor uniformSubScopesProcessor1 = new UniformSubScopesProcessor();
238      UniformSubScopesProcessor uniformSubScopesProcessor2 = new UniformSubScopesProcessor();
239      UniformSubScopesProcessor uniformSubScopesProcessor3 = new UniformSubScopesProcessor();
240      VariableCreator variableCreator = new VariableCreator();
241      #endregion
242
243      #region Create operator graph
244      OperatorGraph.InitialOperator = variableCreator;
245      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
246      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("NewSolutions", new BoolValue(false)));
247      variableCreator.Successor = resultsCollector;
248
249      resultsCollector.CopyValue = new BoolValue(false);
250      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>(IterationsParameter.Name));
251      resultsCollector.ResultsParameter.ActualName = ResultsParameter.Name;
252      resultsCollector.Successor = iterationsChecker;
253
254      iterationsChecker.Name = "IterationsChecker";
255      iterationsChecker.Comparison.Value = ComparisonType.GreaterOrEqual;
256      iterationsChecker.LeftSideParameter.ActualName = "Iterations";
257      iterationsChecker.RightSideParameter.ActualName = "MaximumIterations";
258      iterationsChecker.ResultParameter.ActualName = "Terminate";
259      iterationsChecker.Successor = terminateBranch;
260
261      terminateBranch.Name = "TerminateChecker";
262      terminateBranch.ConditionParameter.ActualName = "Terminate";
263      terminateBranch.FalseBranch = referenceSetUpdateMethod;
264
265      referenceSetUpdateMethod.TargetParameter.ActualName = TargetParameter.ActualName;
266      referenceSetUpdateMethod.Successor = assigner1;
267
268      assigner1.Name = "NewSolutions = true";
269      assigner1.LeftSideParameter.ActualName = "NewSolutions";
270      assigner1.RightSideParameter.Value = new BoolValue(true);
271      assigner1.Successor = subScopesProcessor1;
272
273      subScopesProcessor1.DepthParameter.Value = new IntValue(1);
274      subScopesProcessor1.Operators.Add(new EmptyOperator());
275      subScopesProcessor1.Operators.Add(childrenCreator);
276      subScopesProcessor1.Successor = newSolutionsBranch;
277
278      childrenCreator.Name = "SubsetGenerator";
279      childrenCreator.ParentsPerChildParameter.Value = new IntValue(2);
280      childrenCreator.Successor = assigner2;
281
282      assigner2.Name = "NewSolutions = false";
283      assigner2.LeftSideParameter.ActualName = "NewSolutions";
284      assigner2.RightSideParameter.Value = new BoolValue(false);
285      assigner2.Successor = uniformSubScopesProcessor1;
286
287      uniformSubScopesProcessor1.DepthParameter.Value = new IntValue(1);
288      uniformSubScopesProcessor1.Operator = executePathRelinkingBranch;
289      uniformSubScopesProcessor1.Successor = solutionPoolUpdateMethod;
290
291      executePathRelinkingBranch.Name = "ExecutePathRelinkingChecker";
292      executePathRelinkingBranch.ConditionParameter.ActualName = ExecutePathRelinkingParameter.ActualName;
293      executePathRelinkingBranch.TrueBranch = pathRelinker;
294      executePathRelinkingBranch.FalseBranch = crossover;
295
296      pathRelinker.Name = "PathRelinker";
297      pathRelinker.OperatorParameter.ActualName = "PathRelinker";
298      pathRelinker.Successor = offspringProcessor;
299
300      crossover.Name = "Crossover";
301      crossover.OperatorParameter.ActualName = "Crossover";
302      crossover.Successor = offspringProcessor;
303
304      offspringProcessor.TargetParameter.ActualName = TargetParameter.ActualName;
305      offspringProcessor.Successor = rightSelector;
306
307      rightSelector.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
308      rightSelector.CopySelected = new BoolValue(false);
309      rightSelector.Successor = subScopesProcessor2;
310
311      subScopesProcessor2.DepthParameter.Value = new IntValue(1);
312      subScopesProcessor2.Operators.Add(new EmptyOperator());
313      subScopesProcessor2.Operators.Add(uniformSubScopesProcessor2);
314      subScopesProcessor2.Successor = mergingReducer;
315
316      uniformSubScopesProcessor2.DepthParameter.Value = new IntValue(2);
317      uniformSubScopesProcessor2.Operator = solutionImprover1;
318
319      solutionImprover1.Name = "SolutionImprover";
320      solutionImprover1.OperatorParameter.ActualName = "Improver";
321      solutionImprover1.Successor = solutionEvaluator1;
322
323      solutionEvaluator1.Name = "SolutionEvaluator";
324      solutionEvaluator1.OperatorParameter.ActualName = "Evaluator";
325
326      solutionPoolUpdateMethod.QualityParameter.ActualName = QualityParameter.ActualName;
327      solutionPoolUpdateMethod.TargetParameter.ActualName = TargetParameter.ActualName;
328      solutionPoolUpdateMethod.Successor = analyzer;
329
330      analyzer.Name = "Analyzer";
331      analyzer.OperatorParameter.ActualName = "Analyzer";
332
333      newSolutionsBranch.Name = "NewSolutionsChecker";
334      newSolutionsBranch.ConditionParameter.ActualName = "NewSolutions";
335      newSolutionsBranch.TrueBranch = subScopesProcessor1;
336      newSolutionsBranch.FalseBranch = populationRebuildMethod;
337
338      populationRebuildMethod.QualityParameter.ActualName = QualityParameter.ActualName;
339      populationRebuildMethod.Successor = subScopesProcessor3;
340
341      subScopesProcessor3.DepthParameter.Value = new IntValue(1);
342      subScopesProcessor3.Operators.Add(solutionsCreator);
343      subScopesProcessor3.Operators.Add(new EmptyOperator());
344      subScopesProcessor3.Successor = iterationsCounter;
345
346      solutionsCreator.Name = "DiversificationGenerationMethod";
347      solutionsCreator.NumberOfSolutionsParameter.ActualName = "PopulationSize";
348      solutionsCreator.Successor = uniformSubScopesProcessor3;
349
350      uniformSubScopesProcessor3.DepthParameter.Value = new IntValue(1);
351      uniformSubScopesProcessor3.Operator = solutionImprover2;
352
353      solutionImprover2.Name = "SolutionImprover";
354      solutionImprover2.OperatorParameter.ActualName = "Improver";
355      solutionImprover2.Successor = solutionEvaluator2;
356
357      solutionEvaluator2.Name = "SolutionEvaluator";
358      solutionEvaluator2.OperatorParameter.ActualName = "Evaluator";
359
360      iterationsCounter.Name = "IterationCounter";
361      iterationsCounter.IncrementParameter.Value = new IntValue(1);
362      iterationsCounter.ValueParameter.ActualName = "Iterations";
363      iterationsCounter.Successor = resultsCollector;
364      #endregion
365    }
366
367    public override IOperation Apply() {
368      if (ImproverParameter.ActualValue == null)
369        return null;
370      return base.Apply();
371    }
372  }
373}
Note: See TracBrowser for help on using the repository browser.