Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. Vol. 13, pp. 533-549



Yüklə 329 Kb.
tarix30.10.2018
ölçüsü329 Kb.
#76087



  • Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. Vol. 13, pp. 533-549.

  • Hansen, P. 1986. The Steepest Ascent Mildest Descent Heuristic for Combinatorial Programming. Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy.



3 main strategies [7]:

  • 3 main strategies [7]:

    • Forbidding strategy: control what enters the tabu list
    • Freeing strategy: control what exits the tabu list and when
    • Short-term strategy: manage interplay between the forbidding strategy and freeing strategy to select trial solutions


Local search procedure

  • Local search procedure

  • Neighborhood structure

  • Aspiration conditions

  • Form of tabu moves

  • Addition of a tabu move

  • Maximum size of tabu list

  • Stopping rule



A chief way to exploit memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu) [1].

  • A chief way to exploit memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu) [1].

  • A neighborhood is constructed to identify adjacent solutions that can be reached from current solution [8].

  • The classification depends on the history of the search, and particularly on the recency or frequency that certain move or solution components, called attributes, have participated in generating past solutions [1].

  • A tabu list records forbidden moves, which are referred to as tabu moves [5].

  • Tabu restrictions are subject to an important exception. When a tabu move has a sufficiently attractive evaluation where it would result in a solution better than any visited so far, then its tabu classification may be overridden. A condition that allows such an override to occur is called an aspiration criterion[1].



Step 1: Choose an initial solution i in S. Set i* = i and k=0.

  • Step 1: Choose an initial solution i in S. Set i* = i and k=0.

  • Step 2: Set k=k+1 and generate a subset V* of solution in N(i,k) such that neither one of the Tabu conditions is violated or at least one of the aspiration conditions holds.

  • Step 3: Choose a best j in V* and set i=j.

  • Step 4: If f(i) < f(i*) then set i* = i.

  • Step 5: Update Tabu and aspiration conditions.

  • Step 6: If a stopping condition is met then stop. Else go to Step 2.



Some immediate stopping conditions could be the following [4]:

  • Some immediate stopping conditions could be the following [4]:

  • N(i, K+1) = 0. (no feasible solution in the neighborhood of solution i)

  • K is larger than the maximum number of iterations allowed.

  • The number of iterations since the last improvement of i* is larger than a specified number.

  • Evidence can be given that an optimum solution has been obtained.





Minimum spanning tree problem with constraints.

    • Minimum spanning tree problem with constraints.
    • Objective: Connects all nodes with minimum costs


New cost = 75 (iteration 2)

  • New cost = 75 (iteration 2)

  • ( new best so far solution)



* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

  • * A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

  • Iteration 3 new cost = 85



* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

  • * A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)

  • Iteration 4 new cost = 70 Override tabu status



Optimal Solution

  • Optimal Solution

  • Cost = 70

  • Additional iterations only find

  • inferior solutions



Long term memory

  • Long term memory

  • We’ll see how this information is used in a minute



When search not going well; e.g., haven’t found an improving neighbor in some iterations

  • When search not going well; e.g., haven’t found an improving neighbor in some iterations

  • New best solutions become rare



Intensify search in promising regions

  • Intensify search in promising regions

  • When to intensify vs. diversify: interesting; further topic we will not cover



Pros:

  • Pros:

    • Allows non-improving solution to be accepted in order to escape from a local optimum (true too for GA, SimAnn, AntColOpt)
    • The use of Tabu list (helps avoid cycles and move reversal)
    • Can be applied to both discrete and continuous solution spaces
    • For larger and more difficult problems (scheduling, quadratic assignment and vehicle routing), tabu search obtains solutions that rival and often surpass the best solutions previously found by other approaches [1].
  • Cons:

    • Too many parameters to be determined
    • Number of iterations could be very large
    • Global optimum may not be found, depends on parameter settings (also true of GA, SimAnn, AntColOpt)


[1] Glover, F., Kelly, J. P., and Laguna, M. 1995. Genetic Algorithms and Tabu Search: Hybrids for Optimization. Computers and Operations Research. Vol. 22, No. 1, pp. 111 – 134.

  • [1] Glover, F., Kelly, J. P., and Laguna, M. 1995. Genetic Algorithms and Tabu Search: Hybrids for Optimization. Computers and Operations Research. Vol. 22, No. 1, pp. 111 – 134.

  • [2] Glover, F. and Laguna, M. 1997. Tabu Search. Norwell, MA: Kluwer Academic Publishers.

  • [3] Hanafi, S. 2001. On the Convergence of Tabu Search. Journal of Heuristics. Vol. 7, pp. 47 – 58.

  • [4] Hertz, A., Taillard, E. and Werra, D. A Tutorial on Tabu Search. Accessed on April 14, 2005: http://www.cs.colostate.edu/~whitley/CS640/hertz92tutorial.pdf

  • [5] Hillier, F.S. and Lieberman, G.J. 2005. Introduction to Operations Research. New York, NY: McGraw-Hill. 8th Ed.

  • [6] Ji, M. and Tang, H. 2004. Global Optimizations and Tabu Search Based on Mamory. Applied Mathematics and Computation. Vol. 159, pp. 449 – 457.

  • [7] Pham, D.T. and Karaboga, D. 2000. Intelligent Optimisation Techniques – Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks. London: Springer-Verlag.

  • [8] Reeves, C.R. 1993. Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons, Inc.



Yüklə 329 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2022
rəhbərliyinə müraciət

    Ana səhifə