共查询到20条相似文献,搜索用时 0 毫秒
1.
In this paper simplicial branch-and-bound algorithms for concave minimization problems are discussed. Some modifications of the basic algorithm are presented, mainly consisting in rules to start local searches, introduction of cuts and updates of the original objective function. While some of these tools are not new in the literature, it is the first time, to the authors' knowledge, that they are used to guarantee the finiteness of a simplicial branch-and-bound approach. 相似文献
2.
In this paper, we will propose an efficient heuristic algorithm for solving concave quadratic programming problems whose rank of the objective function is relatively small. This algorithm is a combination of Tuy's cutting plane to eliminate the feasible region and a kind of tabu-search method to find a good vertex. We first generate a set of V of vertices and select one of these vertices as a starting point at each step, and apply tabu-search and Tuy's cutting plane algorithm where the list of tabu consists of those vertices eliminated by cutting planes and those newly generated vertices by cutting planes. When all vertices of the set V are eliminated, the algorithm is terminated. This algorithm need not converge to a global minimum, but it can work very well when the rank is relatively small (up to seven). The incumbent solutions are in fact globally optimal for all tested problems. We also propose an alternative algorithm by incorporating Rosen's hyperrectangle cut. This algorithm is more efficient than the combination of Tuy's cutting plane and tabu-search. 相似文献
3.
Global Optimization by Multilevel Coordinate Search 总被引:3,自引:0,他引:3
Inspired by a method by Jones et al. (1993), we present a global optimization algorithm based on multilevel coordinate search. It is guaranteed to converge if the function is continuous in the neighborhood of a global minimizer. By starting a local search from certain good points, an improved convergence result is obtained. We discuss implementation details and give some numerical results. 相似文献
4.
The method of partitioned random search has been proposed in recent years to obtain an as good as possible solution for the global optimization problem (1). A practical algorithm has been developed and applied to real-life problems. However, the design of this algorithm was based mainly on intuition. The theoretical foundation of the method is an important issue in the development of efficient algorithms for such problems. In this paper, we generalize previous theoretical results and propose a sequential sampling policy for the partitioned random search for global optimization with sampling cost and discounting factor. A proof of the optimality of the proposed sequential sampling policy is given by using the theory of optimal stopping. 相似文献
5.
D. W. Bulger 《Journal of Optimization Theory and Applications》2007,133(3):289-301
Grover’s quantum algorithm promises a quadratic acceleration for any problem formulable as a search. For unstructured search
problems, its implementation and performance are well understood. The curse of dimensionality and the intractability of the
general global optimization problem require any identifiable structure or regularity to be incorporated into a solution method.
This paper addresses the application of Grover’s algorithm when a local search technique is available, thereby combining the
quadratic acceleration with the acceleration seen in the multistart method.
The author thanks Dr. Bill Baritompa for helpful discussions. 相似文献
6.
一种改进的禁忌搜索算法及其在连续全局优化中的应用 总被引:1,自引:1,他引:1
禁忌搜索算法是一种元启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题中。本文针对有界闭区域上的连续函数全局优化问题,提出了一种改进的禁忌搜索算法,并进行了理论分析和数值实验。数值实验表明,对于连续函数全局优化问题的求解该算法是可行有效的,并且结构简单,迭代次数较少,是一种较好的全局启发式优化算法。 相似文献
7.
A Numerical Evaluation of Several Stochastic Algorithms on Selected Continuous Global Optimization Test Problems 总被引:9,自引:0,他引:9
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. 相似文献
8.
This work deals with the solution of ill-conditioned unconstrained minimization problems by means of pattern search methods. To this end, the usual requirement of monotonic reduction of the objective function is relaxed and nonmonotone pattern search methods are proposed, which maintain the convergence properties of their monotone counterparts. Numerical experimentation on several well-known ill-conditioned functions is reported. The results highlight a class of pattern search methods which benefit very much by the introduction of nonmonotone strategies. 相似文献
9.
10.
In previous work (Krasnogor, . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol,
UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474–488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When
“syntactic sugar” is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic
algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are
applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness
results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover,
we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical
applications) also give rise to PLS-complete problems.
Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users. 相似文献
Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users. 相似文献
11.
A function F : Rn R is called a piecewise convex function if it can be decomposed into F(x)=min{f
j(x) j M}, where f
j :Rn R is convex for all j M={1,2...,m}. In this article, we provide an algorithm for solving F(x) subject to xD, which is based on global optimality conditions. We report first computational experiments on small examples and open up some issues to improve the checking of optimality conditions. 相似文献
12.
Functions with local minima and size of their region of attraction known a priori, are often needed for testing the performance of algorithms that solve global optimization problems. In this paper we investigate a technique for constructing test functions for global optimization problems for which we fix a priori: (i) the problem dimension, (ii) the number of local minima, (iii) the local minima points, (iv) the function values of the local minima. Further, the size of the region of attraction of each local minimum may be made large or small. The technique consists of first constructing a convex quadratic function and then systematically distorting selected parts of this function so as to introduce local minima. 相似文献
13.
We describe global optimization problems from three different fields representing many-body potentials in physical chemistry, optimal control of a chemical reactor, and fitting a statistical model to empirical data. Historical background for each of the problems as well as the practical significance of the first two are given. The problems are solved by using eight recently developed stochastic global optimization algorithms representing controlled random search (4 algorithms), simulated annealing (2 algorithms), and clustering (2 algorithms). The results are discussed, and the importance of global optimization in each respective field is focused. 相似文献
14.
Generalized hill climbing algorithms provide a framework for modeling several local search algorithms for hard discrete optimization problems. This paper introduces and analyzes generalized hill climbing algorithm performance measures that reflect how effectively an algorithm has performed to date in visiting a global optimum and how effectively an algorithm may pes]rform in the future in visiting such a solution. These measures are also used to obtain a necessary asymptotic convergence (in probability) condition to a global optimum, which is then used to show that a common formulation of threshold accepting does not converge. These measures assume particularly simple forms when applied to specific search strategies such as Monte Carlo search and threshold accepting. 相似文献
15.
Global Interval Methods for Local Nonsmooth Optimization 总被引:4,自引:0,他引:4
An interval method for determining local solutions of nonsmooth unconstrained optimization problems is discussed. The objective function is assumed to be locally Lipschitz and to have appropriate interval inclusions. The method consists of two parts, a local search and a global continuation and termination. The local search consists of a globally convergent descent algorithm showing similarities to -bundle methods. While -bundle methods use polytopes as inner approximations of the -subdifferentials, which are the main tools of almost all bundle concepts, our method uses axes parallel boxes as outer approximations of the -subdifferentials. The boxes are determined almost automatically with inclusion techniques of interval arithmetic. The dimension of the boxes is equal to the dimension of the problem and remains constant during the whole computation. The application of boxes does not suffer from the necessity to invest methodical and computational efforts to adapt the polytopes to the latest state of the computation as well as to simplify them when the number of vertices becomes too large, as is the case with the polytopes. The second part of the method applies interval techniques of global optimization to the approximative local solution obtained from the search of the first part in order to determine guaranteed error bounds or to improve the solution if necessary. We present prototype algorithms for both parts of the method as well as a complete convergence theory for them and demonstrate how outer approximations can be obtained. 相似文献
16.
In this paper, we describe an approach for solving the quadratic assignment problem (QAP) that is based on genetic algorithms (GA). It will be shown that a standard canonical GA (SGA), which involves genetic operators of selection, reproduction, crossover, and mutation, tends to fall short of the desired performance expected of a search algorithm. The performance deteriorates significantly as the size of the problem increases. To address this syndrome, it is common for GA-based techniques to be embedded with deterministic local search procedures. It is proposed that the local search should involve simple procedure of genome reordering that should not be too complex. More importantly, from a computational point of view, the local search should not carry with it the full cost of evaluating a chromosome after each move in the localized landscape. Results of simulation on several difficult QAP benchmarks showed the effectiveness of our approaches. 相似文献
17.
为探寻存在搜寻成本情况下消费者购买可替代产品时的定价与库存问题,从消费者效用出发,对厂商收益构建了基于马尔可夫决策过程的优化模型。在消费者方面,分析了其购买与继续搜寻的条件,并分别在搜寻成本不变和搜寻成本边际递减的情况下研究了消费者保留效用的变化情况以及购买相应产品的概率。此外,与很多相关文献不同的是,由于搜寻成本的存在,该情形下的消费者并不一定会在完成购买之前搜寻完所有的产品。在厂商方面,根据实际情况构建不同搜寻顺序下的收益模型并求解出最优定价策略与库存策略,并将定价模型与库存策略扩展到了动态的环境,为厂商制定价格及库存方案提供相应的决策支持。 相似文献
18.
K. Moshirvaziri 《Journal of Optimization Theory and Applications》1998,98(1):83-108
This paper presents a method for constructing test problems with known global solutions for concave minimization under linear constraints with an additional convex constraint and for reverse convex programs with an additional convex constraint. The importance of such a construction can be realized from the fact that the well known d.c. programming problem can be formulated in this form. Then, the method is further extended to generate test problems with more than one convex constraint, tight or untight at the global solution. 相似文献
19.
Jinchao Xu 《应用数学学报(英文版)》2002,18(2):185-200
Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids. 相似文献
20.
We describe the application of two global optimization methods, namely of genetic and random search type algorithms in shape optimization. When the so-called fictitious domain approaches are used for the numerical realization of state problems, the resulting minimized function is non-differentiable and stair-wise, in general. Such complicated behaviour excludes the use of classical local methods. Specific modifications of the above-mentioned global methods for our class of problems are described. Numerical results of several model examples computed by different variants of genetic and random search type algorithms are discussed. 相似文献