共查询到20条相似文献,搜索用时 578 毫秒
1.
In this paper, a discrete filled function algorithm embedded with continuous approximation is proposed to solve max-cut problems. A new discrete filled function is defined for max-cut problems, and properties of the function are studied. In the process of finding an approximation to the global solution of a max-cut problem, a continuation optimization algorithm is employed to find local solutions of a continuous relaxation of the max-cut problem, and then global searches are performed by minimizing the proposed filled function. Unlike general filled function methods, characteristics of max-cut problems are used. The parameters in the proposed filled function need not to be adjusted and are exactly the same for all max-cut problems that greatly increases the efficiency of the filled function method. Numerical results and comparisons on some well known max-cut test problems show that the proposed algorithm is efficient to get approximate global solutions of max-cut problems. 相似文献
2.
The global optimization method based on discrete filled function is a new method that solves large scale max-cut problems. We first define a new discrete filled function based on the structure of the max-cut problem and analyze its properties. Unlike the continuous filled function methods, by the characteristic of the max-cut problem, the parameters in the proposed filled function does not need to be adjusted. By combining a procedure that randomly generates initial points for minimization of the proposed filled function, the proposed algorithm can greatly reduce the computational time and be applied to large scale max-cut problems. Numerical results and comparisons with several heuristic methods indicate that the proposed algorithm is efficient and stable to obtain high quality solution of large scale max-cut problems. 相似文献
3.
Cheng-xian Xu Xiao-liang Feng-min Xu 《计算数学(英文版)》2006,24(6):749-760
An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs. 相似文献
4.
A definition of the discrete filled function is given in this paper. Based on the definition, a discrete filled function is proposed. Theoretical properties of the proposed discrete filled function are investigated, and an algorithm for discrete global optimization is developed from the new discrete filled function. The implementation of the algorithms on several test problems is reported with satisfactory numerical results. 相似文献
5.
Feng Min XU Cheng Xian XU Xing Si LI 《数学学报(英文版)》2007,23(7):1257-1264
A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs. 相似文献
6.
离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的. 相似文献
7.
A filled function method for constrained global optimization 总被引:1,自引:0,他引:1
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. 相似文献
8.
9.
A New Filled Function Method for Global Optimization 总被引:3,自引:0,他引:3
A novel filled function is suggested in this paper for identifying a global minimum point for a general class of nonlinear programming problems with a closed bounded domain. Theoretical and numerical properties of the proposed filled function are investigated and a solution algorithm is proposed. The implementation of the algorithm on several test problems is reported with satisfactory numerical results. 相似文献
10.
A new filled function with one parameter is proposed for solving constrained global optimization problems without the coercive condition, in which the filled function contains neither exponential term nor fractional term and is easy to be calculated. A corresponding filled function algorithm is established based on analysis of the properties of the filled function. At last, we perform numerical experiments on some typical test problems using the algorithm and the detailed numerical results show that the algorithm is effective. 相似文献
11.
The max-cut problem is a classical NP-hard problem in graph theory. In this paper, we adopt a local search method, called MCFM, which is a simple modification of the Fiduccia-Mattheyses heuristic method in Fiduccia and Mattheyses (Proc. ACM/IEEE DAC, pp. 175?C181, 1982) for the circuit partitioning problem in very large scale integration of circuits and systems. The method uses much less computational cost than general local search methods. Then, an auxiliary function is presented which has the same global maximizers as the max-cut problem. We show that maximization of the function using MCFM can escape successfully from previously converged discrete local maximizers by taking increasing values of a parameter. An algorithm is proposed for the max-cut problem, by maximizing the auxiliary function using MCFM from random initial solutions. Computational experiments were conducted on three sets of standard test instances from the literature. Experimental results show that the proposed algorithm is effective for the three sets of standard test instances. 相似文献
12.
Discrete Filled Function Method for Discrete Global Optimization 总被引:6,自引:0,他引:6
A discrete filled function method is developed in this paper to solve discrete global optimization problems over strictly pathwise connected domains. Theoretical properties of the proposed discrete filled function are investigated and a solution algorithm is proposed. Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the applicability and efficiency of the proposed method. 相似文献
13.
Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison. 相似文献
14.
Blas Pelegrín Juani L. Redondo Pascual Fernández Inmaculada García Pilar M. Ortigosa 《Journal of Global Optimization》2007,38(2):249-264
In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer
linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like
algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete
location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions)
and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely
used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains
better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown
by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set
of known test problems are also provided. 相似文献
15.
16.
In this paper, a new filled function which has better properties is proposed for identifying a global minimum point for a general class of nonlinear programming problems within a closed bounded domain. An algorithm for unconstrained global optimization is developed from the new filled function. Theoretical and numerical properties of the proposed filled function are investigated. The implementation of the algorithm on seven test problems is reported with satisfactory numerical results. 相似文献
17.
提出一个基于滤子技术的填充函数算法, 用于求解带箱式约束的非凸全局优化问题. 填充函数算法是求解全局优化问题的有效方法之一, 而滤子技术以其良好的数值效果广泛应用于局部优化算法中. 为优化填充函数方法, 应用滤子来监控迭代过程. 首先给出一个新的填充函数并讨论了其特性, 在此基础上提出了理论算法及算法性质. 最后列出数值实验结果以说明算法的有效性. 相似文献
18.
19.
填充函数法是求解多变量、多极值函数全局优化问题的有效方法.这种方法的关键是构造填充函数.本文在无Lipschitz连续条件下,对一般无约束最优化问题提出了一类单参数填充函数.讨论了其填充性质,并设计了一个求解约束全局优化问题的填充函数算法,数值实验表明,算法是有效的. 相似文献