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 |
|
---|
22 | using System;
|
---|
23 | using System.Linq;
|
---|
24 | using HeuristicLab.Analysis;
|
---|
25 | using HeuristicLab.Common;
|
---|
26 | using HeuristicLab.Core;
|
---|
27 | using HeuristicLab.Data;
|
---|
28 | using HeuristicLab.Optimization;
|
---|
29 | using HeuristicLab.Parameters;
|
---|
30 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
31 | using HeuristicLab.PluginInfrastructure;
|
---|
32 | using HeuristicLab.Problems.GeneralizedQuadraticAssignment.Common;
|
---|
33 | using HeuristicLab.Random;
|
---|
34 |
|
---|
35 | namespace 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 | }
|
---|
218 | InitializeFromInstallation(LocalImprovementParameter, x => x.ProblemType.IsAssignableFrom(Problem.GetType()));
|
---|
219 | InitializeFromProblem(PathRelinkingParameter);
|
---|
220 | InitializeFromProblem(EliteSetMergerParameter);
|
---|
221 | } else {
|
---|
222 | LocalImprovementParameter.ValidValues.Clear();
|
---|
223 | PathRelinkingParameter.ValidValues.Clear();
|
---|
224 | EliteSetMergerParameter.ValidValues.Clear();
|
---|
225 | }
|
---|
226 | Analyzer.Operators.Add(analyzer);
|
---|
227 |
|
---|
228 | Parameterize();
|
---|
229 | }
|
---|
230 |
|
---|
231 | private void Parameterize() {
|
---|
232 | if (Problem != null) {
|
---|
233 | MainLoop.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
|
---|
234 | MainLoop.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
|
---|
235 |
|
---|
236 | analyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
|
---|
237 |
|
---|
238 | if (LocalImprovementParameter.Value != null)
|
---|
239 | LocalImprovementParameter.Value.Problem = Problem;
|
---|
240 | }
|
---|
241 | foreach (var localImprovement in LocalImprovementParameter.ValidValues) {
|
---|
242 | localImprovement.MaximumIterationsParameter.ActualName = LocalImprovementMaximumIterationsParameter.Name;
|
---|
243 | localImprovement.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
|
---|
244 | localImprovement.ResultsParameter.ActualName = "Results";
|
---|
245 | }
|
---|
246 | foreach (var merger in EliteSetMergerParameter.ValidValues) {
|
---|
247 | merger.PopulationSizeParameter.ActualName = EliteSetSizeParameter.Name;
|
---|
248 | }
|
---|
249 | }
|
---|
250 |
|
---|
251 | private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
|
---|
252 | InitializeFromProblem<T>(parameter, x => true);
|
---|
253 | }
|
---|
254 | private void InitializeFromProblem<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
|
---|
255 | if (parameter == null) throw new ArgumentNullException("parameter");
|
---|
256 | if (condition == null) throw new ArgumentNullException("condition");
|
---|
257 | string oldName = String.Empty;
|
---|
258 | if (parameter.Value != null) oldName = parameter.Value.Name;
|
---|
259 | parameter.ValidValues.Clear();
|
---|
260 | foreach (var item in Problem.Operators.OfType<T>().Where(condition)) {
|
---|
261 | parameter.ValidValues.Add(item);
|
---|
262 | }
|
---|
263 | var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
|
---|
264 | if (newItem != null) parameter.Value = newItem;
|
---|
265 | }
|
---|
266 | private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter) where T : class, INamedItem {
|
---|
267 | InitializeFromInstallation<T>(parameter, x => true);
|
---|
268 | }
|
---|
269 | private void InitializeFromInstallation<T>(ConstrainedValueParameter<T> parameter, Func<T, bool> condition) where T : class, INamedItem {
|
---|
270 | if (parameter == null) throw new ArgumentNullException("parameter");
|
---|
271 | if (condition == null) throw new ArgumentNullException("condition");
|
---|
272 | string oldName = String.Empty;
|
---|
273 | if (parameter.Value != null) oldName = parameter.Value.Name;
|
---|
274 | parameter.ValidValues.Clear();
|
---|
275 | foreach (var item in ApplicationManager.Manager.GetInstances<T>().Where(condition)) {
|
---|
276 | parameter.ValidValues.Add(item);
|
---|
277 | }
|
---|
278 | var newItem = parameter.ValidValues.FirstOrDefault(x => x.Name == oldName);
|
---|
279 | if (newItem != null) parameter.Value = newItem;
|
---|
280 | }
|
---|
281 | #endregion
|
---|
282 | }
|
---|
283 | }
|
---|