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

EVOLUTIONARY STABLE STRATEGY ANT COLONY ALGORITHM FOR SOLVING GRAPH COLOURING

作　　者：赵焕平[1] 胡可[2] 李敬文[3] 

机构地区：[1]南阳理工学院计算机与信息工程学院,河南南阳473004 [2]南阳理工学院,河南南阳473004 [3]兰州交通大学电子与信息工程学院,甘肃兰州730070

出　　处：《计算机应用与软件》2013年第5期22-24,40,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(10771091)

摘　　要：针对图着色问题,在传统的启发式蚁群算法的基础上提出一种进化稳定策略蚁群算法。进化稳定策略蚁群算法针对蚁群算法的隐含并行性,利用变换因子自适应地更新信息素,动态自适应地调节启发式因子的作用参数,增强算法的搜索能力,加快算法的收敛速度,同时避免了传统蚁群算法容易陷入局部最优的问题。通过给地图着色的仿真实验结果表示,该方法对图着色问题的求解是可行、有效的,通过大量实验表明算法在求解质量上优于启发式蚁群算法。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.

关 键 词：图着色 蚁群算法 进化稳定策略 变换因子 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]