Free cookie consent management tool by TermsFeed Policy Generator

source: branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RandomizedRobustTabooSearch.cs @ 6416

Last change on this file since 6416 was 6416, checked in by abeham, 13 years ago

#1541

  • Added PermutationView that allows to change the permutation type
  • Updated AFA and PopDiv Analyzer
  • Simplified QAP name to just the instance when loading from embedded resource
File size: 13.3 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.Encodings.PermutationEncoding;
29using HeuristicLab.Operators;
30using HeuristicLab.Optimization;
31using HeuristicLab.Optimization.Operators;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.Random;
35
36namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms {
37  [Item("Randomized Robust Taboo Search (QAP)", "This algorithm is based on Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]
38  [Creatable("Algorithms")]
39  [StorableClass]
40  public sealed class RandomizedRobustTabooSearchQAP : 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    private FixedValueParameter<MultiAnalyzer> AnalyzerParameter {
55      get { return (FixedValueParameter<MultiAnalyzer>)Parameters["Analyzer"]; }
56    }
57    private FixedValueParameter<IntValue> SeedParameter {
58      get { return (FixedValueParameter<IntValue>)Parameters["Seed"]; }
59    }
60    private FixedValueParameter<BoolValue> SetSeedRandomlyParameter {
61      get { return (FixedValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
62    }
63    private FixedValueParameter<IntValue> MaximumIterationsParameter {
64      get { return (FixedValueParameter<IntValue>)Parameters["MaximumIterations"]; }
65    }
66    private FixedValueParameter<IntValue> MinimumTabuTenureParameter {
67      get { return (FixedValueParameter<IntValue>)Parameters["MinimumTabuTenure"]; }
68    }
69    private FixedValueParameter<IntValue> MaximumTabuTenureParameter {
70      get { return (FixedValueParameter<IntValue>)Parameters["MaximumTabuTenure"]; }
71    }
72    private FixedValueParameter<IntValue> TabuTenureAdaptionIntervalParameter {
73      get { return (FixedValueParameter<IntValue>)Parameters["TabuTenureAdaptionInterval"]; }
74    }
75    #endregion
76
77    #region Properties
78    public int Seed {
79      get { return SeedParameter.Value.Value; }
80      set { SeedParameter.Value.Value = value; }
81    }
82    public bool SetSeedRandomly {
83      get { return SetSeedRandomlyParameter.Value.Value; }
84      set { SetSeedRandomlyParameter.Value.Value = value; }
85    }
86    public int MaximumIterations {
87      get { return MaximumIterationsParameter.Value.Value; }
88      set { MaximumIterationsParameter.Value.Value = value; }
89    }
90    public int MinimumTabuTenure {
91      get { return MinimumTabuTenureParameter.Value.Value; }
92      set { MinimumTabuTenureParameter.Value.Value = value; }
93    }
94    public int MaximumTabuTenure {
95      get { return MaximumTabuTenureParameter.Value.Value; }
96      set { MaximumTabuTenureParameter.Value.Value = value; }
97    }
98    public int TabuTenureAdaptionInterval {
99      get { return TabuTenureAdaptionIntervalParameter.Value.Value; }
100      set { TabuTenureAdaptionIntervalParameter.Value.Value = value; }
101    }
102    #endregion
103
104    [Storable]
105    private SolutionsCreator solutionsCreator;
106    [Storable]
107    private QAPRandomizedRobustTabooSeachOperator mainOperator;
108    [Storable]
109    private BestAverageWorstQualityAnalyzer qualityAnalyzer;
110
111    [StorableConstructor]
112    private RandomizedRobustTabooSearchQAP(bool deserializing) : base(deserializing) { }
113    private RandomizedRobustTabooSearchQAP(RandomizedRobustTabooSearchQAP original, Cloner cloner)
114      : base(original, cloner) {
115      solutionsCreator = cloner.Clone(original.solutionsCreator);
116      mainOperator = cloner.Clone(original.mainOperator);
117      qualityAnalyzer = cloner.Clone(original.qualityAnalyzer);
118    }
119    public RandomizedRobustTabooSearchQAP() {
120      Parameters.Add(new FixedValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", new MultiAnalyzer()));
121      Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The seed value of the random number generator.", new IntValue(0)));
122      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)));
123      Parameters.Add(new FixedValueParameter<IntValue>("MaximumIterations", "The number of iterations that the algorithm should run.", new IntValue(10000)));
124      Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(20)));
125      Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(10)));
126      Parameters.Add(new FixedValueParameter<IntValue>("TabuTenureAdaptionInterval", "The amount of iterations that have to pass before the tabu tenure is adapted.", new IntValue(60)));
127
128      qualityAnalyzer = new BestAverageWorstQualityAnalyzer();
129      qualityAnalyzer.ResultsParameter.ActualName = "Results";
130      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);
131
132      RandomCreator randomCreator = new RandomCreator();
133      randomCreator.RandomParameter.ActualName = "Random";
134      randomCreator.SeedParameter.Value = null;
135      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
136      randomCreator.SetSeedRandomlyParameter.Value = null;
137      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
138
139      OperatorGraph.InitialOperator = randomCreator;
140
141      VariableCreator variableCreator = new VariableCreator();
142      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
143      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("TabuTenure", new IntValue(0)));
144      randomCreator.Successor = variableCreator;
145
146      ResultsCollector resultsCollector = new ResultsCollector();
147      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration."));
148      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("TabuTenure", "The actual tabu tenure."));
149      variableCreator.Successor = resultsCollector;
150
151      solutionsCreator = new SolutionsCreator();
152      solutionsCreator.NumberOfSolutions = new IntValue(1);
153      resultsCollector.Successor = solutionsCreator;
154
155      Placeholder analyzer = new Placeholder();
156      analyzer.Name = "(Analyzer)";
157      analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name;
158      solutionsCreator.Successor = analyzer;
159
160      UniformSubScopesProcessor ussp = new UniformSubScopesProcessor();
161      analyzer.Successor = ussp;
162
163      mainOperator = new QAPRandomizedRobustTabooSeachOperator();
164      mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality";
165      mainOperator.IterationsParameter.ActualName = "Iterations";
166      mainOperator.LongTermMemoryParameter.ActualName = "LongTermMemory";
167      mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
168      mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name;
169      mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name;
170      mainOperator.RandomParameter.ActualName = "Random";
171      mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory";
172      mainOperator.TabuTenureAdaptionIntervalParameter.ActualName = TabuTenureAdaptionIntervalParameter.Name;
173      mainOperator.TabuTenureParameter.ActualName = "TabuTenure";
174      mainOperator.ResultsParameter.ActualName = "Results";
175      ussp.Operator = mainOperator;
176
177      IntCounter iterationsCounter = new IntCounter();
178      iterationsCounter.ValueParameter.ActualName = "Iterations";
179      iterationsCounter.Increment = new IntValue(1);
180      ussp.Successor = iterationsCounter;
181
182      Comparator comparator = new Comparator();
183      comparator.Name = "Iterations < MaximumIterations ?";
184      comparator.LeftSideParameter.ActualName = "Iterations";
185      comparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
186      comparator.Comparison = new Comparison(ComparisonType.Less);
187      comparator.ResultParameter.ActualName = "ContinueByIteration";
188      iterationsCounter.Successor = comparator;
189
190      ConditionalBranch branch = new ConditionalBranch();
191      branch.ConditionParameter.ActualName = "ContinueByIteration";
192      branch.TrueBranch = analyzer;
193      comparator.Successor = branch;
194
195      RegisterEventHandlers();
196    }
197
198    public override IDeepCloneable Clone(Cloner cloner) {
199      return new RandomizedRobustTabooSearchQAP(this, cloner);
200    }
201
202    protected override void OnProblemChanged() {
203      base.OnProblemChanged();
204      UpdateProblemSpecificParameters();
205      ParameterizeOperators();
206      UpdateAnalyzers();
207    }
208
209    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
210      base.Problem_EvaluatorChanged(sender, e);
211      ParameterizeOperators();
212      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
213    }
214
215    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
216      base.Problem_OperatorsChanged(sender, e);
217      UpdateAnalyzers();
218    }
219
220    protected override void Problem_Reset(object sender, EventArgs e) {
221      base.Problem_Reset(sender, e);
222      UpdateProblemSpecificParameters();
223      ParameterizeOperators();
224      UpdateAnalyzers();
225    }
226
227    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
228      ParameterizeOperators();
229    }
230
231    private void RegisterEventHandlers() {
232      if (Problem != null) {
233        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
234      }
235    }
236
237    public override void Start() {
238      if (ExecutionState == ExecutionState.Prepared) {
239        IntMatrix shortTermMemory = new IntMatrix(Problem.Weights.Rows, Problem.Weights.Rows);
240        DoubleMatrix shortTermMemory2 = new DoubleMatrix(Problem.Weights.Rows, Problem.Weights.Rows);
241        IntMatrix longTermMemory = new IntMatrix(Problem.Weights.Rows, Problem.Weights.Rows);
242        for (int i = 0; i < shortTermMemory.Rows; i++)
243          for (int j = 0; j < shortTermMemory.Rows; j++) {
244            shortTermMemory[i, j] = -1;
245            shortTermMemory2[i, j] = double.MinValue;
246            longTermMemory[i, j] = -1;
247          }
248
249        GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory));
250        GlobalScope.Variables.Add(new Variable("ShortTermMemory2", shortTermMemory2));
251        GlobalScope.Variables.Add(new Variable("LongTermMemory", longTermMemory));
252      }
253      base.Start();
254    }
255
256    private void UpdateProblemSpecificParameters() {
257      MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows);
258      MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows);
259      TabuTenureAdaptionInterval = 2 * MaximumTabuTenure;
260    }
261
262    private void UpdateAnalyzers() {
263      AnalyzerParameter.Value.Operators.Clear();
264      if (Problem != null) {
265        foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>())
266          if (!(analyzer is AlleleFrequencyAnalyzer<Permutation>) && !(analyzer is PopulationDiversityAnalyzer<Permutation>))
267            AnalyzerParameter.Value.Operators.Add(analyzer);
268      }
269      AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);
270    }
271
272    private void ParameterizeOperators() {
273      if (Problem != null) {
274        solutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
275        solutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
276
277        qualityAnalyzer.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.Name;
278
279        mainOperator.DistancesParameter.ActualName = Problem.DistancesParameter.Name;
280        mainOperator.PermutationParameter.ActualName = Problem.SolutionCreator.PermutationParameter.ActualName;
281        mainOperator.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
282        mainOperator.WeightsParameter.ActualName = Problem.WeightsParameter.Name;
283      }
284    }
285  }
286}
Note: See TracBrowser for help on using the repository browser.