Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Async/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs @ 14535

Last change on this file since 14535 was 13349, checked in by jkarder, 9 years ago

#2258: added StartAsync to IExecutable
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 System.Threading;
25using System.Threading.Tasks;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Operators;
31using HeuristicLab.Optimization;
32using HeuristicLab.Optimization.Operators;
33using HeuristicLab.Parameters;
34using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
38  [Item("Robust Taboo Search (RTS)", "The algorithm is described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]
39  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 130)]
40  [StorableClass]
41  public sealed class RobustTabooSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent {
42    public string Filename { get; set; }
43
44    #region Problem Properties
45    public override Type ProblemType {
46      get { return typeof(QuadraticAssignmentProblem); }
47    }
48    public new QuadraticAssignmentProblem Problem {
49      get { return (QuadraticAssignmentProblem)base.Problem; }
50      set { base.Problem = value; }
51    }
52    #endregion
53
54    #region Parameter Properties
55    public IValueParameter<MultiAnalyzer> AnalyzerParameter {
56      get { return (IValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
57    }
58    public FixedValueParameter<IntValue> SeedParameter {
59      get { return (FixedValueParameter<IntValue>)Parameters["Seed"]; }
60    }
61    public FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
62      get { return (FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
63    }
64    public FixedValueParameter<IntValue> MaximumIterationsParameter {
65      get { return (FixedValueParameter<IntValue>)Parameters["MaximumIterations"]; }
66    }
67    public FixedValueParameter<IntValue> MinimumTabuTenureParameter {
68      get { return (FixedValueParameter<IntValue>)Parameters["MinimumTabuTenure"]; }
69    }
70    public FixedValueParameter<IntValue> MaximumTabuTenureParameter {
71      get { return (FixedValueParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
72    }
73    public FixedValueParameter<BoolValue> UseAlternativeAspirationParameter {
74      get { return (FixedValueParameter<BoolValue>)Parameters["UseAlternativeAspiration"]; }
75    }
76    public FixedValueParameter<IntValue> AlternativeAspirationTenureParameter {
77      get { return (FixedValueParameter<IntValue>)Parameters["AlternativeAspirationTenure"]; }
78    }
79    public FixedValueParameter<BoolValue> UseNewTabuTenureAdaptionSchemeParameter {
80      get { return (FixedValueParameter<BoolValue>)Parameters["UseNewTabuTenureAdaptionScheme"]; }
81    }
82    public FixedValueParameter<BoolValue> TerminateOnOptimalSolutionParameter {
83      get { return (FixedValueParameter<BoolValue>)Parameters["TerminateOnOptimalSolution"]; }
84    }
85    #endregion
86
87    #region Properties
88    public int Seed {
89      get { return SeedParameter.Value.Value; }
90      set { SeedParameter.Value.Value = value; }
91    }
92    public bool SetSeedRandomly {
93      get { return SetSeedRandomlyParameter.Value.Value; }
94      set { SetSeedRandomlyParameter.Value.Value = value; }
95    }
96    public int MaximumIterations {
97      get { return MaximumIterationsParameter.Value.Value; }
98      set { MaximumIterationsParameter.Value.Value = value; }
99    }
100    public int MinimumTabuTenure {
101      get { return MinimumTabuTenureParameter.Value.Value; }
102      set { MinimumTabuTenureParameter.Value.Value = value; }
103    }
104    public int MaximumTabuTenure {
105      get { return MaximumTabuTenureParameter.Value.Value; }
106      set { MaximumTabuTenureParameter.Value.Value = value; }
107    }
108    public bool UseAlternativeAspiration {
109      get { return UseAlternativeAspirationParameter.Value.Value; }
110      set { UseAlternativeAspirationParameter.Value.Value = value; }
111    }
112    public int AlternativeAspirationTenure {
113      get { return AlternativeAspirationTenureParameter.Value.Value; }
114      set { AlternativeAspirationTenureParameter.Value.Value = value; }
115    }
116    public bool UseNewTabuTenureAdaptionScheme {
117      get { return UseNewTabuTenureAdaptionSchemeParameter.Value.Value; }
118      set { UseNewTabuTenureAdaptionSchemeParameter.Value.Value = value; }
119    }
120    public bool TerminateOnOptimalSolution {
121      get { return TerminateOnOptimalSolutionParameter.Value.Value; }
122      set { TerminateOnOptimalSolutionParameter.Value.Value = value; }
123    }
124    #endregion
125
126    [Storable]
127    private SolutionsCreator solutionsCreator;
128    [Storable]
129    private RobustTabooSeachOperator mainOperator;
130    [Storable]
131    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
132
133    [StorableConstructor]
134    private RobustTabooSearch(bool deserializing) : base(deserializing) { }
135    private RobustTabooSearch(RobustTabooSearch original, Cloner cloner)
136      : base(original, cloner) {
137      solutionsCreator = cloner.Clone(original.solutionsCreator);
138      mainOperator = cloner.Clone(original.mainOperator);
139      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
140      RegisterEventHandlers();
141    }
142    public RobustTabooSearch() {
143      Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", new MultiAnalyzer()));
144      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The seed value of the random number generator.", new IntValue(0)));
145      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)));
146      Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(10000)));
147      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(10)));
148      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(20)));
149      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)));
150      Parameters.Add(new FixedValueParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.", new IntValue(int.MaxValue)));
151      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)));
152      Parameters.Add(new FixedValueParameter<BoolValue>("UseNewTabuTenureAdaptionScheme", @"In an updated version of his implementation, Eric Taillard introduced a different way to change the tabu tenure.
153Instead of setting it uniformly between min and max, it will be set between 0 and max according to a right-skewed distribution.
154Set 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.
155Please note that the MinimumTabuTenure parameter has no effect in the new version.", new BoolValue(true)));
156
157      TerminateOnOptimalSolutionParameter.Hidden = true;
158
159      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
160      qualityAnalyzer.ResultsParameter.ActualName = "Results";
161      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);
162
163      RandomCreator randomCreator = new RandomCreator();
164      randomCreator.RandomParameter.ActualName = "Random";
165      randomCreator.SeedParameter.Value = null;
166      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
167      randomCreator.SetSeedRandomlyParameter.Value = null;
168      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
169
170      VariableCreator variableCreator = new VariableCreator();
171      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
172      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("EvaluatedSolutions", new IntValue(1)));
173      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("EvaluatedSolutionEquivalents", new DoubleValue(1)));
174
175      ResultsCollector resultsCollector = new ResultsCollector();
176      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration."));
177      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "Number of evaluated solutions."));
178
179      solutionsCreator = new SolutionsCreator();
180      solutionsCreator.NumberOfSolutions = new IntValue(1);
181
182      Placeholder analyzer = new Placeholder();
183      analyzer.Name = "(Analyzer)";
184      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
185
186      UniformSubScopesProcessor ussp = new UniformSubScopesProcessor();
187
188      mainOperator = new RobustTabooSeachOperator();
189      mainOperator.AlternativeAspirationTenureParameter.ActualName = AlternativeAspirationTenureParameter.Name;
190      mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality";
191      mainOperator.IterationsParameter.ActualName = "Iterations";
192      mainOperator.LastMoveParameter.ActualName = "LastMove";
193      mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
194      mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name;
195      mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name;
196      mainOperator.MoveQualityMatrixParameter.ActualName = "MoveQualityMatrix";
197      mainOperator.RandomParameter.ActualName = "Random";
198      mainOperator.ResultsParameter.ActualName = "Results";
199      mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory";
200      mainOperator.UseAlternativeAspirationParameter.ActualName = UseAlternativeAspirationParameter.Name;
201      mainOperator.EvaluatedSolutionsParameter.ActualName = "EvaluatedSolutions";
202      mainOperator.EvaluatedSolutionEquivalentsParameter.ActualName = "EvaluatedSolutionEquivalents";
203
204      ConditionalBranch qualityStopBranch = new ConditionalBranch();
205      qualityStopBranch.Name = "Terminate on optimal quality?";
206      qualityStopBranch.ConditionParameter.ActualName = "TerminateOnOptimalSolution";
207
208      Comparator qualityComparator = new Comparator();
209      qualityComparator.Comparison = new Comparison(ComparisonType.Greater);
210      qualityComparator.LeftSideParameter.ActualName = "BestQuality";
211      qualityComparator.RightSideParameter.ActualName = "BestKnownQuality";
212      qualityComparator.ResultParameter.ActualName = "ContinueByQuality";
213
214      ConditionalBranch continueByQualityBranch = new ConditionalBranch();
215      continueByQualityBranch.ConditionParameter.ActualName = "ContinueByQuality";
216
217      IntCounter iterationsCounter = new IntCounter();
218      iterationsCounter.ValueParameter.ActualName = "Iterations";
219      iterationsCounter.Increment = new IntValue(1);
220
221      Comparator comparator = new Comparator();
222      comparator.Name = "Iterations < MaximumIterations ?";
223      comparator.LeftSideParameter.ActualName = "Iterations";
224      comparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
225      comparator.Comparison = new Comparison(ComparisonType.Less);
226      comparator.ResultParameter.ActualName = "ContinueByIteration";
227
228      ConditionalBranch continueByIterationBranch = new ConditionalBranch();
229      continueByIterationBranch.ConditionParameter.ActualName = "ContinueByIteration";
230
231      OperatorGraph.InitialOperator = randomCreator;
232      randomCreator.Successor = variableCreator;
233      variableCreator.Successor = resultsCollector;
234      resultsCollector.Successor = solutionsCreator;
235      solutionsCreator.Successor = analyzer;
236      analyzer.Successor = ussp;
237      ussp.Operator = mainOperator;
238      ussp.Successor = qualityStopBranch;
239      qualityStopBranch.FalseBranch = iterationsCounter;
240      qualityStopBranch.TrueBranch = qualityComparator;
241      qualityStopBranch.Successor = null;
242      qualityComparator.Successor = continueByQualityBranch;
243      continueByQualityBranch.TrueBranch = iterationsCounter;
244      continueByQualityBranch.FalseBranch = null;
245      continueByQualityBranch.Successor = null;
246      iterationsCounter.Successor = comparator;
247      comparator.Successor = continueByIterationBranch;
248      continueByIterationBranch.TrueBranch = analyzer;
249      continueByIterationBranch.FalseBranch = null;
250      continueByIterationBranch.Successor = null;
251
252      RegisterEventHandlers();
253      Problem = new QuadraticAssignmentProblem();
254    }
255
256    public override IDeepCloneable Clone(Cloner cloner) {
257      return new RobustTabooSearch(this, cloner);
258    }
259
260    #region Event Handlers
261    protected override void OnProblemChanged() {
262      base.OnProblemChanged();
263      UpdateProblemSpecificParameters();
264      ParameterizeOperators();
265      UpdateAnalyzers();
266    }
267
268    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
269      base.Problem_EvaluatorChanged(sender, e);
270      ParameterizeOperators();
271      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
272    }
273
274    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
275      base.Problem_OperatorsChanged(sender, e);
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 async Task StartAsync(CancellationToken cancellationToken) {
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      await base.StartAsync(cancellationToken);
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.