Solving 2-way graph partitioning problem using genetic algorithm based on Latin hypercube sampling
拉丁超立方体抽样遗传算法求解图的二划分问题

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.