关键词: 巡回旅行商问题, 遗传算法, 模拟退火算法, 贪心交叉算子, 退火选择

Abstract: The Traveling Salesman Problem（TSP） is a well-known NP complete problem，while the Genetic Algorithm（GA） is one of the ideal methods in solving it.Because the problem is a special sequence，the general cross-operator in the problem solving effect is not ideal.The greedy cross-3PM operator is proposed，while the annealing selection method is introduced，and a new si-
mulated annealing genetic algorithm GCBSAGA（Greed Cross-3PM Based on Simulated Annealing Genetic Algorithms） is formed.The algorithm combines simulated annealing and genetic algorithm together，making genetic algorithm in the early stage play a powerful global search function.It is easy to converge to the global optimum solution；In the later stage，the simulated annealing genetic algorithms are used to deal with the overall situation of pre-optimum solution.And it makes full use of simulated annealing’s latter part of the power of local search and eventually converges to the global optimal solution.After the experimental data verification provided by the internationally recognized TSPLIB，GCBSABA in the case eil76，eil101，pr144，st70 are found to provide better optimal path solution than TSPLIB.

Key words: Traveling Salesman Problem（TSP）, genetic algorithms, simulated annealing, greed cross-operator, annealing choice