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

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

#1614:

  • Implementing basic algorithm according to paper (rechecking all operators)
  • Checking implementation with paper
  • Improved speed of move generator
  • Improved speed of randomized solution creator
File size: 15.9 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.Linq;
24using HeuristicLab.Analysis;
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.PluginInfrastructure;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Algorithms.GRASP {
37  /// <summary>
38  /// The algorithm combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking and is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.
39  /// </summary>
40  [Item("GRASP+PR", "The algorithm combines the Greedy Randomized Adaptive Search Procedure (GRASP) with Path Relinking and is described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with path-relinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527-565.")]
41  [Creatable(CreatableAttribute.Categories.PopulationBasedAlgorithms)]
42  [StorableClass]
43  public sealed class GRASPWithPathRelinking : HeuristicOptimizationEngineAlgorithm, IStorableContent {
44    public string Filename { get; set; }
45
46    #region Problem Properties
47    public override Type ProblemType {
48      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
49    }
50    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
51      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
52      set { base.Problem = value; }
53    }
54    #endregion
55
56    #region Parameter Properties
57    private IValueParameter<BoolValue> SetSeedRandomlyParameter {
58      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
59    }
60    private IValueParameter<IntValue> SeedParameter {
61      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
62    }
63    private IValueParameter<MultiAnalyzer> AnalyzerParameter {
64      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
65    }
66    public IValueParameter<IntValue> MaximumIterationsParameter {
67      get { return (IValueParameter<IntValue>)Parameters["MaximumIterations"]; }
68    }
69    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
70      get { return (IFixedValueParameter<IntValue>)Parameters["EliteSetSize"]; }
71    }
72    private IFixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
73      get { return (IFixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
74    }
75    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
76      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
77    }
78    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
79      get { return (IFixedValueParameter<IntValue>)Parameters["MinimumEliteSetSize"]; }
80    }
81    public ConstrainedValueParameter<ICrossover> PathRelinkingParameter {
82      get { return (ConstrainedValueParameter<ICrossover>)Parameters["PathRelinking"]; }
83    }
84    public ConstrainedValueParameter<IPopulationReducer> EliteSetReducerParameter {
85      get { return (ConstrainedValueParameter<IPopulationReducer>)Parameters["EliteSetReducer"]; }
86    }
87    #endregion
88
89    #region Properties
90    public BoolValue SetSeedRandomly {
91      get { return SetSeedRandomlyParameter.Value; }
92      set { SetSeedRandomlyParameter.Value = value; }
93    }
94    public IntValue Seed {
95      get { return SeedParameter.Value; }
96      set { SeedParameter.Value = value; }
97    }
98    public MultiAnalyzer Analyzer {
99      get { return AnalyzerParameter.Value; }
100      set { AnalyzerParameter.Value = value; }
101    }
102    public IntValue EliteSetSize {
103      get { return EliteSetSizeParameter.Value; }
104      set { EliteSetSizeParameter.Value.Value = value.Value; }
105    }
106    public IntValue LocalImprovementMaximumIterations {
107      get { return LocalImprovementMaximumIterationsParameter.Value; }
108      set { LocalImprovementMaximumIterationsParameter.Value.Value = value.Value; }
109    }
110
111    private RandomCreator RandomCreator {
112      get { return (RandomCreator)OperatorGraph.InitialOperator; }
113    }
114    private VariableCreator VariableCreator {
115      get { return (VariableCreator)RandomCreator.Successor; }
116    }
117    private SolutionsCreator SolutionsCreator {
118      get { return (SolutionsCreator)VariableCreator.Successor; }
119    }
120    private SubScopesCounter SubScopesCounter {
121      get { return (SubScopesCounter)SolutionsCreator.Successor; }
122    }
123    private ResultsCollector ResultsCollector {
124      get { return (ResultsCollector)SubScopesCounter.Successor; }
125    }
126    private GRASPWithPathRelinkingMainLoop MainLoop {
127      get { return (GRASPWithPathRelinkingMainLoop)ResultsCollector.Successor; }
128    }
129    #endregion
130
131    [Storable]
132    private BestAverageWorstQualityAnalyzer analyzer;
133
134    [StorableConstructor]
135    private GRASPWithPathRelinking(bool deserializing) : base(deserializing) { }
136    private GRASPWithPathRelinking(GRASPWithPathRelinking original, Cloner cloner)
137      : base(original, cloner) {
138      analyzer = cloner.Clone(original.analyzer);
139      RegisterEventHandlers();
140    }
141    public GRASPWithPathRelinking()
142      : base() {
143      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
144      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator."));
145      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer()));
146      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations that the algorithm should run.", new IntValue(1000)));
147      Parameters.Add(new FixedValueParameter<IntValue>("EliteSetSize", "The elite set stores the best found solutions.", new IntValue(10)));
148      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations performed by the local improvement operator.", new IntValue(1000)));
149      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "Performs a local search on the solution."));
150      Parameters.Add(new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimum amount of elites for performing path relinking.", new IntValue(2)));
151      Parameters.Add(new ConstrainedValueParameter<ICrossover>("PathRelinking", "The operator that performs the path relinking."));
152      Parameters.Add(new ConstrainedValueParameter<IPopulationReducer>("EliteSetReducer", "The operator that reduces the old elite set and the new solution(s) to a new elite set."));
153
154      analyzer = new BestAverageWorstQualityAnalyzer();
155      Analyzer.Operators.Add(analyzer);
156
157      var randomCreator = new RandomCreator();
158      OperatorGraph.InitialOperator = randomCreator;
159
160      randomCreator.RandomParameter.ActualName = "Random";
161      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
162      randomCreator.SeedParameter.Value = null;
163      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
164      randomCreator.SetSeedRandomlyParameter.Value = null;
165     
166      var variableCreator = new VariableCreator();
167      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
168      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
169      randomCreator.Successor = variableCreator;
170     
171      var solutionsCreator = new SolutionsCreator();
172      solutionsCreator.NumberOfSolutionsParameter.ActualName = MinimumEliteSetSizeParameter.Name;
173      solutionsCreator.ParallelParameter.Value = new BoolValue(true);
174      variableCreator.Successor = solutionsCreator;
175
176      var subscopesCounter = new SubScopesCounter();
177      subscopesCounter.Name = "EvaluatedSolutions++";
178      subscopesCounter.AccumulateParameter.Value.Value = true;
179      subscopesCounter.ValueParameter.ActualName = "EvaluatedSolutions";
180      solutionsCreator.Successor = subscopesCounter;
181
182      var resultsCollector = new ResultsCollector();
183      resultsCollector.CopyValue.Value = false;
184      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "Counter for the number of times the evaluation function is called."));
185      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The algorithm's current iteration"));
186      subscopesCounter.Successor = resultsCollector;
187
188      var mainLoop = new GRASPWithPathRelinkingMainLoop();
189      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
190      mainLoop.EliteSetReducerParameter.ActualName = EliteSetReducerParameter.Name;
191      mainLoop.EliteSetSizeParameter.ActualName = EliteSetSizeParameter.Name;
192      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
193      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
194      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
195      mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
196      mainLoop.ResultsParameter.ActualName = "Results";
197      resultsCollector.Successor = mainLoop;
198
199      InitializeOperators();
200      RegisterEventHandlers();
201    }
202
203    public override IDeepCloneable Clone(Cloner cloner) {
204      return new GRASPWithPathRelinking(this, cloner);
205    }
206
207    public override void Prepare() {
208      if (Problem != null) base.Prepare();
209    }
210
211    #region Events
212    protected override void OnProblemChanged() {
213      InitializeOperators();
214      base.OnProblemChanged();
215    }
216
217    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
218      Parameterize();
219      base.Problem_SolutionCreatorChanged(sender, e);
220    }
221    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
222      Parameterize();
223      base.Problem_EvaluatorChanged(sender, e);
224    }
225    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
226      InitializeOperators();
227      base.Problem_OperatorsChanged(sender, e);
228    }
229
230    private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
231      Parameterize();
232    }
233    #endregion
234
235    #region Helpers
236    [StorableHook(HookType.AfterDeserialization)]
237    private void AfterDeserialization() {
238      if (Problem != null) {
239      }
240      RegisterEventHandlers();
241    }
242
243    private void RegisterEventHandlers() {
244      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
245    }
246
247    private void InitializeOperators() {
248      Analyzer.Operators.Clear();
249      if (Problem != null) {
250        foreach (IAnalyzer a in Problem.Operators.OfType<IAnalyzer>()) {
251          foreach (var param in a.Parameters.OfType<IScopeTreeLookupParameter>())
252            param.Depth = 1;
253          Analyzer.Operators.Add(a);
254          Analyzer.Operators.SetItemCheckedState(a, a.EnabledByDefault);
255        }
256        InitializeFromInstallation(LocalImprovementParameter, x => x is ILocalImprovementAlgorithmOperator
257          && ((ILocalImprovementAlgorithmOperator)x).ProblemType.IsInstanceOfType(Problem));
258        InitializeFromProblem(PathRelinkingParameter);
259        InitializeFromProblem(EliteSetReducerParameter);
260      } else {
261        LocalImprovementParameter.ValidValues.Clear();
262        PathRelinkingParameter.ValidValues.Clear();
263        EliteSetReducerParameter.ValidValues.Clear();
264      }
265      Analyzer.Operators.Add(analyzer);
266
267      Parameterize();
268    }
269
270    private void Parameterize() {
271      if (Problem != null) {
272        SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
273        SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
274
275        MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
276        MainLoop.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
277
278        analyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
279
280        if (LocalImprovementParameter.Value != null) {
281          if (LocalImprovementParameter.Value is ILocalImprovementAlgorithmOperator)
282            ((ILocalImprovementAlgorithmOperator)LocalImprovementParameter.Value).Problem = Problem;
283        }
284      }
285      foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
286        localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
287        localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
288        localImprovement.ResultsParameter.ActualName = "Results";
289      }
290      foreach (var reducer in EliteSetReducerParameter.ValidValues) {
291        reducer.MinimumPopulationSizeParameter.ActualName = MinimumEliteSetSizeParameter.Name;
292        reducer.MaximumPopulationSizeParameter.ActualName = EliteSetSizeParameter.Name;
293      }
294    }
295
296    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
297      InitializeFromProblem<T>(parameter, x => true);
298    }
299    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
300      if (parameter == null) throw new ArgumentNullException("parameter");
301      if (condition == null) throw new ArgumentNullException("condition");
302      string oldName = String.Empty;
303      if (parameter.Value != null) oldName = parameter.Value.Name;
304      parameter.ValidValues.Clear();
305      foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
306        parameter.ValidValues.Add(item);
307      }
308      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
309      if (newItem != null) parameter.Value = newItem;
310    }
311    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
312      InitializeFromInstallation<T>(parameter, x => true);
313    }
314    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
315      if (parameter == null) throw new ArgumentNullException("parameter");
316      if (condition == null) throw new ArgumentNullException("condition");
317      string oldName = String.Empty;
318      if (parameter.Value != null) oldName = parameter.Value.Name;
319      parameter.ValidValues.Clear();
320      foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
321        parameter.ValidValues.Add(item);
322      }
323      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
324      if (newItem != null) parameter.Value = newItem;
325    }
326    #endregion
327  }
328}
Note: See TracBrowser for help on using the repository browser.