source: branches/1614_GeneralizedQAP/HeuristicLab.Algorithms.GRASP/3.3/GRASPWithPathRelinkingMainLoop.cs @ 15713

Last change on this file since 15713 was 15507, checked in by abeham, 5 years ago

#1614:

  • fixed some bugs introduced in last commit (project file, tests)
  • fixed ApproximateLocalSearch due to change in move evaluator that outputs an absolute quality of the move and not a delta
  • added evaluated solution counting to approximate local search
  • GRASP+PR: restructured main loop and combined iteration initialization with variable creator outside
File size: 10.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2017 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.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Selection;
34
35namespace HeuristicLab.Algorithms.GRASP {
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<IntValue> IterationsParameter {
40      get { return (IValueLookupParameter<IntValue>)Parameters["Iterations"]; }
41    }
42    public IValueLookupParameter<IOperator> SolutionCreatorParameter {
43      get { return (IValueLookupParameter<IOperator>)Parameters["SolutionCreator"]; }
44    }
45    public IValueLookupParameter<IOperator> EvaluatorParameter {
46      get { return (IValueLookupParameter<IOperator>)Parameters["Evaluator"]; }
47    }
48    public IValueLookupParameter<IntValue> EvaluatedSolutionsParameter {
49      get { return (IValueLookupParameter<IntValue>)Parameters["EvaluatedSolutions"]; }
50    }
51    public IValueLookupParameter<IntValue> MaximumIterationsParameter {
52      get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
53    }
54    public IValueLookupParameter<ResultCollection> ResultsParameter {
55      get { return (IValueLookupParameter<ResultCollection>)Parameters["Results"]; }
56    }
57    public IValueLookupParameter<IntValue> EliteSetSizeParameter {
58      get { return (IValueLookupParameter<IntValue>)Parameters["EliteSetSize"]; }
59    }
60    public IValueLookupParameter<IOperator> LocalImprovementParameter {
61      get { return (IValueLookupParameter<IOperator>)Parameters["LocalImprovement"]; }
62    }
63    public IValueLookupParameter<IOperator> PathRelinkingParameter {
64      get { return (IValueLookupParameter<IOperator>)Parameters["PathRelinking"]; }
65    }
66    public IValueLookupParameter<IOperator> EliteSetReducerParameter {
67      get { return (IValueLookupParameter<IOperator>)Parameters["EliteSetReducer"]; }
68    }
69    public IValueLookupParameter<IOperator> AnalyzerParameter {
70      get { return (IValueLookupParameter<IOperator>)Parameters["Analyzer"]; }
71    }
72
73    [StorableConstructor]
74    protected GRASPWithPathRelinkingMainLoop(bool deserializing) : base(deserializing) { }
75    protected GRASPWithPathRelinkingMainLoop(GRASPWithPathRelinkingMainLoop original, Cloner cloner)
76      : base(original, cloner) { }
77    public GRASPWithPathRelinkingMainLoop()
78      : base() {
79      Parameters.Add(new ValueLookupParameter<IntValue>("Iterations", "The algorithm's current iteration."));
80      Parameters.Add(new ValueLookupParameter<IOperator>("SolutionCreator", "The solution creation procedure which ideally should be a greedy initialization heuristic."));
81      Parameters.Add(new ValueLookupParameter<IOperator>("Evaluator", "The evaluator which calculates the fitness of a solutions."));
82      Parameters.Add(new ValueLookupParameter<IntValue>("EvaluatedSolutions", "The number of evaluated solutions."));
83      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The number of maximum iterations that should be performed."));
84      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "Specifies where the results are stored."));
85      Parameters.Add(new ValueLookupParameter<IntValue>("EliteSetSize", "The size of the elite set."));
86      Parameters.Add(new ValueLookupParameter<IOperator>("LocalImprovement", "The operator which performs the local improvement."));
87      Parameters.Add(new ValueLookupParameter<IOperator>("PathRelinking", "The operator which performs the path relinking."));
88      Parameters.Add(new ValueLookupParameter<IOperator>("EliteSetReducer", "The operator that reduces the existing elite set and the new solution to a new elite set."));
89      Parameters.Add(new ValueLookupParameter<IOperator>("Analyzer", "The analyzer that is to be applied."));
90
91      var analyzer1 = new Placeholder() { Name = "(Analyzer)" };
92      analyzer1.OperatorParameter.ActualName = AnalyzerParameter.Name;
93
94      var selector1 = new RandomSelector();
95      selector1.NumberOfSelectedSubScopesParameter.Value = new IntValue(1);
96      selector1.CopySelected.Value = true;
97
98      var ssp1 = new SubScopesProcessor();
99
100      var eo1 = new EmptyOperator();
101
102      var solutionsCreator = new SolutionsCreator();
103      solutionsCreator.ParallelParameter.Value = new BoolValue(false);
104      solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
105      solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
106      solutionsCreator.NumberOfSolutions = new IntValue(1);
107
108      var ssp2 = new SubScopesProcessor();
109
110      var eo2 = new EmptyOperator();
111
112      var placeholder1 = new Placeholder() { Name = "(LocalImprovement)" };
113      placeholder1.OperatorParameter.ActualName = LocalImprovementParameter.Name;
114
115      var childrenCreator = new ChildrenCreator();
116      childrenCreator.ParentsPerChild = new IntValue(2);
117
118      var ssp3 = new SubScopesProcessor();
119
120      var placeholder2 = new Placeholder() { Name = "(PathRelinking)" };
121      placeholder2.OperatorParameter.ActualName = PathRelinkingParameter.Name;
122
123      var placeholder3 = new Placeholder() { Name = "(Evaluator)" };
124      placeholder3.OperatorParameter.ActualName = EvaluatorParameter.Name;
125
126      var subScopesRemover = new SubScopesRemover();
127      subScopesRemover.RemoveAllSubScopes = true;
128
129      var ssp4 = new SubScopesProcessor();
130
131      var placeholder4 = new Placeholder();
132      placeholder4.Name = "(LocalImprovement)";
133      placeholder4.OperatorParameter.ActualName = LocalImprovementParameter.Name;
134
135      var placeholder5 = new Placeholder() { Name = "(EliteSetReplacer)" };
136      placeholder5.OperatorParameter.ActualName = EliteSetReducerParameter.Name;
137
138      var counter = new IntCounter() { Name = "Iterations++" };
139      counter.ValueParameter.ActualName = IterationsParameter.Name;
140      counter.Increment = new IntValue(1);
141
142      var analyzer2 = new Placeholder() { Name = "(Analyzer)" };
143      analyzer2.OperatorParameter.ActualName = AnalyzerParameter.Name;
144
145      var comparator3 = new Comparator() { Name = "Iterations >= MaximumIterations" };
146      comparator3.Comparison.Value = ComparisonType.GreaterOrEqual;
147      comparator3.LeftSideParameter.ActualName = IterationsParameter.Name;
148      comparator3.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
149      comparator3.ResultParameter.ActualName = "TerminatedByIteration";
150
151      var conditionalBranch3 = new ConditionalBranch() { Name = "Terminate by Iterations?" };
152      conditionalBranch3.ConditionParameter.ActualName = "TerminatedByIteration";
153
154      OperatorGraph.InitialOperator = analyzer1;
155      analyzer1.Successor = selector1;
156      selector1.Successor = ssp1;
157      ssp1.Operators.Add(eo1);
158      ssp1.Operators.Add(solutionsCreator);
159      ssp1.Successor = placeholder5;
160      eo1.Successor = null;
161      solutionsCreator.Successor = ssp2;
162      ssp2.Operators.Add(eo2);
163      ssp2.Operators.Add(placeholder1);
164      ssp2.Successor = childrenCreator;
165      eo2.Successor = null;
166      placeholder1.Successor = null;
167      childrenCreator.Successor = ssp3;
168      ssp3.Operators.Add(placeholder2);
169      ssp3.Successor = null;
170      placeholder2.Successor = placeholder3;
171      placeholder3.Successor = subScopesRemover;
172      subScopesRemover.Successor = placeholder4;
173      placeholder4.Successor = null;
174      placeholder5.Successor = counter;
175      counter.Successor = analyzer2;
176      analyzer2.Successor = comparator3;
177      comparator3.Successor = conditionalBranch3;
178      conditionalBranch3.TrueBranch = null;
179      conditionalBranch3.FalseBranch = selector1;
180      conditionalBranch3.Successor = null;
181    }
182
183    public override IDeepCloneable Clone(Cloner cloner) {
184      return new GRASPWithPathRelinkingMainLoop(this, cloner);
185    }
186
187    private void Parameterize() {
188      var operators = Walk(OperatorGraph).ToArray();
189
190      foreach (var solutionsCreator in operators.OfType<SolutionsCreator>()) {
191        solutionsCreator.SolutionCreatorParameter.ActualName = SolutionCreatorParameter.Name;
192        solutionsCreator.EvaluatorParameter.ActualName = EvaluatorParameter.Name;
193      }
194    }
195
196    /// <summary>
197    /// Walks an operator graph in that it jumps from one operator to all its operator parameters and yields each operator it touches.
198    /// Cycles are detected and not walked twice.
199    /// </summary>
200    /// <param name="graph">The operator graph that should be walked.</param>
201    /// <returns>An enumeration of all the operators that could be found.</returns>
202    private IEnumerable<IOperator> Walk(OperatorGraph graph) {
203      var open = new Stack<IOperator>();
204      var visited = new HashSet<IOperator>();
205      open.Push(graph.InitialOperator);
206
207      while (open.Any()) {
208        IOperator current = open.Pop();
209        if (visited.Contains(current)) continue;
210        visited.Add(current);
211        yield return current;
212
213        foreach (var parameter in current.Parameters.OfType<IValueParameter>()) {
214          if (typeof(IOperator).IsAssignableFrom(parameter.DataType)) {
215            if (parameter.Value != null)
216              open.Push((IOperator)parameter.Value);
217          }
218        }
219        var algOp = current as AlgorithmOperator;
220        if (algOp != null && algOp.OperatorGraph.InitialOperator != null) {
221          open.Push(algOp.OperatorGraph.InitialOperator);
222        }
223      }
224    }
225
226    public event EventHandler ProblemChanged;
227    protected virtual void OnProblemChanged() {
228      Parameterize();
229      var handler = ProblemChanged;
230      if (handler != null) handler(this, EventArgs.Empty);
231    }
232  }
233}
Note: See TracBrowser for help on using the repository browser.