一种混合局部搜索算法的遗传算法求解旅行商问题

摘要

Genetic algorithm is prone to premature and weak in local optimisation capability.In light of this,we propose an efficient hybrid genetic algorithm for solving the travelling salesman problem.The algorithm first generates initial population with weighted nearest neighbour method,for the identical individuals in population,the new individuals created by K-nearest neighbour method are to replace them, then those individuals with poor adaptability will be eliminated,and new individuals are to be created by crossover operator.At last,3-opt algorithm will be applied to some individuals for optimisation and variation,for those excellent individuals in the population,the improved Lin-Kernighan algorithm will be employed for optimisation.Simulation results of part of examples in TSPLIB show that the proposed improved genetic algorithm mixed with local search algorithm can find solutions of high quality efficiently when applied to travelling salesman problem.%针对遗传算法容易产生早熟现象以及局部寻优能力较差的缺点，提出一种求解旅行商问题的高效混合遗传算法。该算法首先用加权最近邻法产生初始种群，对种群中相同的个体，用 K-近邻法产生新的个体代替相同的个体，然后淘汰适应性较差的个体，用交叉操作产生新的个体，最后，对部分个体进行3-opt 优化变异，对种群中优秀个体用改进的 Lin-Kernighan 算法进行优化。对TSPLIB 中部分实例的仿真结果表明，所提出的混合局部搜索算法的改进遗传算法在求解 TSP 问题时可以高效地获得高质量的解。