求解非连通图旅行商问题的改进遗传算法

Improved genetic algorithm for solving traveling salesman problems in unconnected graph

为了克服传统遗传算法的早熟收敛问题,提出改进遗传算法。采用基于旅行商遍历城市顺序的染色体编码,结合随机法与贪心法生成初始种群,提高遗传效率。通过执行优先保留交叉和平移变异操作,引入局部邻域搜索,给出最优解是否满足非连通约束的判据。最后,实验结果验证了该算法的有效性。

Because the Traditional Genetic Algorithm（TGA） had defects of premature convergence and slow convergence, an improved genetic algorithm （IGA） was put forward. The IGA adopted the chromosome encoding scheme based on sequence of city which traveling salesman passed through, combined stochastic method and greedy method ways to produce the initial populations so as to contain optimal value, avoid infeasible chromosomes and improve the subsequently genetic efficiency. Then, precedence preservation crossover and shift change mutation operations were executed. At the same time, local neighborhood search was introduced to accelerate convergence. Furthermore, the criterion was given to judge whether optimal solution meets unconnected graph constraints or not. Finally, computation results proved the effectiveness of IGA.