The Study Of Several Evolutionary Algorithms For Solving Generalized Travelling Salesman Problem

The Generalized Travelling Salesman Problem (GTSP) is a variant of the TravellingSalesman Problem (TSP). It is an NP-hard problem with more intensive application fields andbeing solved with more difficulties. An Evolutionary Algorithm (EA) is a kind of randomlysearch algorithm using mechanisms inspired by biological evolution. It can be used in solvingthe complicated problems which are solved with difficulties using traditional algorithms,especially be used in solving NP-hard problems. Nowadays, the methods for solving GTSPare mainly divided into traditional search algorithms and evolutionary algorithms. It needstime for searching when using traditional algorithms, while solving precision is affected bythe search capability and stability of evolutionary algorithms. This doctoral dissertationproject is mainly about the study of evolutionary algorithms for solving GTSP. Severalevolutionary algorithms were designed for solving the first and the second kind of GTSPrespectively. The major innovations of this work are as follows:1. A novel memetic algorithm based on genetic algorithm was brought forth to solve thefirst kind of GTSP. It is a shortcoming for traditional genetic algorithms when solving GTSPthat it’s difficult to find out a solution with high precision. The solving precision can beeffectively increased by using local search algorithm. However, unrestrained local search willlargely decrease the solving efficiency of the algorithm. In this dissertation, the timecomplexity of the whole algorithm had been decreased by reducing unnecessary local searchthrough setting threshold switch and searched list. Moreover, the convergence of algorithm inthis dissertation was compared with that of hybrid chromosome genetic algorithm. Finally,this novel algorithm had been proved effective by performing numerical simulation of the firstkind of GTSP examples derived from multiple standard problems in the TSP base.2. The deficiency of traditional Ant Colony Optimization (ACO) for solving GTSP wasdiscussed. In this dissertation, by analyzing the biological characteristics of ants, a kind ofACO existing outlier was designed to solve the first kind of GTSP. This algorithm imitatedthe behavior of an ant strayed from colony finding a nearby colony, which solved theprecision problem of traditional ACO when solving the GTSP. Meanwhile, to avoid gettingtrapped in local optimum, our new algorithm combines mutation operators and the strategy oflocal search. Finally, the results of numerical simulation proved this kind of algorithm is moreeffective than the traditional ACO.3. The researches of the second kind of GTSP are few, so are the solution methods. Thisdissertation for the first time designs the relevant local search strategies for the second kind of GTSP, and for the first time expends the application field of ACO to solve the second kind ofGTSP. In the new designed ACO in this dissertation, a new artificial visiting ant strategy wasdesigned according to the characters of the second kind of GTSP. Adaptive value was taken tothe parameters of α and β which affect the searching effectiveness of algorithm. The newdesigned ACO also combines new designed local search strategy and mutation operators. Theresults of numerical simulation showed that the new designed ACO could effectively solve thesecond kind of GTSP.4. Regarding the lack of solving methods and high operational complexity of the existingmethods for the second kind of GTSP, a weight matrix remodeling algorithm is presentedthrough analyzing the characters of weight matrix of two kinds of GTSP. After the weightmatrix of the second kind of GTSP being remodeled, the second kind of GTSP can beindirectly solved using memetic algorithm based on genetic algorithm which is used in thefirst kind of GTSP. Through this way, the accuracy of solution for the second kind of GTSP ismarkedly increased and complexity of operation is decreased. Finally, using this algorithm wetested the second kind of GTSP examples derived from multiple standard problems in the TSPbase. Results showed that this algorithm could effectively solve the second kind of GTSP.