Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs @ 10180

Last change on this file since 10180 was 9456, checked in by swagner, 12 years ago

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