基于遗传算法的TSP算法求解20大城市最短旅途

裴佳明 周斌 郦丽

摘要：Traveling Salesman Problem，简称TSP问题，也就是我们常说的旅行推销员问题，是数学中的一种典型问题。本文将基于遗传算法，选取20个城市作为样本，利用TSP算法来制定最优化的旅游线路。

关键词：遗传算法;TSP算法;最短旅途

中图分类号：TP312      文献标识码：A

文章编号：1009-3044（2019）16-0194-02

开放科学（资源服务）标识码（OSID）：

我们所说的TSP算法基本可以简单概述为求解最优化的线路组合。具体要求为每个城市都要走且只走一遍，终点城市同出发城市为同一个，在此基础上实现所走路程的最短[1-3]。在下文将以20个城市作为案例分析，探索TSP算法解决旅游线路最优问题的具体方法。

1 问题描述

本文选取了20个城市，依次编号为1至20号，随机设定城市坐标，如下图标所示：

立足于遗传算法的TSP算法具体来看包含初始化、个体评价、选择运算、交叉运算、变异运算以及经过选择-交叉-变异运算之后的下一群体这六大步骤[4]。其运算流程如下：

2 遗传算法优缺点

在具体进行算法设计之前有必要对遗传算法的优缺点进行分析，以便更好地进行算法的设计。首先来看遗传算法的优点主要表现在不必借助辅助信息、在检索过程中造成局部最优的可能性低、廣泛的表示可行解、可扩展、群体搜索以及便于同其他技术结合使用等[5]。而遗传算法的缺点主要表现在以下几个方面，像是过早收敛、缺乏有效的定量分析、效率同其他优化方法相比较低、优化问题的相关约束难以系统的表示以及编码不规则等等。

3 算法设计

通常在实际操作中会借助二进制编码的形式表现遗传算法的解空间，需要注意的是这种方法并不能够表示TSP问题的解，需要用十进制编码更为恰当[6]。我们将这20个城市进行编号，从1标到20。

假设从城市8出发，经过1-20个城市最后回到城市8的一条路径，可以自然地用一维数组来表示：

对于所选取的这20个旅游城市样本，其TSP算法中，我们设定种群的规模为40，那么采用二维数组来表示解的空间就可以写作：tour[40][20]。

对于如何选择合适的种群规模应该有所依据，不能单纯地追求大规模，单纯的大规模种群容易导致计算成本的增加，而且TSP算法也难以改进。像是本文中20个城市的TSP算法，采取小规模的种群即可。种群初始化时，先产生1，2，…，20的一条规则路径，然后用Collections.shuffle将他们打乱顺序，保证这条路径变成了一条随机的路径，这样产生了一个个体;同样地产生种群里其他个体。

TSP算法的设计需要考虑适应度以及交叉操作。适应度在面对不同的问题时，其定义方式也有所不同，不过一般是用它来表明解或是个体的优劣程度。如果我们假设这20个城市（k1、k2……k20）是一个整数编码的染色体，那么适应度就是正好走完这20个样本城市，回到出发点城市的最短距离的一个倒数。TSP算法中优化选择的目标就是确保适应度函数值能够是尽可能大的染色体，一般而言，适应度的函数值比较大的染色体，质量也更优越。在对所有种群的个人进行适应值求取后，就会将所求得的适应度最大的个人进行保存，等演化结束后，这一个体就是最优解。

至于交叉操作，可以称得上是遗传算法中最主要的一种操作方式。借助交叉操作，能够获得新的个体，所获得的新个体能够体现出父辈的个体特征，所表现的是一种信息交换的理念。如果将父辈的样本进行分组，则每一组的计算过程如下：

这个交叉过程保证了城市的唯一性，避免了冲突。

我们也可以将变异理解为外界环境对种群的一种影响。对于本文中所选择的20个样本城市，使其随机产生两个比20小的整数，来对整体进行分割，我们设定这一分割的整数是8和3，具体如下所示：

这一变异操作的优点在于它能够保持原有片段路径，改变的只是整个路径同两端点的连接，而倒序前后的切割段路径还是同之前一般，是一种有所选择的取舍，能够尽可能的保证所得到的后代是合理的途径。

4 实验结果分析

5 结语

综上所述，对于这一典型的优化组合算法问题，在诸多领域都有着广泛的应用，像是物流配送、交通运输以及电路设计等等，在国内外的研究都在不断深化。希望能够通过本文基于遗传算法的TSP算法来求解20个样本城市的最短旅行线路分析，能够为我国关于遗传算法以及TSP算法的进一步深入研究提供一点借鉴经验。

参考文献：

[1] 张立毅，高杨，费腾，王玉婧.求解旅行商问题的搜寻者遗传算法[J].数学的实践与认识，2019，49（07）：115-122.

[2] 岳鹏齐.基于遗传算法解决TSP问题探索[J].现代信息科技，2019，3（04）：10-12.

[3] 唐天兵，张铭明，蒙祖强.混合蛙跳遗传算法求解旅行商问题[J].广西大学学报（自然科学版），2018，43（05）：1811-1817.

[4] 刘云飞.基于TSP问题的仿生算法比较[J].电子技术与软件工程，2019（02）：110-111.

[5] 陈洋卓，李青青，罗天扬，等.基于遗传算法的TSP问题优化方法[J].科技风，2019（01）：59-60.

[6] 郭丰林.基于遗传算法的旅游线路规划研究[J].现代营销（经营版），2019（01）：134.

【通联编辑：李雅琪】