Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASPWithPathRelinkingMainLoop.cs @ 7412

Last change on this file since 7412 was 7412, checked in by abeham, 12 years ago

#1614: worked on GQAP and GRASP+PR

File size: 12.1 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 System;
23using System.Linq;
24using HeuristicLab.Common;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Operators;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
33using HeuristicLab.Selection;
34
35namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms {
36  [Item("GRASP+PR MainLoop", "The main loop that implements the behavior of the GRASP+PR algorithm.")]
37  [StorableClass]
38  public class GRASPWithPathRelinkingMainLoop : AlgorithmOperator {
39    public IValueLookupParameter<IOperator> SolutionCreatorParameter {
40      get { return (IValueLookupParameter<IOperator>)Parameters["SolutionCreator"]; }
41    }
42    public IValueLookupParameter<IOperator> EvaluatorParameter {
43      get { return (IValueLookupParameter<IOperator>)Parameters["Evaluator"]; }
44    }
45    public IValueLookupParameter<IntValue> EvaluatedSolutionsParameter {
46      get { return (IValueLookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
47    }
48    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
49      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
50    }
51    public IValueLookupParameter<ResultCollection> ResultsParameter {
52      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
53    }
54    public IValueLookupParameter<IntValue> EliteSetSizeParameter {
55      get { return (IValueLookupParameter<IntValue>)Parameters["EliteSetSize"]; }
56    }
57    public IValueLookupParameter<IOperator> LocalImprovementParameter {
58      get { return (IValueLookupParameter<IOperator>)Parameters["LocalImprovement"]; }
59    }
60    public IValueLookupParameter<IOperator> PathRelinkingParameter {
61      get { return (IValueLookupParameter<IOperator>)Parameters["PathRelinking"]; }
62    }
63    public IValueLookupParameter<IOperator> EliteSetMergerParameter {
64      get { return (IValueLookupParameter<IOperator>)Parameters["EliteSetMerger"]; }
65    }
66    public IValueLookupParameter<IOperator> AnalyzerParameter {
67      get { return (IValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
68    }
69
70    [StorableConstructor]
71    protected GRASPWithPathRelinkingMainLoop(bool deserializing) : base(deserializing) { }
72    protected GRASPWithPathRelinkingMainLoop(GRASPWithPathRelinkingMainLoop original, Cloner cloner)
73      : base(original, cloner) { }
74    public GRASPWithPathRelinkingMainLoop()
75      : base() {
76      Parameters.Add(new ValueLookupParameter<IOperator>("SolutionCreator", "The solution creation procedure which ideally should be a greedy initialization heuristic."));
77      Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The evaluator which calculates the fitness of a solutions."));
78      Parameters.Add(new ValueLookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
79      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of maximum iterations that should be performed."));
80      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "Specifies where the results are stored."));
81      Parameters.Add(new ValueLookupParameter<IntValue>("EliteSetSize", "The size of the elite set."));
82      Parameters.Add(new ValueLookupParameter<IOperator>("LocalImprovement", "The operator which performs the local improvement."));
83      Parameters.Add(new ValueLookupParameter<IOperator>("PathRelinking", "The operator which performs the path relinking."));
84      Parameters.Add(new ValueLookupParameter<IOperator>("EliteSetMerger", "The operator that merges elements in the elite set."));
85      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The analyzer that is to be applied."));
86
87      var variableCreator1 = new VariableCreator();
88      variableCreator1.Name = "Iterations = 0";
89      variableCreator1.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
90
91      var resultsCollector = new ResultsCollector();
92      resultsCollector.CopyValue = new BoolValue(false);
93      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
94
95      var variableCreator2 = new VariableCreator();
96      variableCreator2.Name = "ActualEliteSetSize = 0";
97      variableCreator2.CollectedValues.Add(new ValueParameter<IntValue>("ActualEliteSetSize", new IntValue(0)));
98
99      var subScopesCounter1 = new SubScopesCounter();
100      subScopesCounter1.Name = "ActualEliteSetSize += |SubScopes|";
101      subScopesCounter1.ValueParameter.ActualName = "ActualEliteSetSize";
102
103      var comparator1 = new Comparator();
104      comparator1.Name = "ActualEliteSetSize >= MinimumEliteSetSize";
105      comparator1.Comparison.Value = ComparisonType.GreaterOrEqual;
106      comparator1.LeftSideParameter.ActualName = "ActualEliteSetSize";
107      comparator1.RightSideParameter.ActualName = EliteSetSizeParameter.ActualName;
108      comparator1.ResultParameter.ActualName = "SizeOkay";
109
110      var conditionalBranch1 = new ConditionalBranch();
111      conditionalBranch1.Name = "Elite set has at least ρ elements";
112      conditionalBranch1.ConditionParameter.ActualName = "SizeOkay";
113
114      var selector1 = new RandomSelector();
115      selector1.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
116      selector1.CopySelected.Value = true;
117
118      var selector2 = new RandomSelector();
119      selector2.NumberOfSelectedSubScopesParameter.Value = new IntValue(0);
120
121      var ssp1 = new SubScopesProcessor();
122
123      var eo1 = new EmptyOperator();
124
125      var solutionsCreator = new SolutionsCreator();
126      solutionsCreator.ParallelParameter.Value = new BoolValue(false);
127      solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
128      solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
129      solutionsCreator.NumberOfSolutions = new IntValue(1);
130
131      var subScopesCounter2 = new SubScopesCounter();
132      subScopesCounter2.Name = "Count subscopes";
133      subScopesCounter2.ValueParameter.ActualName = "SolutionScopes";
134
135      var comparator2 = new Comparator();
136      comparator2.Name = "SolutionScopes == 2";
137      comparator2.Comparison.Value = ComparisonType.Equal;
138      comparator2.LeftSideParameter.ActualName = "SolutionScopes";
139      comparator2.RightSideParameter.Value = new IntValue(2);
140      comparator2.ResultParameter.ActualName = "PerformPR";
141
142      var conditionalBranch2 = new ConditionalBranch();
143      conditionalBranch2.Name = "Path relinking?";
144      conditionalBranch2.ConditionParameter.ActualName = "PerformPR";
145
146      var ssp2 = new SubScopesProcessor();
147
148      var eo2 = new EmptyOperator();
149
150      var placeholder1 = new Placeholder();
151      placeholder1.Name = "(LocalImprovement)";
152      placeholder1.OperatorParameter.ActualName = LocalImprovementParameter.Name;
153
154      var childrenCreator = new ChildrenCreator();
155      childrenCreator.ParentsPerChild = new IntValue(2);
156
157      var ssp3 = new SubScopesProcessor();
158
159      var placeholder2 = new Placeholder();
160      placeholder2.Name = "(PathRelinking)";
161      placeholder2.OperatorParameter.ActualName = PathRelinkingParameter.Name;
162
163      var placeholder3 = new Placeholder();
164      placeholder3.Name = "(Evaluator)";
165      placeholder3.OperatorParameter.ActualName = EvaluatorParameter.Name;
166
167      var subScopesRemover = new SubScopesRemover();
168      subScopesRemover.RemoveAllSubScopes = true;
169
170      var ssp4 = new SubScopesProcessor();
171
172      var placeholder4 = new Placeholder();
173      placeholder4.Name = "(LocalImprovement)";
174      placeholder4.OperatorParameter.ActualName = LocalImprovementParameter.Name;
175
176      var placeholder5 = new Placeholder();
177      placeholder5.Name = "(EliteSetMerger)";
178      placeholder5.OperatorParameter.ActualName = EliteSetMergerParameter.Name;
179
180      var counter = new IntCounter();
181      counter.Name = "Iterations++";
182      counter.ValueParameter.ActualName = "Iterations";
183      counter.Increment = new IntValue(1);
184
185      var analyzer1 = new Placeholder();
186      analyzer1.Name = "(Analyzer)";
187      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
188
189      var comparator3 = new Comparator();
190      comparator3.Name = "Iterations >= MaximumIterations";
191      comparator3.Comparison.Value = ComparisonType.GreaterOrEqual;
192      comparator3.LeftSideParameter.ActualName = "Iterations";
193      comparator3.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
194      comparator3.ResultParameter.ActualName = "TerminatedByIteration";
195
196      var conditionalBranch3 = new ConditionalBranch();
197      conditionalBranch3.Name = "Terminate by Iterations?";
198      conditionalBranch3.ConditionParameter.ActualName = "TerminatedByIteration";
199
200      OperatorGraph.InitialOperator = variableCreator1;
201      variableCreator1.Successor = resultsCollector;
202      resultsCollector.Successor = variableCreator2;
203      variableCreator2.Successor = subScopesCounter1;
204      subScopesCounter1.Successor = comparator1;
205      comparator1.Successor = conditionalBranch1;
206      conditionalBranch1.TrueBranch = selector1;
207      conditionalBranch1.FalseBranch = selector2;
208      conditionalBranch1.Successor = ssp1;
209      ssp1.Operators.Add(eo1);
210      ssp1.Operators.Add(solutionsCreator);
211      ssp1.Successor = placeholder5;
212      eo1.Successor = null;
213      solutionsCreator.Successor = subScopesCounter2;
214      subScopesCounter2.Successor = comparator2;
215      comparator2.Successor = conditionalBranch2;
216      conditionalBranch2.TrueBranch = ssp2;
217      conditionalBranch2.FalseBranch = null;
218      conditionalBranch2.Successor = ssp4;
219      ssp2.Operators.Add(eo2);
220      ssp2.Operators.Add(placeholder1);
221      ssp2.Successor = childrenCreator;
222      eo2.Successor = null;
223      placeholder1.Successor = null;
224      childrenCreator.Successor = ssp3;
225      ssp3.Operators.Add(placeholder2);
226      ssp3.Successor = null;
227      placeholder2.Successor = placeholder3;
228      placeholder3.Successor = subScopesRemover;
229      subScopesRemover.Successor = null;
230      ssp4.Operators.Add(placeholder4);
231      ssp4.Successor = null;
232      placeholder5.Successor = counter;
233      counter.Successor = analyzer1;
234      analyzer1.Successor = comparator3;
235      comparator3.Successor = conditionalBranch3;
236      conditionalBranch3.TrueBranch = null;
237      conditionalBranch3.FalseBranch = variableCreator2;
238      conditionalBranch3.Successor = null;
239    }
240
241    public override IDeepCloneable Clone(Cloner cloner) {
242      return new GRASPWithPathRelinkingMainLoop(this, cloner);
243    }
244
245    private void Parameterize() {
246      var operators = OperatorGraph.InitialOperator.Walk().ToArray();
247
248      foreach (var solutionsCreator in operators.OfType<SolutionsCreator>()) {
249        solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
250        solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
251      }
252    }
253
254    public event EventHandler ProblemChanged;
255    protected virtual void OnProblemChanged() {
256      Parameterize();
257      var handler = ProblemChanged;
258      if (handler != null) handler(this, EventArgs.Empty);
259    }
260  }
261}
Note: See TracBrowser for help on using the repository browser.