Stuck at the Bottom of the Nearest Valley
The simplest way to optimize something is to start with a solution, look at small changes to it, and keep any change that makes things better. This is local search, or hill climbing if you are maximizing. For a traveling salesman tour, a small change might be reversing a segment of the route. You repeat until no small change helps.
The problem is where this process stops. It stops at a local optimum, a solution that is better than all of its neighbors but possibly much worse than the best solution overall. On a smooth bowl-shaped landscape that is fine. On the rugged landscapes of real combinatorial problems, with millions of small valleys, a greedy search falls into the first one it finds and never leaves.
Simulated annealing and tabu search both start from this same local search loop. They differ in how they allow it to escape. Annealing escapes by accepting bad moves at random, with a probability that shrinks over time. Tabu search escapes by remembering where it has been and refusing to go back.
Annealing in Metals and in Code
Annealing is an old metallurgical process. A metal is heated and then cooled slowly, which gives its atoms time to settle into an ordered, low-energy crystal structure. Cool it too fast and the atoms freeze in a disordered state full of defects.
In 1953, Nicholas Metropolis and colleagues published a Monte Carlo method for simulating a physical system at a fixed temperature. A random change to the system is proposed. If it lowers the energy, it is accepted. If it raises the energy by some amount Δ, it is accepted with probability exp(−Δ/T), where T is the temperature. At high temperature almost everything is accepted; at low temperature, uphill moves become rare.
Scott Kirkpatrick, C. Daniel Gelatt and Mario Vecchi, working at IBM, turned this into an optimization method in a 1983 paper in Science titled «Optimization by Simulated Annealing.» Their idea was to treat the cost of a solution as energy and to lower T gradually during the search. Early on, the algorithm wanders across the landscape almost freely. Later, it behaves more and more like plain hill climbing. Vladimír Černý reached the same idea independently and published it in 1985 in the Journal of Optimization Theory and Applications, applied to the traveling salesman problem.
The appeal is that the algorithm needs only a cost function and a way to generate neighbors. The same twenty lines of code work on permutations, graphs and bit strings.
The Cooling Schedule
Most of the practical difficulty of simulated annealing is one choice: how fast to lower the temperature. The common answer is geometric cooling, where T is multiplied by a constant such as 0.95 after a fixed number of moves. You also need a starting temperature high enough that most uphill moves are accepted at first, and a rule for when to stop.
There is a theory behind this, and it is unusually clean. Stuart and Donald Geman showed in 1984 that if the temperature falls no faster than a constant divided by the logarithm of the iteration count, the search converges to a global optimum. Bruce Hajek sharpened this in 1988 with a necessary and sufficient condition: the constant must be at least the depth of the deepest local minimum that is not global, meaning the largest uphill climb needed to escape a trap.
The catch is that logarithmic cooling is extremely slow. To halve the temperature you must square the number of iterations. For a realistic problem, the guaranteed schedule takes longer than exhaustive search would. So practitioners use fast schedules that carry no guarantee, and they tune them by experiment. The convergence theorem tells you the method is not arbitrary, but it does not tell you how to run it.
Case: Placing Circuits on a Chip
The first serious application was chip design. Placing thousands of circuit components on a chip so that the wires between them are short is a huge combinatorial problem. Their Science paper reported results on partitioning, placement and wiring of electronic systems, along with traveling salesman instances of several thousand cities.
Carl Sechen and Alberto Sangiovanni-Vincentelli followed with TimberWolf, published in the IEEE Journal of Solid-State Circuits in 1985. It used annealing for standard cell, macro cell and gate array placement, plus global routing. On industrial circuits, they reported area savings of 15 to 62 percent over the layout programs in use at the time.
Not every evaluation was so favorable. David Johnson, Cecilia Aragon, Lyle McGeoch and Catherine Schevon ran a long experimental study published in Operations Research in 1989. On graph partitioning, annealing beat the classic Kernighan-Lin heuristic on large sparse random graphs, but on graphs with geometric structure Kernighan-Lin won by a substantial margin. The authors described annealing’s success as mixed. That conclusion has held up: annealing is a dependable general method, and a good problem-specific heuristic often beats it.
Tabu Search and Short-Term Memory
Fred Glover introduced the term tabu search in a 1986 paper in Computers and Operations Research, «Future Paths for Integer Programming and Links to Artificial Intelligence,» and laid out its principles in a two-part article in the ORSA Journal on Computing starting in 1989. He described it as a metaheuristic superimposed on another heuristic, one that gets past local optimality by forbidding certain moves.
The mechanism works like this. At each step, tabu search examines the neighborhood and moves to the best neighbor that is not forbidden, even if that neighbor is worse than the current solution. This alone would make the search cycle forever, stepping out of a valley and straight back in. To prevent that, it keeps a tabu list of recent moves, or attributes of recent moves, and forbids reversing them for a certain number of iterations, called the tabu tenure.
If the search just swapped jobs A and B, swapping them back is tabu for, say, the next ten iterations. The search is forced to keep moving away from the local optimum it just left. What gets stored is usually an attribute, not a full solution, because attributes are cheap to compare.
This basic version needs no randomness. It always takes the best allowed move, while annealing samples one random neighbor at a time.
Aspiration, Intensification and Diversification
Forbidding moves by attribute has a side effect. Sometimes a tabu move would lead to a solution better than anything found so far, and the tabu list blocks it only because of a coincidence of attributes. Aspiration criteria fix this. The most common one says a tabu move is allowed if it produces a new best solution.
Glover also described longer-term memory. Intensification strategies return to regions where good solutions were found and search them more carefully, for example by fixing features that appear in most of the elite solutions. Diversification strategies push the search toward regions it has rarely visited, often by penalizing moves that have been used frequently. A frequency count per attribute is enough for both.
So tabu search is closer to a framework than a single algorithm. A competitive implementation usually combines tabu lists, aspiration, frequency memory and restarts from elite solutions, tuned to the problem.
Case: Job Shops and Quadratic Assignment
Two results show how much a well-designed tabu search can do. Éric Taillard published Robust Tabu Search for the quadratic assignment problem in Parallel Computing in 1991. Instead of a fixed tabu tenure, it draws the tenure at random from a range, which removes the need to tune one exact value and makes cycling less likely. Robust Tabu Search became a standard reference method for the quadratic assignment problem, and later algorithms often use it as their local improvement step.
Eugeniusz Nowicki and Czesław Smutnicki published «A Fast Taboo Search Algorithm for the Job Shop Problem» in Management Science in 1996. Their key contribution was a small, carefully chosen neighborhood: only swaps of adjacent operations on the critical path of the schedule, which are the only swaps that can shorten the total completion time. With a tiny neighborhood, each step is fast, and tabu memory keeps the search from circling. Their algorithm and its successor, i-TSAB, were for a long time the state of the art for minimizing makespan on standard job shop benchmarks.
In both cases, most of the strength came from the problem structure. The tabu mechanism let the search exploit it without getting stuck.
Randomness Versus Memory
The two methods make an opposite bet. Simulated annealing assumes that random uphill moves, accepted less and less often, will shake the search loose from traps. Tabu search assumes that remembering recent history is enough to avoid revisiting the same traps, and it uses that memory to drive the search deliberately.
In practice, annealing is easier to implement and needs only a cooling schedule. It also works well when neighborhoods are huge and only a random sample of moves can be evaluated. Tabu search evaluates the whole neighborhood, or a large part of it, at every step, so it fits problems where neighborhoods are small or can be scored incrementally.
The two are often combined. Annealing can use a short tabu list to avoid immediate reversals, and tabu search can add random tenure or restarts. Both also serve as the local improvement step inside genetic algorithms, where the population explores broadly and the single-solution method refines the best individuals.
A Final Observation
The convergence theorem for simulated annealing is one of the cleanest results in the field, and almost nobody runs the algorithm the way the theorem requires. The useful version is the one that throws away its own guarantee. Tabu search never had a guarantee, and it became one of the strongest tools for scheduling anyway. For hard combinatorial problems, the better question to ask about a method is not whether it will find the optimum but how it decides to accept a worse solution. A search that never takes a bad step stops in the first valley. Which bad steps it takes, and why, decides most of what it can find.
By: Max Johnson B.
Deja una respuesta