A Hybrid Descent Method for Global Optimization

In this paper, a hybrid descent method, consisting of a simulated annealing algorithm and a gradient-based method, is proposed. The simulated annealing algorithm is used to locate descent points for previously converged local minima. The combined method has the descent property and the convergence is monotonic. To demonstrate the effectiveness of the proposed hybrid descent method, several multi-dimensional non-convex optimization problems are solved. Numerical examples show that global minimum can be sought via this hybrid descent method.     

Speed-up simulated annealing by parallel coordinates

High computational cost is an obstacle to the applications of simulated annealing, especially for moderate and high dimensional problems. Inspired by multidimensional visualization techniques, the notion of parallel coordinates system, or parallel coordinates in short, is introduced into the optimization research area to speed up the convergence rate of simulated annealing. Numerical studies demonstrate that the proposed method can converge to global solutions with reduced computational cost in terms of both the number of function evaluations and CPU time.     

Derivative-free simulated annealing and deflecting function technique for global optimization

A hybrid descent method based on simulated annealing (SA) algorithm and one modifying function technique, named deflecting function method, for global optimization is proposed. Unlike some previously proposed algorithms, the designed SA algorithm is executed repeatedly on the transformed function with respect to one prior-obtained local minimum instead of on the original objective function. Meanwhile, large scale searches at the beginning stages and small scale detections in the last stages are adopted. The global convergence is proved. Simulation demonstrates that the new method utilizes the obtained information effectively, so the convergence is significantly sped up and the success rate is greatly improved, compared with other existing methods. As an experimental result, how to combine SA and the deflecting function technique can make the new method more effective is discussed.     

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.     

基于模拟退火的CRS算法

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

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.     

Adaptive Rejection Metropolis Simulated Annealing for Detecting Global Maximum Regions

A finite mixture model has been used to fit the data from heterogeneous populations to many applications. An Expectation Maximization (EM) algorithm is the most popular method to estimate parameters in a finite mixture model. A Bayesian approach is another method for fitting a mixture model. However, the EM algorithm often converges to the local maximum regions, and it is sensitive to the choice of starting points. In the Bayesian approach, the Markov Chain Monte Carlo (MCMC) sometimes converges to the local mode and is difficult to move to another mode. Hence, in this paper we propose a new method to improve the limitation of EM algorithm so that the EM can estimate the parameters at the global maximum region and to develop a more effective Bayesian approach so that the MCMC chain moves from one mode to another more easily in the mixture model. Our approach is developed by using both simulated annealing (SA) and adaptive rejection metropolis sampling (ARMS). Although SA is a well-known approach for detecting distinct modes, the limitation of SA is the difficulty in choosing sequences of proper proposal distributions for a target distribution. Since ARMS uses a piecewise linear envelope function for a proposal distribution, we incorporate ARMS into an SA approach so that we can start a more proper proposal distribution and detect separate modes. As a result, we can detect the maximum region and estimate parameters for this global region. We refer to this approach as ARMS annealing. By putting together ARMS annealing with the EM algorithm and with the Bayesian approach, respectively, we have proposed two approaches: an EM-ARMS annealing algorithm and a Bayesian-ARMS annealing approach. We compare our two approaches with traditional EM algorithm alone and Bayesian approach alone using simulation, showing that our two approaches are comparable to each other but perform better than EM algorithm alone and Bayesian approach alone. Our two approaches detect the global maximum region well and estimate the parameters in this region. We demonstrate the advantage of our approaches using an example of the mixture of two Poisson regression models. This mixture model is used to analyze a survey data on the number of charitable donations.     

An efficient algorithm for range computation of polynomials using the Bernstein form

We present a novel optimization algorithm for computing the ranges of multivariate polynomials using the Bernstein polynomial approach. The proposed algorithm incorporates four accelerating devices, namely the cut-off test, the simplified vertex test, the monotonicity test, and the concavity test, and also possess many new features, such as, the generalized matrix method for Bernstein coefficient computation, a new subdivision direction selection rule and a new subdivision point selection rule. The features and capabilities of the proposed algorithm are compared with those of other optimization techniques: interval global optimization, the filled function method, a global optimization method for imprecise problems, and a hybrid approach combining simulated annealing, tabu search and a descent method. The superiority of the proposed method over the latter methods is illustrated by numerical experiments and qualitative comparisons.     

A Staged Continuous Tabu Search Algorithm for the Global Optimization and its Applications to the Design of Fiber Bragg Gratings

A novel staged continuous Tabu search (SCTS) algorithm is proposed for solving global optimization problems of multi-minima functions with multi-variables. The proposed method comprises three stages that are based on the continuous Tabu search (CTS) algorithm with different neighbor-search strategies, with each devoting to one task. The method searches for the global optimum thoroughly and efficiently over the space of solutions compared to a single process of CTS. The effectiveness of the proposed SCTS algorithm is evaluated using a set of benchmark multimodal functions whose global and local minima are known. The numerical test results obtained indicate that the proposed method is more efficient than an improved genetic algorithm published previously. The method is also applied to the optimization of fiber grating design for optical communication systems. Compared with two other well-known algorithms, namely, genetic algorithm (GA) and simulated annealing (SA), the proposed method performs better in the optimization of the fiber grating design.     

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.     

Sequential Monte Carlo simulated annealing

In this paper, we propose a population-based optimization algorithm, Sequential Monte Carlo Simulated Annealing (SMC-SA), for continuous global optimization. SMC-SA incorporates the sequential Monte Carlo method to track the converging sequence of Boltzmann distributions in simulated annealing. We prove an upper bound on the difference between the empirical distribution yielded by SMC-SA and the Boltzmann distribution, which gives guidance on the choice of the temperature cooling schedule and the number of samples used at each iteration. We also prove that SMC-SA is more preferable than the multi-start simulated annealing method when the sample size is sufficiently large.     

蛋白质空间结构预测的一种优化模型及算法

用理论方法预测蛋白质结构有两个难点,第一是要有一个合理的势函数,第二是要有一个有效的寻优方法找到势函数的全局极小点,本文采用联合残基力场建立了蛋白质空间结构预测模型,然后用我们给出的一种改进模拟退火算法搜索势函数的全局极小点,对脑啡肽的空间结构进行了预测和分析。     

DESA: a new hybrid global optimization method and its application to analog integrated circuit sizing

This paper presents a new hybrid global optimization method referred to as DESA. The algorithm exploits random sampling and the metropolis criterion from simulated annealing to perform global search. The population of points and efficient search strategy of differential evolution are used to speed up the convergence. The algorithm is easy to implement and has only a few parameters. The theoretical global convergence is established for the hybrid method. Numerical experiments on 23 mathematical test functions have shown promising results. The method was also integrated into SPICE OPUS circuit simulator to evaluate its practical applicability in the area of analog integrated circuit sizing. Comparison was made with basic simulated annealing, differential evolution, and a multistart version of the constrained simplex method. The latter was already a part of SPICE OPUS and produced good results in past research.     

Evolutionary Simulated Annealing With Application to Image Restoration

Simulated annealing is a randomized algorithm proposed for finding a global optimum in large problems where a target function may have many local extrema. This article considers a modification of the simulated annealing algorithm that turns it into a deterministic technique. Instead of carrying out a stochastic jump based on the annealing update density, the update density is used to select a fixed number of candidate parameter vectors which are all fed to the next iteration of the algorithm. The selection criterion involves not only the update density height, but also information about the origin of the candidate vector. Thus, each iteration produces a cooperative collection of parameter vectors in hope of exploring the parameter space in search of the optimum more thoroughly than the regular annealing. The technique is shown to outperform regular annealing on the problem of restoration of lattice images consisting of simple-shaped objects.     

Random tunneling by means of acceptance-rejection sampling for global optimization

Any global minimization algorithm is made by several local searches performed sequentially. In the classical multistart algorithm, the starting point for each new local search is selected at random uniformly in the region of interest. In the tunneling algorithm, such a starting point is required to have the same function value obtained by the last local minimization. We introduce the class of acceptance-rejection based algorithms in order to investigate intermediate procedures. A particular instance is to choose at random the new point approximately according to a Boltzmann distribution, whose temperatureT is updated during the algorithm. AsT 0, such distribution peaks around the global minima of the cost function, producing a kind of random tunneling effect. The motivation for such an approach comes from recent works on the simulated annealing approach in global optimization. The resulting algorithm has been tested on several examples proposed in the literature.     

一类非线性两级整数规划问题的全局优化方法

本文研究了整数规划连续化的途径,对一类非线性两级整数规划问题的上级规划连续化以后采用模拟退火算法;其对应的下级规划问题采用离散搜索法求解,从而给出了求解一类非线性两级整数规划问题的一种全局优化算法,并通过算例验证了该算法是有效的.     

An efficient algorithm for large scale global optimization of continuous functions

A fast descent algorithm, resorting to a “stretching” function technique and built on one hybrid method (GRSA) which combines simulated annealing (SA) algorithm and gradient based methods for large scale global optimizations, is proposed. Unlike the previously proposed method in which the original objective functions remain unchanged during the whole course of optimization, the new method firstly constructs an auxiliary function on one local minimizer obtained by gradient based methods and then SA is executed on this constructed auxiliary function instead of on the original objective function in order that we can improve the jumping ability of SA algorithm to escape from the currently discovered local minimum to a better one from which the gradient based methods restart a new local search. The above procedure is repeated until a global minimum is detected. In addition, corresponding to the adopted “stretching” technique, a new next trial point generating scheme is designed. It is verified by simulation especially on large scale problems that the convergence speed is greatly accelerated, which is its main difference from many other reported methods that mostly cope with functions with less than 50 variables and does not apply to large scale optimization problems. Furthermore, the new algorithm functions as a global optimization procedure with a high success probability and high solution precision.     

Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

Improved methods of assembly sequence determination for automatic assembly systems

The assembly sequence is determined using product unit cost as the performance measure. The global optimum for a given problem is found by partially enumerating assembly station configurations with branch and bound methods. The study shows that the proposed methods perform faster than simulated annealing for the example problems used. It is shown that the unit cost function is not necessarily convex which is assumed in previous research.     

Simulated annealing and object point processes: Tools for analysis of spatial patterns

This paper introduces a three-dimensional object point process—the Bisous model—that can be used as a prior for three-dimensional spatial pattern analysis. Maximization of likelihood or penalized-likelihood functions based on this model requires global optimization techniques, such as the simulated annealing algorithm. Theoretical properties of the model are discussed and the convergence of the proposed optimization method is proved. Finally, a simulation study is presented.