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

摘要

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