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.     

Investigation of temperature parallel simulated annealing for optimizing continuous functions with application to hyperspectral tomography

The simulated annealing (SA) algorithm is a well-established optimization technique which has found applications in many research areas. However, the SA algorithm is limited in its application due to the high computational cost and the difficulties in determining the annealing schedule. This paper demonstrates that the temperature parallel simulated annealing (TPSA) algorithm, a parallel implementation of the SA algorithm, shows great promise to overcome these limitations when applied to continuous functions. The TPSA algorithm greatly reduces the computational time due to its parallel nature, and avoids the determination of the annealing schedule by fixing the temperatures during the annealing process. The main contributions of this paper are threefold. First, this paper explains a simple and effective way to determine the temperatures by applying the concept of critical temperature (T_C). Second, this paper presents systematic tests of the TPSA algorithm on various continuous functions, demonstrating comparable performance as well-established sequential SA algorithms. Third, this paper demonstrates the application of the TPSA algorithm on a difficult practical inverse problem, namely the hyperspectral tomography problem. The results and conclusions presented in this work provide are expected to be useful for the further development and expanded applications of the TPSA algorithm.     

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     

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.     

Parallel simulated annealing

This article introduces the notion of restricted parallelism for networks, a generalization of the unlimited parallelism for Boltzmann machines. The convergence of the annealing algorithm in the restricted parallel form is established, for an arbitrary network.     

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.     

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.     

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.     

A simulated annealing approach to the nesting problem in the textile manufacturing industry

The nesting problem in the textile industry is the problem of placing a set of irregularly shaped pieces (calledstencils) on a rectangularsurface, such that no stencils overlap and that thetrim loss produced when cutting out the stencils is minimized. Certain constraints may put restrictions on the positions and orientation of some stencils in the layout but, in general, the problem is unconstrained. In this paper, an algorithmic approach using simulated annealing is presented covering a wide variety of constraints which may occur in the industrial manufacturing process. The algorithm has high performance, is quite simple to use, is extensible with respect to the set of constraints to be met, and is easy to implement.The work of this author was supported in part by grant Le 491/3-1 from the German Research Association (DFG).     

Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

The vehicle routing problem (VRP) under capacity and distance restrictions involves the design of a set of minimum cost delivery routes, originating and terminating at a central depot, which services a set of customers. Each customer must be supplied exactly once by one vehicle route. The total demand of any vehicle must not exceed the vehicle capacity. The total length of any route must not exceed a pre-specified bound. Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated. A special data structure for the tabu search algorithm is implemented which has reduced notably the computational time by more than 50%. An estimate for the tabu list size is statistically derived. Computational results are reported on a sample of seventeen bench-mark test problems from the literature and nine randomly generated problems. The new methods improve significantly both the number of vehicles used and the total distances travelled on all results reported in the literature.     

Application of the renormalization group to deterministic global minimization of molecular conformation energy functions

We outline a new global minimization method in which the Gibbs distribution of the objective function is deterministically annealed by tracing the evolution of a multiple-Gaussian-packet approximation. Solutions are reached by iterative approximations with decreasing coarse-graining of both objective-function and spatial scales. Results from application of a partial implementation to the atomic-microcluster conformation problem are presented.     

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.     

Simulated annealing for constrained global optimization

Hide-and-Seek is a powerful yet simple and easily implemented continuous simulated annealing algorithm for finding the maximum of a continuous function over an arbitrary closed, bounded and full-dimensional body. The function may be nondifferentiable and the feasible region may be nonconvex or even disconnected. The algorithm begins with any feasible interior point. In each iteration it generates a candidate successor point by generating a uniformly distributed point along a direction chosen at random from the current iteration point. In contrast to the discrete case, a single step of this algorithm may generateany point in the feasible region as a candidate point. The candidate point is then accepted as the next iteration point according to the Metropolis criterion parametrized by anadaptive cooling schedule. Again in contrast to discrete simulated annealing, the sequence of iteration points converges in probability to a global optimum regardless of how rapidly the temperatures converge to zero. Empirical comparisons with other algorithms suggest competitive performance by Hide-and-Seek.This material is based on work supported by a NATO Collaborative Research Grant, no. 0119/89.     

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.     

Improvement on the northby algorithm for molecular conformation: Better solutions

In 1987, Northby presented an efficient lattice based search and optimization procedure to compute ground states ofn-atom Lennard-Jones clusters and reported putative global minima for 13n150. In this paper, we introduce simple data structures which reduce the time complexity of the Northby algorithm for lattice search fromO(n^5/3) per move toO(n^2/3) per move for ann-atom cluster involving full Lennard-Jones potential function. If nearest neighbor potential function is used, the time complexity can be further reduced toO(logn) per move for ann-atom cluster. The lattice local minimizers with lowest potential function values are relaxed by a powerful Truncated Newton algorithm. We are able to reproduce the minima reported by Northby. The improved algorithm is so efficient that less than 3 minutes of CPU time on the Cray-XMP is required for each cluster size in the above range. We then further improve the Northby algorithm by relaxingevery lattice local minimizer found in the process. This certainly requires more time. However, lower energy configurations were found with this improved algorithm forn=65, 66, 75, 76, 77 and 134. These findings also show that in some cases, the relaxation of a lattice local minimizer with a worse potential function value may lead to a local minimizer with a better potential function value.     

基于模拟退火算法的数字岩心建模方法

简要介绍了模拟退火算法,给出了用于建立数字岩心的三个重要参考函数:孔隙度、两点概率函数和线性路径函数.详细阐述了基于模拟退火算法建立数字岩心的理论方法,介绍了算法中重要参数的设置方法,包括初始温度、降温条件、降温方案及运行终止条件.通过实例运算验证了上述理论的适用性,研究表明:模拟退火算法可以有效降低系统能量,在局部范围内能明显体现孔隙空间特征;由于受到输入建模资料所含信息量的限制,所生成的数字岩心孔隙分布较凌乱,整体连通性差,因而期待新的建模参考函数的开发.     

Continuous optimization by a variant of simulated annealing

A variant of the simulated annealing algorithm, based on the generalized method of Bohachevsky et al., is proposed for continuous optimization problems. The algorithm automatically adjusts the step sizes to reflect the local slopes and function values, and it controls the random directions to point favorably toward potential improvements. Computational results on some well known functions show substantial improvements both in solution quality and efficiency.     

Local and global optimization by parallel algorithms for MIMD systems

This paper describes an implementation on the Neptune system at Loughborough University of Sutti's parallel (MIMD) algorithm [1–3] and an analysis of its performance. Parallel asynchronous versions of Powell's method [6] and Price's algorithm [7] are proposed, designed for efficient implementation on MIMD systems.This work has been developed during the author's stay at the Numerical Optimization Centre, Hatfield Polytechnic, England.