Research On Path Planning Problem Based On Improved Ant Colony Optimization

Path planning problems is a class of optimization problems that have a wide range of use scenarios in daily life and industrial production.Due to the the scale-up of living space and production of humans,the disadvantages of inefficient and slow frequently occur in traditional methods which cannot solving these problem well.The Ant Colony Optimization has many excellent characteristics such as strong global search ability,positive feedback,robuness and potential parallelism,it has been widely used in path planning problem and other fields since it presented the 1990 s and has achieved great performance.In this thesis,two improved ant colony algorithms are designed to solve the capacited vehicle routing problem and the robot path planning problem.The major work of the thesis are as follows.1.A multi-strategy improved ant colony algorithm is proposed for the Capacitied Vehicle Routing Problem.Firstly,a state transition rule based on node demand is designed,which makes the ants make path construction based on three elements: pheromone,heuristic information and node demand information,thus increasing the possibility of ants finding a path that meets the constraints;secondly,the pheromone is perturbed with a certain probability using sigmoid function during the iterative process to weaken the gap of pheromone level on different paths,which gives ants more opportunities to explore suboptimal paths to find better solutions.Then,an adaptive pheromone evaporation coefficient is designed.which determines the pheromone evaporation by the distribution of current generation path lengths.Finally,a local search operator 2-opt is introduced to speed up the iterative process of the algorithm.Tests on several instances demonstrate the effectiveness of the improved algorithm.2.An improved ant colony optimization algorithm based on pheromone initialization and penalty function is proposed for the robot path planning problem.Firstly,to solve the problem that the initial phenomeno distribution cannot guide the search direction of ant colony effectively when solving the RPPP,the pheromone initialization process is introduced to guide the search direction of the ant colony and speed up the iteration process before the iteration starts.Secondly,an angle factor that depict the turning of the path is designed,which is added to the fitness function as a penalty factor,gradually guide the search to a smoother path with fewer turns in the iterative process to improve the overall quality of the path.Finally,the performance of the improved algorithm is verified on two instances of different scale and complexity.