Chapter 8 Theory and Practice of simulated Annealing (1121211)
Текст из файла
Chapter 10THE THEORY AND PRACTICE OFSIMULATED ANNEALINGDarrall HendersonDepartment of Mathematical SciencesUnited States Military AcademyWest Point, NY 10996-1786, USAE-mail: darrall@stanfordalumni.orgSheldon H. JacobsonDepartment of Mechanical and Industrial EngineeringUniversity of Illinois at Urbana-Champaign1206 West Green Street, MC-244Urbana, Illinois 61801-2906, USAE-mail: shj@uiuc.eduAlan W. JohnsonDepartment of Mathematical SciencesUnited States Military AcademyWest Point, NY 10996-1786, USAE-mail: aa2895@usma.eduSimulated annealing is a popular local search meta-heuristic used to address discreteand, to a lesser extent, continuous optimization problems. The key feature of simulated annealingis that it provides a means to escape local optima by allowing hill-climbing moves (i.e., moveswhich worsen the objective function value) in hopes of finding a global optimum.
A brief historyof simulated annealing is presented, including a review of its application to discrete and continuous optimization problems. Convergence theory for simulated annealing is reviewed, as wellas recent advances in the analysis of finite time performance. Other local search algorithms arediscussed in terms of their relationship to simulated annealing. The chapter also presents practical guidelines for the implementation of simulated annealing in terms of cooling schedules,neighborhood functions, and appropriate applications.AbstractKeywords: Local Search Algorithms, Simulated Annealing, Heuristics, Meta-heuristics288D.
Henderson et al.1 BACKGROUND SURVEYSimulated annealing is a local search algorithm (meta-heuristic) capable of escapingfrom local optima. Its ease of implementation, convergence properties and its useof hill-climbing moves to escape local optima have made it a popular technique overthe past two decades.
It is typically used to address discrete, and to a lesser extent,continuous optimization problems. Recent survey articles that provide a good overviewof simulated annealing’s theoretical development and domains of application includeEglese (1990), Fleischer (1995), Koulamas et al. (1994), and Romeo and SangiovanniVincentelli (1991). Aarts and Korst (1989) and van Laarhoven and Aarts (1988) devoteentire books to the subject.
Aarts and Lenstra (1997) dedicate a chapter to simulatedannealing in their book on local search algorithms for discrete optimization problems.1.1History and MotivationSimulated annealing is so named because of its analogy to the process of physicalannealing with solids, in which a crystalline solid is heated and then allowed to coolvery slowly until it achieves its most regular possible crystal lattice configuration (i.e., itsminimum lattice energy state), and thus is free of crystal defects. If the cooling scheduleis sufficiently slow, the final configuration results in a solid with such superior structuralintegrity.
Simulated annealing establishes the connection between this type of thermodynamic behavior and the search for global minima for a discrete optimization problem.Furthermore, it provides an algorithmic means for exploiting such a connection.At each iteration of a simulated annealing algorithm applied to a discrete optimization problem, the objective function generates values for two solutions (the currentsolution and a newly selected solution) are compared. Improving solutions are alwaysaccepted, while a fraction of non-improving (inferior) solutions are accepted in thehope of escaping local optima in search of global optima.
The probability of accepting non-improving solutions depends on a temperature parameter, which is typicallynon-increasing with each iteration of the algorithm.The key algorithmic feature of simulated annealing is that it provides a meansto escape local optima by allowing hill-climbing moves (i.e., moves which worsenthe objective function value). As the temperature parameter is decreased to zero, hillclimbing moves occur less frequently, and the solution distribution associated with theinhomogeneous Markov chain that models the behavior of the algorithm converges to aform in which all the probability is concentrated on the set of globally optimal solutions(provided that the algorithm is convergent; otherwise the algorithm will converge toa local optimum, which may or not be globally optimal).1.2Definition of TermsTo describe the specific features of a simulated annealing algorithm for discrete optimization problems, several definitions are needed.
Let be the solution space (i.e., theset of all possible solutions). Letbe an objective function defined onthe solution space. The goal is to find a global minimum,such thatfor allThe objective function must be bounded to ensurethatexists. Defineto be the neighborhood function forTherefore,associated with every solution,are neighboring solutions,that can bereached in a single iteration of a local search algorithm.The Theory and Practice of Simulated Annealing289Simulated annealing starts with an initial solutionneighboring solutionis then generated (either randomly or using some pre-specified rule). Simulated annealing is based on the Metropolis acceptance criterion (Metropolis et al.,1953), which models how a thermodynamic system moves from the current solution(state)to a candidate solutionin which the energy content is beingminimized.
The candidate solution,is accepted as the current solution based on theacceptance probabilityDefineas the temperature parameter at (outer loop) iteration k, such thatThis acceptance probability is the basic element of the search mechanism in simulated annealing. If the temperature is reduced sufficiently slowly, then the systemcan reach an equilibrium (steady state) at each iteration k.
Letdenote the energies (objective function values) associated with solutionsandrespectively. This equilibrium follows the Boltzmann distribution, whichcan be described as the probability of the system being in statewith energyat temperature T such thatIf the probability of generating a candidate solutionwherethen a non-negative square stochastic matrixprobabilitiesfrom the neighbors of solutioncan be defined with transitionfor all solutionsand all iterations k = 1,2,...
andThesetransition probabilities define a sequence of solutions generated from an inhomogeneous Markov chain (Romeo and Sangiovanni-Vincentelli, 1991). Note that boldfacetype indicates matrix/vector notation, and all vectors are row vectors.290 D. Henderson et al.1.3 Statement of AlgorithmSimulated annealing is outlined in pseudo-code (Eglese, 1990).Select an initial solutionSelect the temperature change counter k=0Select a temperature cooling schedule,Select an initial temperatureSelect a repetition schedule,that defines the number of iterations executed at eachtemperature,RepeatSet repetition counter m = 0RepeatGenerate a solutionCalculateIfIfwith probabilityUntil stopping criterion is metThis simulated annealing formulation results intotal iterations being executed, where k corresponds to the value for at which the stoppingcriteria is met.
In addition, iffor all k, then the temperature changes at eachiteration.1.4Discrete versus Continuous ProblemsThe majority of the theoretical developments and application work with simulatedannealing has been for discrete optimization problems. However simulated annealinghas also been used as a tool to address problems in the continuous domain. There isconsiderable interest in using simulated annealing for global optimization over regionscontaining several local and global minima (due to inherent non-linearity of objectivefunctions). Fabian (1997) studies the performance of simulated annealing methods forfinding a global minimum of a function and Bohachevsky et al. (1986) presents a generalized simulated annealing algorithm for function optimization for use in statisticalapplications.
Optimization of continuous functions involves finding a candidate location by picking a direction from the current (incumbent) solution and a step size totake in this direction, and evaluating the function at the new (candidate) location. Ifthe function value of this candidate location is an improvement over the function valueof the incumbent location, then the candidate becomes the incumbent. This migration through local minima in search of a global minimum continues until the globalminimum is found or some termination criteria are reached.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
