ROUTE Planing Base On Improved Genetic Algorithm

Path planning technology has been widely applied in the aircraft, the surface vessels, ground vehicles and robot navigation system. The main methods which solving the route planning problem include AStar algorithm, genetic algorithm, Ant colony algorithm and so on.Genetic Algorithm (GA) is a bionic method,which mocks the process of biological evolution.How to design genetic algorithm for solving the route planning problem efficiently, has attracted much attention at home and abroad, meanwhile a lot of lectures emerges recently.The area of aircraft route planning of the planning is very extensive, forming a huge search space.As is known, when the basic genetic algorithm is utilized to solve the route planning, it suffers from a large number of deficiencies, such as long time for convergence, large memory require, when the environment is complex, difficulty of constructing feasible solution, and the effect of crossover and mutation operation for the evolution ability of genetic algorithm is poor.To overcome above shortcoming, some measures for enhancing performance are proposed on the basic of genetic algorithm in this thesis as follows:(1) Both retroversion and taboo strategy are incorporated into heuristic neighboring search to guarantee the feasibility of path.(2) The memory requirement and computing cost are reduced by extracting key chain from original feasible route.(3) The optimization performance is improved by locally adaptive mutation and crossover operator acting on key chains.A path planning simulation platform in three-dimensional space is developed using visual C++6.0+OpenGl environment, under which three algorithms such as standard ACO, A*and the new algorithms presented in this article are implemented and tested, the performance are compared each other sequentially. Experimental results show new algorithm can plan the safety trajectory of robot under complex obstacle environments and overmatch other algorithms, as well as running time can meet the demand of practical applications.