中文摘要：

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