一种求解旅行商问题的交叉禁忌搜索

提出一种改进的禁忌搜索（TS）一交又禁忌搜索（CTS），并用于混合优化问题旅行商问题（TSP）的求解。CTS主要包括集中策略和分散策略，采用选择规律的改变促进移动的混合，集中策略增强了算法的局部搜索能力；分散策略是用于开辟新的搜索空间，在CTS中，采用遗传算法中的交叉算子作为分散策略，优解选择法作为集中策略。CTS、标准TS、带集中裳略的TS和蚁群算法用于求解相同的TSP例子，所用例子都是来自TSPLIB例子库和Fogel路径。求解结果显示了CTS的性能优于其它算法。

Crossover Tabu Search for Traveling Salesman Problem

An improved tabu search-crossover tabu search(CTS)was proposed,which is applied for solving a well-known combinatorial optimization problem--the traveling salesman problem(TSP).The key strategies of the CTS are intensification strategy and diversification strategy.Intensification strategies,based on modifying choice rules to encourage move combinations,were used to enhance the efficiency of local search.Diversifications strategies were designed to drive the search into new regions,i.e.,exploit the new search spaces.The CTS implement the crossover operator of the genetic algorithm(GA)as the diversification strategy,and the strategy for selecting elite solutions as the intensification strategy.CTS,standard TS,standard TS with intensification strategy and ant colony system(ACS)were used to solve the same TSP problems which come from the library of TSP instances TSPLIB and other three TSP instances of Fogel's path.The results show better CTS performances than other kinds of algorithms.