Abstract: In order to overcome the problems of slow convergence and low quality when the ant colony algorithm solves the Traveling Salesman Problem（TSP）, this paper proposes a new self-adaptive double-population ant colony algorithm RBAC with entropy. Firstly, the ant colony is divided into red ant colony and black ant colony. The red ant colony introduces the feedback operator in the path selection to optimize the quality of solution. The black ant colony introduces the load operator and the feedback operator to accelerate the convergence speed in the pheromone update rule and prevent falling into local optimum. Secondly, the entropy is used to control the division of red-black ant colony. When the entropy reaches the target value, the red ant colony is inactivated and the corresponding number of black ants are copied, so that the quality of the solution is improved in the prophase and the convergence speed is accelerated in the later stage. Finally, RBAC is applied to solve the TSP problem and compared with the classical ACS algorithm. The results show that RBAC achieves a good balance between the quality of the solution and the convergence speed, especially in large-scale urban problems.

Key words: entropy, ant colony algorithm, adaptive partitioning, feedback operator, load operator

摘要： 为了克服蚁群算法解决旅行商问题（TSP）存在的收敛速度慢和解的质量不高等问题，提出了一种新的引入熵的自适应双种群蚁群算法RBAC。将蚁群划分为红蚁群和黑蚁群，红蚁群在路径选择中引入反馈算子优化解的质量，黑蚁群在信息素更新规则引入负荷算子和反馈算子加快收敛速度并防止陷入局部最优。运用信息熵调控红黑蚁群的划分，当熵值达到目标数值时使红蚁群失活并复制相应数量黑蚂蚁，从而前期提高解的质量，后期加速收敛速度。应用RBAC求解TSP问题，并与经典ACS算法进行比较，结果表明RBAC算法在解的质量和收敛速度之间达到良好的平衡，尤其在大规模城市问题中效果更好。

关键词: 熵, 蚁群算法, 自适应划分, 反馈算子, 负荷算子