Improvement Of Ant Colony Optimization Algorithm And Its Applications In Several Optimization Problems

Ant colony optimization(ACO)algorithm is proposed based on the intelligent behavior of ant colony in the foraging process.The algorithm has many advantages,such as parallelism,positive feedback,and self-organization.The ACO algorithm was first used to solve Traveling Salesman Problem(TSP),and later was used to solve problems such as path planning and data mining.TSP is to find a Hamiltonian circuit with minimum weight in the undirected weighted graph;path planning is one of the important topics in the field of robotics research,and its purpose is to find an optimal path for the robot to meet specific indicators in an obstacle environment.When using the ACO algorithm to solve these two problems,there are defects such as low convergence rate and being susceptible to trap in local optimal solutions.For this reason,this paper proposes three improved ACO algorithms to solve these two problems.The main work is summarized as follows:(1)Concerning the drawbacks of the ACO algorithm such as low convergence rate and being susceptible to trap in local optimal solutions,an ACO algorithm based on an improved pheromones double updating strategy and a local optimization strategy,called IPDULACO,was proposed for solving TSP.Secondary update was performed on the pheromones of the sub-paths whose contribution degree to the colony's currently obtained optimal solution are bigger than a prescribed contribution threshold,in order to increase the selection probability of the sub-paths that constitute the potential optimal solution and hence to accelerate the convergence rate of the proposed algorithm.Also,when the ant colony gets trapped in local optimal solution in the search process,the random insertion method is utilized to change the city sequences of the current optimal solution in order to enhance the algorithm's ability of jumping out of local optima.(2)For the unknown and time-varying characteristics of dynamic environment,a new method for mobile robot path planning is proposed in this paper.In this method,the environment model established by the grid method is convexized first in order to avoid falling into U-shaped traps when the robot moves along the planned path and thus to speed up the path planning.Second,a double-layer ant colony optimization(DACO)algorithm is proposed.In each iteration of DACO algorithm,a path is found by the outer ACO algorithm first,then on basis of which a small environment is constructed,and then the robot re-plans path by the inner ACO algorithm in the small environment;if the newly obtained path is better,then the global optimal path is updated and a new pheromone secondary update strategy proposed in this paper is executed.At last,three kinds of obstacle avoidance strategies are put forward according to the volume and speed of different dynamic obstacles in the environment.In the dynamic environment,the DACO algorithm first plans a global optimal path from the starting point to the destination with respect to the current environment for the robot,then from the current starting point,the robot acquires the dynamic environment's information by its embedded sensor and implements Waiting-for-obstacle avoidance strategy,Collision avoidance strategy or Rear-end collision avoidance strategy when necessary,and then the robot moves to next position as a new starting point.Simulation results show that theproposed can plan a safe and shortest path for mobile robot in real time under dynamic environment and is a practical and effective method for mobile robot path planning.(3)Concerning the drawbacks of being susceptible to trap in local optimal solutions,when the ACO algorithm was used in three-dimensional path planning problems,and concerning the characteristics of three-dimensional environment,an improved ACO algorithm is proposed.Firstly,according to the distance from the next optional node to the end point,different size weights are assigned.The near node gives a larger weight,and the far node gives a smaller weight.In addition,in order to improve the quality of the optimal solution and speed up the convergence,the node selection probability is improved by adding a height factor,so as to compel the algorithm to explore the area with high fitness values.The simulation results also show the effectiveness of the improved algorithm.