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

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

Improved GRASP based circuit partitioning algorithm

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%.