基于贪心随机自适应搜索的电路划分改进算法  

Improved GRASP based circuit partitioning algorithm

作　　者：詹青青[1] 朱文兴[2] 

机构地区：[1]福州大学数学与计算机科学学院,福建福州350002 [2]福州大学离散数学与理论计算机科学研究中心,福建福州350002

出　　处：《浙江大学学报（工学版）》2007年第10期1679-1683,共5页Journal of Zhejiang University：Engineering Science

基　　金：福建省自然科学基金资助项目(2006J0030)

摘　　要：为提高基于迭代改进的传统电路划分算法的划分质量,提出了一种基于贪心随机自适应搜索过程(greedyrandomized adaptive search procedure,GRASP)的电路划分改进算法.GRASP由构造阶段和局部搜索阶段组成,能够快速构造较好的初始划分.在其构造阶段引入启发式子集选择策略,并与高效搜索技术Path-Relinking相结合,在各个局部最优解之间建立路径,从而有效搜索了局部最优解空间.实验结果表明,该算法与基本GRASP相比,能在合理的时间范围内改进解的质量,获得更好的划分结果.在获得的最小划分上,改进程度最大达到33.3%;而在平均划分上,最大达到27.4%.An improved circuit partitioning algorithm based on the greedy randomized adaptive search procedure （GRASP） was presented to improve the circuit partitioning quality of traditional iterative improvement-based algorithms. GRASP consisted of a construction phase and a local search phase and could construct good initial partitions quickly. In the construction phase, a heuristic strategy was introduced to select clusters. A very efficient searching technique called Path-Relinking was integrated into the GRASP iterative process to build paths among local optimal solutions and effectively explore the local optimal solution space. The experimental results indicated that compared to the basic GRASP, the modified algorithm improved the solution quality in a reasonable period, and obtained better partition. The minimum cut-size reached 33.3% while the average cut-size was up to 27.4%.

关 键 词：电路划分 贪心随机自适应搜索过程 启发式策略 PATH-RELINKING 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]