Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file was 17181, checked in by swagner, 5 years ago

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