组合优化是一个新兴的领域,它与数学最优化一样是运筹学的一个重要组成部分,而且是偏重应用的数学领域。本文对图与组合优化问题中的一个典型问题,即图的顶点着色问题进行了研究。图的顶点着色问题是典型的NP完全组合问题,在调度安排、时间表编制等方面有许多应用,构造求图顶点着色问题的近似最优算法有重要的现实意义。粒子群算法是一种新的基于群体智能的随机优化算法,同其它的进化算法相比,其最具吸引人的特征是简单容易实现和更强的全局优化能力。为此,粒子群算法一经提出,立刻引起了演化计算等领域的学者们的广泛关注,并在短短的几年时间里出现大量的研究成果,形成了一个研究热点,在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。本文给出了标准粒子群的图顶点着色的算法,设计了图顶点着色问题的编码方法和适应度函数,确定了粒子群的飞行方式。并通过引入模拟退火算法克服了标准粒子群陷入局部最优的缺点,提高了粒子群体的搜索性能。随后,通过对粒子群飞行速度进化方程的本质性的研究,由它的进化特点与遗传算法的相应部分进行类比,设计出了遗传粒子群算法,通过遗传算法中交叉和变异算子的作用,同样的实现了粒子速度的更新。并且,实验结果证明,这种遗传粒子群算法在图顶点着色问题中比标准粒子群算法搜索的准确性更好。但是由于遗传算法在收敛速度上的不足,我们在粒子飞行过程中加入了模拟退火算子,大幅地提高了算法的收敛速度。