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

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