图着色问题的新遗传算法

摘要

针对遗传算法求解图着色问题需多次产生初始种群的问题,提出了一种改进算法.该算法采用比较机制,淘汰不可行的基因,然后使用动态的适应度函数,使得有效个体以较大的概率存活到下一代种群中,从而达到无需多次产生初始种群的目的.与传统框架下的算法相比,新算法求得最优解的时间至少缩短了51%,且具有从一个局部最优解快速跳到下一个局部最优解,最终收敛到全局最优解的优点.