现实生活中有很多实际问题是将某种对象的集合按照一定的规则进行分类的,而图染色问题恰好是按照某种规则对图中的顶点、边等元素进行分类的,所以很多实际问题都可以抽象成图,并利用图染色的方法解决。图染色问题是图论研究领域的主要方向,国内外的专家学者们已经做了大量的研究工作来寻求解决各种染色问题的具体方法。常见的有经典的智能算法,如遗传算法、模拟退火算法等。对于较小规模的图来说,使用这些算法来解决图染色问题时可以得到最优解或次优解。但是当要求解的图的规模增大时,算法的时间复杂度及算法的效率都会受到很大影响。另外,这些算法只能用来解决点染色、边染色这2个基本的染色问题,对于本文要研究的染色条件稍微复杂的可约染色,这些算法是解决不了的,所以需要寻求新的算法来解决。对于图的可约染色问题,在已公开发表的文献中只是给出了相关的定义,或是针对特殊图如星扇轮等给出了一些有用的结论,具体解决问题的方法目前还没有。所以本文针对随机图(无向简单连通图)的点可约边染色、点可约全染色、邻点可约边染色、邻点可约全染色4个问题,提出了相应的解决方案。本文的主要研究工作有以下几个方面。(1)介绍了图论及图染色的发展过程,给出了本文的研究目的及意义。(2)介绍了经典的智能算法在图染色中的应用,分析了这些算法的优点及不足。(3)针对随机图,设计了4个启发式多目标优化算法,分别实现了点可约边染色、点可约全染色、邻点可约边染色、邻点可约全染色问题。对于点可约染色,其基本思想是将目标问题分解成几个子问题,设计相应的子约束函数,然后根据这些子约束函数进行迭代调整,逐步解决每个子问题,最终使得图中度数相同的所有顶点其色集合相同,此时总目标函数的值为0,染色成功,算法结束。相比点可约染色,邻点可约染色算法的基本思想是通过逐步迭代调整使得图中度数相同且相邻的顶点其色集合相同。文中首先对算法都进行了详细的描述;其次分别对4个算法进行了测试,同时也给出了部分实验的结果;再次从正确性、收敛性(单调性、有界性)以及时间复杂度3个方面对算法进行了详细分析,得到算法的时间复杂度为O(n3);最后对4个算法进行了总结。