均匀设计抽样混合遗传算法求解图的二划分问题

遗传算法(GA)的运行机理及特点是具有定向制导的随机搜索技术，其定向制导的原则是:导向以高适应度模式为祖先的"家族"方向。以此结论为基础，利用均匀设计抽样(UDS)的理论和方法,对遗传算法中的交叉操作进行重新设计，并在分析图二划分问题特点的基础上，结合局部搜索策略，给出了一个求解图二划分问题的新遗传算法，称之为基于均匀设计抽样的混合遗传算法。最后将该算法与简单遗传算法和佳点集遗传算法进行比较。通过模拟比较,可以看出新算法不但提高了算法的求解速度和精度,而且避免了常有的早期收敛现象。

Solving 2-way graph partitioning problem using genetic algorithm based on uniform design sampling

Genetic Algorithm (GA) is a guided random search and the guiding direction always aims at the family whose ancestors have schemata with high fitness. Based on the results, the crossover operation in GA was redesigned by using the principle of random uniform design sampling and combining the locale search strategy. Then a new GA called Genetic Algorithm based on Uniform Design Sampling (UDS) was presented. The new GA was applied to solve the 2-way graph partitioning problem. Compared to simple GA and good point GA for solving this problem, the simulation results show that the new GA has superiority in terms of speed and accuracy and overcomes premature convergence.