一类组合优化问题的新解法及其收敛性

A Novel Algorithm and Its Convergence for a Class of Combinatorial Optimization Problems

混合 LT 法是一种解组合优化问题的新方法,这种方法将约束分为两部分,其一用 Lagrange 方 法来处理,另一部分用罚函数来处理。与现存的 Hop?eld 网络比较,这种方法有几个优点:它 既能用于二次函数,还能用于非二次函数;且在控制人为的加权参数时,它减少了对外部的依 赖。本文提出了一种新的混合 LT 法,使用它,能更快找到更准确的解,并且对这种方法作了收 敛性分析,给出了收敛性的必要条件和充分条件。从而说明这种方法是可行的和有效的,可用于 很多组合优化问题。

The Hybrid LT scheme is a new type of schemes for combinatorial optimization problems. The constraints are divided into two parts. One is treated by Lagrange approach, and the other by penalty or barrier function. In cmparison with the existing Hop?eld type networks, the new scheme has several new features. It can be applicable to non-quadratic energy functions, and has reduced the dependence on arti?cial weighting parameters which have to be controlled externally. A new hybrid LT algorithm is proposed in this paper, by which we can ?nd a high quality solution quickly. In addition, the convergence on the proposed algortihm is investigated, and necessary condition and su?cient condition of convergence were given. The theoretical analysis and computer simulation results revealed that the proposed algorithm is e?cient and convergent for a very wide variety of combinatorial optimization problems.