Free cookie consent management tool by TermsFeed Policy Generator

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

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

#1614

  • Add BestKnownSolutions parameter
  • Assignment view
    • Clicking on an equipment highlights all related equipments
    • Clicking on a location highlights other locations that contain equipment to which relations exist
    • Showing installation costs when nothing is selected
  • Analyzers were present double times
  • Fixed GRASP to check EnabledByDefault
File size: 13.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    public IValueParameter<IntValue> MaximumIterationsParameter {
64      get { return (IValueParameter<IntValue>)Parameters["MaximumIterations"]; }
65    }
66    private IFixedValueParameter<IntValue> EliteSetSizeParameter {
67      get { return (IFixedValueParameter<IntValue>)Parameters["EliteSetSize"]; }
68    }
69    private IFixedValueParameter<IntValue> LocalImprovementMaximumIterationsParameter {
70      get { return (IFixedValueParameter<IntValue>)Parameters["LocalImprovementMaximumIterations"]; }
71    }
72    private ConstrainedValueParameter<ILocalImprovementOperator> LocalImprovementParameter {
73      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["LocalImprovement"]; }
74    }
75    public IFixedValueParameter<IntValue> MinimumEliteSetSizeParameter {
76      get { return (IFixedValueParameter<IntValue>)Parameters["MinimumEliteSetSize"]; }
77    }
78    public ConstrainedValueParameter<ICrossover> PathRelinkingParameter {
79      get { return (ConstrainedValueParameter<ICrossover>)Parameters["PathRelinking"]; }
80    }
81    public ConstrainedValueParameter<IMerger> EliteSetMergerParameter {
82      get { return (ConstrainedValueParameter<IMerger>)Parameters["EliteSetMerger"]; }
83    }
84    #endregion
85
86    #region Properties
87    public BoolValue SetSeedRandomly {
88      get { return SetSeedRandomlyParameter.Value; }
89      set { SetSeedRandomlyParameter.Value = value; }
90    }
91    public IntValue Seed {
92      get { return SeedParameter.Value; }
93      set { SeedParameter.Value = value; }
94    }
95    public MultiAnalyzer Analyzer {
96      get { return AnalyzerParameter.Value; }
97      set { AnalyzerParameter.Value = value; }
98    }
99    public IntValue EliteSetSize {
100      get { return EliteSetSizeParameter.Value; }
101      set { EliteSetSizeParameter.Value.Value = value.Value; }
102    }
103    public IntValue LocalImprovementMaximumIterations {
104      get { return LocalImprovementMaximumIterationsParameter.Value; }
105      set { LocalImprovementMaximumIterationsParameter.Value.Value = value.Value; }
106    }
107
108    private RandomCreator RandomCreator {
109      get { return (RandomCreator)OperatorGraph.InitialOperator; }
110    }
111    private GRASPWithPathRelinkingMainLoop MainLoop {
112      get { return RandomCreator.Successor as GRASPWithPathRelinkingMainLoop; }
113    }
114    #endregion
115
116    [Storable]
117    private BestAverageWorstQualityAnalyzer analyzer;
118
119    [StorableConstructor]
120    private GRASPWithPathRelinking(bool deserializing) : base(deserializing) { }
121    private GRASPWithPathRelinking(GRASPWithPathRelinking original, Cloner cloner)
122      : base(original, cloner) {
123      analyzer = cloner.Clone(original.analyzer);
124      RegisterEventHandlers();
125    }
126    public GRASPWithPathRelinking()
127      : base() {
128      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
129      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator."));
130      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze each iteration.", new MultiAnalyzer()));
131      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of iterations that the algorithm should run.", new IntValue(1000)));
132      Parameters.Add(new FixedValueParameter<IntValue>("EliteSetSize", "The elite set stores the best found solutions.", new IntValue(10)));
133      Parameters.Add(new FixedValueParameter<IntValue>("LocalImprovementMaximumIterations", "The maximum number of iterations performed by the local improvement operator.", new IntValue(1000)));
134      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("LocalImprovement", "Performs a local search on the solution."));
135      Parameters.Add(new FixedValueParameter<IntValue>("MinimumEliteSetSize", "(ρ) The minimum amount of elites for performing path relinking.", new IntValue(2)));
136      Parameters.Add(new ConstrainedValueParameter<ICrossover>("PathRelinking", "The operator that performs the path relinking."));
137      Parameters.Add(new ConstrainedValueParameter<IMerger>("EliteSetMerger", "The operator that merges new solutions into the elite set."));
138
139      analyzer = new BestAverageWorstQualityAnalyzer();
140      Analyzer.Operators.Add(analyzer);
141
142      RandomCreator randomCreator = new RandomCreator();
143      OperatorGraph.InitialOperator = randomCreator;
144
145      randomCreator.RandomParameter.ActualName = "Random";
146      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
147      randomCreator.SeedParameter.Value = null;
148      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
149      randomCreator.SetSeedRandomlyParameter.Value = null;
150
151      var mainLoop = new GRASPWithPathRelinkingMainLoop();
152      mainLoop.AnalyzerParameter.ActualName = AnalyzerParameter.Name;
153      mainLoop.EliteSetMergerParameter.ActualName = EliteSetMergerParameter.Name;
154      mainLoop.EliteSetSizeParameter.ActualName = EliteSetSizeParameter.Name;
155      mainLoop.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
156      mainLoop.LocalImprovementParameter.ActualName = LocalImprovementParameter.Name;
157      mainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
158      mainLoop.PathRelinkingParameter.ActualName = PathRelinkingParameter.Name;
159      mainLoop.ResultsParameter.ActualName = "Results";
160      randomCreator.Successor = mainLoop;
161
162      InitializeOperators();
163      RegisterEventHandlers();
164    }
165
166    public override IDeepCloneable Clone(Cloner cloner) {
167      return new GRASPWithPathRelinking(this, cloner);
168    }
169
170    public override void Prepare() {
171      if (Problem != null) base.Prepare();
172    }
173
174    #region Events
175    protected override void OnProblemChanged() {
176      InitializeOperators();
177      base.OnProblemChanged();
178    }
179
180    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
181      Parameterize();
182      base.Problem_SolutionCreatorChanged(sender, e);
183    }
184    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
185      Parameterize();
186      base.Problem_EvaluatorChanged(sender, e);
187    }
188    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
189      InitializeOperators();
190      base.Problem_OperatorsChanged(sender, e);
191    }
192
193    private void LocalImprovementParameter_ValueChanged(object sender, EventArgs e) {
194      Parameterize();
195    }
196    #endregion
197
198    #region Helpers
199    [StorableHook(HookType.AfterDeserialization)]
200    private void AfterDeserialization() {
201      if (Problem != null) {
202      }
203      RegisterEventHandlers();
204    }
205
206    private void RegisterEventHandlers() {
207      LocalImprovementParameter.ValueChanged += new EventHandler(LocalImprovementParameter_ValueChanged);
208    }
209
210    private void InitializeOperators() {
211      Analyzer.Operators.Clear();
212      if (Problem != null) {
213        foreach (IAnalyzer a in Problem.Operators.OfType<IAnalyzer>()) {
214          foreach (var param in a.Parameters.OfType<IScopeTreeLookupParameter>())
215            param.Depth = 1;
216          Analyzer.Operators.Add(a);
217          Analyzer.Operators.SetItemCheckedState(a, a.EnabledByDefault);
218        }
219        InitializeFromInstallation(LocalImprovementParameter, x => x.ProblemType.IsAssignableFrom(Problem.GetType()));
220        InitializeFromProblem(PathRelinkingParameter);
221        InitializeFromProblem(EliteSetMergerParameter);
222      } else {
223        LocalImprovementParameter.ValidValues.Clear();
224        PathRelinkingParameter.ValidValues.Clear();
225        EliteSetMergerParameter.ValidValues.Clear();
226      }
227      Analyzer.Operators.Add(analyzer);
228
229      Parameterize();
230    }
231
232    private void Parameterize() {
233      if (Problem != null) {
234        MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
235        MainLoop.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
236
237        analyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
238
239        if (LocalImprovementParameter.Value != null)
240          LocalImprovementParameter.Value.Problem = Problem;
241      }
242      foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
243        localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
244        localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
245        localImprovement.ResultsParameter.ActualName = "Results";
246      }
247      foreach (var merger in EliteSetMergerParameter.ValidValues) {
248        merger.PopulationSizeParameter.ActualName = EliteSetSizeParameter.Name;
249      }
250    }
251
252    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
253      InitializeFromProblem<T>(parameter, x => true);
254    }
255    private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
256      if (parameter == null) throw new ArgumentNullException("parameter");
257      if (condition == null) throw new ArgumentNullException("condition");
258      string oldName = String.Empty;
259      if (parameter.Value != null) oldName = parameter.Value.Name;
260      parameter.ValidValues.Clear();
261      foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
262        parameter.ValidValues.Add(item);
263      }
264      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
265      if (newItem != null) parameter.Value = newItem;
266    }
267    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
268      InitializeFromInstallation<T>(parameter, x => true);
269    }
270    private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
271      if (parameter == null) throw new ArgumentNullException("parameter");
272      if (condition == null) throw new ArgumentNullException("condition");
273      string oldName = String.Empty;
274      if (parameter.Value != null) oldName = parameter.Value.Name;
275      parameter.ValidValues.Clear();
276      foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
277        parameter.ValidValues.Add(item);
278      }
279      var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
280      if (newItem != null) parameter.Value = newItem;
281    }
282    #endregion
283  }
284}
Note: See TracBrowser for help on using the repository browser.