Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 12966 was 12835, checked in by abeham, 9 years ago

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