Solving TSP Optimization Problem Based On Hybrid Genetic Algorithm

Traveling salesman problem is a famous path planning problem,which has a wide range of applications in real life.With the increase in the number of cities,the optimization ability of the traditional algorithms in the huge search space of traveling salesman problem is getting worse and worse,and it is difficult to achieve the purpose of finding the optimal solution precisely.Thus,how to design an approximate solution algorithm with high performance has attracted many scholars' attention.Genetic Algorithm(GA)has become a commonly used algorithm in the study of combinatorial optimization problems because of its excellent performance and good global search.However,it has been exposed that the GA is difficult to search in the local space,resulting in the disadvantages of low search efficiency and poor solution quality in the late evolution of the algorithm when it is used in practical application in long term.Therefore,in recent years,scholars have improved the performance of the algorithm by combining the local search.At present,there are some better local search operators for Traveling Salesman Problem(TSP)such as various forms of opt(2-opt,3-opt,etc.)and Lin-Kernighan(LK),of which LK is less commonly used because of its high complexity.In addition,due to the inherent characteristics of opt,its various forms of local search operators are also difficult to search the individual neighborhood.In summary,this thesis inserts the Single Insertion(SI)and the Swap into the local search of TSP problem,and combines them with 2-opt to form a special set of local search operators.Besides,in view of the good global search ability of GA,we embed the above-mentioned set of operators into GA to form a hybrid GA(HGA)and use it to solve the TSP problem.It turns out that the HGA is effective by testing the data of different city sizes in international TSPLIB,and comparing the experimental results obtained by five algorithms.Aiming at the traveling salesman problem based on stochastic constrained programming model,this thesis uses the uncertain traveling salesman problem test data generated by TSPLIB benchmark test data to measure and verify the performance of UHGA algorithm,and gives the corresponding analysis about the experimental results.