共查询到20条相似文献,搜索用时 156 毫秒
1.
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. 相似文献
2.
3.
本文是对非线性规划问题提出的一种算法,该算法把模拟退火算法应用到CRS算法中,根据模拟退火算法每一次迭代都体现集中和扩散两个策略的平衡的特点,使CRS算法更能够搜索到全局最优解,而不会陷入局部最优解。最后把提出的算法应用到两个典型的函数优化问题中,结果表明,算法是可行的、有效的 相似文献
4.
Global optimization and simulated annealing 总被引:19,自引:0,他引:19
In this paper we are concerned with global optimization, which can be defined as the problem of finding points on a bounded subset of
n
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. 相似文献
5.
Yanfang Shen Seksan Kiatsupaibul Zelda B. Zabinsky Robert L. Smith 《Journal of Global Optimization》2007,38(3):333-365
We present an analytically derived cooling schedule for a simulated annealing algorithm applicable to both continuous and
discrete global optimization problems. An adaptive search algorithm is used to model an idealized version of simulated annealing
which is viewed as consisting of a series of Boltzmann distributed sample points. Our choice of cooling schedule ensures linearity
in the expected number of sample points needed to become arbitrarily close to a global optimum. 相似文献
6.
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. 相似文献
7.
Chang C. Y. Dorea Judinor A. Guerra Jr. Rafael Morgado Andre G. C. Pereira 《Numerical Functional Analysis & Optimization》2013,34(2):164-171
The genetic algorithm (GA) has been widely used to solve combinatorial global optimization problems. Despite the successes that GA encounters in practical applications, there exist few precise results on its behavior. In this article, we formulate a fully rigorous mathematical modeling of GA as a multistage Markov chain and derive convergence results. Variations that include the simulated annealing algorithm and the GA with superindividual are considered. 相似文献
8.
Ding-Jun Chen Chung-Yeol Lee Cheol-Hoon Park Pedro Mendes 《Journal of Global Optimization》2007,39(2):261-289
We implemented five conversions of simulated annealing (SA) algorithm from sequential-to-parallel forms on high-performance
computers and applied them to a set of standard function optimization problems in order to test their performances. According
to the experimental results, we eventually found that the traditional approach to parallelizing simulated annealing, namely,
parallelizing moves in sequential SA, difficultly handled very difficult problem instances. Divide-and-conquer decomposition
strategy used in a search space sometimes might find the global optimum function value, but it frequently resulted in great
time cost if the random search space was considerably expanded. The most effective way we found in identifying the global
optimum solution is to introduce genetic algorithm (GA) and build a highly hybrid GA+SA algorithm. In this approach, GA has
been applied to each cooling temperature stage. Additionally, the performance analyses of the best algorithm among the five
implemented algorithms have been done on the IBM Beowulf PCs Cluster and some comparisons have been made with some recent
global optimization algorithms in terms of the number of functional evaluations needed to obtain a global minimum, success
rate and solution quality. 相似文献
9.
10.
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. 相似文献
11.
An aspiration based simulated annealing algorithm for continuousvariables has been proposed. The new algorithm is similar to the one givenby Dekkers and Aarts (1991) except that a kind of memory is introduced intothe procedure with a self-regulatory mechanism. The algorithm has beenapplied to a set of standard global optimization problems and a number ofmore difficult, complex, practical problems and its performance comparedwith that of the algorithm of Dekkers and Aarts (1991). The new algorithmappears to offer a useful alternative to some of the currently availablestochastic algorithms for global optimization. 相似文献
12.
Stochastic global search algorithms such as genetic algorithms are used to attack difficult combinatorial optimization problems.
However, genetic algorithms suffer from the lack of a convergence proof. This means that it is difficult to establish reliable
algorithm braking criteria without extensive a priori knowledge of the solution space. The hybrid genetic algorithm presented here combines a genetic algorithm with simulated
annealing in order to overcome the algorithm convergence problem. The genetic algorithm runs inside the simulated annealing
algorithm and provides convergence via a Boltzmann cooling process. The hybrid algorithm was used successfully to solve a
classical 30-city traveling salesman problem; it consistently outperformed both a conventional genetic algorithm and a conventional
simulated annealing algorithm.
This work was supported by the University of Colorado at Colorado Springs. 相似文献
13.
Zelda B. Zabinsky David Bulger Charoenchai Khompatraporn 《Journal of Global Optimization》2010,46(2):273-286
Two common questions when one uses a stochastic global optimization algorithm, e.g., simulated annealing, are when to stop
a single run of the algorithm, and whether to restart with a new run or terminate the entire algorithm. In this paper, we
develop a stopping and restarting strategy that considers tradeoffs between the computational effort and the probability of
obtaining the global optimum. The analysis is based on a stochastic process called Hesitant Adaptive Search with Power-Law
Improvement Distribution (HASPLID). HASPLID models the behavior of stochastic optimization algorithms, and motivates an implementable
framework, Dynamic Multistart Sequential Search (DMSS). We demonstrate here the practicality of DMSS by using it to govern
the application of a simple local search heuristic on three test problems from the global optimization literature. 相似文献
14.
Guoliang Xue 《Journal of Global Optimization》1994,4(2):187-208
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 相似文献
15.
A Hybrid Descent Method for Global Optimization 总被引:6,自引:2,他引:4
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. 相似文献
16.
Stochastic optimization methods such as evolutionary algorithms and Markov Chain Monte Carlo methods usually involve a Markov search of the optimization domain. Evolutionary annealing is an evolutionary algorithm that leverages all the information gathered by previous queries to the cost function. Evolutionary annealing can be viewed either as simulated annealing with improved sampling or as a non-Markovian selection mechanism for evolutionary algorithms. This article develops the basic algorithm and presents implementation details. Evolutionary annealing is a martingale-driven optimizer, where evaluation yields a source of increasingly refined information about the fitness function. A set of experiments with twelve standard global optimization benchmarks is performed to compare evolutionary annealing with six other stochastic optimization methods. Evolutionary annealing outperforms other methods on asymmetric, multimodal, non-separable benchmarks and exhibits strong performance on others. It is therefore a promising new approach to global optimization. 相似文献
17.
In this paper, we present a simulated annealing algorithm for solving multi-objective simulation optimization problems. The algorithm is based on the idea of simulated annealing with constant temperature, and uses a rule for accepting a candidate solution that depends on the individual estimated objective function values. The algorithm is shown to converge almost surely to an optimal solution. It is applied to a multi-objective inventory problem; the numerical results show that the algorithm converges rapidly. 相似文献
18.
《Journal of Computational and Applied Mathematics》2006,191(2):269-279
Stochastic methods have gained some popularity in global optimization in that most of them do not assume the cost functions to be differentiable. They have capabilities to avoid being trapped by local optima, and may converge even faster than gradient-based optimization methods on some problems. The present paper proposes an optimization method, which reduces the search space by means of densification curves, coupled with the dynamic canonical descent algorithm. The performances of the new method are shown on several known problems classically used for testing optimization algorithms, and proved to outperform competitive algorithms such as simulated annealing and genetic algorithms. 相似文献
19.
Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem 总被引:1,自引:0,他引:1
The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems. 相似文献
20.
Combining simulated annealing with local search heuristics 总被引:2,自引:0,他引:2
We introduce a meta-heuristic to combine simulated annealing with local search methods for CO problems. This new class of
Markov chains leads to significantly more powerful optimization methods than either simulated annealing or local search. The
main idea is to embed deterministic local search techniques into simulated annealing so that the chain explores only local
optima. It makes large, global changes, even at low temperatures, thus overcoming large barriers in configuration space. We
have tested this meta-heuristic for the traveling salesman and graph partitioning problems. Tests on instances from public
libraries and random ensembles quantify the power of the method. Our algorithm is able to solve large instances to optimality,
improving upon local search methods very significantly. For the traveling salesman problem with randomly distributed cities,
in a square, the procedure improves on 3-opt by 1.6%, and on Lin-Kernighan local search by 1.3%. For the partitioning of sparse
random graphs of average degree equal to 5, the improvement over Kernighan-Lin local search is 8.9%. For both CO problems,
we obtain new best heuristics. 相似文献