求解图着色问题的最大最小蚁群搜索算法  

Max-Min ant Search Algorithm for Solving Graph Coloring Problem

作　　者：朱虎[1] 宋恩民[2] 路志宏[1] 

机构地区：[1]华中科技大学数学与统计学院,湖北武汉430074 [2]华中科技大学计算机科学与技术学院,湖北武汉430074

出　　处：《计算机仿真》2010年第3期190-192,236,共4页Computer Simulation

基　　金：基于网格的数字化医疗决策支持系统(2006AA02Z347)

摘　　要：针对图着色问题在传统的启发式蚁群算法的基础上提出了一种最大最小蚂蚁系统搜索算法,最大最小蚁群系统将正反馈、分布式计算特点与启发式算法思想有效的结合起来,可以改进信息素更新策略和引入了信息素平滑机制,使得加快了求解的收敛速度,又有效的避免了启发式算法易陷入局部最优。通过给中国地图着色的仿真实验结果表明,方法对图着色问题的求解是可行、有效的;并通过大量的实验证明了算法在求解的效率和求解的稳定性方面优于传统的蚁群算法。The paper proposes a new Max - Min ant search algorithm for graph coloring problem based on the traditional heuristic ant algorithm. The new algorithm combines the feature of positive feedback, distributed computing of Max - Min ant algorithm with heuristic algorithm effectively, and can improve the strategy of pheromone updating and introduce smoothing mechanism of pheromone. The algorithm not only accelerates convergence but also avoids running into local minimum of heuristic algorithm easily for solving problem. The simulation result by coloring Chinese map shows that the effectiveness and feasibility of the method; and the results of lots of experiments prove that the new algorithm is better than basic ant algorithm on computational efficiency and stability.

关 键 词：图着色 蚁群搜索算法 最大最小蚂蚁搜索算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]