source: branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/ScatterSearchMainLoop.cs @ 7786

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

#1331:

  • fixed bug in path relinking selection
  • fixed bug in ScatterSearch.Prepare()
  • added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
  • switched from diversity calculation to similarity calculation
  • separated IPathRelinker from ICrossover
  • changed TestFunctionsImprovementOperator to use reflection for evaluating functions
  • changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
  • improved TravelingSalesmanImprovementOperator
  • improved operator graph
  • removed specific operators used to evaluate TestFunctions problems
  • removed custom crossover operator (NChildCrossover)
  • added parameters and adjusted types
  • adjusted event handling
  • changed access levels
  • minor code improvements
File size: 16.9 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<SimilarityCalculator> SimilarityCalculatorParameter {
89      get { return (IValueLookupParameter<SimilarityCalculator>)Parameters["SimilarityCalculator"]; }
90    }
91    public IValueLookupParameter<ISolutionCreator> SolutionCreatorParameter {
92      get { return (IValueLookupParameter<ISolutionCreator>)Parameters["SolutionCreator"]; }
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 IEvaluator Evaluator {
110      get { return EvaluatorParameter.ActualValue; }
111      set { EvaluatorParameter.ActualValue = value; }
112    }
113    private BoolValue ExecutePathRelinking {
114      get { return ExecutePathRelinkingParameter.ActualValue; }
115      set { ExecutePathRelinkingParameter.ActualValue = value; }
116    }
117    private IImprovementOperator Improver {
118      get { return ImproverParameter.ActualValue; }
119      set { ImproverParameter.ActualValue = value; }
120    }
121    private IntValue Iterations {
122      get { return IterationsParameter.ActualValue; }
123      set { IterationsParameter.ActualValue = value; }
124    }
125    private BoolValue Maximization {
126      get { return MaximizationParameter.ActualValue; }
127      set { MaximizationParameter.ActualValue = value; }
128    }
129    private IntValue MaximumIterations {
130      get { return MaximumIterationsParameter.ActualValue; }
131      set { MaximumIterationsParameter.ActualValue = value; }
132    }
133    private IntValue NumberOfHighQualitySolutions {
134      get { return NumberOfHighQualitySolutionsParameter.ActualValue; }
135      set { NumberOfHighQualitySolutionsParameter.ActualValue = value; }
136    }
137    private IPathRelinker PathRelinker {
138      get { return PathRelinkerParameter.ActualValue; }
139      set { PathRelinkerParameter.ActualValue = value; }
140    }
141    private IntValue PopulationSize {
142      get { return PopulationSizeParameter.ActualValue; }
143      set { PopulationSizeParameter.ActualValue = value; }
144    }
145    private IntValue ReferenceSetSize {
146      get { return ReferenceSetSizeParameter.ActualValue; }
147      set { ReferenceSetSizeParameter.ActualValue = value; }
148    }
149    private DoubleValue Quality {
150      get { return QualityParameter.ActualValue; }
151      set { QualityParameter.ActualValue = value; }
152    }
153    private IRandom Random {
154      get { return RandomParameter.ActualValue; }
155      set { RandomParameter.ActualValue = value; }
156    }
157    private VariableCollection Results {
158      get { return ResultsParameter.ActualValue; }
159      set { ResultsParameter.ActualValue = value; }
160    }
161    private SimilarityCalculator SimilarityCalculator {
162      get { return SimilarityCalculatorParameter.ActualValue; }
163      set { SimilarityCalculatorParameter.ActualValue = value; }
164    }
165    private ISolutionCreator SolutionCreator {
166      get { return SolutionCreatorParameter.ActualValue; }
167      set { SolutionCreatorParameter.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"));
183      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality"));
184      Parameters.Add(new ValueLookupParameter<ICrossover>("Crossover"));
185      Parameters.Add(new ValueLookupParameter<IEvaluator>("Evaluator"));
186      Parameters.Add(new ValueLookupParameter<BoolValue>("ExecutePathRelinking"));
187      Parameters.Add(new ValueLookupParameter<IOperator>("Improver"));
188      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations"));
189      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
190      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations"));
191      Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
192      Parameters.Add(new ValueLookupParameter<IPathRelinker>("PathRelinker"));
193      Parameters.Add(new ValueLookupParameter<IntValue>("PopulationSize"));
194      Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
195      Parameters.Add(new ValueLookupParameter<DoubleValue>("Quality"));
196      Parameters.Add(new ValueLookupParameter<IRandom>("Random"));
197      Parameters.Add(new ValueLookupParameter<VariableCollection>("Results"));
198      Parameters.Add(new ValueLookupParameter<SimilarityCalculator>("SimilarityCalculator"));
199      Parameters.Add(new ValueLookupParameter<ISolutionCreator>("SolutionCreator"));
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      SubScopesProcessor subScopesProcessor1 = new SubScopesProcessor();
226      SubScopesProcessor subScopesProcessor2 = new SubScopesProcessor();
227      SubScopesProcessor subScopesProcessor3 = new SubScopesProcessor();
228      ConditionalBranch terminateBranch = new ConditionalBranch();
229      UniformSubScopesProcessor uniformSubScopesProcessor1 = new UniformSubScopesProcessor();
230      UniformSubScopesProcessor uniformSubScopesProcessor2 = new UniformSubScopesProcessor();
231      UniformSubScopesProcessor uniformSubScopesProcessor3 = new UniformSubScopesProcessor();
232      VariableCreator variableCreator = new VariableCreator();
233      #endregion
234
235      #region Create operator graph
236      OperatorGraph.InitialOperator = variableCreator;
237      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
238      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("NewSolutions", new BoolValue(false)));
239      variableCreator.Successor = resultsCollector;
240
241      resultsCollector.CopyValue = new BoolValue(false);
242      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>(IterationsParameter.Name));
243      resultsCollector.ResultsParameter.ActualName = ResultsParameter.Name;
244      resultsCollector.Successor = iterationsChecker;
245
246      iterationsChecker.Name = "IterationsChecker";
247      iterationsChecker.Comparison.Value = ComparisonType.GreaterOrEqual;
248      iterationsChecker.LeftSideParameter.ActualName = "Iterations";
249      iterationsChecker.RightSideParameter.ActualName = "MaximumIterations";
250      iterationsChecker.ResultParameter.ActualName = "Terminate";
251      iterationsChecker.Successor = terminateBranch;
252
253      terminateBranch.Name = "TerminateChecker";
254      terminateBranch.ConditionParameter.ActualName = "Terminate";
255      terminateBranch.FalseBranch = referenceSetUpdateMethod;
256
257      referenceSetUpdateMethod.Successor = assigner1;
258
259      assigner1.Name = "NewSolutions = true";
260      assigner1.LeftSideParameter.ActualName = "NewSolutions";
261      assigner1.RightSideParameter.Value = new BoolValue(true);
262      assigner1.Successor = subScopesProcessor1;
263
264      subScopesProcessor1.DepthParameter.Value = new IntValue(1);
265      subScopesProcessor1.Operators.Add(new EmptyOperator());
266      subScopesProcessor1.Operators.Add(childrenCreator);
267      subScopesProcessor1.Successor = newSolutionsBranch;
268
269      childrenCreator.Name = "SubsetGenerator";
270      childrenCreator.ParentsPerChildParameter.Value = new IntValue(2);
271      childrenCreator.Successor = assigner2;
272
273      assigner2.Name = "NewSolutions = false";
274      assigner2.LeftSideParameter.ActualName = "NewSolutions";
275      assigner2.RightSideParameter.Value = new BoolValue(false);
276      assigner2.Successor = uniformSubScopesProcessor1;
277
278      uniformSubScopesProcessor1.DepthParameter.Value = new IntValue(1);
279      uniformSubScopesProcessor1.Operator = executePathRelinkingBranch;
280      uniformSubScopesProcessor1.Successor = solutionPoolUpdateMethod;
281
282      executePathRelinkingBranch.Name = "ExecutePathRelinkingChecker";
283      executePathRelinkingBranch.ConditionParameter.ActualName = ExecutePathRelinkingParameter.ActualName;
284      executePathRelinkingBranch.TrueBranch = pathRelinker;
285      executePathRelinkingBranch.FalseBranch = crossover;
286
287      pathRelinker.Name = "PathRelinker";
288      pathRelinker.OperatorParameter.ActualName = "PathRelinker";
289      pathRelinker.Successor = offspringProcessor;
290
291      crossover.Name = "Crossover";
292      crossover.OperatorParameter.ActualName = "Crossover";
293      crossover.Successor = offspringProcessor;
294
295      offspringProcessor.Successor = rightSelector;
296
297      rightSelector.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
298      rightSelector.CopySelected = new BoolValue(false);
299      rightSelector.Successor = subScopesProcessor2;
300
301      subScopesProcessor2.DepthParameter.Value = new IntValue(1);
302      subScopesProcessor2.Operators.Add(new EmptyOperator());
303      subScopesProcessor2.Operators.Add(uniformSubScopesProcessor2);
304      subScopesProcessor2.Successor = mergingReducer;
305
306      uniformSubScopesProcessor2.DepthParameter.Value = new IntValue(2);
307      uniformSubScopesProcessor2.Operator = solutionImprover1;
308
309      solutionImprover1.Name = "SolutionImprover";
310      solutionImprover1.OperatorParameter.ActualName = "Improver";
311      solutionImprover1.Successor = solutionEvaluator1;
312
313      solutionEvaluator1.Name = "SolutionEvaluator";
314      solutionEvaluator1.OperatorParameter.ActualName = "Evaluator";
315
316      solutionPoolUpdateMethod.Successor = analyzer;
317
318      analyzer.Name = "Analyzer";
319      analyzer.OperatorParameter.ActualName = "Analyzer";
320
321      newSolutionsBranch.Name = "NewSolutionsChecker";
322      newSolutionsBranch.ConditionParameter.ActualName = "NewSolutions";
323      newSolutionsBranch.TrueBranch = subScopesProcessor1;
324      newSolutionsBranch.FalseBranch = populationRebuildMethod;
325
326      populationRebuildMethod.Successor = subScopesProcessor3;
327
328      subScopesProcessor3.DepthParameter.Value = new IntValue(1);
329      subScopesProcessor3.Operators.Add(solutionsCreator);
330      subScopesProcessor3.Operators.Add(new EmptyOperator());
331      subScopesProcessor3.Successor = iterationsCounter;
332
333      solutionsCreator.Name = "DiversificationGenerationMethod";
334      solutionsCreator.NumberOfSolutionsParameter.ActualName = "PopulationSize";
335      solutionsCreator.Successor = uniformSubScopesProcessor3;
336
337      uniformSubScopesProcessor3.DepthParameter.Value = new IntValue(1);
338      uniformSubScopesProcessor3.Operator = solutionImprover2;
339
340      solutionImprover2.Name = "SolutionImprover";
341      solutionImprover2.OperatorParameter.ActualName = "Improver";
342      solutionImprover2.Successor = solutionEvaluator2;
343
344      solutionEvaluator2.Name = "SolutionEvaluator";
345      solutionEvaluator2.OperatorParameter.ActualName = "Evaluator";
346
347      iterationsCounter.Name = "IterationCounter";
348      iterationsCounter.IncrementParameter.Value = new IntValue(1);
349      iterationsCounter.ValueParameter.ActualName = "Iterations";
350      iterationsCounter.Successor = resultsCollector;
351      #endregion
352    }
353
354    public override IOperation Apply() {
355      return base.Apply();
356    }
357  }
358}
Note: See TracBrowser for help on using the repository browser.