CAJ | 학술논문

针对图着色问题在传统的启发式蚁群算法的基础上提出了一种最大最小蚂蚁系统搜索算法,最大最小蚁群系统将正反馈、分布式计算特点与启发式算法思想有效的结合起来,可以改进信息素更新策略和引入了信息素平滑机制,使得加快了求解的收敛速度,又有效的避免了启发式算法易陷入局部最优.通过给中国地图着色的仿真实验结果表明,方法对图着色问题的求解是可行、有效的;并通过大量的实验证明了算法在求解的效率和求解的稳定性方面优于传统的蚁群算法.
침대도착색문제재전통적계발식의군산법적기출상제출료일충최대최소마의계통수색산법,최대최소의군계통장정반궤、분포식계산특점여계발식산법사상유효적결합기래,가이개진신식소경신책략화인입료신식소평활궤제,사득가쾌료구해적수렴속도,우유효적피면료계발식산법역함입국부최우.통과급중국지도착색적방진실험결과표명,방법대도착색문제적구해시가행、유효적;병통과대량적실험증명료산법재구해적효솔화구해적은정성방면우우전통적의군산법.
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.