An adaptive simulated annealing algorithm for global optimization over continuous variables

A method is presented for attempting global minimization for a function of continuous variables subject to constraints. The method, calledAdaptive Simulated Annealing (ASA), is distinguished by the fact that the fixed temperature schedules and step generation routines that characterize other implementations are here replaced by heuristic-based methods that effectively eliminate the dependence of the algorithm's overall performance on user-specified control parameters. A parallelprocessing version of ASA that gives increased efficiency is presented and applied to two standard problems for illustration and comparison.This research was supported by the University Research Initiative of the U.S. Army Research Office.     

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.     

Molecular conformation on the CM-5 by parallel two-level simulated annealing

In this paper, we propose a new kind of simulated annealing algorithm calledtwo-level simulated annealing for solving certain class of hard combinatorial optimization problems. This two-level simulated annealing algorithm is less likely to get stuck at a non-global minimizer than conventional simulated annealing algorithms. We also propose a parallel version of our two-level simulated annealing algorithm and discuss its efficiency. This new technique is then applied to the Molecular Conformation problem in 3 dimensional Euclidean space. Extensive computational results on Thinking Machines CM-5 are presented. With the full Lennard-Jones potential function, we were able to get satisfactory results for problems for cluster sizes as large as 100,000. A peak rate of over 0.8 giga flop per second in 64-bit operations was sustained on a partition with 512 processing elements. To the best of our knowledge, ground states of Lennard-Jones clusters of size as large as these have never been reported before.Also a researcher at the Army High Performance Computing Research Center, University of Minnesota, Minneapolis, MN 55415     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

Cybernetic optimization by simulated annealing: Accelerating convergence by parallel processing and probabilistic feedback control

The convergence of the simulated annealing algorithm is accelerated by a probabilistic feedback control scheme. This scheme uses two or more parallel processors to solve the same or related combinatorial optimization problems and are coupled by a probabilistic measure of quality (PMQ). The PMQ is used to generate an error signal for use in feedback control. Control over the search process is achieved by using the error signal to modulate the temperature parameter. Other aspects of control theory, such as the system gain and its effects on system performance, are described. Theoretical and experimental results show that such a scheme increases the steadystate probability of the globally optimal solutions.     

A parallel method for finding the global minimum of univariate functions

We describe a new parallel method for solving global optimization problems. The formulation of the decision rules of this method is presented. We examine convergence conditions of the proposed algorithm and establish conditions which guarantee a considerable speedup with respect to the sequential version of the algorithm. We also present some numerical experiments executed on Alliant FX/80 for one class of multiextremal functions.The authors are greatly indebted to R. G. Strongin who stimulated the fulfillment of this research. They also would like to thank the anonymous referees for their useful suggestions.The research of the first author was partially supported by Grant 9494/NC/89 from the Italian Government under the Italian-Soviet Agreement about the Cultural and Scientific Exchange in 1990–1991. He thanks the Systems Department, University of Calabria, where he was a Visitor.     

Isotropic effective energy simulated annealing searches for low energy molecular cluster states

The search for low energy states of molecular clusters is associated with the study of molecular conformation and especially protein folding. This paper describes a new global minimization algorithm which is effective and efficient for finding low energy states and hence stable structures of molecular clusters. The algorithm combines simulated annealing with a class of effective energy functions which are transformed from the original energy function based on the theory of renormalization groups. The algorithm converges to low energy states asymptotically, and is more efficient than a general simulated annealing method.     

Homogeneous grouping of nuclear fuel cans through simulated annealing and tabu search

Collections of cans containing nuclear fuel have to be grouped in batches that are as homogeneous as possible with respect to several criteria. This highly combinatorial problem, which can be described as grouping or clustering, is tackled using simulated annealing and tabu search. Both approaches are submitted to extensive experimentation on a real data set and several artificial ones. Two variants of the basic approaches called Locally optimized simulated annealing and Tabu search with variable offset are also tested. Sensitivity to parameter choice and to problem size are investigated. All four algorithms outperform a local search heuristic previously proposed in the literature; on the class of instances dealt with, a remarkably stable ranking of the four algorithms emerges.     

Variants of simulated annealing for the examination timetabling problem

This paper is concerned with the use of simulated annealing in the solution of the multi-objective examination timetabling problem. The solution method proposed optimizes groups of objectives in different phases. Some decisions from earlier phases may be altered later as long as the solution quality with respect to earlier phases does not deteriorate. However, such limitations may disconnect the solution space, thereby causing optimal or near-optimal solutions to be missed. Three variants of our basic simulated annealing implementation which are designed to overcome this problem are proposed and compared using real university data as well as artificial data sets. The underlying principles and conclusions stemming from the use of this method are generally applicable to many other multi-objective type problems.     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

A simulated annealing driven multi-start algorithm for bound constrained global optimization

A derivative-free simulated annealing driven multi-start algorithm for continuous global optimization is presented. We first propose a trial point generation scheme in continuous simulated annealing which eliminates the need for the gradient-based trial point generation. We then suitably embed the multi-start procedure within the simulated annealing algorithm. We modify the derivative-free pattern search method and use it as the local search in the multi-start procedure. We study the convergence properties of the algorithm and test its performance on a set of 50 problems. Numerical results are presented which show the robustness of the algorithm. Numerical comparisons with a gradient-based simulated annealing algorithm and three population-based global optimization algorithms show that the new algorithm could offer a reasonable alternative to many currently available global optimization algorithms, specially for problems requiring ‘direct search’ type algorithm.     

一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

A statistical analysis of simulated annealing applied to the p-median problem

We present a statistical analysis of simulated annealing applied to the p-median problem. The algorithm we use combines elements of the vertex substitution method of Teitz and Bart with the general methodology of simulated annealing. The cooling schedule adopted incorporates the notion of temperature adjustments rather than just temperature reductions. Computational results are given for test problems ranging from 100 to 900 vertices, retrieved from Beasley's OR-Library for combinatorial problems. Each problem was run for a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the optimal solution was 1.62%, after all runs for each of the test problems were computed. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stochastic comparison algorithm for continuous optimization with estimation

The problem of stochastic optimization for arbitrary objective functions presents a dual challenge. First, one needs to repeatedly estimate the objective function; when no closed-form expression is available, this is only possible through simulation. Second, one has to face the possibility of determining local, rather than global, optima. In this paper, we show how the stochastic comparison approach recently proposed in Ref. 1 for discrete optimization can be used in continuous optimization. We prove that the continuous stochastic comparison algorithm converges to an -neighborhood of the global optimum for any >0. Several applications of this approach to problems with different features are provided and compared to simulated annealing and gradient descent algorithms.This work was supported in part by the National Science Foundation under Grants EID-92-12122 and ECS-88-01912, and by a Grant from United Technologies/Otis Elevator Company.     

An algorithm for global optimization of Lipschitz continuous functions

An algorithm is presented which locates the global minimum or maximum of a function satisfying a Lipschitz condition. The algorithm uses lower bound functions defined on a partitioned domain to generate a sequence of lower bounds for the global minimum. Convergence is proved, and some numerical results are presented.     

Asymptotic convergence of a simulated annealing algorithm for multiobjective optimization problems

In this paper we consider a simulated annealing algorithm for multiobjective optimization problems. With a suitable choice of the acceptance probabilities, the algorithm is shown to converge asymptotically, that is, the Markov chain that describes the algorithm converges with probability one to the Pareto optimal set.     

Optimization methods for computing global minima of nonconvex potential energy functions

The minimization of potential energy functions plays an important role in the determination of ground states or stable states of certain classes of molecular clusters and proteins. In this paper we introduce some of the most commonly used potential energy functions and discuss different optimization methods used in the minimization of nonconvex potential energy functions. A very complete bibliography is also given.Also a researcher at the Army High Performance Computing Research Center, University of Minnesota, Minneapolis, MN 55415     

Comparative analysis of the cutting angle and simulated annealing methods in global optimization

This article presents a comparative analysis of two methods of global optimization: the simulated annealing method and a method based on a combination of the cutting angle method and a local search. This analysis is carried out using results of numerical experiments. These results demonstrate that the combined method is more effective than the simulated annealing method.