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 |
|
---|
22 | using HeuristicLab.Analysis;
|
---|
23 | using HeuristicLab.Core;
|
---|
24 | using HeuristicLab.Data;
|
---|
25 | using HeuristicLab.Operators;
|
---|
26 | using HeuristicLab.Parameters;
|
---|
27 | using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
|
---|
28 | using HeuristicLab.Selection;
|
---|
29 |
|
---|
30 | namespace HeuristicLab.Algorithms.TS {
|
---|
31 | /// <summary>
|
---|
32 | /// An operator which represents a Tabu Search.
|
---|
33 | /// </summary>
|
---|
34 | [Item("TSOperator", "An operator which represents a Tabu Search.")]
|
---|
35 | [StorableClass]
|
---|
36 | public class TSOperator : AlgorithmOperator {
|
---|
37 | #region Parameter properties
|
---|
38 | public ValueLookupParameter<IRandom> RandomParameter {
|
---|
39 | get { return (ValueLookupParameter<IRandom>)Parameters["Random"]; }
|
---|
40 | }
|
---|
41 | public ValueLookupParameter<BoolData> MaximizationParameter {
|
---|
42 | get { return (ValueLookupParameter<BoolData>)Parameters["Maximization"]; }
|
---|
43 | }
|
---|
44 | public SubScopesLookupParameter<DoubleData> QualityParameter {
|
---|
45 | get { return (SubScopesLookupParameter<DoubleData>)Parameters["Quality"]; }
|
---|
46 | }
|
---|
47 | public ValueLookupParameter<IntData> MaximumIterationsParameter {
|
---|
48 | get { return (ValueLookupParameter<IntData>)Parameters["MaximumIterations"]; }
|
---|
49 | }
|
---|
50 | public ValueLookupParameter<IntData> TabuTenureParameter {
|
---|
51 | get { return (ValueLookupParameter<IntData>)Parameters["TabuTenure"]; }
|
---|
52 | }
|
---|
53 | public ValueLookupParameter<VariableCollection> ResultsParameter {
|
---|
54 | get { return (ValueLookupParameter<VariableCollection>)Parameters["Results"]; }
|
---|
55 | }
|
---|
56 | public ValueLookupParameter<IOperator> MoveGeneratorParameter {
|
---|
57 | get { return (ValueLookupParameter<IOperator>)Parameters["MoveGenerator"]; }
|
---|
58 | }
|
---|
59 | public ValueLookupParameter<IOperator> MoveQualityEvaluatorParameter {
|
---|
60 | get { return (ValueLookupParameter<IOperator>)Parameters["MoveQualityEvaluator"]; }
|
---|
61 | }
|
---|
62 | public ValueLookupParameter<IOperator> MoveTabuEvaluatorParameter {
|
---|
63 | get { return (ValueLookupParameter<IOperator>)Parameters["MoveTabuEvaluator"]; }
|
---|
64 | }
|
---|
65 | public ValueLookupParameter<IOperator> TabuSelectorParameter {
|
---|
66 | get { return (ValueLookupParameter<IOperator>)Parameters["TabuSelector"]; }
|
---|
67 | }
|
---|
68 | public ValueLookupParameter<IOperator> MoveTabuMakerParameter {
|
---|
69 | get { return (ValueLookupParameter<IOperator>)Parameters["MoveTabuMaker"]; }
|
---|
70 | }
|
---|
71 | public ValueLookupParameter<IOperator> MoveMakerParameter {
|
---|
72 | get { return (ValueLookupParameter<IOperator>)Parameters["MoveMaker"]; }
|
---|
73 | }
|
---|
74 |
|
---|
75 | private ScopeParameter CurrentScopeParameter {
|
---|
76 | get { return (ScopeParameter)Parameters["CurrentScope"]; }
|
---|
77 | }
|
---|
78 | public IScope CurrentScope {
|
---|
79 | get { return CurrentScopeParameter.ActualValue; }
|
---|
80 | }
|
---|
81 | #endregion
|
---|
82 |
|
---|
83 | public TSOperator()
|
---|
84 | : base() {
|
---|
85 | #region Create parameters
|
---|
86 | Parameters.Add(new ValueLookupParameter<IRandom>("Random", "A pseudo random number generator."));
|
---|
87 | Parameters.Add(new ValueLookupParameter<BoolData>("Maximization", "True if the problem is a maximization problem, otherwise false."));
|
---|
88 | Parameters.Add(new SubScopesLookupParameter<DoubleData>("Quality", "The value which represents the quality of a solution."));
|
---|
89 | Parameters.Add(new ValueLookupParameter<IntData>("MaximumIterations", "The maximum number of generations which should be processed."));
|
---|
90 | Parameters.Add(new ValueLookupParameter<IntData>("TabuTenure", "The length of the tabu list, and also means the number of iterations a move is kept tabu"));
|
---|
91 | Parameters.Add(new ValueLookupParameter<VariableCollection>("Results", "The variable collection where results should be stored."));
|
---|
92 |
|
---|
93 | Parameters.Add(new ValueLookupParameter<IOperator>("MoveGenerator", "The operator that generates the moves."));
|
---|
94 | Parameters.Add(new ValueLookupParameter<IOperator>("MoveQualityEvaluator", "The operator that evaluates the quality of a move."));
|
---|
95 | Parameters.Add(new ValueLookupParameter<IOperator>("MoveTabuEvaluator", "The operator that evaluates whether a move is tabu."));
|
---|
96 | TabuSelector tabuSelectorOp = new TabuSelector();
|
---|
97 | tabuSelectorOp.NumberOfSelectedSubScopes = new IntData(1);
|
---|
98 | Parameters.Add(new ValueLookupParameter<IOperator>("TabuSelector", "The operator that selects among the moves the next best.", tabuSelectorOp));
|
---|
99 | Parameters.Add(new ValueLookupParameter<IOperator>("MoveTabuMaker", "The operator that declares a move tabu."));
|
---|
100 | Parameters.Add(new ValueLookupParameter<IOperator>("MoveMaker", "The operator that performs a move and updates the quality."));
|
---|
101 |
|
---|
102 | Parameters.Add(new ScopeParameter("CurrentScope", "The current scope which represents a population of solutions on which the TS should be applied."));
|
---|
103 | #endregion
|
---|
104 |
|
---|
105 | #region Create operators
|
---|
106 | TabuListCreator tabuListCreator = new TabuListCreator();
|
---|
107 | VariableCreator variableCreator = new VariableCreator();
|
---|
108 | BestQualityMemorizer bestQualityMemorizer = new BestQualityMemorizer();
|
---|
109 | ResultsCollector resultsCollector = new ResultsCollector();
|
---|
110 | UniformSequentialSubScopesProcessor mainProcessor = new UniformSequentialSubScopesProcessor();
|
---|
111 | Placeholder moveGenerator = new Placeholder();
|
---|
112 | UniformSequentialSubScopesProcessor moveEvaluationProcessor = new UniformSequentialSubScopesProcessor();
|
---|
113 | Placeholder moveQualityEvaluator = new Placeholder();
|
---|
114 | Placeholder moveTabuEvaluator = new Placeholder();
|
---|
115 | SubScopesSorter moveQualitySorter = new SubScopesSorter();
|
---|
116 | BestAverageWorstQualityCalculator bestAverageWorstMoveQualityCalculator = new BestAverageWorstQualityCalculator();
|
---|
117 | Placeholder tabuSelector = new Placeholder();
|
---|
118 | RightReducer rightReducer = new RightReducer();
|
---|
119 | UniformSequentialSubScopesProcessor moveMakingProcessor = new UniformSequentialSubScopesProcessor();
|
---|
120 | Placeholder moveTabuMaker = new Placeholder();
|
---|
121 | Placeholder moveMaker = new Placeholder();
|
---|
122 | DataTableValuesCollector valuesCollector = new DataTableValuesCollector();
|
---|
123 | SubScopesRemover subScopesRemover = new SubScopesRemover();
|
---|
124 | IntCounter iterationsCounter = new IntCounter();
|
---|
125 | Comparator iterationsComparator = new Comparator();
|
---|
126 | ConditionalBranch iterationsTermination = new ConditionalBranch();
|
---|
127 | EmptyOperator finished = new EmptyOperator();
|
---|
128 |
|
---|
129 | variableCreator.CollectedValues.Add(new ValueParameter<IntData>("Iterations", new IntData(0)));
|
---|
130 | variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Best Move Quality", new DoubleData(0)));
|
---|
131 | variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Average Move Quality", new DoubleData(0)));
|
---|
132 | variableCreator.CollectedValues.Add(new ValueParameter<DoubleData>("Worst Move Quality", new DoubleData(0)));
|
---|
133 | variableCreator.CollectedValues.Add(new ValueParameter<DataTable>("MoveQualities", new DataTable("MoveQualities")));
|
---|
134 |
|
---|
135 | resultsCollector.CollectedValues.Add(new LookupParameter<IntData>("Iterations"));
|
---|
136 | resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Quality") { ActualName = "BestQuality" });
|
---|
137 | resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Move Quality"));
|
---|
138 | resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Average Move Quality"));
|
---|
139 | resultsCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Worst Move Quality"));
|
---|
140 | resultsCollector.CollectedValues.Add(new LookupParameter<DataTable>("MoveQualities"));
|
---|
141 | resultsCollector.ResultsParameter.ActualName = "Results";
|
---|
142 |
|
---|
143 | mainProcessor.Name = "Solution processor (UniformSequentialSubScopesProcessor)";
|
---|
144 |
|
---|
145 | moveGenerator.Name = "MoveGenerator (placeholder)";
|
---|
146 | moveGenerator.OperatorParameter.ActualName = "MoveGenerator";
|
---|
147 |
|
---|
148 | moveQualityEvaluator.Name = "MoveQualityEvaluator (placeholder)";
|
---|
149 | moveQualityEvaluator.OperatorParameter.ActualName = "MoveQualityEvaluator";
|
---|
150 |
|
---|
151 | moveTabuEvaluator.Name = "MoveTabuEvaluator (placeholder)";
|
---|
152 | moveTabuEvaluator.OperatorParameter.ActualName = "MoveTabuEvaluator";
|
---|
153 |
|
---|
154 | moveQualitySorter.DescendingParameter.ActualName = "Maximization";
|
---|
155 | moveQualitySorter.ValueParameter.ActualName = "MoveQuality";
|
---|
156 |
|
---|
157 | bestAverageWorstMoveQualityCalculator.AverageQualityParameter.ActualName = "Average Move Quality";
|
---|
158 | bestAverageWorstMoveQualityCalculator.BestQualityParameter.ActualName = "Best Move Quality";
|
---|
159 | bestAverageWorstMoveQualityCalculator.MaximizationParameter.ActualName = "Maximization";
|
---|
160 | bestAverageWorstMoveQualityCalculator.QualityParameter.ActualName = "MoveQuality";
|
---|
161 | bestAverageWorstMoveQualityCalculator.WorstQualityParameter.ActualName = "Worst Move Quality";
|
---|
162 |
|
---|
163 | tabuSelector.Name = "TabuSelector (placeholder)";
|
---|
164 | tabuSelector.OperatorParameter.ActualName = "TabuSelector";
|
---|
165 |
|
---|
166 | moveMakingProcessor.Name = "MoveMaking processor (UniformSequentialSubScopesProcessor)";
|
---|
167 |
|
---|
168 | moveTabuMaker.Name = "MoveTabuMaker (placeholder)";
|
---|
169 | moveTabuMaker.OperatorParameter.ActualName = "MoveTabuMaker";
|
---|
170 |
|
---|
171 | moveMaker.Name = "MoveMaker (placeholder)";
|
---|
172 | moveMaker.OperatorParameter.ActualName = "MoveMaker";
|
---|
173 |
|
---|
174 | valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Best Move Quality"));
|
---|
175 | valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Average Move Quality"));
|
---|
176 | valuesCollector.CollectedValues.Add(new LookupParameter<DoubleData>("Worst Move Quality"));
|
---|
177 | valuesCollector.DataTableParameter.ActualName = "MoveQualities";
|
---|
178 |
|
---|
179 | subScopesRemover.RemoveAllSubScopes = true;
|
---|
180 |
|
---|
181 | iterationsCounter.Name = "Iterations Counter";
|
---|
182 | iterationsCounter.Increment = new IntData(1);
|
---|
183 | iterationsCounter.ValueParameter.ActualName = "Iterations";
|
---|
184 |
|
---|
185 | iterationsComparator.Name = "Iterations Comparator";
|
---|
186 | iterationsComparator.Comparison = new ComparisonData(Comparison.Less);
|
---|
187 | iterationsComparator.LeftSideParameter.ActualName = "Iterations";
|
---|
188 | iterationsComparator.RightSideParameter.ActualName = "MaximumIterations";
|
---|
189 | iterationsComparator.ResultParameter.ActualName = "IterationsCondition";
|
---|
190 |
|
---|
191 | iterationsTermination.Name = "Iterations Termination Condition";
|
---|
192 | iterationsTermination.ConditionParameter.ActualName = "IterationsCondition";
|
---|
193 | #endregion
|
---|
194 |
|
---|
195 | #region Create operator graph
|
---|
196 | OperatorGraph.InitialOperator = tabuListCreator;
|
---|
197 | tabuListCreator.Successor = variableCreator;
|
---|
198 | variableCreator.Successor = bestQualityMemorizer;
|
---|
199 | bestQualityMemorizer.Successor = resultsCollector;
|
---|
200 | resultsCollector.Successor = mainProcessor;
|
---|
201 | mainProcessor.Operator = moveGenerator;
|
---|
202 | mainProcessor.Successor = valuesCollector;
|
---|
203 | moveGenerator.Successor = moveEvaluationProcessor;
|
---|
204 | moveEvaluationProcessor.Operator = moveQualityEvaluator;
|
---|
205 | moveEvaluationProcessor.Successor = moveQualitySorter;
|
---|
206 | moveQualityEvaluator.Successor = moveTabuEvaluator;
|
---|
207 | moveQualitySorter.Successor = bestAverageWorstMoveQualityCalculator;
|
---|
208 | bestAverageWorstMoveQualityCalculator.Successor = tabuSelector;
|
---|
209 | tabuSelector.Successor = rightReducer;
|
---|
210 | rightReducer.Successor = moveMakingProcessor;
|
---|
211 | moveMakingProcessor.Operator = moveTabuMaker;
|
---|
212 | moveMakingProcessor.Successor = subScopesRemover;
|
---|
213 | moveTabuMaker.Successor = moveMaker;
|
---|
214 | valuesCollector.Successor = iterationsCounter;
|
---|
215 | iterationsCounter.Successor = iterationsComparator;
|
---|
216 | iterationsComparator.Successor = iterationsTermination;
|
---|
217 | iterationsTermination.TrueBranch = bestQualityMemorizer;
|
---|
218 | iterationsTermination.FalseBranch = finished;
|
---|
219 | #endregion
|
---|
220 | }
|
---|
221 | }
|
---|
222 | }
|
---|