Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/GRASPWithPathRelinking.cs @ 7478

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

#1614: simplified GRASP+PR operator graph, replaced IMerger with an IPopulationReducer

File size: 14.2 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.Analysis;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms {
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("Algorithms")]
42  [StorableClass]
43  public sealed class GRASPWithPathRelinking : HeuristicOptimizationEngineAlgorithm {
44    #region Problem Properties
45    public override Type ProblemType {
46      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
47    }
48    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
49      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
50      set { base.Problem = value; }
51    }
52    #endregion
53
54    #region Parameter Properties
55    private IValueParameter<BoolValue> SetSeedRandomlyParameter {
56      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
57    }
58    private IValueParameter<IntValue> SeedParameter {
59      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
60    }
61    private IValueParameter<MultiAnalyzer> AnalyzerParameter {
62      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
63    }
64    public IValueParameter<IntValue> MaximumIterationsParameter {
65      get { return (IValueParameter<IntValue>)Parameters["MaximumIterations"]; }
66    }
67    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
68      get { return (IFixedValueParameter<IntValue>)Parameters["EliteSetSize"]; }
69    }
70    private IFixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
71      get { return (IFixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
72    }
73    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
74      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
75    }
76    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
77      get { return (IFixedValueParameter<IntValue>)Parameters["MinimumEliteSetSize"]; }
78    }
79    public ConstrainedValueParameter<ICrossover> PathRelinkingParameter {
80      get { return (ConstrainedValueParameter<ICrossover>)Parameters["PathRelinking"]; }
81    }
82    public ConstrainedValueParameter<IPopulationReducer> EliteSetReducerParameter {
83      get { return (ConstrainedValueParameter<IPopulationReducer>)Parameters["EliteSetReducer"]; }
84    }
85    #endregion
86
87    #region Properties
88    public BoolValue SetSeedRandomly {
89      get { return SetSeedRandomlyParameter.Value; }
90      set { SetSeedRandomlyParameter.Value = value; }
91    }
92    public IntValue Seed {
93      get { return SeedParameter.Value; }
94      set { SeedParameter.Value = value; }
95    }
96    public MultiAnalyzer Analyzer {
97      get { return AnalyzerParameter.Value; }
98      set { AnalyzerParameter.Value = value; }
99    }
100    public IntValue EliteSetSize {
101      get { return EliteSetSizeParameter.Value; }
102      set { EliteSetSizeParameter.Value.Value = value.Value; }
103    }
104    public IntValue LocalImprovementMaximumIterations {
105      get { return LocalImprovementMaximumIterationsParameter.Value; }
106      set { LocalImprovementMaximumIterationsParameter.Value.Value = value.Value; }
107    }
108
109    private RandomCreator RandomCreator {
110      get { return (RandomCreator)OperatorGraph.InitialOperator; }
111    }
112    private SolutionsCreator SolutionsCreator {
113      get { return (SolutionsCreator)RandomCreator.Successor; }
114    }
115    private GRASPWithPathRelinkingMainLoop MainLoop {
116      get { return SolutionsCreator.Successor as GRASPWithPathRelinkingMainLoop; }
117    }
118    #endregion
119
120    [Storable]
121    private BestAverageWorstQualityAnalyzer analyzer;
122
123    [StorableConstructor]
124    private GRASPWithPathRelinking(bool deserializing) : base(deserializing) { }
125    private GRASPWithPathRelinking(GRASPWithPathRelinking original, Cloner cloner)
126      : base(original, cloner) {
127      analyzer = cloner.Clone(original.analyzer);
128      RegisterEventHandlers();
129    }
130    public GRASPWithPathRelinking()
131      : base() {
132      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
133      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator."));
134      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer()));
135      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations that the algorithm should run.", new IntValue(1000)));
136      Parameters.Add(new FixedValueParameter<IntValue>("EliteSetSize", "The elite set stores the best found solutions.", new IntValue(10)));
137      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations performed by the local improvement operator.", new IntValue(1000)));
138      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "Performs a local search on the solution."));
139      Parameters.Add(new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimum amount of elites for performing path relinking.", new IntValue(2)));
140      Parameters.Add(new ConstrainedValueParameter<ICrossover>("PathRelinking", "The operator that performs the path relinking."));
141      Parameters.Add(new ConstrainedValueParameter<IPopulationReducer>("EliteSetReducer", "The operator that reduces the old elite set and the new solution(s) to a new elite set."));
142
143      analyzer = new BestAverageWorstQualityAnalyzer();
144      Analyzer.Operators.Add(analyzer);
145
146      var randomCreator = new RandomCreator();
147      OperatorGraph.InitialOperator = randomCreator;
148
149      randomCreator.RandomParameter.ActualName = "Random";
150      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
151      randomCreator.SeedParameter.Value = null;
152      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
153      randomCreator.SetSeedRandomlyParameter.Value = null;
154
155      var solutionsCreator = new SolutionsCreator();
156      solutionsCreator.NumberOfSolutionsParameter.ActualName = MinimumEliteSetSizeParameter.Name;
157      solutionsCreator.ParallelParameter.Value = new BoolValue(true);
158      randomCreator.Successor = solutionsCreator;
159
160      var mainLoop = new GRASPWithPathRelinkingMainLoop();
161      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
162      mainLoop.EliteSetReducerParameter.ActualName = EliteSetReducerParameter.Name;
163      mainLoop.EliteSetSizeParameter.ActualName = EliteSetSizeParameter.Name;
164      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
165      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
166      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
167      mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
168      mainLoop.ResultsParameter.ActualName = "Results";
169      solutionsCreator.Successor = mainLoop;
170
171      InitializeOperators();
172      RegisterEventHandlers();
173    }
174
175    public override IDeepCloneable Clone(Cloner cloner) {
176      return new GRASPWithPathRelinking(this, cloner);
177    }
178
179    public override void Prepare() {
180      if (Problem != null) base.Prepare();
181    }
182
183    #region Events
184    protected override void OnProblemChanged() {
185      InitializeOperators();
186      base.OnProblemChanged();
187    }
188
189    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
190      Parameterize();
191      base.Problem_SolutionCreatorChanged(sender, e);
192    }
193    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
194      Parameterize();
195      base.Problem_EvaluatorChanged(sender, e);
196    }
197    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
198      InitializeOperators();
199      base.Problem_OperatorsChanged(sender, e);
200    }
201
202    private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
203      Parameterize();
204    }
205    #endregion
206
207    #region Helpers
208    [StorableHook(HookType.AfterDeserialization)]
209    private void AfterDeserialization() {
210      if (Problem != null) {
211      }
212      RegisterEventHandlers();
213    }
214
215    private void RegisterEventHandlers() {
216      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
217    }
218
219    private void InitializeOperators() {
220      Analyzer.Operators.Clear();
221      if (Problem != null) {
222        foreach (IAnalyzer a in Problem.Operators.OfType<IAnalyzer>()) {
223          foreach (var param in a.Parameters.OfType<IScopeTreeLookupParameter>())
224            param.Depth = 1;
225          Analyzer.Operators.Add(a);
226          Analyzer.Operators.SetItemCheckedState(a, a.EnabledByDefault);
227        }
228        InitializeFromInstallation(LocalImprovementParameter, x => x.ProblemType.IsAssignableFrom(Problem.GetType()));
229        InitializeFromProblem(PathRelinkingParameter);
230        InitializeFromProblem(EliteSetReducerParameter);
231      } else {
232        LocalImprovementParameter.ValidValues.Clear();
233        PathRelinkingParameter.ValidValues.Clear();
234        EliteSetReducerParameter.ValidValues.Clear();
235      }
236      Analyzer.Operators.Add(analyzer);
237
238      Parameterize();
239    }
240
241    private void Parameterize() {
242      if (Problem != null) {
243        SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
244        SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
245
246        MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
247        MainLoop.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
248
249        analyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
250
251        if (LocalImprovementParameter.Value != null)
252          LocalImprovementParameter.Value.Problem = Problem;
253      }
254      foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
255        localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
256        localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
257        localImprovement.ResultsParameter.ActualName = "Results";
258      }
259      foreach (var reducer in EliteSetReducerParameter.ValidValues) {
260        reducer.MinimumPopulationSizeParameter.ActualName = MinimumEliteSetSizeParameter.Name;
261        reducer.MaximumPopulationSizeParameter.ActualName = EliteSetSizeParameter.Name;
262      }
263    }
264
265    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
266      InitializeFromProblem<T>(parameter, x => true);
267    }
268    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
269      if (parameter == null) throw new ArgumentNullException("parameter");
270      if (condition == null) throw new ArgumentNullException("condition");
271      string oldName = String.Empty;
272      if (parameter.Value != null) oldName = parameter.Value.Name;
273      parameter.ValidValues.Clear();
274      foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
275        parameter.ValidValues.Add(item);
276      }
277      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
278      if (newItem != null) parameter.Value = newItem;
279    }
280    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
281      InitializeFromInstallation<T>(parameter, x => true);
282    }
283    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
284      if (parameter == null) throw new ArgumentNullException("parameter");
285      if (condition == null) throw new ArgumentNullException("condition");
286      string oldName = String.Empty;
287      if (parameter.Value != null) oldName = parameter.Value.Name;
288      parameter.ValidValues.Clear();
289      foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
290        parameter.ValidValues.Add(item);
291      }
292      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
293      if (newItem != null) parameter.Value = newItem;
294    }
295    #endregion
296  }
297}
Note: See TracBrowser for help on using the repository browser.