图着色问题由最初的“四色猜想”问题引申而来,研究者们不断将其应用于解决各类实际问题,包括频道分配问题、任务调度问题、停机位分配问题等组合优化问题。虽然图着色问题的应用范围非常之广,但是确定图的着色数却是一个十分困难的事情。关于图着色的算法研究非常之多,大体分为精确算法和近似算法。精确算法借助严格的数学方法来获得最精确最优解,但其复杂度相当高,因此只能把它当作一种理想的求解算法而一般不应用于实际求解。近似算法凭借其快速搜索的性能而获得问题的更优解,在问题研究领域中得到广泛应用。目前关于图着色问题的近似算法求解方法很多,而遗传算法和蚁群算法作为最具代表的两种算法,在图着色问题上得到不断应用和改进。遗传算法由于自身具有的特性(自组织、自适应性、全局收敛性等特点),因此能够寻求更优解。但是由于其复杂的结构设计(包括编码方式、适应度函数的设定、遗传算子的设定),微小的设计偏差都会影响算法求解的结果。因此针对图着色这一特殊问题,提出了合适的编码方式和采用特殊的遗传算子—换位算子、切断算子、拼接算子等；借助符号编码方式来很好的描述问题的约束条件；借助换位算子来保证下一代群体始终向着更优解的方向搜索,加快收敛到最优解的速度；借助切断算子和拼接算子为染色体种群的多样性发展提供了更多可能。在使用改进的遗传算法求解图着色问题时,虽然比传统的遗传算法的收敛速度更快,但是其初始群体比较单一,为了减少初始种群的个数从而达到求解更优解的目的,提出用一种算法的搜索结果作为改进遗传算法的初始解。由于贪心算法实现简单,寻优度不高；禁忌搜索算法本身也是对初始群体依赖性较大,也不适于解决改进遗传算法所要解决的问题；模拟退火算法虽避免了对初值的依赖性,但是求解结果并不能方便的转换为传统遗传算法的初始解结构。蚁群算法具有局部收敛性,能准确的描述图着色问题的约束条件,并且所求解的结果能很方便的转换为传统遗传算法的初始解结构,因此更适合于进行初始化搜索。本文首先介绍了传统遗传算法的设计及其用于求解图着色问题时存在的缺陷,针对图着色问题的特殊性,根据遗传算法的编码方式和特殊算子,提出了改进的遗传算法模型,即编码方式采用符号编码,而遗传算子的设计则采用基因换位算子、拼接算子、切断算子来取代原来的交叉算子,使求解过程始终朝着更优的方向发展,加快了收敛速度。然后针对改进遗传算法的求解模型存在的初始群体单一性问题,提出了用蚁群搜索算法为其提供初始解的思想。最后总体介绍了融合算法的求解过程,并用Matlab工具对标准着色算例的图和大量随机生成的图进行仿真实验,实验结果证明了本文提出的算法的有效性。