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

Last change on this file since 12810 was 12810, checked in by abeham, 7 years ago

#2444: Added evaluation output to RTS

File size: 20.7 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 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(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 130)]
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      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(0)));
171      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedMoves", new IntValue(0)));
172
173      ResultsCollector resultsCollector = new ResultsCollector();
174      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration."));
175      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of full solution evaluations."));
176      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedMoves", "The number of move evaluations."));
177
178      solutionsCreator = new SolutionsCreator();
179      solutionsCreator.NumberOfSolutions = new IntValue(1);
180
181      IntCounter counter = new IntCounter();
182      counter.ValueParameter.ActualName = "EvaluatedSolutions";
183      counter.Increment = new IntValue(1);
184
185      Placeholder analyzer = new Placeholder();
186      analyzer.Name = "(Analyzer)";
187      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
188
189      UniformSubScopesProcessor ussp = new UniformSubScopesProcessor();
190
191      mainOperator = new RobustTabooSeachOperator();
192      mainOperator.AlternativeAspirationTenureParameter.ActualName = AlternativeAspirationTenureParameter.Name;
193      mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality";
194      mainOperator.IterationsParameter.ActualName = "Iterations";
195      mainOperator.LastMoveParameter.ActualName = "LastMove";
196      mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
197      mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name;
198      mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name;
199      mainOperator.MoveQualityMatrixParameter.ActualName = "MoveQualityMatrix";
200      mainOperator.RandomParameter.ActualName = "Random";
201      mainOperator.ResultsParameter.ActualName = "Results";
202      mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory";
203      mainOperator.UseAlternativeAspirationParameter.ActualName = UseAlternativeAspirationParameter.Name;
204      mainOperator.EvaluatedMovesParameter.ActualName = "EvaluatedMoves";
205
206      ConditionalBranch qualityStopBranch = new ConditionalBranch();
207      qualityStopBranch.Name = "Terminate on optimal quality?";
208      qualityStopBranch.ConditionParameter.ActualName = "TerminateOnOptimalSolution";
209
210      Comparator qualityComparator = new Comparator();
211      qualityComparator.Comparison = new Comparison(ComparisonType.Greater);
212      qualityComparator.LeftSideParameter.ActualName = "BestQuality";
213      qualityComparator.RightSideParameter.ActualName = "BestKnownQuality";
214      qualityComparator.ResultParameter.ActualName = "ContinueByQuality";
215
216      ConditionalBranch continueByQualityBranch = new ConditionalBranch();
217      continueByQualityBranch.ConditionParameter.ActualName = "ContinueByQuality";
218
219      IntCounter iterationsCounter = new IntCounter();
220      iterationsCounter.ValueParameter.ActualName = "Iterations";
221      iterationsCounter.Increment = new IntValue(1);
222
223      Comparator comparator = new Comparator();
224      comparator.Name = "Iterations < MaximumIterations ?";
225      comparator.LeftSideParameter.ActualName = "Iterations";
226      comparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
227      comparator.Comparison = new Comparison(ComparisonType.Less);
228      comparator.ResultParameter.ActualName = "ContinueByIteration";
229
230      ConditionalBranch continueByIterationBranch = new ConditionalBranch();
231      continueByIterationBranch.ConditionParameter.ActualName = "ContinueByIteration";
232
233      OperatorGraph.InitialOperator = randomCreator;
234      randomCreator.Successor = variableCreator;
235      variableCreator.Successor = resultsCollector;
236      resultsCollector.Successor = solutionsCreator;
237      solutionsCreator.Successor = counter;
238      counter.Successor = analyzer;
239      analyzer.Successor = ussp;
240      ussp.Operator = mainOperator;
241      ussp.Successor = qualityStopBranch;
242      qualityStopBranch.FalseBranch = iterationsCounter;
243      qualityStopBranch.TrueBranch = qualityComparator;
244      qualityStopBranch.Successor = null;
245      qualityComparator.Successor = continueByQualityBranch;
246      continueByQualityBranch.TrueBranch = iterationsCounter;
247      continueByQualityBranch.FalseBranch = null;
248      continueByQualityBranch.Successor = null;
249      iterationsCounter.Successor = comparator;
250      comparator.Successor = continueByIterationBranch;
251      continueByIterationBranch.TrueBranch = analyzer;
252      continueByIterationBranch.FalseBranch = null;
253      continueByIterationBranch.Successor = null;
254
255      RegisterEventHandlers();
256      Problem = new QuadraticAssignmentProblem();
257    }
258
259    public override IDeepCloneable Clone(Cloner cloner) {
260      return new RobustTabooSearch(this, cloner);
261    }
262
263    #region Event Handlers
264    protected override void OnProblemChanged() {
265      base.OnProblemChanged();
266      UpdateProblemSpecificParameters();
267      ParameterizeOperators();
268      UpdateAnalyzers();
269    }
270
271    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
272      base.Problem_EvaluatorChanged(sender, e);
273      ParameterizeOperators();
274      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
275    }
276
277    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
278      base.Problem_OperatorsChanged(sender, e);
279      UpdateAnalyzers();
280    }
281
282    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
283      ParameterizeOperators();
284    }
285
286    private void UseAlternativeAspirationParameter_ValueChanged(object sender, EventArgs e) {
287      UpdateAlternativeAspirationTenure();
288    }
289
290    private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) {
291      if (AlternativeAspirationTenure < MaximumIterations && !UseAlternativeAspiration) {
292        SetSilentlyUseAlternativeAspirationParameter(true);
293      } else if (AlternativeAspirationTenure >= MaximumIterations && UseAlternativeAspiration) {
294        SetSilentlyUseAlternativeAspirationParameter(false);
295      }
296    }
297
298    private void MaximumIterationsParameter_ValueChanged(object sender, EventArgs e) {
299      if (MaximumIterations < AlternativeAspirationTenure && UseAlternativeAspiration) {
300        SetSilentlyUseAlternativeAspirationParameter(false);
301      } else if (MaximumIterations >= AlternativeAspirationTenure && !UseAlternativeAspiration) {
302        SetSilentlyUseAlternativeAspirationParameter(true);
303      }
304    }
305
306    private void UseNewTabuTenureAdaptionSchemeParameter_ValueChanged(object sender, EventArgs e) {
307      UpdateProblemSpecificParameters();
308    }
309    #endregion
310
311    [StorableHook(HookType.AfterDeserialization)]
312    private void AfterDeserialization() {
313      // BackwardsCompatibility3.3
314      #region Backwards compatible code, remove with 3.4
315      if (Parameters["Analyzer"] is FixedValueParameter<MultiAnalyzer>) {
316        MultiAnalyzer analyzer = AnalyzerParameter.Value;
317        Parameters.Remove("Analyzer");
318        Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", analyzer));
319      }
320      #endregion
321      RegisterEventHandlers();
322    }
323
324    private void RegisterEventHandlers() {
325      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
326      AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged);
327      MaximumIterationsParameter.Value.ValueChanged += new EventHandler(MaximumIterationsParameter_ValueChanged);
328      UseNewTabuTenureAdaptionSchemeParameter.Value.ValueChanged += new EventHandler(UseNewTabuTenureAdaptionSchemeParameter_ValueChanged);
329    }
330
331    protected override void RegisterProblemEvents() {
332      base.RegisterProblemEvents();
333      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
334    }
335
336    protected override void DeregisterProblemEvents() {
337      Problem.Evaluator.QualityParameter.ActualNameChanged -= new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
338      base.DeregisterProblemEvents();
339    }
340
341    public override void Prepare() {
342      if (Problem != null) base.Prepare();
343    }
344
345    public override void Start() {
346      if (ExecutionState == ExecutionState.Prepared) {
347        int dim = Problem.Weights.Rows;
348        IntMatrix shortTermMemory = new IntMatrix(dim, dim);
349        for (int i = 0; i < dim; i++)
350          for (int j = 0; j < dim; j++) {
351            shortTermMemory[i, j] = -(dim * (i + 1) + j + 1);
352          }
353
354        GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory));
355        GlobalScope.Variables.Add(new Variable("MoveQualityMatrix", new DoubleMatrix(dim, dim)));
356      }
357      base.Start();
358    }
359
360    private void UpdateProblemSpecificParameters() {
361      UpdateTabuTenure();
362      UpdateAlternativeAspirationTenure();
363    }
364
365    private void UpdateTabuTenure() {
366      if (UseNewTabuTenureAdaptionScheme) {
367        MinimumTabuTenure = 0;
368        MaximumTabuTenure = 8 * Problem.Weights.Rows;
369      } else {
370        MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
371        MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
372      }
373    }
374
375    private void UpdateAlternativeAspirationTenure() {
376      if (UseAlternativeAspiration) {
377        int n = Problem.Weights.Rows;
378        // Taillard has given two formulas for calculating default values: n^2 / 2 and later n^2 * 5
379        // However these do not really model the values he used in his original publication though
380        // The following formula is a linear regression model on the problem size and parameters
381        // given in Table 3 in Taillard1991 and was lower-bounded artificially by 100
382        AlternativeAspirationTenure = Math.Max(203 * n - 2274, 100);
383      } else {
384        AlternativeAspirationTenure = int.MaxValue;
385      }
386    }
387
388    private void UpdateAnalyzers() {
389      AnalyzerParameter.Value.Operators.Clear();
390      if (Problem != null) {
391        foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) {
392          AnalyzerParameter.Value.Operators.Add(analyzer, analyzer.EnabledByDefault);
393          if (!(analyzer is BestQAPSolutionAnalyzer))
394            AnalyzerParameter.Value.Operators.SetItemCheckedState(analyzer, false);
395        }
396      }
397      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer, qualityAnalyzer.EnabledByDefault);
398    }
399
400    private void ParameterizeOperators() {
401      if (Problem != null) {
402        solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
403        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
404
405        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.Name;
406
407        mainOperator.DistancesParameter.ActualName = Problem.DistancesParameter.Name;
408        mainOperator.PermutationParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
409        mainOperator.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
410        mainOperator.WeightsParameter.ActualName = Problem.WeightsParameter.Name;
411      }
412    }
413
414    private void SetSilentlyUseAlternativeAspirationParameter(bool value) {
415      UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
416      UseAlternativeAspiration = value;
417      UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged);
418    }
419  }
420}
Note: See TracBrowser for help on using the repository browser.