面向图分割问题的确定性退火控制算法  

A deterministic annealing control algorithm for a general graph partitioning problem

作　　者：吴征天 高庆 WU Zheng-tian;GAO Qing(School of Electronic and Information Engineering,Suzhou University of Science and Technology,Suzhou Jiangsu 215000,China;Department of Mechanical Engineering,Politecnico di Milano,Milan 20156,Italy;School of Automation Science and Electrical Engineering,Beihang University,Beijing 100191,China;Beijing Advanced Innovation Center for Big Data and Brain Computing,Beihang University,Beijing 100191,China)

机构地区：[1]苏州科技大学电子与信息工程学院,江苏苏州215000 [2]米兰理工大学机械工程学院,意大利米兰20156 [3]北京航空航天大学自动化科学与电气工程学院,北京100191 [4]北京航空航天大学大数据科学与脑机智能高精尖创新中心,北京100191

出　　处：《控制理论与应用》2019年第11期1936-1941,共6页Control Theory & Applications

基　　金：国家自然科学基金项目(61803279,61903016);德国亚历山大冯洪堡基金项目;中国国家留学基金委项目资助~~

摘　　要：图分割问题是一种典型的NP–hard问题,如何对其进行高效求解一直都是学界和工业界的一个难题.本文构建了一种新型的确定性退火控制算法,提供了图分割问题的一种高质量近似解法.算法主要由两部分构成:全局收敛的迭代过程以及屏障函数最小点组成的收敛路径.本文证明了,当屏障因子从足够大的实数降为0,沿着一系列由屏障问题最小点组成的收敛路径可以得到图分割问题的一种高质量的近似解.仿真计算结果表明本文所构建算法相比已有方法的优越性.The graph partitioning problem is well known to be NP–hard and it is still a challenge to solve this problem effectively. In this paper, a new deterministic annealing control algorithm is developed, with which an approximation solution to a general graph partitioning problem is obtained. This algorithm can be decomposed into a globally convergent iterative procedure and a path of minimum points of a barrier problem. In the algorithm, a high-quality solution is obtained along a path of a series of barrier problems’ minimum points when the barrier parameter decreases to 0. Simulation results show the advantages of the proposed algorithm over the existing approach.

关 键 词：图分割问题 屏障因子 近似算法 确定性退火控制算法 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]