Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 3340 was 3340, checked in by abeham, 14 years ago

Updated Tabu search, permutation move operators, real vector move operators, binary vector move operators #840
Added a Tabu Search TSP workbench

File size: 20.6 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Core;
26using HeuristicLab.Data;
27using HeuristicLab.Optimization;
28using HeuristicLab.Operators;
29using HeuristicLab.Optimization.Operators;
30using HeuristicLab.Parameters;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32using HeuristicLab.PluginInfrastructure;
33
34namespace HeuristicLab.Algorithms.TabuSearch {
35  [Item("Tabu Search", "A tabu search algorithm.")]
36  [Creatable("Algorithms")]
37  [StorableClass]
38  public sealed class TabuSearch : EngineAlgorithm {
39    #region Problem Properties
40    public override Type ProblemType {
41      get { return typeof(ISingleObjectiveProblem); }
42    }
43    public new ISingleObjectiveProblem Problem {
44      get { return (ISingleObjectiveProblem)base.Problem; }
45      set { base.Problem = value; }
46    }
47    #endregion
48
49    #region Parameter Properties
50    private ValueParameter<IntValue> SeedParameter {
51      get { return (ValueParameter<IntValue>)Parameters["Seed"]; }
52    }
53    private ValueParameter<BoolValue> SetSeedRandomlyParameter {
54      get { return (ValueParameter<BoolValue>)Parameters["SetSeedRandomly"]; }
55    }
56    private ConstrainedValueParameter<IMoveGenerator> MoveGeneratorParameter {
57      get { return (ConstrainedValueParameter<IMoveGenerator>)Parameters["MoveGenerator"]; }
58    }
59    private ConstrainedValueParameter<IMoveMaker> MoveMakerParameter {
60      get { return (ConstrainedValueParameter<IMoveMaker>)Parameters["MoveMaker"]; }
61    }
62    private ConstrainedValueParameter<ISingleObjectiveMoveEvaluator> MoveEvaluatorParameter {
63      get { return (ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>)Parameters["MoveEvaluator"]; }
64    }
65    private ConstrainedValueParameter<ITabuChecker> TabuCheckerParameter {
66      get { return (ConstrainedValueParameter<ITabuChecker>)Parameters["TabuChecker"]; }
67    }
68    private ConstrainedValueParameter<ITabuMaker> TabuMakerParameter {
69      get { return (ConstrainedValueParameter<ITabuMaker>)Parameters["TabuMaker"]; }
70    }
71    private ValueParameter<IntValue> TabuTenureParameter {
72      get { return (ValueParameter<IntValue>)Parameters["TabuTenure"]; }
73    }
74    private ValueParameter<IntValue> MaximumIterationsParameter {
75      get { return (ValueParameter<IntValue>)Parameters["MaximumIterations"]; }
76    }
77    private ValueParameter<IntValue> SampleSizeParameter {
78      get { return (ValueParameter<IntValue>)Parameters["SampleSize"]; }
79    }
80    #endregion
81
82    #region Properties
83    public IntValue Seed {
84      get { return SeedParameter.Value; }
85      set { SeedParameter.Value = value; }
86    }
87    public BoolValue SetSeedRandomly {
88      get { return SetSeedRandomlyParameter.Value; }
89      set { SetSeedRandomlyParameter.Value = value; }
90    }
91    public IMoveGenerator MoveGenerator {
92      get { return MoveGeneratorParameter.Value; }
93      set { MoveGeneratorParameter.Value = value; }
94    }
95    public IMoveMaker MoveMaker {
96      get { return MoveMakerParameter.Value; }
97      set { MoveMakerParameter.Value = value; }
98    }
99    public ISingleObjectiveMoveEvaluator MoveEvaluator {
100      get { return MoveEvaluatorParameter.Value; }
101      set { MoveEvaluatorParameter.Value = value; }
102    }
103    public ITabuChecker TabuChecker {
104      get { return TabuCheckerParameter.Value; }
105      set { TabuCheckerParameter.Value = value; }
106    }
107    public ITabuMaker TabuMaker {
108      get { return TabuMakerParameter.Value; }
109      set { TabuMakerParameter.Value = value; }
110    }
111    public IntValue TabuTenure {
112      get { return TabuTenureParameter.Value; }
113      set { TabuTenureParameter.Value = value; }
114    }
115    public IntValue MaximumIterations {
116      get { return MaximumIterationsParameter.Value; }
117      set { MaximumIterationsParameter.Value = value; }
118    }
119    private RandomCreator RandomCreator {
120      get { return (RandomCreator)OperatorGraph.InitialOperator; }
121    }
122    private SolutionsCreator SolutionsCreator {
123      get { return (SolutionsCreator)RandomCreator.Successor; }
124    }
125    private TabuSearchMainLoop MainLoop {
126      get { return (TabuSearchMainLoop)SolutionsCreator.Successor; }
127    }
128    #endregion
129
130    public TabuSearch()
131      : base() {
132      Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
133      Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
134      Parameters.Add(new ConstrainedValueParameter<IMoveGenerator>("MoveGenerator", "The operator used to generate moves to the neighborhood of the current solution."));
135      Parameters.Add(new ConstrainedValueParameter<IMoveMaker>("MoveMaker", "The operator used to perform a move."));
136      Parameters.Add(new ConstrainedValueParameter<ISingleObjectiveMoveEvaluator>("MoveEvaluator", "The operator used to evaluate a move."));
137      Parameters.Add(new ConstrainedValueParameter<ITabuChecker>("TabuChecker", "The operator to check whether a move is tabu or not."));
138      Parameters.Add(new ConstrainedValueParameter<ITabuMaker>("TabuMaker", "The operator used to insert attributes of a move into the tabu list."));
139      Parameters.Add(new ValueParameter<IntValue>("TabuTenure", "The length of the tabu list.", new IntValue(10)));
140      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
141      Parameters.Add(new ValueParameter<IntValue>("SampleSize", "The neighborhood size for stochastic sampling move generators", new IntValue(100)));
142
143      RandomCreator randomCreator = new RandomCreator();
144      SolutionsCreator solutionsCreator = new SolutionsCreator();
145      TabuSearchMainLoop tsMainLoop = new TabuSearchMainLoop();
146      OperatorGraph.InitialOperator = randomCreator;
147
148      randomCreator.RandomParameter.ActualName = "Random";
149      randomCreator.SeedParameter.ActualName = SeedParameter.Name;
150      randomCreator.SeedParameter.Value = null;
151      randomCreator.SetSeedRandomlyParameter.ActualName = SetSeedRandomlyParameter.Name;
152      randomCreator.SetSeedRandomlyParameter.Value = null;
153      randomCreator.Successor = solutionsCreator;
154
155      solutionsCreator.NumberOfSolutions = new IntValue(1);
156      solutionsCreator.Successor = tsMainLoop;
157
158      tsMainLoop.MoveGeneratorParameter.ActualName = MoveGeneratorParameter.Name;
159      tsMainLoop.MoveMakerParameter.ActualName = MoveMakerParameter.Name;
160      tsMainLoop.MoveEvaluatorParameter.ActualName = MoveEvaluatorParameter.Name;
161      tsMainLoop.TabuCheckerParameter.ActualName = TabuCheckerParameter.Name;
162      tsMainLoop.TabuMakerParameter.ActualName = TabuMakerParameter.Name;
163      tsMainLoop.MaximumIterationsParameter.ActualName = MaximumIterationsParameter.Name;
164      tsMainLoop.RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
165      tsMainLoop.ResultsParameter.ActualName = "Results";
166
167      Initialize();
168    }
169    [StorableConstructor]
170    private TabuSearch(bool deserializing) : base(deserializing) { }
171
172    public override IDeepCloneable Clone(Cloner cloner) {
173      TabuSearch clone = (TabuSearch)base.Clone(cloner);
174      clone.Initialize();
175      return clone;
176    }
177
178    public override void Prepare() {
179      if (Problem != null && MoveGenerator != null && MoveMaker != null && MoveEvaluator != null &&
180          TabuChecker != null && TabuMaker != null)
181        base.Prepare();
182    }
183
184    #region Events
185    protected override void OnProblemChanged() {
186      ParameterizeStochasticOperator(Problem.SolutionCreator);
187      ParameterizeStochasticOperator(Problem.Evaluator);
188      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
189      foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
190        op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
191      }
192      foreach (ITabuChecker op in Problem.Operators.OfType<ITabuChecker>()) {
193        op.MoveTabuParameter.ActualNameChanged += new EventHandler(TabuChecker_MoveTabuParameter_ActualNameChanged);
194      }
195      ParameterizeSolutionsCreator();
196      ParameterizeMainLoop();
197      UpdateMoveGenerator();
198      UpdateMoveParameters();
199      ParameterizeMoveGenerators();
200      ParameterizeMoveEvaluator();
201      ParameterizeMoveMaker();
202      ParameterizeTabuMaker();
203      ParameterizeTabuChecker();
204      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
205      base.OnProblemChanged();
206    }
207    protected override void Problem_SolutionCreatorChanged(object sender, EventArgs e) {
208      ParameterizeStochasticOperator(Problem.SolutionCreator);
209      ParameterizeSolutionsCreator();
210      base.Problem_SolutionCreatorChanged(sender, e);
211    }
212    protected override void Problem_EvaluatorChanged(object sender, EventArgs e) {
213      ParameterizeStochasticOperator(Problem.Evaluator);
214      ParameterizeSolutionsCreator();
215      ParameterizeMainLoop();
216      ParameterizeMoveEvaluator();
217      ParameterizeMoveMaker();
218      ParameterizeTabuMaker();
219      ParameterizeTabuChecker();
220      Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
221      base.Problem_EvaluatorChanged(sender, e);
222    }
223    protected override void Problem_VisualizerChanged(object sender, EventArgs e) {
224      ParameterizeStochasticOperator(Problem.Visualizer);
225      ParameterizeMainLoop();
226      if (Problem.Visualizer != null) Problem.Visualizer.VisualizationParameter.ActualNameChanged += new EventHandler(Visualizer_VisualizationParameter_ActualNameChanged);
227      base.Problem_VisualizerChanged(sender, e);
228    }
229    protected override void Problem_OperatorsChanged(object sender, EventArgs e) {
230      foreach (IOperator op in Problem.Operators) ParameterizeStochasticOperator(op);
231      // This may seem pointless, but some operators already have the eventhandler registered, others don't
232      // FIXME: Is there another way to solve this problem?
233      foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
234        op.MoveQualityParameter.ActualNameChanged -= new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
235        op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
236      }
237      foreach (ITabuChecker op in Problem.Operators.OfType<ITabuChecker>()) {
238        op.MoveTabuParameter.ActualNameChanged -= new EventHandler(TabuChecker_MoveTabuParameter_ActualNameChanged);
239        op.MoveTabuParameter.ActualNameChanged += new EventHandler(TabuChecker_MoveTabuParameter_ActualNameChanged);
240      }
241      UpdateMoveGenerator();
242      UpdateMoveParameters();
243      ParameterizeMainLoop();
244      ParameterizeMoveGenerators();
245      ParameterizeMoveEvaluator();
246      ParameterizeMoveMaker();
247      ParameterizeTabuMaker();
248      ParameterizeTabuChecker();
249      base.Problem_OperatorsChanged(sender, e);
250    }
251    private void Evaluator_QualityParameter_ActualNameChanged(object sender, EventArgs e) {
252      ParameterizeMainLoop();
253      ParameterizeMoveEvaluator();
254      ParameterizeMoveMaker();
255      ParameterizeTabuMaker();
256      ParameterizeTabuChecker();
257    }
258    private void MoveGeneratorParameter_ValueChanged(object sender, EventArgs e) {
259      UpdateMoveParameters();
260    }
261    private void MoveEvaluatorParameter_ValueChanged(object sender, EventArgs e) {
262      ParameterizeMainLoop();
263      ParameterizeMoveEvaluator();
264      ParameterizeMoveMaker();
265      ParameterizeTabuMaker();
266      ParameterizeTabuChecker();
267    }
268    private void MoveEvaluator_MoveQualityParameter_ActualNameChanged(object sender, EventArgs e) {
269      ParameterizeMainLoop();
270      ParameterizeMoveEvaluator();
271      ParameterizeMoveMaker();
272      ParameterizeTabuMaker();
273      ParameterizeTabuChecker();
274    }
275    private void TabuCheckerParameter_ValueChanged(object sender, EventArgs e) {
276      ParameterizeMainLoop();
277    }
278    private void TabuChecker_MoveTabuParameter_ActualNameChanged(object sender, EventArgs e) {
279      ParameterizeMainLoop();
280    }
281    private void Visualizer_VisualizationParameter_ActualNameChanged(object sender, EventArgs e) {
282      ParameterizeMainLoop();
283    }
284    private void SampleSizeParameter_NameChanged(object sender, EventArgs e) {
285      ParameterizeMoveGenerators();
286    }
287    #endregion
288
289    #region Helpers
290    [StorableHook(HookType.AfterDeserialization)]
291    private void Initialize() {
292      if (Problem != null) {
293        Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
294        foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
295          op.MoveQualityParameter.ActualNameChanged += new EventHandler(MoveEvaluator_MoveQualityParameter_ActualNameChanged);
296        }
297        if (Problem.Visualizer != null) Problem.Visualizer.VisualizationParameter.ActualNameChanged += new EventHandler(Visualizer_VisualizationParameter_ActualNameChanged);
298      }
299      MoveGeneratorParameter.ValueChanged += new EventHandler(MoveGeneratorParameter_ValueChanged);
300      MoveEvaluatorParameter.ValueChanged += new EventHandler(MoveEvaluatorParameter_ValueChanged);
301      TabuCheckerParameter.ValueChanged += new EventHandler(TabuCheckerParameter_ValueChanged);
302      SampleSizeParameter.NameChanged += new EventHandler(SampleSizeParameter_NameChanged);
303    }
304    private void UpdateMoveGenerator() {
305      IMoveGenerator oldMoveGenerator = MoveGenerator;
306      MoveGeneratorParameter.ValidValues.Clear();
307      if (Problem != null) {
308        foreach (IMoveGenerator generator in Problem.Operators.OfType<IMoveGenerator>().OrderBy(x => x.Name)) {
309          MoveGeneratorParameter.ValidValues.Add(generator);
310        }
311      }
312      if (oldMoveGenerator != null && MoveGeneratorParameter.ValidValues.Any(x => x.GetType() == oldMoveGenerator.GetType()))
313        MoveGenerator = MoveGeneratorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveGenerator.GetType());
314      if (MoveGenerator == null) {
315        ClearMoveParameters();
316      }
317    }
318    private void UpdateMoveParameters() {
319      IMoveMaker oldMoveMaker = MoveMaker;
320      ISingleObjectiveMoveEvaluator oldMoveEvaluator = MoveEvaluator;
321      ITabuChecker oldTabuMoveEvaluator = TabuChecker;
322      ITabuMaker oldTabuMoveMaker = TabuMaker;
323      ClearMoveParameters();
324      if (MoveGenerator != null) {
325        List<Type> moveTypes = MoveGenerator.GetType().GetInterfaces().Where(x => typeof(IMoveOperator).IsAssignableFrom(x)).ToList();
326        foreach (Type type in moveTypes.ToList()) {
327          if (moveTypes.Any(t => t != type && type.IsAssignableFrom(t)))
328            moveTypes.Remove(type);
329        }
330        foreach (Type type in moveTypes) {
331          var operators = Problem.Operators.Where(x => type.IsAssignableFrom(x.GetType())).OrderBy(x => x.Name);
332          foreach (IMoveMaker moveMaker in operators.OfType<IMoveMaker>())
333            MoveMakerParameter.ValidValues.Add(moveMaker);
334          foreach (ISingleObjectiveMoveEvaluator moveEvaluator in operators.OfType<ISingleObjectiveMoveEvaluator>())
335            MoveEvaluatorParameter.ValidValues.Add(moveEvaluator);
336          foreach (ITabuChecker tabuMoveEvaluator in operators.OfType<ITabuChecker>())
337            TabuCheckerParameter.ValidValues.Add(tabuMoveEvaluator);
338          foreach (ITabuMaker tabuMoveMaker in operators.OfType<ITabuMaker>())
339            TabuMakerParameter.ValidValues.Add(tabuMoveMaker);
340        }
341        if (oldMoveMaker != null) {
342          IMoveMaker mm = MoveMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveMaker.GetType());
343          if (mm != null) MoveMaker = mm;
344        }
345        if (oldMoveEvaluator != null) {
346          ISingleObjectiveMoveEvaluator me = MoveEvaluatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldMoveEvaluator.GetType());
347          if (me != null) MoveEvaluator = me;
348        }
349        if (oldTabuMoveMaker != null) {
350          ITabuMaker tmm = TabuMakerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTabuMoveMaker.GetType());
351          if (tmm != null) TabuMaker = tmm;
352        }
353        if (oldTabuMoveEvaluator != null) {
354          ITabuChecker tme = TabuCheckerParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldTabuMoveEvaluator.GetType());
355          if (tme != null) TabuChecker = tme;
356        }
357      }
358    }
359    private void ClearMoveParameters() {
360      MoveMakerParameter.ValidValues.Clear();
361      MoveEvaluatorParameter.ValidValues.Clear();
362      TabuCheckerParameter.ValidValues.Clear();
363      TabuMakerParameter.ValidValues.Clear();
364    }
365    private void ParameterizeSolutionsCreator() {
366      SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
367      SolutionsCreator.SolutionCreatorParameter.ActualName = Problem.SolutionCreatorParameter.Name;
368    }
369    private void ParameterizeMainLoop() {
370      MainLoop.BestKnownQualityParameter.ActualName = Problem.BestKnownQualityParameter.Name;
371      MainLoop.MaximizationParameter.ActualName = Problem.MaximizationParameter.Name;
372      MainLoop.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
373      if (MoveEvaluator != null)
374        MainLoop.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
375      if (TabuChecker != null)
376        MainLoop.MoveTabuParameter.ActualName = TabuChecker.MoveTabuParameter.ActualName;
377      MainLoop.VisualizerParameter.ActualName = Problem.VisualizerParameter.Name;
378      if (Problem.Visualizer != null)
379        MainLoop.VisualizationParameter.ActualName = Problem.Visualizer.VisualizationParameter.ActualName;
380    }
381    private void ParameterizeStochasticOperator(IOperator op) {
382      if (op is IStochasticOperator)
383        ((IStochasticOperator)op).RandomParameter.ActualName = RandomCreator.RandomParameter.ActualName;
384    }
385    private void ParameterizeMoveGenerators() {
386      if (Problem != null) {
387        foreach (IMultiMoveGenerator generator in Problem.Operators.OfType<IMultiMoveGenerator>())
388          generator.SampleSizeParameter.ActualName = SampleSizeParameter.Name;
389      }
390    }
391    private void ParameterizeMoveEvaluator() {
392      foreach (ISingleObjectiveMoveEvaluator op in Problem.Operators.OfType<ISingleObjectiveMoveEvaluator>()) {
393        op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
394      }
395    }
396    private void ParameterizeMoveMaker() {
397      foreach (IMoveMaker op in Problem.Operators.OfType<IMoveMaker>()) {
398        op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
399        if (MoveEvaluator != null)
400          op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
401      }
402    }
403    private void ParameterizeTabuMaker() {
404      foreach (ITabuMaker op in Problem.Operators.OfType<ITabuMaker>()) {
405        op.QualityParameter.ActualName = Problem.Evaluator.QualityParameter.ActualName;
406        if (MoveEvaluator != null)
407          op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
408      }
409    }
410    private void ParameterizeTabuChecker() {
411      foreach (ITabuChecker op in Problem.Operators.OfType<ITabuChecker>()) {
412        if (MoveEvaluator != null)
413          op.MoveQualityParameter.ActualName = MoveEvaluator.MoveQualityParameter.ActualName;
414        if (TabuChecker != null)
415          op.MoveTabuParameter.ActualName = TabuChecker.MoveTabuParameter.ActualName;
416      }
417    }
418    #endregion
419  }
420}
Note: See TracBrowser for help on using the repository browser.