文 献 综 述
一、研究背景
在图论领域的一个无向图中，满足两两之间有边连接的顶点的集合，被称之为该无向图的团。团是图论中的基本概念，可用于许多数学问题和图的构造。通常将顶点团覆盖问题转换成图着色问题进行研究与解决。
图着色问题（Graph Coloring Problem, GCP） 又称着色问题，是最著名的NP-完全问题之一。内容包括点着色、边着色、图的全着色等。GCP在组合分析和实际生活中有这广泛的应用背景，如任务调度。资源分配。排课表、VLSI布线和测试等，目前大量的科技、管理及工业设计等领域问题都可归结为图着色问题来解决；一些典型的组合问题，如最大支配集、二次分配、最大覆盖问题等也都可以转化为图着色问题来加以研究。
对“四色猜想”和“五色定理”的证明曾相继引出许多理论结果，以及有关色多项式和一些着色数上界的结论。后来出于应用需要，更多的研究集中到了算法设计方面。早期的算法研究主要是诸如基于布尔代数运算的着色算法和基于深度优先检索的回溯算法等经典方法，后来在用传统方法解决复杂及较大规模的问题出现困难时，一些近似算法或启发式算法陆续问世，而近些年来随着智能算法的发展，遗传算法和模拟退火等自适应算法逐渐受到了人们的重视。但由于图着色问题是个典型的NP-难题，大部分早期算法的时间复杂性为指数级的，而智能算法在图着色方面的应用还处于试探阶段，成果较少。
图着色问题主要分为点着色、边着色、图的全着色。经一定的变换，图的边着色和全着色都可以等价地转化为图的点着色。点着色是对图G(V,E)的顶点进行着色，要求将每个顶点涂上一种颜色，使得任何相邻顶点都具有不同颜色。若用K种颜色能够对G的顶点进行一种着色，就称G(V,E)是K点可着色的，若K为图G(V,E)的最小着色数，则称图G(V,E)为K色图。
二、Ant-based Algorithm 蚁群算法
蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了
将蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。
与其他优化算法相比，蚁群算法具有以下几个特点：
