The Research Of MOTSP Base On Modified Genetic Algorithm

In the traveling salesman Problem(TSP),we are given n cities together with the pairwise distanees between each two cities.The goal is to find the shortest tour visits every city exactly once and in the end returns to its starting city.The TSP is one of the most famous Problems in combinatorial optimization.The cost to resolve TSP is exponential and it is proven to be NP-hard.However,In many application areas of scientific management and economic decision making,there are a lot of multi-objective optimization Problems.In a specific Traveling Salesman Problem(TSP),often have to consider some goals simultaneously,such as the shortest route,the minimum time,the lowest risk, the minimum cost and many other factors.How to get a fair and reasonable solution is a complicated issue.Multi-objective TSP(MOTSP),a new research filed of evolutionary computation, is an NP-hard problem which comes from the applications of communications,logistics.It is harder than classical TSP.Researching MOTSP would promote a development of some realristic problems such as investment problem.The investors usually want to invest less capital,have less risking and much retuns.So researching MOTSP is of great theoretical significance and research value.Some researches on MOTSP have been done recently.Based on the above backgrounds,we designed an genetic algorithm that can solve the optimal solutions of MOTSP.we have done the following work:1.Introduce the basic knowledge of TSP and genetic algorithm,and the research status for TSP.2.introduce the author's Productions about MOTSP:By ananlyzing the deficiency of traditional GA in solving MOTSP and the characterristic of MOTSP,we have a series of improvement when used to solve TSP,it firstly took advantage of Grefenstettet representation to encode,introduced a linear function to calculate selection rate,the crossover operator and the mutation operators were improved,and established an adapted MOTSP model,then designed an algorithm that can solve the optimal solutions of MOTSP better.The emulation results proved the validity in solving MOTSP.Finally,we summarize our work and state the future work we need to do.