Abstract: Based on the idea of sequential heuristic search, this paper proposes a new ant colony optimization algorithm for the classical graph coloring problem to effectively avoid the weakness of easily running into local minimum of heuristic research. Series of numerical simulations and experiments show the effectiveness and generality of the method.

Key words: graph coloring, heuristic search, ant algorithm

摘要： 针对经典的图着色问题，该文在随机序列启发式搜索求解的基础上，引进蚂蚁算法优化思想，设计了一种新型算法，有效地避免了启发式搜索易陷入局部极小的缺陷。通过给地图着色和仿真实验结果表明，该方法对图着色问题的求解是可行、有效的，且具有通用性。

关键词: 图着色, 启发式搜索, 蚂蚁算法