Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PersistenceSpeedUp/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs @ 16003

Last change on this file since 16003 was 6760, checked in by epitzer, 13 years ago

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