面向有约束TSP的一种混合启发式算法

A hybrid heuristic algorithm for constrained TSP

为了克服传统算法求解有约束TSP的早熟收敛缺陷,提出混合启发式算法。采用基于遍历城市顺序的染色体编码,结合随机法与贪心法生成较优初始种群,执行优先保留交叉和平移变异操作,引入局部邻域及混沌搜索,设计特定的适应度函数,给出最优解判据,最后证实该算法的有效性。

A hybrid heuristic algorithm is proposed to overcome premature convergence of the tradi- tional algorithm used for solving constrained Travelling Salesman Problem （TSP）. The algorithm adopted the chromosome encoding scheme based on solutions to the travelling salesman problem, combined with the stochastic method and the greedy method ways of producing superior initial pop ulations. Precedence Preservation, Crossover and Shift Change Mutation operations were executed, and chaos searching and local neighborhood searching were introduced. Furthermore, by means of setting a specific fitness function, the criteria were used to extract an optimal solution. Finally, the effectiveness of the new algorithm is demonstrated.