Application Of An Improved Genetic Algorithm In TSP

Genetic algorithm is a kind of intelligent algorithm,which simulate the process of biological evolution.It has been widely used in complex problem processing,such an function optimization and combination optimization.As its randomness in operation,the convergent speed and the accuracy of the solution are not very ideal.Therefor,it is necessary to improve the algorithm.This paper put forward a genetic algorithm which is based on individual cognition and abandon probability model used early.The main work of this paper include following aspects:First of all,the chromosome structure of genetic algorithm is revised in this paper,and it introduces the promoter and redundant sequences.The promoter is used to control individual evolution.Individuals could have multiple selection operators,crossover operators and mutation operators,while enhance the flexibility of evolution greatly.The redundant sequence is used to record individual status information in the evolution process,and provide foundation for updating the promoter.Then,this paper proposes a tracking selection operator,self-matching crossover operator,chain type mutation operator and heap type mutation operator for the improved chromosome structure.These genetic operators can fully reflect the advantages of the promoter and redundant sequence.Afterward,this paper presents an evolutionary controller.It contains six kinds of operating mechanism,including evaluation mechanism,replication mechanism,regeneration mechanism,tracking mechanism,coverage mechanism and neutralization mechanism.Each mechanism play an important role in the evolution of the population.Finally,the genetic algorithm based on individual cognition is applied to solve traveling salesman problem.Experiments were carried out from three aspects: population diversity,convergence rate and solution precision.The results shows that the improved genetic algorithm can solve traveling salesman problem effectively.