Free cookie consent management tool by TermsFeed Policy Generator

source: branches/GP-MoveOperators/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs @ 10888

Last change on this file since 10888 was 8206, checked in by gkronber, 12 years ago

#1847: merged r8084:8205 from trunk into GP move operators branch
File size: 20.1 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.Operators;
29using HeuristicLab.Optimization;
30using HeuristicLab.Optimization.Operators;
31using HeuristicLab.Parameters;
32using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
33using HeuristicLab.Random;
34
35namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
36  [Item("Robust Taboo Search", "The algorithm is described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]
37  [Creatable("Algorithms")]
38  [StorableClass]
39  public sealed class RobustTabooSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent {
40    public string Filename { get; set; }
41
42    #region Problem Properties
43    public override Type ProblemType {
44      get { return typeof(QuadraticAssignmentProblem); }
45    }
46    public new QuadraticAssignmentProblem Problem {
47      get { return (QuadraticAssignmentProblem)base.Problem; }
48      set { base.Problem = value; }
49    }
50    #endregion
51
52    #region Parameter Properties
53    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
54      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
55    }
56    public FixedValueParameter<IntValue> SeedParameter {
57      get { return (FixedValueParameter<IntValue>)Parameters["Seed"]; }
58    }
59    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
60      get { return (FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
61    }
62    public FixedValueParameter<IntValue> MaximumIterationsParameter {
63      get { return (FixedValueParameter<IntValue>)Parameters["MaximumIterations"]; }
64    }
65    public FixedValueParameter<IntValue> MinimumTabuTenureParameter {
66      get { return (FixedValueParameter<IntValue>)Parameters["MinimumTabuTenure"]; }
67    }
68    public FixedValueParameter<IntValue> MaximumTabuTenureParameter {
69      get { return (FixedValueParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
70    }
71    public FixedValueParameter<BoolValue> UseAlternativeAspirationParameter {
72      get { return (FixedValueParameter<BoolValue>)Parameters["UseAlternativeAspiration"]; }
73    }
74    public FixedValueParameter<IntValue> AlternativeAspirationTenureParameter {
75      get { return (FixedValueParameter<IntValue>)Parameters["AlternativeAspirationTenure"]; }
76    }
77    public FixedValueParameter<BoolValue> UseNewTabuTenureAdaptionSchemeParameter {
78      get { return (FixedValueParameter<BoolValue>)Parameters["UseNewTabuTenureAdaptionScheme"]; }
79    }
80    public FixedValueParameter<BoolValue> TerminateOnOptimalSolutionParameter {
81      get { return (FixedValueParameter<BoolValue>)Parameters["TerminateOnOptimalSolution"]; }
82    }
83    #endregion
84
85    #region Properties
86    public int Seed {
87      get { return SeedParameter.Value.Value; }
88      set { SeedParameter.Value.Value = value; }
89    }
90    public bool SetSeedRandomly {
91      get { return SetSeedRandomlyParameter.Value.Value; }
92      set { SetSeedRandomlyParameter.Value.Value = value; }
93    }
94    public int MaximumIterations {
95      get { return MaximumIterationsParameter.Value.Value; }
96      set { MaximumIterationsParameter.Value.Value = value; }
97    }
98    public int MinimumTabuTenure {
99      get { return MinimumTabuTenureParameter.Value.Value; }
100      set { MinimumTabuTenureParameter.Value.Value = value; }
101    }
102    public int MaximumTabuTenure {
103      get { return MaximumTabuTenureParameter.Value.Value; }
104      set { MaximumTabuTenureParameter.Value.Value = value; }
105    }
106    public bool UseAlternativeAspiration {
107      get { return UseAlternativeAspirationParameter.Value.Value; }
108      set { UseAlternativeAspirationParameter.Value.Value = value; }
109    }
110    public int AlternativeAspirationTenure {
111      get { return AlternativeAspirationTenureParameter.Value.Value; }
112      set { AlternativeAspirationTenureParameter.Value.Value = value; }
113    }
114    public bool UseNewTabuTenureAdaptionScheme {
115      get { return UseNewTabuTenureAdaptionSchemeParameter.Value.Value; }
116      set { UseNewTabuTenureAdaptionSchemeParameter.Value.Value = value; }
117    }
118    public bool TerminateOnOptimalSolution {
119      get { return TerminateOnOptimalSolutionParameter.Value.Value; }
120      set { TerminateOnOptimalSolutionParameter.Value.Value = value; }
121    }
122    #endregion
123
124    [Storable]
125    private SolutionsCreator solutionsCreator;
126    [Storable]
127    private RobustTabooSeachOperator mainOperator;
128    [Storable]
129    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
130
131    [StorableConstructor]
132    private RobustTabooSearch(bool deserializing) : base(deserializing) { }
133    private RobustTabooSearch(RobustTabooSearch original, Cloner cloner)
134      : base(original, cloner) {
135      solutionsCreator = cloner.Clone(original.solutionsCreator);
136      mainOperator = cloner.Clone(original.mainOperator);
137      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
138      RegisterEventHandlers();
139    }
140    public RobustTabooSearch() {
141      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", new MultiAnalyzer()));
142      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The seed value of the random number generator.", new IntValue(0)));
143      Parameters.Add(new FixedValueParameter<BoolValue>("SetSeedRandomly", "True whether the seed should be set randomly for each run, false if it should be fixed.", new BoolValue(true)));
144      Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(10000)));
145      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(10)));
146      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(20)));
147      Parameters.Add(new FixedValueParameter<BoolValue>("UseAlternativeAspiration", "True if the alternative aspiration condition should be used that takes moves that have not been made for some time above others.", new BoolValue(false)));
148      Parameters.Add(new FixedValueParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.", new IntValue(int.MaxValue)));
149      Parameters.Add(new FixedValueParameter<BoolValue>("TerminateOnOptimalSolution", "True when the algorithm should stop if it reached a quality equal or smaller to the BestKnownQuality.", new BoolValue(false)));
150      Parameters.Add(new FixedValueParameter<BoolValue>("UseNewTabuTenureAdaptionScheme", @"In an updated version of his implementation, Eric Taillard introduced a different way to change the tabu tenure.
151Instead of setting it uniformly between min and max, it will be set between 0 and max according to a right-skewed distribution.
152Set this option to false if you want to optimize using the earlier 1991 version, and set to true if you want to optimize using the newer version.
153Please note that the MinimumTabuTenure parameter has no effect in the new version.", new BoolValue(true)));
154
155      TerminateOnOptimalSolutionParameter.Hidden = true;
156
157      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
158      qualityAnalyzer.ResultsParameter.ActualName = "Results";
159      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);
160
161      RandomCreator randomCreator = new RandomCreator();
162      randomCreator.RandomParameter.ActualName = "Random";
163      randomCreator.SeedParameter.Value = null;
164      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
165      randomCreator.SetSeedRandomlyParameter.Value = null;
166      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
167
168      VariableCreator variableCreator = new VariableCreator();
169      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
170
171      ResultsCollector resultsCollector = new ResultsCollector();
172      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration."));
173
174      solutionsCreator = new SolutionsCreator();
175      solutionsCreator.NumberOfSolutions = new IntValue(1);
176
177      Placeholder analyzer = new Placeholder();
178      analyzer.Name = "(Analyzer)";
179      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
180
181      UniformSubScopesProcessor ussp = new UniformSubScopesProcessor();
182
183      mainOperator = new RobustTabooSeachOperator();
184      mainOperator.AlternativeAspirationTenureParameter.ActualName = AlternativeAspirationTenureParameter.Name;
185      mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality";
186      mainOperator.IterationsParameter.ActualName = "Iterations";
187      mainOperator.LastMoveParameter.ActualName = "LastMove";
188      mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
189      mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name;
190      mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name;
191      mainOperator.MoveQualityMatrixParameter.ActualName = "MoveQualityMatrix";
192      mainOperator.RandomParameter.ActualName = "Random";
193      mainOperator.ResultsParameter.ActualName = "Results";
194      mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory";
195      mainOperator.UseAlternativeAspirationParameter.ActualName = UseAlternativeAspirationParameter.Name;
196
197      ConditionalBranch qualityStopBranch = new ConditionalBranch();
198      qualityStopBranch.Name = "Terminate on optimal quality?";
199      qualityStopBranch.ConditionParameter.ActualName = "TerminateOnOptimalSolution";
200
201      Comparator qualityComparator = new Comparator();
202      qualityComparator.Comparison = new Comparison(ComparisonType.Greater);
203      qualityComparator.LeftSideParameter.ActualName = "BestQuality";
204      qualityComparator.RightSideParameter.ActualName = "BestKnownQuality";
205      qualityComparator.ResultParameter.ActualName = "ContinueByQuality";
206
207      ConditionalBranch continueByQualityBranch = new ConditionalBranch();
208      continueByQualityBranch.ConditionParameter.ActualName = "ContinueByQuality";
209
210      IntCounter iterationsCounter = new IntCounter();
211      iterationsCounter.ValueParameter.ActualName = "Iterations";
212      iterationsCounter.Increment = new IntValue(1);
213
214      Comparator comparator = new Comparator();
215      comparator.Name = "Iterations < MaximumIterations ?";
216      comparator.LeftSideParameter.ActualName = "Iterations";
217      comparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
218      comparator.Comparison = new Comparison(ComparisonType.Less);
219      comparator.ResultParameter.ActualName = "ContinueByIteration";
220
221      ConditionalBranch continueByIterationBranch = new ConditionalBranch();
222      continueByIterationBranch.ConditionParameter.ActualName = "ContinueByIteration";
223
224      OperatorGraph.InitialOperator = randomCreator;
225      randomCreator.Successor = variableCreator;
226      variableCreator.Successor = resultsCollector;
227      resultsCollector.Successor = solutionsCreator;
228      solutionsCreator.Successor = analyzer;
229      analyzer.Successor = ussp;
230      ussp.Operator = mainOperator;
231      ussp.Successor = qualityStopBranch;
232      qualityStopBranch.FalseBranch = iterationsCounter;
233      qualityStopBranch.TrueBranch = qualityComparator;
234      qualityStopBranch.Successor = null;
235      qualityComparator.Successor = continueByQualityBranch;
236      continueByQualityBranch.TrueBranch = iterationsCounter;
237      continueByQualityBranch.FalseBranch = null;
238      continueByQualityBranch.Successor = null;
239      iterationsCounter.Successor = comparator;
240      comparator.Successor = continueByIterationBranch;
241      continueByIterationBranch.TrueBranch = analyzer;
242      continueByIterationBranch.FalseBranch = null;
243      continueByIterationBranch.Successor = null;
244
245      RegisterEventHandlers();
246      Problem = new QuadraticAssignmentProblem();
247    }
248
249    public override IDeepCloneable Clone(Cloner cloner) {
250      return new RobustTabooSearch(this, cloner);
251    }
252
253    #region Event Handlers
254    protected override void OnProblemChanged() {
255      base.OnProblemChanged();
256      UpdateProblemSpecificParameters();
257      ParameterizeOperators();
258      UpdateAnalyzers();
259    }
260
261    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
262      base.Problem_EvaluatorChanged(sender, e);
263      ParameterizeOperators();
264      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
265    }
266
267    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
268      base.Problem_OperatorsChanged(sender, e);
269      UpdateAnalyzers();
270    }
271
272    protected override void Problem_Reset(object sender, EventArgs e) {
273      base.Problem_Reset(sender, e);
274      UpdateProblemSpecificParameters();
275      ParameterizeOperators();
276      UpdateAnalyzers();
277    }
278
279    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
280      ParameterizeOperators();
281    }
282
283    private void UseAlternativeAspirationParameter_ValueChanged(object sender, EventArgs e) {
284      UpdateAlternativeAspirationTenure();
285    }
286
287    private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) {
288      if (AlternativeAspirationTenure < MaximumIterations && !UseAlternativeAspiration) {
289        SetSilentlyUseAlternativeAspirationParameter(true);
290      } else if (AlternativeAspirationTenure >= MaximumIterations && UseAlternativeAspiration) {
291        SetSilentlyUseAlternativeAspirationParameter(false);
292      }
293    }
294
295    private void MaximumIterationsParameter_ValueChanged(object sender, EventArgs e) {
296      if (MaximumIterations < AlternativeAspirationTenure && UseAlternativeAspiration) {
297        SetSilentlyUseAlternativeAspirationParameter(false);
298      } else if (MaximumIterations >= AlternativeAspirationTenure && !UseAlternativeAspiration) {
299        SetSilentlyUseAlternativeAspirationParameter(true);
300      }
301    }
302
303    private void UseNewTabuTenureAdaptionSchemeParameter_ValueChanged(object sender, EventArgs e) {
304      UpdateProblemSpecificParameters();
305    }
306    #endregion
307
308    [StorableHook(HookType.AfterDeserialization)]
309    private void AfterDeserialization() {
310      // BackwardsCompatibility3.3
311      #region Backwards compatible code, remove with 3.4
312      if (Parameters["Analyzer"] is FixedValueParameter<MultiAnalyzer>) {
313        MultiAnalyzer analyzer = AnalyzerParameter.Value;
314        Parameters.Remove("Analyzer");
315        Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", analyzer));
316      }
317      #endregion
318      RegisterEventHandlers();
319    }
320
321    private void RegisterEventHandlers() {
322      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
323      AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged);
324      MaximumIterationsParameter.Value.ValueChanged += new EventHandler(MaximumIterationsParameter_ValueChanged);
325      UseNewTabuTenureAdaptionSchemeParameter.Value.ValueChanged += new EventHandler(UseNewTabuTenureAdaptionSchemeParameter_ValueChanged);
326    }
327
328    protected override void RegisterProblemEvents() {
329      base.RegisterProblemEvents();
330      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
331    }
332
333    protected override void DeregisterProblemEvents() {
334      Problem.Evaluator.QualityParameter.ActualNameChanged -= new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
335      base.DeregisterProblemEvents();
336    }
337
338    public override void Prepare() {
339      if (Problem != null) base.Prepare();
340    }
341
342    public override void Start() {
343      if (ExecutionState == ExecutionState.Prepared) {
344        int dim = Problem.Weights.Rows;
345        IntMatrix shortTermMemory = new IntMatrix(dim, dim);
346        for (int i = 0; i < dim; i++)
347          for (int j = 0; j < dim; j++) {
348            shortTermMemory[i, j] = -(dim * (i + 1) + j + 1);
349          }
350
351        GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory));
352        GlobalScope.Variables.Add(new Variable("MoveQualityMatrix", new DoubleMatrix(dim, dim)));
353      }
354      base.Start();
355    }
356
357    private void UpdateProblemSpecificParameters() {
358      UpdateTabuTenure();
359      UpdateAlternativeAspirationTenure();
360    }
361
362    private void UpdateTabuTenure() {
363      if (UseNewTabuTenureAdaptionScheme) {
364        MinimumTabuTenure = 0;
365        MaximumTabuTenure = 8 * Problem.Weights.Rows;
366      } else {
367        MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
368        MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
369      }
370    }
371
372    private void UpdateAlternativeAspirationTenure() {
373      if (UseAlternativeAspiration) {
374        int n = Problem.Weights.Rows;
375        // Taillard has given two formulas for calculating default values: n^2 / 2 and later n^2 * 5
376        // However these do not really model the values he used in his original publication though
377        // The following formula is a linear regression model on the problem size and parameters
378        // given in Table 3 in Taillard1991 and was lower-bounded artificially by 100
379        AlternativeAspirationTenure = Math.Max(203 * n - 2274, 100);
380      } else {
381        AlternativeAspirationTenure = int.MaxValue;
382      }
383    }
384
385    private void UpdateAnalyzers() {
386      AnalyzerParameter.Value.Operators.Clear();
387      if (Problem != null) {
388        foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) {
389          AnalyzerParameter.Value.Operators.Add(analyzer, analyzer.EnabledByDefault);
390          if (!(analyzer is BestQAPSolutionAnalyzer))
391            AnalyzerParameter.Value.Operators.SetItemCheckedState(analyzer, false);
392        }
393      }
394      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
395    }
396
397    private void ParameterizeOperators() {
398      if (Problem != null) {
399        solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
400        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
401
402        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.Name;
403
404        mainOperator.DistancesParameter.ActualName = Problem.DistancesParameter.Name;
405        mainOperator.PermutationParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
406        mainOperator.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
407        mainOperator.WeightsParameter.ActualName = Problem.WeightsParameter.Name;
408      }
409    }
410
411    private void SetSilentlyUseAlternativeAspirationParameter(bool value) {
412      UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
413      UseAlternativeAspiration = value;
414      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
415    }
416  }
417}
Note: See TracBrowser for help on using the repository browser.