带面积约束电路划分的GRASP改进算法  

An improved GRASP algorithm for circuit partition with area constraint

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

机构地区：[1]福州大学数学与计算机科学学院,福建福州350108

出　　处：《福州大学学报（自然科学版）》2010年第4期497-503,共7页Journal of Fuzhou University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(60773126)

摘　　要：首先由改进后的GRASP算法构造初始划分,并作局部搜索产生一组优秀解;再由path-relink ing算法在优秀解间建立路径,搜索路径上的改进解.为满足面积约束,在GRASP算法的构造阶段、局部搜索阶段及path-relink ing算法中都引入面积约束.实验结果表明,与顺序GRASP算法和随机GRASP算法相比,改进的GRASP算法在满足面积约束的条件下能获得更好的划分结果.与改进的GRASP算法相比,由GRASP与path-relink ing相结合的混合算法能进一步改善划分结果,在最小划分上,改进程度最大达到9.8%,在平均划分上,最大达到8.3%.The algorithm generates initial feasible partitions by a randomized greedy method, and improves them by a local search method to produce a series of elite solutions. The modified algorithm is further improved by searching better feasible partitions along paths between elite solutions, which is called the path - relinking method. Experimental results indicate that, comparing to the sequential GRASP and the random GRASP algorithms, the modified GRASP algorithm obtains better feasible partitions. Especially, the GRASP algorithm with path -relinking improves the modified GRASP by 9.8% on the minimum cut - size, and by 8.3% on the average cut - size.

关 键 词：电路划分 面积约束 GRASP算法 path—relinking 

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