图着色问题的逆序蚁群算法研究

针对经典的图着色问题,依据传统图着色算法中逆序图着色的着色思想,结合蚁群算法的搜索机制,给出了逆序蚁群着色算法.根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点,使得算法具有较强的搜索全局最优解的能力.利用计算机生产大量随机图作为测试实例,对比逆序着色算法和逆序蚁群算法,实验结果说明逆序蚁群着色算法提高了求解质量,加快了收敛速度,证明了其优良特性.同时算法效率的提高,也保证了该算法可适用于较大规模的着色问题求解.此外,还进行了一系列对比试验,得出了关键参数的合理取值范围.

Reverse Order Ant Colony Algorithm for Graph Coloring Problem

According to the traditional reverse ordering graph coloring algorithm and combined with ant algorithm searching mechanism, A reverse order ants coloring algorithm is proposed. The dynamic reverse transfering color sequence can give the algorithm strong ability to search the global optimal solution. Large number of random graph coloring experiments show the advantages of reverse ants coloring algorithm, which can improve the quality of solution and make the convergence faster. The improvement of the efficiency of the algorithm also ensures that it can be applied to large-scale cololring problem solving. In addition, through series of computional test, reasonable values range of key parameters are validated.