- Timestamp:
- 07/22/11 12:03:36 (13 years ago)
- Location:
- branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3
- Files:
-
- 1 added
- 1 deleted
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.QuadraticAssignment.Algorithms-3.3.csproj
r6569 r6586 107 107 </ItemGroup> 108 108 <ItemGroup> 109 <Compile Include=" QAPRobustTabooSeachOperator.cs" />109 <Compile Include="RobustTabooSeachOperator.cs" /> 110 110 <Compile Include="RobustTabooSearch.cs" /> 111 111 <None Include="Plugin.cs.frame" /> -
branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment.Algorithms/3.3/RobustTabooSearch.cs
r6351 r6586 26 26 using HeuristicLab.Core; 27 27 using HeuristicLab.Data; 28 using HeuristicLab.Encodings.PermutationEncoding;29 28 using HeuristicLab.Operators; 30 29 using HeuristicLab.Optimization; … … 35 34 36 35 namespace HeuristicLab.Problems.QuadraticAssignment.Algorithms { 37 [Item("Robust Taboo Search (QAP)", "The algorithm is described in Taillard, E. 1991. Robust Taboo Search for the Quadratic Assignment Problem. Parallel Computing 17, pp. 443-455.")]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.")] 38 37 [Creatable("Algorithms")] 39 38 [StorableClass] 40 public sealed class RobustTabooSearch QAP: HeuristicOptimizationEngineAlgorithm, IStorableContent {39 public sealed class RobustTabooSearch : HeuristicOptimizationEngineAlgorithm, IStorableContent { 41 40 public string Filename { get; set; } 42 41 … … 69 68 private FixedValueParameter<IntValue> MaximumTabuTenureParameter { 70 69 get { return (FixedValueParameter<IntValue>)Parameters["MaximumTabuTenure"]; } 71 }72 private FixedValueParameter<IntValue> TabuTenureAdaptionIntervalParameter {73 get { return (FixedValueParameter<IntValue>)Parameters["TabuTenureAdaptionInterval"]; }74 70 } 75 71 private FixedValueParameter<BoolValue> UseAlternativeAspirationParameter { … … 102 98 set { MaximumTabuTenureParameter.Value.Value = value; } 103 99 } 104 public int TabuTenureAdaptionInterval {105 get { return TabuTenureAdaptionIntervalParameter.Value.Value; }106 set { TabuTenureAdaptionIntervalParameter.Value.Value = value; }107 }108 100 public bool UseAlternativeAspiration { 109 101 get { return UseAlternativeAspirationParameter.Value.Value; } … … 119 111 private SolutionsCreator solutionsCreator; 120 112 [Storable] 121 private QAPRobustTabooSeachOperator mainOperator;113 private RobustTabooSeachOperator mainOperator; 122 114 [Storable] 123 115 private BestAverageWorstQualityAnalyzer qualityAnalyzer; 124 116 125 117 [StorableConstructor] 126 private RobustTabooSearch QAP(bool deserializing) : base(deserializing) { }127 private RobustTabooSearch QAP(RobustTabooSearchQAPoriginal, Cloner cloner)118 private RobustTabooSearch(bool deserializing) : base(deserializing) { } 119 private RobustTabooSearch(RobustTabooSearch original, Cloner cloner) 128 120 : base(original, cloner) { 129 121 solutionsCreator = cloner.Clone(original.solutionsCreator); 130 122 mainOperator = cloner.Clone(original.mainOperator); 131 123 qualityAnalyzer = cloner.Clone(original.qualityAnalyzer); 132 } 133 public RobustTabooSearchQAP() { 124 RegisterEventHandlers(); 125 } 126 public RobustTabooSearch() { 134 127 Parameters.Add(new FixedValueParameter<MultiAnalyzer>("Analyzer", "The analyzers that are applied after each iteration.", new MultiAnalyzer())); 135 128 Parameters.Add(new FixedValueParameter<IntValue>("Seed", "The seed value of the random number generator.", new IntValue(0))); … … 138 131 Parameters.Add(new FixedValueParameter<IntValue>("MinimumTabuTenure", "The minimum tabu tenure.", new IntValue(20))); 139 132 Parameters.Add(new FixedValueParameter<IntValue>("MaximumTabuTenure", "The maximum tabu tenure.", new IntValue(10))); 140 Parameters.Add(new FixedValueParameter<IntValue>("TabuTenureAdaptionInterval", "The amount of iterations that have to pass before the tabu tenure is adapted.", new IntValue(60)));141 133 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))); 142 134 Parameters.Add(new FixedValueParameter<IntValue>("AlternativeAspirationTenure", "The time t that a move will be remembered for the alternative aspiration condition.", new IntValue(10000))); 135 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(true))); 143 136 144 137 qualityAnalyzer = new BestAverageWorstQualityAnalyzer(); … … 153 146 randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name; 154 147 155 OperatorGraph.InitialOperator = randomCreator;156 157 148 VariableCreator variableCreator = new VariableCreator(); 158 149 variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("Iterations", new IntValue(0))); 159 variableCreator.CollectedValues.Add(new ValueParameter<IntValue>("TabuTenure", new IntValue(0)));160 randomCreator.Successor = variableCreator;161 150 162 151 ResultsCollector resultsCollector = new ResultsCollector(); 163 152 resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("Iterations", "The actual iteration.")); 164 resultsCollector.CollectedValues.Add(new LookupParameter<IntValue>("TabuTenure", "The actual tabu tenure."));165 variableCreator.Successor = resultsCollector;166 153 167 154 solutionsCreator = new SolutionsCreator(); 168 155 solutionsCreator.NumberOfSolutions = new IntValue(1); 169 resultsCollector.Successor = solutionsCreator;170 156 171 157 Placeholder analyzer = new Placeholder(); 172 158 analyzer.Name = "(Analyzer)"; 173 159 analyzer.OperatorParameter.ActualName = AnalyzerParameter.Name; 174 solutionsCreator.Successor = analyzer;175 160 176 161 UniformSubScopesProcessor ussp = new UniformSubScopesProcessor(); 177 analyzer.Successor = ussp; 178 179 mainOperator = new QAPRobustTabooSeachOperator(); 162 163 mainOperator = new RobustTabooSeachOperator(); 180 164 mainOperator.AlternativeAspirationTenureParameter.ActualName = AlternativeAspirationTenureParameter.Name; 181 165 mainOperator.BestQualityParameter.ActualName = "BestSoFarQuality"; 182 166 mainOperator.IterationsParameter.ActualName = "Iterations"; 183 mainOperator.L ongTermMemoryParameter.ActualName = "LongTermMemory";167 mainOperator.LastMoveParameter.ActualName = "LastMove"; 184 168 mainOperator.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name; 185 169 mainOperator.MaximumTabuTenureParameter.ActualName = MaximumTabuTenureParameter.Name; 186 170 mainOperator.MinimumTabuTenureParameter.ActualName = MinimumTabuTenureParameter.Name; 171 mainOperator.MoveQualityMatrixParameter.ActualName = "MoveQualityMatrix"; 187 172 mainOperator.RandomParameter.ActualName = "Random"; 173 mainOperator.ResultsParameter.ActualName = "Results"; 188 174 mainOperator.ShortTermMemoryParameter.ActualName = "ShortTermMemory"; 189 mainOperator.TabuTenureAdaptionIntervalParameter.ActualName = TabuTenureAdaptionIntervalParameter.Name;190 mainOperator.TabuTenureParameter.ActualName = "TabuTenure";191 175 mainOperator.UseAlternativeAspirationParameter.ActualName = UseAlternativeAspirationParameter.Name; 192 ussp.Operator = mainOperator; 176 177 ConditionalBranch qualityStopBranch = new ConditionalBranch(); 178 qualityStopBranch.Name = "Terminate on optimal quality?"; 179 qualityStopBranch.ConditionParameter.ActualName = "TerminateOnOptimalSolution"; 180 181 Comparator qualityComparator = new Comparator(); 182 qualityComparator.Comparison = new Comparison(ComparisonType.Greater); 183 qualityComparator.LeftSideParameter.ActualName = "BestQuality"; 184 qualityComparator.RightSideParameter.ActualName = "BestKnownQuality"; 185 qualityComparator.ResultParameter.ActualName = "ContinueByQuality"; 186 187 ConditionalBranch continueByQualityBranch = new ConditionalBranch(); 188 continueByQualityBranch.ConditionParameter.ActualName = "ContinueByQuality"; 193 189 194 190 IntCounter iterationsCounter = new IntCounter(); 195 191 iterationsCounter.ValueParameter.ActualName = "Iterations"; 196 192 iterationsCounter.Increment = new IntValue(1); 197 ussp.Successor = iterationsCounter;198 193 199 194 Comparator comparator = new Comparator(); … … 203 198 comparator.Comparison = new Comparison(ComparisonType.Less); 204 199 comparator.ResultParameter.ActualName = "ContinueByIteration"; 200 201 ConditionalBranch continueByIterationBranch = new ConditionalBranch(); 202 continueByIterationBranch.ConditionParameter.ActualName = "ContinueByIteration"; 203 204 OperatorGraph.InitialOperator = randomCreator; 205 randomCreator.Successor = variableCreator; 206 variableCreator.Successor = resultsCollector; 207 resultsCollector.Successor = solutionsCreator; 208 solutionsCreator.Successor = analyzer; 209 analyzer.Successor = ussp; 210 ussp.Operator = mainOperator; 211 ussp.Successor = qualityStopBranch; 212 qualityStopBranch.FalseBranch = iterationsCounter; 213 qualityStopBranch.TrueBranch = qualityComparator; 214 qualityStopBranch.Successor = null; 215 qualityComparator.Successor = continueByQualityBranch; 216 continueByQualityBranch.TrueBranch = iterationsCounter; 217 continueByQualityBranch.FalseBranch = null; 218 continueByQualityBranch.Successor = null; 205 219 iterationsCounter.Successor = comparator; 206 207 ConditionalBranch branch = new ConditionalBranch(); 208 branch.ConditionParameter.ActualName = "ContinueByIteration"; 209 branch.TrueBranch = analyzer; 210 comparator.Successor = branch; 220 comparator.Successor = continueByIterationBranch; 221 continueByIterationBranch.TrueBranch = analyzer; 222 continueByIterationBranch.FalseBranch = null; 223 continueByIterationBranch.Successor = null; 211 224 212 225 RegisterEventHandlers(); … … 214 227 215 228 public override IDeepCloneable Clone(Cloner cloner) { 216 return new RobustTabooSearch QAP(this, cloner);229 return new RobustTabooSearch(this, cloner); 217 230 } 218 231 … … 246 259 } 247 260 261 private void UseAlternativeAspirationParameter_ValueChanged(object sender, EventArgs e) { 262 UpdateAlternativeAspirationTenure(); 263 } 264 265 private void AlternativeAspirationTenureParameter_ValueChanged(object sender, EventArgs e) { 266 if (AlternativeAspirationTenure < MaximumIterations 267 && !UseAlternativeAspiration) { 268 UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged); 269 UseAlternativeAspiration = true; 270 UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged); 271 } else if (AlternativeAspirationTenure >= MaximumIterations 272 && UseAlternativeAspiration) { 273 UseAlternativeAspirationParameter.Value.ValueChanged -= new EventHandler(UseAlternativeAspirationParameter_ValueChanged); 274 UseAlternativeAspiration = false; 275 UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged); 276 } 277 } 278 279 [StorableHook(HookType.AfterDeserialization)] 280 private void AfterDeserialization() { 281 RegisterEventHandlers(); 282 } 283 248 284 private void RegisterEventHandlers() { 249 if (Problem != null) { 250 Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); 251 } 285 UseAlternativeAspirationParameter.Value.ValueChanged += new EventHandler(UseAlternativeAspirationParameter_ValueChanged); 286 AlternativeAspirationTenureParameter.Value.ValueChanged += new EventHandler(AlternativeAspirationTenureParameter_ValueChanged); 287 } 288 289 protected override void RegisterProblemEvents() { 290 base.RegisterProblemEvents(); 291 Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged); 292 } 293 294 protected override void DeregisterProblemEvents() { 295 Problem.Evaluator.QualityParameter.ActualNameChanged -= new EventHandler(Evaluator_QualityParameter_ActualNameChanged); 296 base.DeregisterProblemEvents(); 252 297 } 253 298 254 299 public override void Start() { 255 300 if (ExecutionState == ExecutionState.Prepared) { 256 DoubleMatrix shortTermMemory = new DoubleMatrix(Problem.Weights.Rows, Problem.Weights.Rows); 257 DoubleMatrix longTermMemory = new DoubleMatrix(Problem.Weights.Rows, Problem.Weights.Rows); 258 for (int i = 0; i < shortTermMemory.Rows; i++) 259 for (int j = 0; j < shortTermMemory.Rows; j++) { 260 shortTermMemory[i, j] = -1; 261 longTermMemory[i, j] = -1; 301 int dim = Problem.Weights.Rows; 302 IntMatrix shortTermMemory = new IntMatrix(dim, dim); 303 for (int i = 0; i < dim; i++) 304 for (int j = 0; j < dim; j++) { 305 shortTermMemory[i, j] = -(dim * (i + 1) + j + 1); 262 306 } 263 307 264 308 GlobalScope.Variables.Add(new Variable("ShortTermMemory", shortTermMemory)); 265 GlobalScope.Variables.Add(new Variable(" LongTermMemory", longTermMemory));309 GlobalScope.Variables.Add(new Variable("MoveQualityMatrix", new DoubleMatrix(dim, dim))); 266 310 } 267 311 base.Start(); … … 271 315 MinimumTabuTenure = (int)(0.9 * Problem.Weights.Rows); 272 316 MaximumTabuTenure = (int)(1.1 * Problem.Weights.Rows); 273 TabuTenureAdaptionInterval = 2 * MaximumTabuTenure; 317 UpdateAlternativeAspirationTenure(); 318 } 319 320 private void UpdateAlternativeAspirationTenure() { 321 if (UseAlternativeAspiration) { 322 AlternativeAspirationTenure = Problem.Weights.Rows * Problem.Weights.Rows / 2; 323 } else { 324 AlternativeAspirationTenure = int.MaxValue; 325 } 274 326 } 275 327 … … 277 329 AnalyzerParameter.Value.Operators.Clear(); 278 330 if (Problem != null) { 279 foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) 280 if (!(analyzer is AlleleFrequencyAnalyzer<Permutation>) && !(analyzer is PopulationDiversityAnalyzer<Permutation>)) 281 AnalyzerParameter.Value.Operators.Add(analyzer); 331 foreach (IAnalyzer analyzer in ((IProblem)Problem).Operators.OfType<IAnalyzer>()) { 332 AnalyzerParameter.Value.Operators.Add(analyzer); 333 if (!(analyzer is BestQAPSolutionAnalyzer)) 334 AnalyzerParameter.Value.Operators.SetItemCheckedState(analyzer, false); 335 } 282 336 } 283 337 AnalyzerParameter.Value.Operators.Add(qualityAnalyzer);
Note: See TracChangeset
for help on using the changeset viewer.