The Application And Research Of Multi-population Ant Colony System Based On Adaptive Classification Mechanism

In order to improve the working efficiency of robots,this paper research for issues about robot patrol route planning and path planning.Firstly,several classical traditional ant colony algorithms,such as ant system,are studied and analyzed.Then,to improve the self-adaptive effect,the single-population algorithm is improved by classification mechanism.After that,the concept of information entropy is introduced to measure the diversity,and to decide when to and how to use the communication strategies.The heterogeneous ant colony algorithm based on entropy has been proposed as well.Further,by introducing game theory mechanism to deep the understanding of Multi-population communication mechanism,a universal communication mechanism for multi-population algorithms is constructed.The effectiveness of the proposed algorithm is verified by TSP experiments.Also,the algorithms proposed in this paper are applied to practical problems to verify its effect.In this paper,the main work have done as follows:Firstly,in order to improve the self-adaptability of the algorithm,with the idea of wolf pack algorithm,an improved ant colony algorithm based on dynamic classification is proposed.First of all,the population classification model is established according to the dynamic classification operator;Then,the head-effect strategy with roulette can improve the coordination mechanism and increase the communication between populations;At the same time,in order to increase the convergence speed,the dynamic pheromone update strategy with normalization can be taken with the ant algorithm pheromone update formula kept to reflect the influence of elite.In order to verify the effect,the grid method is used to build the robot motion space model.This algorithm is applied to the path planning problem and compared with several intelligence algorithm.The simulation results show that the algorithm can converge quickly and find the optimal path with fewer iterations with relatively high efficiency.Then,in order to strengthen the dynamic relationship among populations,information entropy is used to measure the diversity of algorithms,and a dynamic heterogeneous ant colony algorithm based on information entropy is proposed,which consists allotropic mechanism and the heterogeneous colonies.Entropy is used to measure the diversity,and to decide when to and how to use the communication strategy.Then the heterogeneous colonies with complementary advantages are proposed to balance the convergence speed and the diversity of the algorithm.Besides,two operators are proposed to improve the performance of the algorithm,such as the adaptive 3-Opt operator and the dynamic-pheromone-reset operator.Finally,a TSP example is used to verify the effectiveness of the algorithm.After that,in order to improve the robustness of the algorithm,an Entropy-Game based Multi-population Ant Colony Optimization is proposed.The core of this chapter is the composition of a versatile multi-population communication mechanism.First,the master-slave cooperative game mechanism is used,and the Shapley formula as well as the information entropy is used to adjust the weight of each operator.Meanwhile the rewarding-publishing operator is built to improve the convergence.Then,the introduction of tit-for-tat strategy for sub-populations can help collaborative learning and improve the diversity.Next,the introduction of coordination game mechanism based on Pareto Optimality can facilitate adaptive cooperation and improve the performance.Finally,this algorithm is tested in several TSP instances.The experimental results suggest that it has good performance with higher stability and higher precision in TSP instances.Finally,after the theoretical analysis and verification,to verify the performance of the proposed algorithms,experiments are carried out to solve the robot path planning problem.The point-to-point path planning is carried out by using the improved ant colony algorithm based on dynamic classification,and the multi-points route planning can be transformed into TSP,and the multi-population algorithm is used to solve this problem.The simulation is carried out by MATLAB and the experiment results show that the proposed algorithms can solve path planning problems with high efficiency and precision.