Dual-population Ant Colony Algoriyhm Based On Adaptive Learning Mechanism And Its Application

Ant Colony Algorithm is a bionic algorithm that mimics the foraging behavior of ant colonies.It is robust,can be parallelized,and easily combined with other algorithms.It shows a strong advantage in solving complex combinatorial optimization problems.At present,ant colony algorithm has been widely used in many fields,and has achieved good results and has gradually attracted the attention and research of more experts and scholars.Based on the existing theoretical research of ant colony algorithm,this paper proposes a two-population ant colony algorithm with adaptive learning mechanism for the shortcomings of ant colony algorithm with slow convergence rate and easy to fall into local optimum.After experiments on TSP problems of different scales,the results show that the convergence speed and accuracy of the algorithm are improved.The specific work is as follows:Firstly,an adaptive simulated annealing ant colony algorithm based on the theory of max-min ant system was proposed in this paper.The algorithm accepting the difference solution with a certain probability at a high temperature,that optimizes the path after each iteration and increases the global searching ability of the algorithm,and an adaptive pheromone updating strategy is adopted to increase the global search ability of the algorithm in the early stage and accelerate the convergence speed of the algorithm in the later stage;In the low temperature stage,the convergence rate of the algorithm is accelerated by the value of the temperature coefficient,and then the tempering mechanism is adopted to avoid the local optimum and the quality of the solution is improved.At the same time,the 3opt algorithm is used to further optimize the quality of the algorithm.The experimental results show that the proposed algorithm achieves a certain degree of improvement in the convergence speed and quality of the algorithm in small and medium-sized cities.Secondly,in order to better solve the large-scale TSP problem.In this paper,the adaptive learning mechanism between two populations is used to improve the performance of the algorithm by referring from the behavior of ants' group exchange and cooperation in reality.The algorithm introduces a reward penalty model after two population exchanges.The reward operator improves the convergence speed of the algorithm and the penalty operator improves the diversity of the algorithm.Two population cooperative search paths by SA-MMAS(Adaptive simulated annealing ant colony algorithm based on max-min ant system)and MMAS(MAX-MIN Ant System),and then the ant colonies dynamically communicate pheromone according to different city sizes which enhanced algorithm robustness on a city scale.After communication between the two colonies,the incentive penalty model was used to give dynamic feedback to the learning cooperative behavior between the two colonies,thus balancing the diversity and conver gence speed of the algorithm.Verified by 17 classic TSP(Traveling Salesman Problem)instances,the results show that the algorithm can obtain the optimal solution or near optimal solution with fewer iterations.It is more effective for medium and large-scale TSP problems,thus verifying the efficiency and feasibility of the algorithm.Finally,In order to verify the practical application effect of the proposed algorithm,the improved ant colony algorithm is applied to the actual mobile robot path planning scenario based on ROS platform.And the performance of the algorithm and ant colony algorithm in robot path planning is compared by MATLAB simulation.At last the components in ROS are used to realize the communication of multiple robots.The results show that the proposed algorithm can not only find a better path than the original ant colony algorithm in the actual robot path planning,but also has a shorter time and better effect.