Ant Colony Optimization Applied In Generalized Traveling Salesman Problem

Traveling Salesman Problem(TSP) is a classical thesis in graph theory,but Generalized Traveling Salesman Problem(GTSP) is more valuable in engineering practice.For TSP there are some effective methods to solve it,but for GTSP there is only few report about it.Ant Colony Optimization(ACO) can be used for solving TSP,in this thesis it was extended to solve GTSP,and its efficiency was testified by solving a typical GTSP example.M(number of ants),α(heuristic factor of information),β(heuristic factor of aspiration),ρ(pheromone trail persistence),Q(quantity of trail ) are the important parameters of ACO.They have a great influence not only upon the efficiency of the algorithm,but also upon the accuracy.Calculation lots of examples,the relation between these five parameters and the characteristics of the algorithm was discussed in this thesis,in order to choice the correct values of these five parameters.At last,the ACO program developed in this thesis was used to solve a GTSP example,which comes from the engineering practice,and its validity was testified.