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

摘要

Based on the traditional reverse ordering graph coloring algorithm and combining with searching mechanism of ant algorithm,a reverse order ant coloy coloring algorithm was proposed to resolve graph coloring problems.In the algorithm according to the color progress and the adjacent points degree,the dynamic reverse transferring color sequence can give the algorithm strong ability to search the global optimal solution.A large number of random graph coloring experiments show the advantages of the new algorithm.The algorithm can improve the quality of solution and make the convergence faster.An improvement of the efficiency of the algorithm also ensures that it can be applied to solve large-scale coloring problems.In addition,through series of computer test, reasonable value ranges of key parameters were validated.%针对经典的图着色问题，依据传统图着色算法中逆序图着色的着色思想，结合蚁群算法的搜索机制，给出了逆序蚁群着色算法。根据着色进度和未着色点的相邻点度数随机动态逆序选择新的着色点，使得算法具有较强的搜索全局最优解的能力。利用计算机生产大量随机图作为测试实例，对比逆序着色算法和逆序蚁群算法，实验结果说明逆序蚁群着色算法提高了求解质量，加快了收敛速度，证明了其优良特性。同时算法效率的提高，也保证了该算法可适用于较大规模的着色问题求解。此外，还进行了一系列对比试验，得出了关键参数的合理取值范围。