求解图着色问题的进化稳定策略蚁群算法

摘要

针对图着色问题,在传统的启发式蚁群算法的基础上提出一种进化稳定策略蚁群算法.进化稳定策略蚁群算法针对蚁群算法的隐合并行性,利用变换因子自适应地更新信息素,动态自适应地调节启发式因子的作用参数,增强算法的搜索能力,加快算法的收敛速度,同时避免了传统蚁群算法容易陷入局部最优的问题.通过给地图着色的仿真实验结果表示,该方法对图着色问题的求解是可行、有效的,通过大量实验表明算法在求解质量上优于启发式蚁群算法.%In the paper we propose an evolutionary stable strategy ant colony algorithm for graph colouring problem based on the traditional heuristic ant colony algorithm.Aiming at the implicit parallelism of ant colony algorithm,the new algorithm uses conversion factor to update the pheromone adaptively,and dynamically and adaptively adjusts the parameters of heuristic factor,therefore enhances the search capability of algorithm and accelerates the algorithm' s convergence speed as well while avoids running into local minimum which the conventional ant colony algorithm is prone to.It is demonstrated by the simulation experimental result of colouring the map that using this method to solve graph colouring is feasible and effective； a great deal of experiments also proves that the new algorithm outperforms the heuristic ant colony algorithm in solution quality.