Simulated Annealing Algorithms for Continuous Global Optimization: Convergence Conditions

In this paper, simulated annealing algorithms for continuous global optimization are considered. After a review of recent convergence results from the literature, a class of algorithms is presented for which strong convergence results can be proved without introducing assumptions which are too restrictive. The main idea of the paper is that of relating both the temperature value and the support dimension of the next candidate point, so that they are small at points with function value close to the current record and bounded away from zero otherwise.     

Convergence of the Simulated Annealing Algorithm for Continuous Global Optimization

A class of simulated annealing algorithms for continuous global optimization is considered in this paper. The global convergence property is analyzed with respect to the objective value sequence and the minimum objective value sequence induced by simulated annealing algorithms. The convergence analysis provides the appropriate conditions on both the generation probability density function and the temperature updating function. Different forms of temperature updating functions are obtained with respect to different kinds of generation probability density functions, leading to different types of simulated annealing algorithms which all guarantee the convergence to the global optimum.     

Derivative-Free Filter Simulated Annealing Method for Constrained Continuous Global Optimization

In this paper, a simulated-annealing-based method called Filter Simulated Annealing (FSA) method is proposed to deal with the constrained global optimization problem. The considered problem is reformulated so as to take the form of optimizing two functions, the objective function and the constraint violation function. Then, the FSA method is applied to solve the reformulated problem. The FSA method invokes a multi-start diversification scheme in order to achieve an efficient exploration process. To deal with the considered problem, a filter-set-based procedure is built in the FSA structure. Finally, an intensification scheme is applied as a final stage of the proposed method in order to overcome the slow convergence of SA-based methods. The computational results obtained by the FSA method are promising and show a superior performance of the proposed method, which is a point-to-point method, against population-based methods.     

Aspiration Based Simulated Annealing Algorithm

An aspiration based simulated annealing algorithm for continuousvariables has been proposed. The new algorithm is similar to the one givenby Dekkers and Aarts (1991) except that a kind of memory is introduced intothe procedure with a self-regulatory mechanism. The algorithm has beenapplied to a set of standard global optimization problems and a number ofmore difficult, complex, practical problems and its performance comparedwith that of the algorithm of Dekkers and Aarts (1991). The new algorithmappears to offer a useful alternative to some of the currently availablestochastic algorithms for global optimization.     

Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms to address intractable discrete optimization problems. This paper introduces a measure for determining the expected number of iterations to visit a predetermined objective function level, given that an inferior objective function level has been reached in a finite number of iterations. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using this measure. S²A uses a fixed cooling schedule during the algorithm execution. Though S²A is probably nonconvergent, its finite-time performance can be assessed using the finite-time performance measure defined in this paper.     

Performance Analysis of Cyclical Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Measures for assessing the finite-time performance of GHC algorithms have been developed using this framework, including the expected number of iterations to visit a predetermined objective function value level. This paper analyzes how the expected number of iterations to visit a predetermined objective function value level can be estimated for cyclical simulated annealing. Cyclical simulated annealing uses a cooling schedule that cycles through a set of temperature values. Computational results with traveling salesman problem instances taken from TSPLIB show how the expected number of iterations to visit solutions with predetermined objective function levels can be estimated for cyclical simulated annealing.AMS 2000 Subject Classification 90-08 Computational Methods: Local Search, 90C59 Heuristics: Simulated Annealing     

Convergence of a Simulated Annealing Algorithm for Continuous Global Optimization

In this paper a simulated annealing algorithm for continuous global optimization will be considered. The algorithm, in which a cooling schedule based on the distance between the function value in the current point and an estimate of the global optimum value is employed, has been first introduced in Bohachevsky, Johnson and Stein (1986) [2], but without any proof of convergence. Here it will be proved that, under suitable assumptions, the algorithm is convergent     

Finite-Time Performance Analysis of Static Simulated Annealing Algorithms

Generalized hill climbing (GHC) algorithms provide a framework for modeling local search algorithms for addressing intractable discrete optimization problems. Current theoretical results are based on the assumption that the goal when addressing such problems is to find a globally optimal solution. However, from a practical point of view, solutions that are close enough to a globally optimal solution (where close enough is measured in terms of the objective function value) for a discrete optimization problem may be acceptable. This paper introduces -acceptable solutions, where is a value greater than or equal to the globally optimal objective function value. Moreover, measures for assessing the finite-time performance of GHC algorithms, in terms of identifying -acceptable solutions, are defined. A variation of simulated annealing (SA), termed static simulated annealing (S²A), is analyzed using these measures. S²A uses a fixed cooling schedule during the algorithm's execution. Though S²A is provably nonconvergent, its finite-time performance can be assessed using the finite-time performance measures defined in terms of identifying -acceptable solutions. Computational results with a randomly generated instance of the traveling salesman problem are reported to illustrate the results presented. These results show that upper and lower estimates for the number of iterations to reach a -acceptable solution within a specified number of iterations can be obtained, and that these estimates are most accurate for moderate and high fixed temperature values for the S²A algorithm.     

Pareto Simulated Annealing for Fuzzy Multi-Objective Combinatorial Optimization

The paper presents a metaheuristic method for solving fuzzy multi-objective combinatorial optimization problems. It extends the Pareto simulated annealing (PSA) method proposed originally for the crisp multi-objective combinatorial (MOCO) problems and is called fuzzy Pareto simulated annealing (FPSA). The method does not transform the original fuzzy MOCO problem to an auxiliary deterministic problem but works in the original fuzzy objective space. Its goal is to find a set of approximately efficient solutions being a good approximation of the whole set of efficient solutions defined in the fuzzy objective space. The extension of PSA to FPSA requires the definition of the dominance in the fuzzy objective space, modification of rules for calculating probability of accepting a new solution and application of a defuzzification operator for updating the average position of a solution in the objective space. The use of the FPSA method is illustrated by its application to an agricultural multi-objective project scheduling problem.     

并行机问题的模拟退火调度算法研究

研究了一类调度目标是最小化最大完成时间的并行机调度问题.考虑到此问题的NP-hard特性,引入模拟退火算法思想以获取高质量近优解.分析了现有此问题模拟退火算法的缺陷,定义了关键机器和非关键机器,设计了一个包含局部优化的模拟退火算法.除了交换变换,还引入插入变换以改变各子调度中作业个数.大量的随机数据实验用于验证算法解的质量和计算效率,实验结果表明该模拟退火算法能够在有限时间内为大规模问题求得高质量满意解.     

New Reflection Generator for Simulated Annealing in Mixed-Integer/Continuous Global Optimization

To reduce the well-known jamming problem in global optimization algorithms, we propose a new generator for the simulated annealing algorithm based on the idea of reflection. Furthermore, we give conditions under which the sequence of points generated by this simulated annealing algorithm converges in probability to the global optimum for mixed-integer/continuous global optimization problems. Finally, we present numerical results on some artificial test problems as well as on a composite structural design problem.     

Annealing Algorithms for Multisource Absolute Location Problems on Graph

A methodology is presented for applying annealing techniques tomultisource absolute location problems on graph. Two kinds ofobjective functions are considered: barycenters and centers. Aclass of new algorithms is described: its development startsfrom the iterative cluster-and-locate algorithm and reliesupon the relaxation of the integrality constraints onallocation variables. Experimental results are reported.     

基于模拟退火算法的矩形优化排样问题的研究

考虑了一种矩形优化排样系统中遗传算法和模拟退火算法的结合算法.首先建立了该系统的通用数学模型.然后给出了求解该问题的遗传模拟退火算法.最后用VC++6.0模拟算例的结果表明该算法是一种行之有效的方法.     

基于模拟退火的CRS算法

本文是对非线性规划问题提出的一种算法,该算法把模拟退火算法应用到CRS算法中,根据模拟退火算法每一次迭代都体现集中和扩散两个策略的平衡的特点,使CRS算法更能够搜索到全局最优解,而不会陷入局部最优解。最后把提出的算法应用到两个典型的函数优化问题中,结果表明,算法是可行的、有效的     

Global optimization and simulated annealing

In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of ⁿ in which some real valued functionf assumes its optimal (maximal or minimal) value.We present a stochastic approach which is based on the simulated annealing algorithm. The approach closely follows the formulation of the simulated annealing algorithm as originally given for discrete optimization problems. The mathematical formulation is extended to continuous optimization problems, and we prove asymptotic convergence to the set of global optima. Furthermore, we discuss an implementation of the algorithm and compare its performance with other well-known algorithms. The performance evaluation is carried out for a standard set of test functions from the literature.     

A Controlled Random Search Technique Incorporating the Simulated Annealing Concept for Solving Integer and Mixed Integer Global Optimization Problems

In this paper, a computational algorithm, named RST2ANU algorithm, has been developed for solving integer and mixed integer global optimization problems. This algorithm, which primarily is based on the original controlled random search approach of Price [22i], incorporates a simulated annealing type acceptance criterion in its working so that not only downhill moves but also occasional uphill moves can be accepted. In its working it employs a special truncation procedure which not only ensures that the integer restrictions imposed on the decision variables are satisfied, but also creates greater possibilities for the search leading to a global optimal solution. The reliability and efficiency of the proposed RST2ANU algorithm has been demonstrated on thirty integer and mixed integer optimization problems taken from the literature. The performance of the algorithm has been compared with the performance of the corresponding purely controlled random search based algorithm as well as the standard simulated annealing algorithm. The performance of the method on mathematical models of three realistic problems has also been demonstrated.     

基于模拟退火算法的城市物流多目标配送车辆路径优化研究

基于传统模拟退火算法,通过引入记忆函数、结合GIS手段,运用SPSS聚类分析来确定初始化状态种群、多种群并行机制和新状态的产生.依据种群规模采用不同产生算法来改进算法,并将改进算法应用于城市物流中确定的多目标车辆路径优化问题,验证了算法的可行性与实用价值.此外,改进算法分别与传统模拟退火算法和GIS图解法相比较,优化效率和准确率都得到了很大的提高.     

非光滑总体优化的区间算法[英文]

本文利用区间工具及目标函数的特殊导数，给出一个非光滑总体优化的区间算法，该算法提供了目标函数总体极小值及总体极小点的取值界限（在给定的精度范围内）。我们也将算法推广到并行计算中。数值实验表明本文方法是可靠和有效的。     

基于模拟退火算法的盲均衡器设计

盲均衡技术是不需要训练序列的自适应均衡技术.该项技术可以消除由于通信信道失真造成的码间干扰.本文的目的是对盲均衡技术作一介绍,包括对广泛应用的最大归一化累积量判据的介绍和讨论,并在此基础上提出了基于模拟退火技术的设计方法,最后,对这种盲均衡器骑行了仿真,并得出了相应的结论.     

Computing the Initial Temperature of Simulated Annealing

The classical version of simulated annealing is based on a cooling schedule. Generally, the initial temperature is set such that the acceptance ratio of bad moves is equal to a certain value ₀. In this paper, we first propose a simple algorithm to compute a temperature which is compatible with a given acceptance ratio. Then, we study the properties of the acceptance probability. It is shown that this function is convex for low temperatures and concave for high temperatures. We also provide a lower bound for the number of plateaux of a simulated annealing based on a geometric cooling schedule. Finally, many numerical experiments are reported.