共查询到20条相似文献,搜索用时 31 毫秒
1.
In this paper we develop, analyze, and test a new algorithm for the global minimization of a function subject to simple bounds
without the use of derivatives. The underlying algorithm is a pattern search method, more specifically a coordinate search
method, which guarantees convergence to stationary points from arbitrary starting points. In the optional search phase of
pattern search we apply a particle swarm scheme to globally explore the possible nonconvexity of the objective function. Our
extensive numerical experiments showed that the resulting algorithm is highly competitive with other global optimization methods
also based on function values.
Support for Luís N. Vicente was provided by Centro de Matemática da Universidade de Coimbra and by FCT under grant POCI/MAT/59442/2004. 相似文献
2.
Scatter search is an evolutionary method that, unlike genetic algorithms, operates
on a small set of solutions and makes only limited use of randomization as a proxy for
diversification when searching for a globally optimal solution. The scatter search framework is flexible, allowing the development
of alternative implementations with varying degrees of
sophistication. In this paper, we test the merit of several scatter search designs in the context of global optimization of
multimodal functions. We compare these designs among themselves and choose one to compare against a well-known genetic algorithm
that has been specifically developed for this class of problems. The testing is performed on a set of benchmark multimodal
functions with known global minima. 相似文献
3.
Jaewook Lee 《Journal of Global Optimization》2007,38(1):61-77
A new deterministic method for solving a global optimization problem is proposed. The proposed method consists of three phases.
The first phase is a typical local search to compute a local minimum. The second phase employs a discrete sup-local search
to locate a so-called sup-local minimum taking the lowest objective value among the neighboring local minima. The third phase
is an attractor-based global search to locate a new point of next descent with a lower objective value. The simulation results
through well-known global optimization problems are shown to demonstrate the efficiency of the proposed method. 相似文献
4.
Random search technique is the simplest one of the heuristic algorithms. It is stated in the literature that the probability of finding global minimum is equal to 1 by using the basic random search technique, but it takes too much time to reach the global minimum. Improving the basic random search technique may decrease the solution time. In this study, in order to obtain the global minimum fastly, a new random search algorithm is suggested. This algorithm is called as the Dynamic Random Search Technique (DRASET). DRASET consists of two phases, which are general search and local search based on general solution. Knowledge related to the best solution found in the process of general search is kept and then that knowledge is used as initial value of local search. DRASET’s performance was experimented with 15 test problems and satisfactory results were obtained. 相似文献
5.
Johannes Jahn 《Computational Optimization and Applications》2006,35(2):161-175
This paper presents a multiobjective search algorithm with subdivision technique (MOSAST) for the global solution of multiobjective
constrained optimization problems with possibly noncontinuous objective or constraint functions. This method is based on a
random search method and a new version of the Graef-Younes algorithm and it uses a subdivision technique. Numerical results
are given for bicriterial test problems. 相似文献
6.
Lipschitzian optimization without the Lipschitz constant 总被引:30,自引:0,他引:30
D. R. Jones C. D. Perttunen B. E. Stuckman 《Journal of Optimization Theory and Applications》1993,79(1):157-181
We present a new algorithm for finding the global minimum of a multivariate function subject to simple bounds. The algorithm is a modification of the standard Lipschitzian approach that eliminates the need to specify a Lipschitz constant. This is done by carrying out simultaneous searches using all possible constants from zero to infinity. On nine standard test functions, the new algorithm converges in fewer function evaluations than most competing methods.The motivation for the new algorithm stems from a different way of looking at the Lipschitz constant. In particular, the Lipschitz constant is viewed as a weighting parameter that indicates how much emphasis to place on global versus local search. In standard Lipschitzian methods, this constant is usually large because it must equal or exceed the maximum rate of change of the objective function. As a result, these methods place a high emphasis on global search and exhibit slow convergence. In contrast, the new algorithm carries out simultaneous searches using all possible constants, and therefore operates at both the global and local level. Once the global part of the algorithm finds the basin of convergence of the optimum, the local part of the algorithm quickly and automatically exploits it. This accounts for the fast convergence of the new algorithm on the test functions. 相似文献
7.
郑权等首先提出积分-水平集求总极值的方法,实现算法中采用Monte-Carlo 随机投点产生近似水平集来缩小搜索区域范围,但这一算法可能失去总极值点.此后,邬 冬华等给出了一种修正的积分-水平集的方法,一种区域不收缩的分箱方法以保证总极 值点不被丢失.本文在此基础上采取对不同的箱子采用不同的测度这一策略,使水平值 更充分的下降,更快的达到全局极小值,以提高修正算法的计算效率.最后给出的数值算 例说明了算法是有效的. 相似文献
8.
We present algorithms for the single-source uncapacitated version of the minimum concave cost network flow problem. Each algorithm exploits the fact that an extreme feasible solution corresponds to a sub-tree of the original network. A global search heuristic based on random extreme feasible initial solutions and local search is developed. The algorithm is used to evaluate the complexity of the randomly generated test problems. An exact global search algorithm is developed, based on enumerative search of rooted subtrees. This exact technique is extended to bound the search based on cost properties and linear underestimation. The technique is accelerated by exploiting the network structure. 相似文献
9.
Vincent Kelner Florin Capitanescu Olivier Léonard Louis Wehenkel 《Journal of Computational and Applied Mathematics》2008
Evolutionary algorithms are robust and powerful global optimization techniques for solving large-scale problems that have many local optima. However, they require high CPU times, and they are very poor in terms of convergence performance. On the other hand, local search algorithms can converge in a few iterations but lack a global perspective. The combination of global and local search procedures should offer the advantages of both optimization methods while offsetting their disadvantages. This paper proposes a new hybrid optimization technique that merges a genetic algorithm with a local search strategy based on the interior point method. The efficiency of this hybrid approach is demonstrated by solving a constrained multi-objective mathematical test-case. 相似文献
10.
This study introduces a new algorithm for the ant colony optimization (ACO) method, which has been proposed to solve global optimization problems with continuous decision variables. This algorithm, namely ACO-FRS, involves a strategy for the selection of feasible regions during optimization search and it performs the exploration of the search space using a similar approach to that used by the ants during the search of food. Four variants of this algorithm have been tested in several benchmark problems and the results of this study have been compared with those reported in literature for other ACO-type methods for continuous spaces. Overall, the results show that the incorporation of the selection of feasible regions allows the performing of a global search to explore those regions with low level of pheromone, thus increasing the feasibility of ACO for finding the global optimal solution. 相似文献
11.
This paper proposes a novel metaheuristics approach to find the global optimum of continuous global optimization problems with box constraints. This approach combines the characteristics of modern metaheuristics such as scatter search (SS), genetic algorithms (GAs), and tabu search (TS) and named as hybrid scatter genetic tabu (HSGT) search. The development of the HSGT search, parameter settings, experimentation, and efficiency of the HSGT search are discussed. The HSGT has been tested against a simulated annealing algorithm, a GA under the name GENOCOP, and a modified version of a hybrid scatter genetic (HSG) search by using 19 well known test functions. Applications to Neural Network training are also examined. From the computational results, the HSGT search proved to be quite effective in identifying the global optimum solution which makes the HSGT search a promising approach to solve the general nonlinear optimization problem. 相似文献
12.
We present a multistart method for solving global satisfycing problems. The method uses data generated by linearly converging local algorithms to estimate the cost value at the local minimum to which the local search is converging. When the estimate indicates that the local search is converging to a value higher than the satisfycing value, the local search is interrupted and a new local search is initiated from a randomly generated point. When the satisfycing problem is difficult and the estimation scheme is fairly accurate, the new method is superior over a straightforward adaptation of classical multistart methods. 相似文献
13.
Kar-Ann Toh 《Computational Optimization and Applications》2002,23(1):77-99
This paper addresses the problem of global optimization by means of a monotonic transformation. With an observation on global optimality of functions under such a transformation, we show that a simple and effective algorithm can be derived to search within possible regions containing the global optima. Numerical experiments are performed to compare this algorithm with one that does not incorporate transformed information using several benchmark problems. These results are also compared to best known global search algorithms in the literature. In addition, the algorithm is shown to be useful for several neural network learning problems, which possess much larger parameter spaces. 相似文献
14.
The conjugate gradient method is a useful and powerful approach for solving large-scale minimization problems. Liu and Storey developed a conjugate gradient method, which has good numerical performance but no global convergence under traditional line searches such as Armijo line search, Wolfe line search, and Goldstein line search. In this paper we propose a new nonmonotone line search for Liu-Storey conjugate gradient method (LS in short). The new nonmonotone line search can guarantee the global convergence of LS method and has a good numerical performance. By estimating the Lipschitz constant of the derivative of objective functions in the new nonmonotone line search, we can find an adequate step size and substantially decrease the number of functional evaluations at each iteration. Numerical results show that the new approach is effective in practical computation. 相似文献
15.
This paper is a study of the one-dimensional global optimization problem for continuously differentiable functions. We propose a variant of the so-called P-algorithm, originally proposed for a Wiener process model of an unknown objective function. The original algorithm has proven to be quite effective for global search, though it is not efficient for the local component of the optimization search if the objective function is smooth near the global minimizer. In this paper we construct a P-algorithm for a stochastic model of continuously differentiable functions, namely the once-integrated Wiener process. This process is continuously differentiable, but nowhere does it have a second derivative. We prove convergence properties of the algorithm. 相似文献
16.
Global Optimization using Dynamic Search Trajectories 总被引:1,自引:0,他引:1
Two global optimization algorithms are presented. Both algorithms attempt to minimize an unconstrained objective function through the modeling of dynamic search trajectories. The first, namely the Snyman–Fatti algorithm, originated in the 1980's and still appears an effective global optimization algorithm. The second algorithm is currently under development, and is denoted the modified bouncing ball algorithm. For both algorithms, the search trajectories are modified to increase the likelihood of convergence to a low local minimum. Numerical results illustrate the effectiveness of both algorithms. 相似文献
17.
ArpadBURMEN FrancBRATKOVIC JanezPUHAN IztokFAJFAR TadejTUMA 《数学学报(英文版)》2004,20(3):433-440
An extension of the global convergence framework for unconstrained derivative-free optimization methods is presented. The extension makes it possible for the framework to include optimization methods with varying cardinality of the ordered direction set. Grid-based search methods are shown to be a special case of the more general extended global convergence framework. Furthermore,the required properties of the sequence of ordered direction sets listed in the definition of grid-based methods are relaxed and simplified by removing the requirement of structural equivalence. 相似文献
18.
Cutting Angle Method and a Local Search 总被引:1,自引:0,他引:1
The paper deals with combinations of the cutting angle method in global optimization and a local search. We propose to use special transformed objective functions for each intermediate use of the cutting angle method. We report results of numerical experiments which demonstrate that the proposed approach is very beneficial in the search for a global minimum. 相似文献
19.
K. C. Kiwiel 《Journal of Optimization Theory and Applications》1986,48(3):437-449
This paper presents a method for minimizing the sum of a possibly nonsmooth convex function and a continuously differentiable function. As in the convex case developed by the author, the algorithm is a descent method which generates successive search directions by solving quadratic programming subproblems. An inexact line search ensures global convergence of the method to stationary points. 相似文献
20.
A DERIVATIVE-FREE ALGORITHM FOR UNCONSTRAINED OPTIMIZATION 总被引:1,自引:0,他引:1
Peng Yehui Liu Zhenhai 《高校应用数学学报(英文版)》2005,20(4):491-498
In this paper a hybrid algorithm which combines the pattern search method and the genetic algorithm for unconstrained optimization is presented. The algorithm is a deterministic pattern search algorithm,but in the search step of pattern search algorithm,the trial points are produced by a way like the genetic algorithm. At each iterate, by reduplication,crossover and mutation, a finite set of points can be used. In theory,the algorithm is globally convergent. The most stir is the numerical results showing that it can find the global minimizer for some problems ,which other pattern search algorithms don't bear. 相似文献