Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs @ 7317

Last change on this file since 7317 was 7259, checked in by swagner, 13 years ago

Updated year of copyrights to 2012 (#1716)
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    }
247
248    public override IDeepCloneable Clone(Cloner cloner) {
249      return new RobustTabooSearch(this, cloner);
250    }
251
252    #region Event Handlers
253    protected override void OnProblemChanged() {
254      base.OnProblemChanged();
255      UpdateProblemSpecificParameters();
256      ParameterizeOperators();
257      UpdateAnalyzers();
258    }
259
260    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
261      base.Problem_EvaluatorChanged(sender, e);
262      ParameterizeOperators();
263      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
264    }
265
266    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
267      base.Problem_OperatorsChanged(sender, e);
268      UpdateAnalyzers();
269    }
270
271    protected override void Problem_Reset(object sender, EventArgs e) {
272      base.Problem_Reset(sender, e);
273      UpdateProblemSpecificParameters();
274      ParameterizeOperators();
275      UpdateAnalyzers();
276    }
277
278    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
279      ParameterizeOperators();
280    }
281
282    private void UseAlternativeAspirationParameter_ValueChanged(object sender, EventArgs e) {
283      UpdateAlternativeAspirationTenure();
284    }
285
286    private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) {
287      if (AlternativeAspirationTenure < MaximumIterations && !UseAlternativeAspiration) {
288        SetSilentlyUseAlternativeAspirationParameter(true);
289      } else if (AlternativeAspirationTenure >= MaximumIterations && UseAlternativeAspiration) {
290        SetSilentlyUseAlternativeAspirationParameter(false);
291      }
292    }
293
294    private void MaximumIterationsParameter_ValueChanged(object sender, EventArgs e) {
295      if (MaximumIterations < AlternativeAspirationTenure && UseAlternativeAspiration) {
296        SetSilentlyUseAlternativeAspirationParameter(false);
297      } else if (MaximumIterations >= AlternativeAspirationTenure && !UseAlternativeAspiration) {
298        SetSilentlyUseAlternativeAspirationParameter(true);
299      }
300    }
301
302    private void UseNewTabuTenureAdaptionSchemeParameter_ValueChanged(object sender, EventArgs e) {
303      UpdateProblemSpecificParameters();
304    }
305    #endregion
306
307    [StorableHook(HookType.AfterDeserialization)]
308    private void AfterDeserialization() {
309      // BackwardsCompatibility3.3
310      #region Backwards compatible code, remove with 3.4
311      if (Parameters["Analyzer"] is FixedValueParameter<MultiAnalyzer>) {
312        MultiAnalyzer analyzer = AnalyzerParameter.Value;
313        Parameters.Remove("Analyzer");
314        Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", analyzer));
315      }
316      #endregion
317      RegisterEventHandlers();
318    }
319
320    private void RegisterEventHandlers() {
321      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
322      AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged);
323      MaximumIterationsParameter.Value.ValueChanged += new EventHandler(MaximumIterationsParameter_ValueChanged);
324      UseNewTabuTenureAdaptionSchemeParameter.Value.ValueChanged += new EventHandler(UseNewTabuTenureAdaptionSchemeParameter_ValueChanged);
325    }
326
327    protected override void RegisterProblemEvents() {
328      base.RegisterProblemEvents();
329      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
330    }
331
332    protected override void DeregisterProblemEvents() {
333      Problem.Evaluator.QualityParameter.ActualNameChanged -= new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
334      base.DeregisterProblemEvents();
335    }
336
337    public override void Prepare() {
338      if (Problem != null) base.Prepare();
339    }
340
341    public override void Start() {
342      if (ExecutionState == ExecutionState.Prepared) {
343        int dim = Problem.Weights.Rows;
344        IntMatrix shortTermMemory = new IntMatrix(dim, dim);
345        for (int i = 0; i < dim; i++)
346          for (int j = 0; j < dim; j++) {
347            shortTermMemory[i, j] = -(dim * (i + 1) + j + 1);
348          }
349
350        GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory));
351        GlobalScope.Variables.Add(new Variable("MoveQualityMatrix", new DoubleMatrix(dim, dim)));
352      }
353      base.Start();
354    }
355
356    private void UpdateProblemSpecificParameters() {
357      UpdateTabuTenure();
358      UpdateAlternativeAspirationTenure();
359    }
360
361    private void UpdateTabuTenure() {
362      if (UseNewTabuTenureAdaptionScheme) {
363        MinimumTabuTenure = 0;
364        MaximumTabuTenure = 8 * Problem.Weights.Rows;
365      } else {
366        MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
367        MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
368      }
369    }
370
371    private void UpdateAlternativeAspirationTenure() {
372      if (UseAlternativeAspiration) {
373        int n = Problem.Weights.Rows;
374        // Taillard has given two formulas for calculating default values: n^2 / 2 and later n^2 * 5
375        // However these do not really model the values he used in his original publication though
376        // The following formula is a linear regression model on the problem size and parameters
377        // given in Table 3 in Taillard1991 and was lower-bounded artificially by 100
378        AlternativeAspirationTenure = Math.Max(203 * n - 2274, 100);
379      } else {
380        AlternativeAspirationTenure = int.MaxValue;
381      }
382    }
383
384    private void UpdateAnalyzers() {
385      AnalyzerParameter.Value.Operators.Clear();
386      if (Problem != null) {
387        foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) {
388          AnalyzerParameter.Value.Operators.Add(analyzer, analyzer.EnabledByDefault);
389          if (!(analyzer is BestQAPSolutionAnalyzer))
390            AnalyzerParameter.Value.Operators.SetItemCheckedState(analyzer, false);
391        }
392      }
393      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
394    }
395
396    private void ParameterizeOperators() {
397      if (Problem != null) {
398        solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
399        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
400
401        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.Name;
402
403        mainOperator.DistancesParameter.ActualName = Problem.DistancesParameter.Name;
404        mainOperator.PermutationParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
405        mainOperator.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
406        mainOperator.WeightsParameter.ActualName = Problem.WeightsParameter.Name;
407      }
408    }
409
410    private void SetSilentlyUseAlternativeAspirationParameter(bool value) {
411      UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
412      UseAlternativeAspiration = value;
413      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
414    }
415  }
416}
Note: See TracBrowser for help on using the repository browser.