8
TABU Annealing: An Efficient and Scalable Strategy for Document Retrieval*
This chapter presents a new method, TABU annealing, which reduces the limitations of TABU and simulated annealing (SA) and shows the results of some comparative studies that evaluated the relative performance of different optimization techniques on the same problem.
8.1Simulated Annealing
Simulated annealing allows moves in less good goal directions once in a while to escape local minima. Annealing is the process of cooling material in a heat bath. If the solid material is heated past its melting point and then cooled down in a solid state, the structural properties of the cooled solid depend on the rate of cooling. Slow cooling leads to strong, large crystals. Fast cooling results in imperfections.
We have a problem with maximization over a set of feasible solutions and a relevancy function f calculated for all feasible solutions. The optimal solution could be calculated by exhaustively searching the space, calculating f(s), and selecting the maximum. In practice, the feasible solution space is often too large for this to be practical. Local optimization solves this by searching only a small subset of the solution space. This can be achieved by defining a neighborhood structure on the space and searching only the neighborhood of the current solution for an improvement. If there is no improvement, the current solution is an approximate optimal solution. If there is an improvement, the current solution is replaced by the improvement, and then the process is repeated. In simulated annealing, the neighborhood is searched in a random way. Accept a neighbor whose relevancy is worse than the current solution depending on a control parameter called a temperature.
Metropolis Monte Carlo et al. (1953) first proposed the standard simulated annealing approach. Metropolis proposed the equation of state calculations by fast computing machines. Then the Metropolis Monte Carlo integration algorithm was generalized by the algorithm of Kirkpatrick et al. (1982) to include a temperature schedule for efficient searching. It is reported that SA is very useful for several types of combinatorial optimization to reduce the computation time. The minimum temperature is generally determined by the acceptance ratio during the SA process—that is, the temperature is decreased until the system freezes. Jonathan Rose et al. (1990) proposed a new method for estimating the maximum temperature by using equilibrium dynamics, and Romeo et al. proposed an efficient cooling method, but these methods use experimental parameters, and tuning of these parameters is necessary.
An annealing algorithm needs four basic components:
1.Configurations: A model of what a legal selection (configuration) is. These represent the possible problem solutions over which we will search for a good answer.
2.Move set: A set of allowable moves that will permit us to reach all feasible patterns and one that is easy to compute. These moves are the computations we must perform to move from pattern to pattern as annealing proceeds.
3.Fitness function: To measure how well any given pattern is.
4.Cooling schedule: To anneal the problem from a random solution to a good, frozen placement; specifically, we need a starting hot temperature (or a heuristic for determining a starting temperature for the current problem) and rules to determine when the current temperature is low, by how much to decrease the temperature to low, and when annealing should be terminated.
8.1.1The Simulated Annealing Algorithm
1.Select an initial temperature t0 (a large number).
2.Select an ...
