现实生活中许多复杂的问题都可通过分类、抽象、简化的思想转化成图论问题进行研究解决,如最大支配集、加工调度、任务分配、排课表等典型的组合类问题,而图染色作为图论中一个重要的研究分支,是解决实际问题的一个重要途径。近些年来,一些经典的智能算法被用来研究和尝试解决图染色问题,如粒子群算法、遗传算法、神经网络算法等,但目前这些算法普遍仅应用于解决图的正常点染色和正常边染色,而对于图染色问题中多约束条件的染色问题,公开发表的文献中尚不多见,因此寻求新的智能算法来解决图的多约束条件染色问题是国内外图论研究者都感兴趣的一个重要课题。图的邻点色和可区别染色问题,在已公开发表的文献中对它们的研究都局限于如正则图、星图、完全图等的特殊图,尚无解决一般图的邻点色和可区别染色、点和可区别染色问题的方法。本文根据两种图的色和可区别染色的定义,分别设计了基于多目标优化的染色算法,对算法的正确性、收敛性和复杂度进行了分析,并通过大量的实例测试,得到了一些很有意义的结果。本文的具体工作如下:⑴介绍了一些基本染色概念及相关猜想,并同时给出有关内容的研究背景及目前国内外的研究动态。⑵介绍了两个经典的智能算法(粒子群算法、遗传算法)的基本思想、流程,及其在图染色中的应用,并对这些算法在解决图染色问题的性能上进行了分析。⑶给出了随机图的生成算法和生成有限点数所有伪非同构图的算法,详细描述了算法步骤,并分别对这两种算法进行了算法测试,为之后染色算法的研究提供了基础数据支持。⑷设计并实现了图的色和可区别染色问题中的邻点和可区别边染色、邻点和可区别全染色、点和可区别边染色和点和可区别全染色四个智能优化算法。四个算法的整体思路都是将其染色问题分解为多个特定功能模块的子问题,依次按序通过对子问题的逐步迭代调整直到子问题解决成功,之后以不改变前一子问题的成功状态为前提解决后一个子问题,当所有子问题都成功解决后,即代表该染色成功,算法结束。文中给出了算法的详细流程及测试案例,分析了算法的正确性、收敛性和时间复杂度,测试实例为7个点以内所有伪非同构图和1000个点以内边密度较小的1万个随机连通图,通过对实验结果的分析,表明算法具有较好的执行效率和不算高的时间复杂度,同时给出了若干有意义的经过验证的结论。