Chapter 8 Theory and Practice of simulated Annealing (1121211), страница 7
Текст из файла (страница 7)
Local optimization techniques were previously thought to be unacceptableapproaches to these two problems. Johnson et al. (1991) also observes that for longrun lengths, simulated annealing outperforms the traditional techniques used to solvegraph coloring problems. However, simulated annealing did not compare well withtraditional techniques on the number partitioning problem except for small probleminstances. The third article in the series (not yet published) uses simulated annealingto approach the well-known traveling salesman problem.The Theory and Practice of Simulated Annealing307Koulamas et al.
(1994) focuses specifically on simulated annealing applied to applications in production/operations management and operations research. They discusstraditional problems such as single machine, flow shop and job shop scheduling, lotsizing, and traveling salesman problems as well as non-traditional problems to includegraph coloring and number partitioning. They conclude that simulated annealing is aneffective tool for solving many problems in operations research and that the degreeof accuracy that the algorithm achieves can be controlled by the practitioner, in termsof number of iterations and neighborhood functions (i.e., an increased number of iterations (outer loops) combined with increased number of searches at each iteration(inner loops) can result in solutions with a higher probability of converging to theoptimal solution).
Fleischer (1995) discusses simulated annealing from a historicaland evolutionary point of view in terms of solving difficult optimization problems. Hesummarizes on-going research and presents an application of simulated annealing tograph problems.The simulated annealing algorithm has proved to be a good technique for solving difficult discrete optimization problems.
In engineering optimization, simulatedannealing has emerged as an alternative tool to address problems that are difficult tosolve by conventional mathematical programming techniques. The algorithm’s majordisadvantage is that solving a complex system problem may be an extremely slow,albeit convergent process, using much more processor time than some conventionalalgorithms. Consequently, simulated annealing has not been widely embraced as anoptimization algorithm for engineering problems.
Attempts have been made to improvethe performance of the algorithm either by reducing the annealing length or changingthe generation and the acceptance mechanisms. However, these faster schemes, in general, do not inherit the property of escaping local minima. A more efficient way toreduce the processor time and make simulated annealing a more attractive alternativefor engineering problems is to add parallelism (e.g., see Hamma et al., 2000).
However, the implementation and efficiency of parallel simulated annealing algorithms aretypically problem-dependent. Leite et al. (1999) considers the evaluation of parallelschemes for engineering problems where the solution spaces may be very complexand highly constrained, with function evaluations varying from medium to high cost.In addition, they provide guidelines for selecting appropriate schemes for engineeringproblems. They also present an engineering problem with relatively low fitness evaluation cost and strong time constraints to demonstrate the lower bounds of applicabilityof parallel schemes.Many signal processing applications create optimization problems with multimodal and non-smooth cost functions.
Gradient methods are ineffective in thesesituations because of multiple local minima and the requirement to calculate gradients.Chen and Luk (1999) proposes an adaptive simulated annealing algorithm as a viableoptimization tool for addressing such difficult non-linear optimization problems. Theadaptive simulated annealing algorithm maintains the advantages of simulated annealing, but converges faster. Chen and Luk demonstrate the effectiveness of adaptivesimulated annealing with three signal processing applications: maximum likelihoodjoint channel and data estimation, infinite-impulse-response filter design and evaluation of minimum symbol-error-rate decision feedback equalizer. They conclude thatthe adaptive simulated annealing algorithm is a powerful global optimization tool forsolving such signal processing problems.308D. Henderson et al.Abramson et al.
(1999) describes the use of simulated annealing for solving theschool time tabling problem. They use the scheduling problem to highlight the performance of six different cooling schedules: the basic geometric cooling schedule,a scheme that uses multiple cooling rates, geometric reheating, enhanced geometricreheating, non-monotonic cooling, and reheating as a function of cost. The basic geometric cooling schedule found in van Laarhoven and Aarts (1987) is used as the baselineschedule for comparison purposes.
Experimental results suggest that using multiplecooling rates for a given problem yields better quality solutions in less time thanthe solutions produced by a single cooling schedule. They conclude that the coolingscheme that uses the phase transition temperature (i.e., when sub-parts of the combinatorial optimization problem are solved) in combination with the best solution to dateproduces the best results.Emden-Weinert and Proksch (1999) presents a study of a simulated annealingalgorithm for the airline crew-pairing problem based on an algorithm run-cutting formulation. They found that the algorithm run-time can be decreased and solution qualitycan be improved by using a problem-specific initial solution, relaxing constraints, combining simulated annealing with a problem-specific local improvement heuristic, andby conducting multiple independent runs.There is no question that simulated annealing can demand significant computational time to reach global minima.
Recent attempts to use parallel computing schemesto speed up simulated annealing have provided promising results. Chu et al. (1999)presents a new, efficient, and highly general-purpose parallel optimization methodbased upon simulated annealing that does not depend on the structure of the optimization problem being addressed. Their algorithm was used to analyze a network ofinteracting genes that control embryonic development and other fundamental biological processes. They use a two-stage procedure which monitors and pools performancestatistics obtained simultaneously from all processors and then mixes states at intervals to maintain a Boltzman-like distribution of costs. They demonstrate that theirparallel simulated annealing approach leads to nearly optimal parallel efficiency forcertain optimization problems.
In particular, the approach is appropriate when therelative effort required to compute the cost function is large compared to the relative communication effort between parallel machines for pooling statistics and mixingstates.Alrefaei and Andradottir (1999) presents a modified simulated annealing algorithm with a constant temperature to address discrete optimization problems and usetwo approaches to estimate an optimal solution to the problem. One approach estimates the optimal solution based on the state most visited versus the state last visited,while the other approach uses the best average estimated objective function value toestimate the optimal solution. Both approaches are guaranteed to converge almostsurely to the set of global optimal solutions under mild conditions. They compare performance of the modified simulated annealing algorithm to other forms of simulatedannealing used to solve discrete optimization problems.Creating effective neighborhood functions or neighborhood generation mechanisms is a critical element in designing efficient simulated annealing algorithmsfor discrete optimization problems.
Tian et al. (1999) investigates the applicationof simulated annealing to discrete optimization problems with a permutation property, such as the traveling salesman problem, the flow-shop scheduling problem,and the quadratic assignment problems. They focus on the neighborhood functionThe Theory and Practice of Simulated Annealing 309of the discrete optimization problem and in particular the generation mechanismfor the algorithm used to address the problem.
They introduce six types of perturbation scheme for generating random permutation solutions and prove that eachscheme satisfies asymptotic convergence requirements. The results of the experimental evaluations on the traveling salesman problem, the flow-shop schedulingproblem, and the quadratic assignment problem suggest that the efficiencies of theperturbation schemes are different for each problem type and solution space. Theyconclude that with the proper perturbation scheme, simulated annealing produces efficient solutions to different discrete optimization problems that possess a permutationproperty.Research continues to focus on the idea of simulated annealing applied to optimization of continuous functions.
Continuous global optimization is defined as theproblem of finding points on a bounded subset ofwhere some real valued functionf assumes its optimal (maximal or minimal) value. Application of simulated annealing to continuous optimization generally falls into two classes. The first approachclosely follows the original idea presented by Kirkpatrick et al. (1983) in that thealgorithm mimics the physical annealing process. The second approach describesthe annealing process with Langevin equations, where the global minimum is foundby solving stochastic differential equations (see Aluffi-Pentini et al., 1985). Gemanand Hwang (1986) proves that continuous optimization algorithms based on Langevinequations converge to the global optima.
Dekkers and Aarts (1991) proposes a thirdstochastic approach to address global optimization based on simulated annealing. Theirapproach is very similar to the formulation of simulated annealing as applied to discrete optimization problems. They extend the mathematical formulation of simulatedannealing to continuous optimization problems, and prove asymptotic convergence tothe set of global optima based on the equilibrium distribution of Markov chains. Theyalso discuss an implementation of the proposed algorithm and compares its performance with other well-known algorithms on a standard set of test functions from theliterature.55.1FUTURE DIRECTIONSGeneralized Hill Climbing AlgorithmsGeneralized Hill Climbing algorithms (GHC) (Jacobson et al., 1998) provide aframework for modeling local search algorithms used to address intractable discreteoptimization problems.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
