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

• 作者: 朱文兴 詹青青
• 来源期刊: 浙江大学学报（工学版）
• 学科: 工学
• 关键词: 电路划分 贪心随机自适应搜索过程 启发式策略 Path-Relinking
• 年，卷（期）: 2007,（10）
• 所属期刊栏目: 自动化技术、计算机技术
• 页码范围: 1679-1683
• 页数: 5页
• 分类号: TP301.6
• 字数: 4380字
• 语种: 中文
• DOI: 10.3785/j.issn.1008-973X.2007.10.016

摘要

为提高基于迭代改进的传统电路划分算法的划分质量,提出了一种基于贪心随机自适应搜索过程(greedy randomized adaptive search procedure,GRASP)的电路划分改进算法.GRASP由构造阶段和局部搜索阶段组成,能够快速构造较好的初始划分.在其构造阶段引入启发式子集选择策略,并与高效搜索技术Path-Relinking相结合,在各个局部最优解之间建立路径,从而有效搜索了局部最优解空间.实验结果表明,该算法与基本GRASP相比,能在合理的时间范围内改进解的质量,获得更好的划分结果.在获得的最小划分上,改进程度最大达到33.3%;而在平均划分上,最大达到27.4%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	朱文兴	福州大学离散数学与理论计算机科学研究中心	44	465	10.0	21.0
2	詹青青	福州大学数学与计算机科学学院	5	11	2.0	3.0