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

首先由改进后的GRASP算法构造初始划分， 并作局部搜索产生一组优秀解； 再由path-relinking算法在优秀解间建立路径， 搜索路径上的改进解. 为满足面积约束， 在GRASP算法的构造阶段、 局部搜索阶段及path-relinking算法中都引入面积约束. 实验结果表明， 与顺序GRASP算法和随机GRASP算法相比， 改进的GRASP算法在满足面积约束的条件下能获得更好的划分结果. 与改进的GRASP算法相比， 由GRASP与path-relinking相结合的混合算法能进一步改善划分结果， 在最小划分上， 改进程度最大达到9.8%， 在平均划分上， 最大达到8.3%.