基于遗传算法的TSP问题求解与仿真

TSP问题常用的自然编码方式在进行遗传操作时,会产生不合法路径.设计了一种新的编码方式,能有效避免这一问题,遗传操作简单易行,无需对不合理的基因片段进行合法化修正.在求解过程中,为了解决遗传算法的收敛速度和全局收敛性之间的矛盾、避免早熟,运用了Doping策略和参数切换方法.最后进行了仿真测试.结果表明,该算法能迅速淘汰劣解,具有较快的收敛速度;能有效遏制早熟,对不同规模的TSP问题能有效求得最优解.

Solution and simulation of TSP problem based on genetic algorithm

In Traveling Salesman Problem(TSP),illegal routes may be produced by genetic operations using the traditional encoding method.To avoid this problem,a new encoding method is presented.With the new method,it is easy to implement genetic operations,and it is not necessary to adjust the illicit gene parts in children individuals.To prevent premature convergence and solve the conflict between the convergence speed of genetic algorithm and that of the global convergence,Doping strategy and parameter switch method are used.Experimental result shows that these methods can help to enhance the capabilities of global convergence and avoid premature convergence,and the algorithm is efficient for solving TSP problems with different scales.