Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.Algorithms.TabuSearch/3.3/TabuSearchMainLoop.cs @ 3623

Last change on this file since 3623 was 3521, checked in by abeham, 15 years ago

Updated tabu search to show best quality and best known quality in the chart. Also simplified the operator graph in the main loop. #840
File size: 18.2 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2010 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 HeuristicLab.Analysis;
23using HeuristicLab.Common;
24using HeuristicLab.Core;
25using HeuristicLab.Data;
26using HeuristicLab.Operators;
27using HeuristicLab.Optimization.Operators;
28using HeuristicLab.Parameters;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Selection;
31
32namespace HeuristicLab.Algorithms.TabuSearch {
33  /// <summary>
34  /// An operator which represents a tabu search.
35  /// </summary>
36  [Item("TabuSearchMainLoop", "An operator which represents the main loop of a tabu search.")]
37  [StorableClass]
38  public sealed class TabuSearchMainLoop : AlgorithmOperator {
39    #region Parameter properties
40    public ValueLookupParameter<IRandom> RandomParameter {
41      get { return (ValueLookupParameter<IRandom>)Parameters["Random"]; }
42    }
43    public ValueLookupParameter<BoolValue> MaximizationParameter {
44      get { return (ValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
45    }
46    public LookupParameter<DoubleValue> QualityParameter {
47      get { return (LookupParameter<DoubleValue>)Parameters["Quality"]; }
48    }
49    public ValueLookupParameter<DoubleValue> BestKnownQualityParameter {
50      get { return (ValueLookupParameter<DoubleValue>)Parameters["BestKnownQuality"]; }
51    }
52    public LookupParameter<DoubleValue> MoveQualityParameter {
53      get { return (LookupParameter<DoubleValue>)Parameters["MoveQuality"]; }
54    }
55    public LookupParameter<BoolValue> MoveTabuParameter {
56      get { return (LookupParameter<BoolValue>)Parameters["MoveTabu"]; }
57    }
58    public ValueLookupParameter<IntValue> MaximumIterationsParameter {
59      get { return (ValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
60    }
61    public ValueLookupParameter<IntValue> TabuTenureParameter {
62      get { return (ValueLookupParameter<IntValue>)Parameters["TabuTenure"]; }
63    }
64    public ValueLookupParameter<IOperator> MoveGeneratorParameter {
65      get { return (ValueLookupParameter<IOperator>)Parameters["MoveGenerator"]; }
66    }
67    public ValueLookupParameter<IOperator> MoveEvaluatorParameter {
68      get { return (ValueLookupParameter<IOperator>)Parameters["MoveEvaluator"]; }
69    }
70    public ValueLookupParameter<IOperator> MoveMakerParameter {
71      get { return (ValueLookupParameter<IOperator>)Parameters["MoveMaker"]; }
72    }
73    public ValueLookupParameter<IOperator> TabuCheckerParameter {
74      get { return (ValueLookupParameter<IOperator>)Parameters["TabuChecker"]; }
75    }
76    public ValueLookupParameter<IOperator> TabuMakerParameter {
77      get { return (ValueLookupParameter<IOperator>)Parameters["TabuMaker"]; }
78    }
79    public ValueLookupParameter<IOperator> VisualizerParameter {
80      get { return (ValueLookupParameter<IOperator>)Parameters["Visualizer"]; }
81    }
82    public LookupParameter<IItem> VisualizationParameter {
83      get { return (LookupParameter<IItem>)Parameters["Visualization"]; }
84    }
85    public ValueLookupParameter<VariableCollection> ResultsParameter {
86      get { return (ValueLookupParameter<VariableCollection>)Parameters["Results"]; }
87    }
88    #endregion
89
90    [StorableConstructor]
91    private TabuSearchMainLoop(bool deserializing) : base() { }
92    public TabuSearchMainLoop()
93      : base() {
94      Initialize();
95    }
96
97    private void Initialize() {
98      #region Create parameters
99      Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
100      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, otherwise false."));
101      Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The value which represents the quality of a solution."));
102      Parameters.Add(new ValueLookupParameter<DoubleValue>("BestKnownQuality", "The best known quality value found so far."));
103      Parameters.Add(new LookupParameter<DoubleValue>("MoveQuality", "The value which represents the quality of a move."));
104      Parameters.Add(new LookupParameter<BoolValue>("MoveTabu", "The value that indicates if a move is tabu or not."));
105      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed."));
106      Parameters.Add(new ValueLookupParameter<IntValue>("TabuTenure", "The length of the tabu list, and also means the number of iterations a move is kept tabu"));
107
108      Parameters.Add(new ValueLookupParameter<IOperator>("MoveGenerator", "The operator that generates the moves."));
109      Parameters.Add(new ValueLookupParameter<IOperator>("MoveMaker", "The operator that performs a move and updates the quality."));
110      Parameters.Add(new ValueLookupParameter<IOperator>("MoveEvaluator", "The operator that evaluates a move."));
111      Parameters.Add(new ValueLookupParameter<IOperator>("TabuChecker", "The operator that checks whether a move is tabu."));
112      Parameters.Add(new ValueLookupParameter<IOperator>("TabuMaker", "The operator that declares a move tabu."));
113
114      Parameters.Add(new ValueLookupParameter<IOperator>("Visualizer", "The operator used to visualize solutions."));
115      Parameters.Add(new LookupParameter<IItem>("Visualization", "The item which represents the visualization of solutions."));
116      Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
117      #endregion
118
119      #region Create operators
120      TabuListCreator tabuListCreator = new TabuListCreator();
121      VariableCreator variableCreator = new VariableCreator();
122      BestQualityMemorizer bestQualityMemorizer1 = new BestQualityMemorizer();
123      BestQualityMemorizer bestQualityMemorizer2 = new BestQualityMemorizer();
124      QualityDifferenceCalculator qualityDifferenceCalculator1 = new QualityDifferenceCalculator();
125      Placeholder visualizer1 = new Placeholder();
126      ResultsCollector resultsCollector = new ResultsCollector();
127      SubScopesProcessor solutionProcessor = new SubScopesProcessor();
128      Placeholder moveGenerator = new Placeholder();
129      UniformSubScopesProcessor moveEvaluationProcessor = new UniformSubScopesProcessor();
130      Placeholder moveEvaluator = new Placeholder();
131      Placeholder tabuChecker = new Placeholder();
132      SubScopesSorter moveQualitySorter = new SubScopesSorter();
133      BestAverageWorstQualityCalculator bestAverageWorstMoveQualityCalculator = new BestAverageWorstQualityCalculator();
134      TabuSelector tabuSelector = new TabuSelector();
135      ConditionalBranch emptyNeighborhoodBranch1 = new ConditionalBranch();
136      RightReducer rightReducer = new RightReducer();
137      SubScopesProcessor moveMakingProcessor = new SubScopesProcessor();
138      Placeholder tabuMaker = new Placeholder();
139      Placeholder moveMaker = new Placeholder();
140      SubScopesRemover subScopesRemover = new SubScopesRemover();
141      ConditionalBranch emptyNeighborhoodBranch2 = new ConditionalBranch();
142      IntCounter iterationsCounter = new IntCounter();
143      Comparator iterationsComparator = new Comparator();
144      BestQualityMemorizer bestQualityMemorizer3 = new BestQualityMemorizer();
145      BestQualityMemorizer bestQualityMemorizer4 = new BestQualityMemorizer();
146      QualityDifferenceCalculator qualityDifferenceCalculator2 = new QualityDifferenceCalculator();
147      Placeholder visualizer2 = new Placeholder();
148      DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
149      ConditionalBranch iterationsTermination = new ConditionalBranch();
150
151      variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0)));
152      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("Best Move Quality", new DoubleValue(0)));
153      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("Average Move Quality", new DoubleValue(0)));
154      variableCreator.CollectedValues.Add(new ValueParameter<DoubleValue>("Worst Move Quality", new DoubleValue(0)));
155      variableCreator.CollectedValues.Add(new ValueParameter<BoolValue>("EmptyNeighborhood", new BoolValue(false)));
156      variableCreator.CollectedValues.Add(new ValueParameter<DataTable>("MoveQualities", new DataTable("Move Qualities", "Progress of the tabu search showing the best, average, and worst move found in each iteration.")));
157
158      bestQualityMemorizer1.BestQualityParameter.ActualName = "BestQuality";
159      bestQualityMemorizer1.MaximizationParameter.ActualName = MaximizationParameter.Name;
160      bestQualityMemorizer1.QualityParameter.ActualName = QualityParameter.Name;
161
162      bestQualityMemorizer2.BestQualityParameter.ActualName = BestKnownQualityParameter.Name;
163      bestQualityMemorizer2.MaximizationParameter.ActualName = MaximizationParameter.Name;
164      bestQualityMemorizer2.QualityParameter.ActualName = QualityParameter.Name;
165
166      qualityDifferenceCalculator1.AbsoluteDifferenceParameter.ActualName = "AbsoluteDifferenceBestKnownToBest";
167      qualityDifferenceCalculator1.FirstQualityParameter.ActualName = BestKnownQualityParameter.Name;
168      qualityDifferenceCalculator1.RelativeDifferenceParameter.ActualName = "RelativeDifferenceBestKnownToBest";
169      qualityDifferenceCalculator1.SecondQualityParameter.ActualName = "BestQuality";
170
171      visualizer1.Name = "Visualizer (placeholder)";
172      visualizer1.OperatorParameter.ActualName = VisualizerParameter.Name;
173     
174      resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations"));
175      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Quality", null, "BestQuality"));
176      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Move Quality"));
177      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Average Move Quality"));
178      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Worst Move Quality"));
179      resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("MoveQualities"));
180      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Known Quality", null, BestKnownQualityParameter.Name));
181      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Absolute Difference of Best Known Quality to Best Quality", null, "AbsoluteDifferenceBestKnownToBest"));
182      resultsCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Relative Difference of Best Known Quality to Best Quality", null, "RelativeDifferenceBestKnownToBest"));
183      resultsCollector.CollectedValues.Add(new LookupParameter<IItem>("Solution Visualization", null, VisualizationParameter.Name));
184      resultsCollector.ResultsParameter.ActualName = "Results";
185
186      moveGenerator.Name = "MoveGenerator (placeholder)";
187      moveGenerator.OperatorParameter.ActualName = MoveGeneratorParameter.Name;
188
189      moveEvaluator.Name = "MoveEvaluator (placeholder)";
190      moveEvaluator.OperatorParameter.ActualName = MoveEvaluatorParameter.Name;
191
192      tabuChecker.Name = "TabuChecker (placeholder)";
193      tabuChecker.OperatorParameter.ActualName = TabuCheckerParameter.Name;
194
195      moveQualitySorter.DescendingParameter.ActualName = MaximizationParameter.Name;
196      moveQualitySorter.ValueParameter.ActualName = MoveQualityParameter.Name;
197
198      bestAverageWorstMoveQualityCalculator.AverageQualityParameter.ActualName = "Average Move Quality";
199      bestAverageWorstMoveQualityCalculator.BestQualityParameter.ActualName = "Best Move Quality";
200      bestAverageWorstMoveQualityCalculator.MaximizationParameter.ActualName = "Maximization";
201      bestAverageWorstMoveQualityCalculator.QualityParameter.ActualName = MoveQualityParameter.Name;
202      bestAverageWorstMoveQualityCalculator.WorstQualityParameter.ActualName = "Worst Move Quality";
203
204      tabuSelector.AspirationParameter.Value = new BoolValue(true);
205      tabuSelector.BestQualityParameter.ActualName = "BestQuality";
206      tabuSelector.CopySelected = new BoolValue(false);
207      tabuSelector.EmptyNeighborhoodParameter.ActualName = "EmptyNeighborhood";
208      tabuSelector.MaximizationParameter.ActualName = MaximizationParameter.Name;
209      tabuSelector.MoveQualityParameter.ActualName = MoveQualityParameter.Name;
210      tabuSelector.MoveTabuParameter.ActualName = MoveTabuParameter.Name;
211     
212      moveMakingProcessor.Name = "MoveMaking processor (UniformSubScopesProcessor)";
213
214      emptyNeighborhoodBranch1.Name = "Neighborhood empty?";
215      emptyNeighborhoodBranch1.ConditionParameter.ActualName = "EmptyNeighborhood";
216
217      tabuMaker.Name = "TabuMaker (placeholder)";
218      tabuMaker.OperatorParameter.ActualName = TabuMakerParameter.Name;
219
220      moveMaker.Name = "MoveMaker (placeholder)";
221      moveMaker.OperatorParameter.ActualName = MoveMakerParameter.Name;
222
223      subScopesRemover.RemoveAllSubScopes = true;
224
225      iterationsCounter.Name = "Iterations Counter";
226      iterationsCounter.Increment = new IntValue(1);
227      iterationsCounter.ValueParameter.ActualName = "Iterations";
228
229      iterationsComparator.Name = "Iterations >= MaximumIterations";
230      iterationsComparator.Comparison = new Comparison(ComparisonType.GreaterOrEqual);
231      iterationsComparator.LeftSideParameter.ActualName = "Iterations";
232      iterationsComparator.RightSideParameter.ActualName = MaximumIterationsParameter.Name;
233      iterationsComparator.ResultParameter.ActualName = "Terminate";
234
235      bestQualityMemorizer3.BestQualityParameter.ActualName = "BestQuality";
236      bestQualityMemorizer3.MaximizationParameter.ActualName = MaximizationParameter.Name;
237      bestQualityMemorizer3.QualityParameter.ActualName = QualityParameter.Name;
238
239      bestQualityMemorizer4.BestQualityParameter.ActualName = BestKnownQualityParameter.Name;
240      bestQualityMemorizer4.MaximizationParameter.ActualName = MaximizationParameter.Name;
241      bestQualityMemorizer4.QualityParameter.ActualName = QualityParameter.Name;
242
243      qualityDifferenceCalculator2.AbsoluteDifferenceParameter.ActualName = "AbsoluteDifferenceBestKnownToBest";
244      qualityDifferenceCalculator2.FirstQualityParameter.ActualName = BestKnownQualityParameter.Name;
245      qualityDifferenceCalculator2.RelativeDifferenceParameter.ActualName = "RelativeDifferenceBestKnownToBest";
246      qualityDifferenceCalculator2.SecondQualityParameter.ActualName = "BestQuality";
247
248      visualizer2.Name = "Visualizer (placeholder)";
249      visualizer2.OperatorParameter.ActualName = VisualizerParameter.Name;
250     
251      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Move Quality"));
252      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Average Move Quality"));
253      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Worst Move Quality"));
254      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Quality", null, "BestQuality"));
255      valuesCollector.CollectedValues.Add(new LookupParameter<DoubleValue>("Best Known Quality", null, BestKnownQualityParameter.Name));
256      valuesCollector.DataTableParameter.ActualName = "MoveQualities";
257
258      emptyNeighborhoodBranch2.Name = "Neighborhood empty?";
259      emptyNeighborhoodBranch2.ConditionParameter.ActualName = "EmptyNeighborhood";
260
261      iterationsTermination.Name = "Iterations Termination Condition";
262      iterationsTermination.ConditionParameter.ActualName = "Terminate";
263      #endregion
264
265      #region Create operator graph
266      OperatorGraph.InitialOperator = tabuListCreator;
267      tabuListCreator.Successor = variableCreator;
268      variableCreator.Successor = bestQualityMemorizer1;
269      bestQualityMemorizer1.Successor = bestQualityMemorizer2;
270      bestQualityMemorizer2.Successor = qualityDifferenceCalculator1;
271      qualityDifferenceCalculator1.Successor = visualizer1;
272      visualizer1.Successor = resultsCollector;
273      resultsCollector.Successor = solutionProcessor;
274      solutionProcessor.Operators.Add(moveGenerator);
275      solutionProcessor.Successor = iterationsCounter;
276      moveGenerator.Successor = moveEvaluationProcessor;
277      moveEvaluationProcessor.Operator = moveEvaluator;
278      moveEvaluationProcessor.Successor = moveQualitySorter;
279      moveEvaluator.Successor = tabuChecker;
280      tabuChecker.Successor = null;
281      moveQualitySorter.Successor = bestAverageWorstMoveQualityCalculator;
282      bestAverageWorstMoveQualityCalculator.Successor = tabuSelector;
283      tabuSelector.Successor = emptyNeighborhoodBranch1;
284      emptyNeighborhoodBranch1.FalseBranch = rightReducer;
285      emptyNeighborhoodBranch1.TrueBranch = null;
286      emptyNeighborhoodBranch1.Successor = subScopesRemover;
287      rightReducer.Successor = moveMakingProcessor;
288      moveMakingProcessor.Operators.Add(tabuMaker);
289      moveMakingProcessor.Successor = null;
290      tabuMaker.Successor = moveMaker;
291      moveMaker.Successor = null;
292      subScopesRemover.Successor = null;
293      iterationsCounter.Successor = iterationsComparator;
294      iterationsComparator.Successor = bestQualityMemorizer3;
295      bestQualityMemorizer3.Successor = bestQualityMemorizer4;
296      bestQualityMemorizer4.Successor = qualityDifferenceCalculator2;
297      qualityDifferenceCalculator2.Successor = visualizer2;
298      visualizer2.Successor = valuesCollector;
299      valuesCollector.Successor = emptyNeighborhoodBranch2;
300      emptyNeighborhoodBranch2.TrueBranch = null;
301      emptyNeighborhoodBranch2.FalseBranch = iterationsTermination;
302      emptyNeighborhoodBranch2.Successor = null;
303      iterationsTermination.TrueBranch = null;
304      iterationsTermination.FalseBranch = solutionProcessor;
305      #endregion
306    }
307  }
308}
Note: See TracBrowser for help on using the repository browser.