Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 7383 was 7363, checked in by abeham, 13 years ago

#1614

  • worked on GQAP
File size: 11.4 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.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.PluginInfrastructure;
32using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
33using HeuristicLab.Random;
34
35namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms {
36  /// <summary>
37  /// 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.
38  /// </summary>
39  [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.")]
40  [Creatable("Algorithms")]
41  [StorableClass]
42  public sealed class GRASPWithPathRelinking : HeuristicOptimizationEngineAlgorithm {
43    #region Problem Properties
44    public override Type ProblemType {
45      get { return typeof(ISingleObjectiveHeuristicOptimizationProblem); }
46    }
47    public new ISingleObjectiveHeuristicOptimizationProblem Problem {
48      get { return (ISingleObjectiveHeuristicOptimizationProblem)base.Problem; }
49      set { base.Problem = value; }
50    }
51    #endregion
52
53    #region Parameter Properties
54    private IValueParameter<BoolValue> SetSeedRandomlyParameter {
55      get { return (IValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
56    }
57    private IValueParameter<IntValue> SeedParameter {
58      get { return (IValueParameter<IntValue>)Parameters["Seed"]; }
59    }
60    private IValueParameter<MultiAnalyzer> AnalyzerParameter {
61      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
62    }
63    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
64      get { return (IFixedValueParameter<IntValue>)Parameters["EliteSetSize"]; }
65    }
66    private IFixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
67      get { return (IFixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
68    }
69    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
70      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
71    }
72    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
73      get { return (IFixedValueParameter<IntValue>)Parameters["MinimumEliteSetSize"]; }
74    }
75    public ConstrainedValueParameter<ICrossover> PathRelinkingParameter {
76      get { return (ConstrainedValueParameter<ICrossover>)Parameters["PathRelinking"]; }
77    }
78    public ConstrainedValueParameter<IMerger> EliteSetReplacerParameter {
79      get { return (ConstrainedValueParameter<IMerger>)Parameters["EliteSetMerger"]; }
80    }
81    #endregion
82
83    #region Properties
84    public BoolValue SetSeedRandomly {
85      get { return SetSeedRandomlyParameter.Value; }
86      set { SetSeedRandomlyParameter.Value = value; }
87    }
88    public IntValue Seed {
89      get { return SeedParameter.Value; }
90      set { SeedParameter.Value = value; }
91    }
92    public MultiAnalyzer Analyzer {
93      get { return AnalyzerParameter.Value; }
94      set { AnalyzerParameter.Value = value; }
95    }
96    public IntValue EliteSetSize {
97      get { return EliteSetSizeParameter.Value; }
98      set { EliteSetSizeParameter.Value.Value = value.Value; }
99    }
100    public IntValue LocalImprovementMaximumIterations {
101      get { return LocalImprovementMaximumIterationsParameter.Value; }
102      set { LocalImprovementMaximumIterationsParameter.Value.Value = value.Value; }
103    }
104
105    private RandomCreator RandomCreator {
106      get { return (RandomCreator)OperatorGraph.InitialOperator; }
107    }
108    #endregion
109
110    [StorableConstructor]
111    private GRASPWithPathRelinking(bool deserializing) : base(deserializing) { }
112    private GRASPWithPathRelinking(GRASPWithPathRelinking original, Cloner cloner)
113      : base(original, cloner) {
114      RegisterEventHandlers();
115    }
116    public GRASPWithPathRelinking()
117      : base() {
118      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
119      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator."));
120      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer()));
121      Parameters.Add(new FixedValueParameter<IntValue>("EliteSetSize", "The elite set stores the best found solutions.", new IntValue(10)));
122      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations performed by the local improvement operator.", new IntValue(100)));
123      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "Performs a local search on the solution."));
124      Parameters.Add(new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimum amount of elites for performing path relinking.", new IntValue(1)));
125      Parameters.Add(new ConstrainedValueParameter<ICrossover>("PathRelinking", "The operator that performs the path relinking."));
126      Parameters.Add(new ConstrainedValueParameter<IMerger>("EliteSetMerger", "The operator that merges new solutions into the elite set."));
127
128      RandomCreator randomCreator = new RandomCreator();
129      OperatorGraph.InitialOperator = randomCreator;
130
131      randomCreator.RandomParameter.ActualName = "Random";
132      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
133      randomCreator.SeedParameter.Value = null;
134      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
135      randomCreator.SetSeedRandomlyParameter.Value = null;
136
137      var mainLoop = new GRASPWithPathRelinkingMainLoop();
138      randomCreator.Successor = mainLoop;
139
140      InitializeOperators();
141      RegisterEventHandlers();
142    }
143
144    public override IDeepCloneable Clone(Cloner cloner) {
145      return new GRASPWithPathRelinking(this, cloner);
146    }
147
148    public override void Prepare() {
149      if (Problem != null) base.Prepare();
150    }
151
152    #region Events
153    protected override void OnProblemChanged() {
154      InitializeOperators();
155      base.OnProblemChanged();
156    }
157
158    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
159      Parameterize();
160      base.Problem_SolutionCreatorChanged(sender, e);
161    }
162    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
163      Parameterize();
164      base.Problem_EvaluatorChanged(sender, e);
165    }
166    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
167      InitializeOperators();
168      base.Problem_OperatorsChanged(sender, e);
169    }
170    #endregion
171
172    #region Helpers
173    [StorableHook(HookType.AfterDeserialization)]
174    private void AfterDeserialization() {
175      if (Problem != null) {
176      }
177      RegisterEventHandlers();
178    }
179
180    private void RegisterEventHandlers() {
181
182    }
183
184    private void InitializeOperators() {
185      Analyzer.Operators.Clear();
186      if (Problem != null) {
187        foreach (IAnalyzer analyzer in Problem.Operators.OfType<IAnalyzer>()) {
188          foreach (var param in analyzer.Parameters.OfType<IScopeTreeLookupParameter>())
189            param.Depth = 1;
190          Analyzer.Operators.Add(analyzer);
191        }
192        InitializeFromInstallation(LocalImprovementParameter, x => x.ProblemType.IsAssignableFrom(Problem.GetType()));
193        InitializeFromProblem(PathRelinkingParameter);
194        InitializeFromProblem(EliteSetReplacerParameter);
195      } else {
196        LocalImprovementParameter.ValidValues.Clear();
197        PathRelinkingParameter.ValidValues.Clear();
198        EliteSetReplacerParameter.ValidValues.Clear();
199      }
200
201      Parameterize();
202    }
203
204    private void Parameterize() {
205      foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
206        localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
207        localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
208        localImprovement.ResultsParameter.ActualName = "Results";
209        if (Problem != null && localImprovement.ProblemType.IsAssignableFrom(Problem.GetType()))
210          localImprovement.Problem = Problem;
211      }
212    }
213
214    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
215      InitializeFromProblem(parameter, x => true);
216    }
217    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
218      if (parameter == null) throw new ArgumentNullException("parameter");
219      if (condition == null) throw new ArgumentNullException("condition");
220      string oldName = String.Empty;
221      if (parameter.Value != null) oldName = parameter.Value.Name;
222      parameter.ValidValues.Clear();
223      foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
224        parameter.ValidValues.Add(item);
225      }
226      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
227      if (newItem != null) parameter.Value = newItem;
228    }
229    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
230      InitializeFromInstallation(parameter, x => true);
231    }
232    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
233      if (parameter == null) throw new ArgumentNullException("parameter");
234      if (condition == null) throw new ArgumentNullException("condition");
235      string oldName = String.Empty;
236      if (parameter.Value != null) oldName = parameter.Value.Name;
237      parameter.ValidValues.Clear();
238      foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
239        parameter.ValidValues.Add(item);
240      }
241      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
242      if (newItem != null) parameter.Value = newItem;
243    }
244    #endregion
245  }
246}
Note: See TracBrowser for help on using the repository browser.