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.     

Improving Hit-and-Run for global optimization

Improving Hit-and-Run is a random search algorithm for global optimization that at each iteration generates a candidate point for improvement that is uniformly distributed along a randomly chosen direction within the feasible region. The candidate point is accepted as the next iterate if it offers an improvement over the current iterate. We show that for positive definite quadratic programs, the expected number of function evaluations needed to arbitrarily well approximate the optimal solution is at most O(n^5/2) wheren is the dimension of the problem. Improving Hit-and-Run when applied to global optimization problems can therefore be expected to converge polynomially fast as it approaches the global optimum.Paper presented at the II. IIASA-Workshop on Global Optimization, December 9–14, 1990, Sopron (Hungary).     

Pure adaptive search in global optimization

Pure adaptive seach iteratively constructs a sequence of interior points uniformly distributed within the corresponding sequence of nested improving regions of the feasible space. That is, at any iteration, the next point in the sequence is uniformly distributed over the region of feasible space containing all points that are strictly superior in value to the previous points in the sequence. The complexity of this algorithm is measured by the expected number of iterations required to achieve a given accuracy of solution. We show that for global mathematical programs satisfying the Lipschitz condition, its complexity increases at mostlinearly in the dimension of the problem.This work was supported in part by NATO grant 0119/89.     

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.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

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.     

基于随机搜索的一个约束优化问题的全局收敛算法

讨论了具有一般约束的全局优化问题,给出该问题的一个随机搜索算法,证明了该算法依概率1收敛到问题的全局最优解．数值结果显示该方法是有效的．     

Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

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.     

Improved versions of the LEDE algorithm for constrained global optimization

Two modified versions of the authors’ recent differential evolution algorithm for constrained global optimization are proposed. They incorporate a filter set which results in more efficient implementations of the original algorithm. Numerical results are presented which suggest that the new algorithms are competitive.     

An interval algorithm for constrained global optimization

An interval algorithm for bounding the solutions of a constrained global optimization problem is described. The problem functions are assumed only to be continuous. It is shown how the computational cost of bounding a set which satisfies equality constraints can often be reduced if the equality constraint functions are assumed to be continuously differentiable. Numerical results are presented.     

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.     

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.     

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.     

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.     

Simulated annealing: Use of a new tool in bin packing

Simulated annealing (statistical cooling) is applied to bin packing problems. Different cooling strategies are compared empirically and for a particular 100 item problem a solution is given which is most likely the best known so far.The work was partially done during the author's visit to the University of California, Berkeley, sponsored by the Humboldt-Foundation.     

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     

A filled function method for constrained global optimization

In this paper, a filled function method for solving constrained global optimization problems is proposed. A filled function is proposed for escaping the current local minimizer of a constrained global optimization problem by combining the idea of filled function in unconstrained global optimization and the idea of penalty function in constrained optimization. Then a filled function method for obtaining a global minimizer or an approximate global minimizer of the constrained global optimization problem is presented. Some numerical results demonstrate the efficiency of this global optimization method for solving constrained global optimization problems.