Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearchMainLoop.cs @ 14009

Last change on this file since 14009 was 12012, checked in by ascheibe, 10 years ago

#2212 merged r12008, r12009, r12010 back into trunk

File size: 19.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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<IntValue> EvaluatedSolutionsParameter {
50      get { return (IValueLookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
51    }
52    public IValueLookupParameter<IEvaluator> EvaluatorParameter {
53      get { return (IValueLookupParameter<IEvaluator>)Parameters["Evaluator"]; }
54    }
55    public IValueLookupParameter<BoolValue> ExecutePathRelinkingParameter {
56      get { return (IValueLookupParameter<BoolValue>)Parameters["ExecutePathRelinking"]; }
57    }
58    public IValueLookupParameter<IImprovementOperator> ImproverParameter {
59      get { return (IValueLookupParameter<IImprovementOperator>)Parameters["Improver"]; }
60    }
61    public IValueLookupParameter<IntValue> IterationsParameter {
62      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
63    }
64    public IValueLookupParameter<BoolValue> MaximizationParameter {
65      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
66    }
67    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
68      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
69    }
70    public IValueLookupParameter<IntValue> NumberOfHighQualitySolutionsParameter {
71      get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
72    }
73    public IValueLookupParameter<IPathRelinker> PathRelinkerParameter {
74      get { return (IValueLookupParameter<IPathRelinker>)Parameters["PathRelinker"]; }
75    }
76    public IValueLookupParameter<IntValue> PopulationSizeParameter {
77      get { return (IValueLookupParameter<IntValue>)Parameters["PopulationSize"]; }
78    }
79    public IValueLookupParameter<IntValue> ReferenceSetSizeParameter {
80      get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
81    }
82    public IValueLookupParameter<DoubleValue> QualityParameter {
83      get { return (IValueLookupParameter<DoubleValue>)Parameters["Quality"]; }
84    }
85    public IValueLookupParameter<IRandom> RandomParameter {
86      get { return (IValueLookupParameter<IRandom>)Parameters["Random"]; }
87    }
88    public IValueLookupParameter<VariableCollection> ResultsParameter {
89      get { return (IValueLookupParameter<VariableCollection>)Parameters["Results"]; }
90    }
91    public IValueLookupParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
92      get { return (IValueLookupParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
93    }
94    #endregion
95
96    #region Properties
97    private IMultiAnalyzer Analyzer {
98      get { return AnalyzerParameter.ActualValue; }
99      set { AnalyzerParameter.ActualValue = value; }
100    }
101    private DoubleValue BestKnownQuality {
102      get { return BestKnownQualityParameter.ActualValue; }
103      set { BestKnownQualityParameter.ActualValue = value; }
104    }
105    private ICrossover Crossover {
106      get { return CrossoverParameter.ActualValue; }
107      set { CrossoverParameter.ActualValue = value; }
108    }
109    private IntValue EvaluatedSolutions {
110      get { return EvaluatedSolutionsParameter.ActualValue; }
111      set { EvaluatedSolutionsParameter.ActualValue = value; }
112    }
113    private IEvaluator Evaluator {
114      get { return EvaluatorParameter.ActualValue; }
115      set { EvaluatorParameter.ActualValue = value; }
116    }
117    private BoolValue ExecutePathRelinking {
118      get { return ExecutePathRelinkingParameter.ActualValue; }
119      set { ExecutePathRelinkingParameter.ActualValue = value; }
120    }
121    private IImprovementOperator Improver {
122      get { return ImproverParameter.ActualValue; }
123      set { ImproverParameter.ActualValue = value; }
124    }
125    private IntValue Iterations {
126      get { return IterationsParameter.ActualValue; }
127      set { IterationsParameter.ActualValue = value; }
128    }
129    private BoolValue Maximization {
130      get { return MaximizationParameter.ActualValue; }
131      set { MaximizationParameter.ActualValue = value; }
132    }
133    private IntValue MaximumIterations {
134      get { return MaximumIterationsParameter.ActualValue; }
135      set { MaximumIterationsParameter.ActualValue = value; }
136    }
137    private IntValue NumberOfHighQualitySolutions {
138      get { return NumberOfHighQualitySolutionsParameter.ActualValue; }
139      set { NumberOfHighQualitySolutionsParameter.ActualValue = value; }
140    }
141    private IPathRelinker PathRelinker {
142      get { return PathRelinkerParameter.ActualValue; }
143      set { PathRelinkerParameter.ActualValue = value; }
144    }
145    private IntValue PopulationSize {
146      get { return PopulationSizeParameter.ActualValue; }
147      set { PopulationSizeParameter.ActualValue = value; }
148    }
149    private IntValue ReferenceSetSize {
150      get { return ReferenceSetSizeParameter.ActualValue; }
151      set { ReferenceSetSizeParameter.ActualValue = value; }
152    }
153    private DoubleValue Quality {
154      get { return QualityParameter.ActualValue; }
155      set { QualityParameter.ActualValue = value; }
156    }
157    private IRandom Random {
158      get { return RandomParameter.ActualValue; }
159      set { RandomParameter.ActualValue = value; }
160    }
161    private VariableCollection Results {
162      get { return ResultsParameter.ActualValue; }
163      set { ResultsParameter.ActualValue = value; }
164    }
165    private ISolutionSimilarityCalculator SimilarityCalculator {
166      get { return SimilarityCalculatorParameter.ActualValue; }
167      set { SimilarityCalculatorParameter.ActualValue = value; }
168    }
169    #endregion
170
171    [StorableConstructor]
172    private ScatterSearchMainLoop(bool deserializing) : base(deserializing) { }
173    private ScatterSearchMainLoop(ScatterSearchMainLoop original, Cloner cloner) : base(original, cloner) { }
174    public ScatterSearchMainLoop() : base() { Initialize(); }
175
176    public override IDeepCloneable Clone(Cloner cloner) {
177      return new ScatterSearchMainLoop(this, cloner);
178    }
179
180    private void Initialize() {
181      #region Create parameters
182      Parameters.Add(new ValueLookupParameter<IMultiAnalyzer>("Analyzer", "The analyzer used to analyze each iteration."));
183      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality", "The best known quality value found so far."));
184      Parameters.Add(new ValueLookupParameter<ICrossover>("Crossover", "The operator used to cross solutions."));
185      Parameters.Add(new ValueLookupParameter<IntValue>("EvaluatedSolutions", "The number of times solutions have been evaluated."));
186      Parameters.Add(new ValueLookupParameter<IEvaluator>("Evaluator", "The operator used to evaluate solutions. This operator is executed in parallel, if an engine is used which supports parallelization."));
187      Parameters.Add(new ValueLookupParameter<BoolValue>("ExecutePathRelinking", "True if path relinking should be executed instead of crossover, otherwise false."));
188      Parameters.Add(new ValueLookupParameter<IImprovementOperator>("Improver", "The operator used to improve solutions."));
189      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations", "The number of iterations performed."));
190      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
191      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of iterations which should be processed."));
192      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions", "The number of high quality solutions in the reference set."));
193      Parameters.Add(new ValueLookupParameter<IPathRelinker>("PathRelinker", "The operator used to execute path relinking."));
194      Parameters.Add(new ValueLookupParameter<IntValue>("PopulationSize", "The size of the population of solutions."));
195      Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize", "The size of the reference set."));
196      Parameters.Add(new ValueLookupParameter<DoubleValue>("Quality", "This parameter is used for name translation only."));
197      Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
198      Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
199      Parameters.Add(new ValueLookupParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The operator used to calculate the similarity between two solutions."));
200      #endregion
201
202      #region Create operators
203      Placeholder analyzer = new Placeholder();
204      Assigner assigner1 = new Assigner();
205      Assigner assigner2 = new Assigner();
206      ChildrenCreator childrenCreator = new ChildrenCreator();
207      Placeholder crossover = new Placeholder();
208      Comparator iterationsChecker = new Comparator();
209      IntCounter iterationsCounter = new IntCounter();
210      MergingReducer mergingReducer = new MergingReducer();
211      ConditionalBranch executePathRelinkingBranch = new ConditionalBranch();
212      ConditionalBranch newSolutionsBranch = new ConditionalBranch();
213      OffspringProcessor offspringProcessor = new OffspringProcessor();
214      Placeholder pathRelinker = new Placeholder();
215      PopulationRebuildMethod populationRebuildMethod = new PopulationRebuildMethod();
216      ReferenceSetUpdateMethod referenceSetUpdateMethod = new ReferenceSetUpdateMethod();
217      ResultsCollector resultsCollector = new ResultsCollector();
218      RightSelector rightSelector = new RightSelector();
219      Placeholder solutionEvaluator1 = new Placeholder();
220      Placeholder solutionEvaluator2 = new Placeholder();
221      Placeholder solutionImprover1 = new Placeholder();
222      Placeholder solutionImprover2 = new Placeholder();
223      SolutionPoolUpdateMethod solutionPoolUpdateMethod = new SolutionPoolUpdateMethod();
224      SolutionsCreator solutionsCreator = new SolutionsCreator();
225      DataReducer dataReducer1 = new DataReducer();
226      DataReducer dataReducer2 = new DataReducer();
227      SubScopesProcessor subScopesProcessor1 = new SubScopesProcessor();
228      SubScopesProcessor subScopesProcessor2 = new SubScopesProcessor();
229      SubScopesProcessor subScopesProcessor3 = new SubScopesProcessor();
230      SubScopesProcessor subScopesProcessor4 = new SubScopesProcessor();
231      ConditionalBranch terminateBranch = new ConditionalBranch();
232      UniformSubScopesProcessor uniformSubScopesProcessor1 = new UniformSubScopesProcessor();
233      UniformSubScopesProcessor uniformSubScopesProcessor2 = new UniformSubScopesProcessor();
234      UniformSubScopesProcessor uniformSubScopesProcessor3 = new UniformSubScopesProcessor();
235      VariableCreator variableCreator = new VariableCreator();
236      #endregion
237
238      #region Create operator graph
239      OperatorGraph.InitialOperator = variableCreator;
240      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>(IterationsParameter.Name, new IntValue(0)));
241      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("NewSolutions", new BoolValue(false)));
242      variableCreator.Successor = resultsCollector;
243
244      resultsCollector.CopyValue = new BoolValue(false);
245      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>(IterationsParameter.Name));
246      resultsCollector.ResultsParameter.ActualName = ResultsParameter.Name;
247      resultsCollector.Successor = iterationsChecker;
248
249      iterationsChecker.Name = "IterationsChecker";
250      iterationsChecker.Comparison.Value = ComparisonType.GreaterOrEqual;
251      iterationsChecker.LeftSideParameter.ActualName = IterationsParameter.Name;
252      iterationsChecker.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
253      iterationsChecker.ResultParameter.ActualName = "Terminate";
254      iterationsChecker.Successor = terminateBranch;
255
256      terminateBranch.Name = "TerminateChecker";
257      terminateBranch.ConditionParameter.ActualName = "Terminate";
258      terminateBranch.FalseBranch = referenceSetUpdateMethod;
259
260      referenceSetUpdateMethod.Successor = assigner1;
261
262      assigner1.Name = "NewSolutions = true";
263      assigner1.LeftSideParameter.ActualName = "NewSolutions";
264      assigner1.RightSideParameter.Value = new BoolValue(true);
265      assigner1.Successor = subScopesProcessor1;
266
267      subScopesProcessor1.DepthParameter.Value = new IntValue(1);
268      subScopesProcessor1.Operators.Add(new EmptyOperator());
269      subScopesProcessor1.Operators.Add(childrenCreator);
270      subScopesProcessor1.Successor = newSolutionsBranch;
271
272      childrenCreator.Name = "SubsetGenerator";
273      childrenCreator.ParentsPerChildParameter.Value = new IntValue(2);
274      childrenCreator.Successor = assigner2;
275
276      assigner2.Name = "NewSolutions = false";
277      assigner2.LeftSideParameter.ActualName = "NewSolutions";
278      assigner2.RightSideParameter.Value = new BoolValue(false);
279      assigner2.Successor = uniformSubScopesProcessor1;
280
281      uniformSubScopesProcessor1.DepthParameter.Value = new IntValue(1);
282      uniformSubScopesProcessor1.Operator = executePathRelinkingBranch;
283      uniformSubScopesProcessor1.Successor = solutionPoolUpdateMethod;
284
285      executePathRelinkingBranch.Name = "ExecutePathRelinkingChecker";
286      executePathRelinkingBranch.ConditionParameter.ActualName = ExecutePathRelinkingParameter.ActualName;
287      executePathRelinkingBranch.TrueBranch = pathRelinker;
288      executePathRelinkingBranch.FalseBranch = crossover;
289
290      pathRelinker.Name = "PathRelinker";
291      pathRelinker.OperatorParameter.ActualName = PathRelinkerParameter.Name;
292      pathRelinker.Successor = rightSelector;
293
294      crossover.Name = "Crossover";
295      crossover.OperatorParameter.ActualName = CrossoverParameter.Name;
296      crossover.Successor = offspringProcessor;
297
298      offspringProcessor.Successor = rightSelector;
299
300      rightSelector.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
301      rightSelector.CopySelected = new BoolValue(false);
302      rightSelector.Successor = subScopesProcessor2;
303
304      subScopesProcessor2.DepthParameter.Value = new IntValue(1);
305      subScopesProcessor2.Operators.Add(new EmptyOperator());
306      subScopesProcessor2.Operators.Add(uniformSubScopesProcessor2);
307      subScopesProcessor2.Successor = mergingReducer;
308
309      uniformSubScopesProcessor2.DepthParameter.Value = new IntValue(2);
310      uniformSubScopesProcessor2.Operator = solutionImprover1;
311      uniformSubScopesProcessor2.ParallelParameter.Value = new BoolValue(true);
312      uniformSubScopesProcessor2.Successor = subScopesProcessor4;
313
314      solutionImprover1.Name = "SolutionImprover";
315      solutionImprover1.OperatorParameter.ActualName = ImproverParameter.Name;
316      solutionImprover1.Successor = solutionEvaluator1;
317
318      solutionEvaluator1.Name = "SolutionEvaluator";
319      solutionEvaluator1.OperatorParameter.ActualName = EvaluatorParameter.Name;
320
321      subScopesProcessor4.Operators.Add(dataReducer1);
322
323      dataReducer1.Name = "Increment EvaluatedSolutions";
324      dataReducer1.ParameterToReduce.ActualName = "LocalEvaluatedSolutions";
325      dataReducer1.TargetParameter.ActualName = EvaluatedSolutionsParameter.Name;
326      dataReducer1.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
327      dataReducer1.TargetOperation.Value = new ReductionOperation(ReductionOperations.Sum);
328
329      solutionPoolUpdateMethod.QualityParameter.ActualName = QualityParameter.ActualName;
330      solutionPoolUpdateMethod.Successor = analyzer;
331
332      analyzer.Name = "Analyzer";
333      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
334
335      newSolutionsBranch.Name = "NewSolutionsChecker";
336      newSolutionsBranch.ConditionParameter.ActualName = "NewSolutions";
337      newSolutionsBranch.TrueBranch = subScopesProcessor1;
338      newSolutionsBranch.FalseBranch = populationRebuildMethod;
339
340      populationRebuildMethod.QualityParameter.ActualName = QualityParameter.ActualName;
341      populationRebuildMethod.Successor = subScopesProcessor3;
342
343      subScopesProcessor3.DepthParameter.Value = new IntValue(1);
344      subScopesProcessor3.Operators.Add(solutionsCreator);
345      subScopesProcessor3.Operators.Add(new EmptyOperator());
346      subScopesProcessor3.Successor = iterationsCounter;
347
348      solutionsCreator.Name = "DiversificationGenerationMethod";
349      solutionsCreator.NumberOfSolutionsParameter.ActualName = PopulationSizeParameter.Name;
350      solutionsCreator.Successor = uniformSubScopesProcessor3;
351
352      uniformSubScopesProcessor3.DepthParameter.Value = new IntValue(1);
353      uniformSubScopesProcessor3.Operator = solutionImprover2;
354      uniformSubScopesProcessor3.ParallelParameter.Value = new BoolValue(true);
355      uniformSubScopesProcessor3.Successor = dataReducer2;
356
357      solutionImprover2.Name = "SolutionImprover";
358      solutionImprover2.OperatorParameter.ActualName = ImproverParameter.Name;
359      solutionImprover2.Successor = solutionEvaluator2;
360
361      solutionEvaluator2.Name = "SolutionEvaluator";
362      solutionEvaluator2.OperatorParameter.ActualName = EvaluatorParameter.Name;
363
364      dataReducer2.Name = "Increment EvaluatedSolutions";
365      dataReducer2.ParameterToReduce.ActualName = "LocalEvaluatedSolutions";
366      dataReducer2.TargetParameter.ActualName = EvaluatedSolutionsParameter.Name;
367      dataReducer2.ReductionOperation.Value = new ReductionOperation(ReductionOperations.Sum);
368      dataReducer2.TargetOperation.Value = new ReductionOperation(ReductionOperations.Sum);
369
370      iterationsCounter.Name = "IterationCounter";
371      iterationsCounter.IncrementParameter.Value = new IntValue(1);
372      iterationsCounter.ValueParameter.ActualName = IterationsParameter.Name;
373      iterationsCounter.Successor = resultsCollector;
374      #endregion
375    }
376
377    public override IOperation Apply() {
378      if (ImproverParameter.ActualValue == null)
379        return null;
380      return base.Apply();
381    }
382  }
383}
Note: See TracBrowser for help on using the repository browser.