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     

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.     

Parallel Simulated Annealing Algorithms in Global Optimization

Global optimization involves the difficult task of the identification of global extremities of mathematical functions. Such problems are often encountered in practice in various fields, e.g., molecular biology, physics, industrial chemistry. In this work, we develop five different parallel Simulated Annealing (SA) algorithms and compare them on an extensive test bed used previously for the assessment of various solution approaches in global optimization. The parallel SA algorithms consist of various categories: the asynchronous approach where no information is exchanged among parallel runs and the synchronous approaches where solutions are exchanged using genetic operators, or where solutions are transmitted only occasionally, or where highly coupled synchronization is achieved at every iteration. One of these approaches, which occasionally applies partial information exchanges (controlled in terms of solution quality), provides particularly notable results for functions with vast search spaces of up to 400 dimensions. Previous attempts with other approaches, such as sequential SA, adaptive partitioning algorithms and clustering algorithms, to identify the global optima of these functions have failed without exception.     

Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems

In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed.     

A Continuous Genetic Algorithm Designed for the Global Optimization of Multimodal Functions

Genetic algorithms are stochastic search approaches based on randomized operators, such as selection, crossover and mutation, inspired by the natural reproduction and evolution of the living creatures. However, few published works deal with their application to the global optimization of functions depending on continuous variables.A new algorithm called Continuous Genetic Algorithm (CGA) is proposed for the global optimization of multiminima functions. In order to cover a wide domain of possible solutions, our algorithm first takes care over the choice of the initial population. Then it locates the most promising area of the solution space, and continues the search through an intensification inside this area. The selection, the crossover and the mutation are performed by using the decimal code. The efficiency of CGA is tested in detail through a set of benchmark multimodal functions, of which global and local minima are known. CGA is compared to Tabu Search and Simulated Annealing, as alternative algorithms.     

Stochastic Methods for Practical Global Optimization

Engineering design problems often involve global optimization of functions that are supplied as black box functions. These functions may be nonconvex, nondifferentiable and even discontinuous. In addition, the decision variables may be a combination of discrete and continuous variables. The functions are usually computationally expensive, and may involve finite element methods. An engineering example of this type of problem is to minimize the weight of a structure, while limiting strain to be below a certain threshold. This type of global optimization problem is very difficult to solve, yet design engineers must find some solution to their problem – even if it is a suboptimal one. Sometimes the most difficult part of the problem is finding any feasible solution. Stochastic methods, including sequential random search and simulated annealing, are finding many applications to this type of practical global optimization problem. Improving Hit-and-Run (IHR) is a sequential random search method that has been successfully used in several engineering design applications, such as the optimal design of composite structures. A motivation to IHR is discussed as well as several enhancements. The enhancements include allowing both continuous and discrete variables in the problem formulation. This has many practical advantages, because design variables often involve a mixture of continuous and discrete values. IHR and several variations have been applied to the composites design problem. Some of this practical experience is discussed.     

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.     

Objective Function Features Providing Barriers to Rapid Global Optimization

The purposes of this discussion paper are twofold. First, features of an objective function landscape which provide barriers to rapid finding of the global optimum are described. Second, stochastic algorithms are discussed and their performance examined, both theoretically and computationally, as the features change. The paper lays a foundation for the later findings paper.     

一种改进的禁忌搜索算法及其在连续全局优化中的应用

禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

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.     

求无约束连续全局优化问题的单参数填充函数法

填充函数法是求解全局优化问题的一个重要的确定性算法,这种方法的关键是构造具有良好性质的填充函数.构造了一个新的求解无约束全局优化问题的填充函数.函数连续可微且只包含一个参数.通过分析该函数的相关性质,设计了相应的算法.数值实验表明该算法简单有效.     

New Modified Function Method for Global Optimization

In this paper, a class of global optimization problems is considered. Corresponding to each local minimizer obtained, we introduced a new modified function and construct a corresponding optimization subproblem with one constraint. Then, by applying a local search method to the one-constraint optimization subproblem and using the local minimizer as the starting point, we obtain a better local optimal solution. This process is continued iteratively. A termination rule is obtained which can serve as stopping criterion for the iterating process. To demonstrate the efficiency of the proposed approach, numerical examples are solved.This research was partially supported by the National Science Foundation of China, Grant 10271073.     

Simulated annealing and tabu search approaches for the Corridor Allocation Problem

In the Corridor Allocation Problem, we are given n facilities to be arranged along a corridor. The arrangements on either side of the corridor should start from a common point on the left end of the corridor. In addition, no space is allowed between two adjacent facilities. The problem is motivated by applications such as the arrangement of rooms in office buildings, hospitals, shopping centers or schools. Tabu search and simulated annealing algorithms are presented to minimize the sum of weighted distances between every pair of facilities. The algorithms are evaluated on several instances of different sizes either randomly generated or available in the literature. Both algorithms reached the optimal (when available) or best-known solutions of the instances with n ? 30. For larger instances with size 42 ? n ? 70, the simulated annealing implementation obtained smaller objective values, while requiring a smaller number of function evaluations.     

一类新的求全局优化问题的填充函数

填充函数方法是一种寻找全局极小解的有效方法.本文首先对现有的填充函数进行研究分析,然后构造出一类新的填充函数,设计算法,并通过数值试验验证了该函数和算法的有效性.     

A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems

There is a need for a methodology to fairly compare and present evaluation study results of stochastic global optimization algorithms. This need raises two important questions of (i) an appropriate set of benchmark test problems that the algorithms may be tested upon and (ii) a methodology to compactly and completely present the results. To address the first question, we compiled a collection of test problems, some are better known than others. Although the compilation is not exhaustive, it provides an easily accessible collection of standard test problems for continuous global optimization. Five different stochastic global optimization algorithms have been tested on these problems and a performance profile plot based on the improvement of objective function values is constructed to investigate the macroscopic behavior of the algorithms. The paper also investigates the microscopic behavior of the algorithms through quartile sequential plots, and contrasts the information gained from these two kinds of plots. The effect of the length of run is explored by using three maximum numbers of function evaluations and it is shown to significantly impact the behavior of the algorithms.     

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.