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

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