拉丁超立方体抽样遗传算法求解图的二划分问题

Solving 2-way graph partitioning problem using genetic algorithm based on Latin hypercube sampling

图的二划分问题是一个典型的NP-hard组合优化问题,在许多领域都有重要应用.近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想.基于理想浓度模型的机理分析,利用拉丁超立方体抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个解决图二划分问题的新的遗传算法,称之为拉丁超立方体抽样遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较,可以看出新的算法提高了求解的质量、速度和精度.

The 2-way graph partitioning problem is a typical NP-hard combination optimization, and is significantly applied to many fields of science and engineering. Recently, many intelligent optimization methods including the traditional genetic algorithm（GA） are employed to solve this problem, but the result is not effective as we desired. Based on the ideal density model, we redesign the crossover operation in GA by using the Latin hypercube sampling, and combined the result with the local search strategy of the 2-way graph partitioning problem; thus, presenting a new genetic algorithm based on Latin hypercube sampling for solving the 2-way graph partitioning problem. Comparison of simulation results in solving the 2-way graph partitioning problem with this new GA, the simple GA and the good point GA shows that this new method has superiority in speed, accuracy and precision.