Research On Intelligent Algorithm For Traveling Salesman Problem

In recent years,with the rapid development of logistics and transportation industry,the problem of path optimization has attracted the attention of many scholars again.As one of the basic problems of path optimization and classical operations research,the travel salesman problem(TSP)has been widely concerned by relevant researchers.To do a good job in the study of the TSP has an important role in the modern transportation logistics industry.This thesis mainly starts with the classical genetic algorithm and optimizes the relevant operators of the algorithm to solve the TSP.In addition,the traditional single-objective model of the TSP is improved to a two-objective model,and a multi-objective BSO algorithm based on non-dominated ranking is proposed to verify the new model.The full text is divided into five chapters,and the specific contents are arranged as follows:(1)Chapter 1 mainly introduces the research significance and development of travel salesman problem and its theory.Chapter 1 expounds the specific results of the theoretical and algorithm research on TSP problem and its derivation by domestic and foreign scholars in recent years.At the same time,this thesis presents the motivation and main research work of the topic.In chapter 2,the mathematical basic models of MTSP derived from single objective TSP and multi-objective TSP are given,and the current relevant algorithms to solve this kind of problems are shown,including ant colony algorithm and simulated annealing algorithm.(2)In chapter 3,a Bioinformation Heuristic Genetic Algorithm(BHGA)based on classical Genetic Algorithm is proposed.The algorithm improved several processes of the classical genetic algorithm.Firstly it includes the new fitness function,which comprises the number of cities and topological location into the function.Secondly,the minimum increment algorithm is used to initialize the population of the genetic algorithm and retain the elite individuals in each generation of the algorithm.Finally,a bioinformation heuristic genetic algorithm for solving single-target TSP is obtained by introducing nucleic acid sequence comparison technology in the basis of bioinformatics.And the improved algorithm is verified by experimental data.(3)In chapter 4,the single objective TSP is improved from the mathematical model.In the new model,in addition to considering the decision variable of the most basic individual fitness function in the intelligent algorithm for solving the traveling salesman problem,the average outlier distance is also introduced as another decision variable of the model.By adding the concepts of Pareto domination,Pareto optimal solution and Pareto frontier in the multi-objective optimization problem(MOP),the fast non dominated sorting algorithm is used to deal with the double objectives,and it is introduced into the brainstorming algorithm to solve the multi-objective TSP.Therefore,an improved multi-objective BSO algorithm based on fast non dominated sorting(BSO-FNS)is proposed,and the simulation experiment is carried out on the proposed algorithmChapter 5 summarizes the theory and algorithm research of the TSP,and prospects the future research of this problem.