基于遗传算法解决TSP问题探索

2019-09-10岳鹏齐

现代信息科技 2019年4期

摘要：遗传算法在TSP问题的解决过程中发挥着较为重要的作用。本文从遗传算法的基本原理与算法步骤入手，简述遗传算法的基本原理及遗传算法的基本步骤，然后对基于遗传算法的TSP问题解决方式进行了分析，包括TSP问题建模、TSP问题遗传算法设计、编码方式、算子选择、单点交叉、变异算子、其他参数等，最后从选择因子分析和算法测试分析两方面对基于遗传算法的TSP问题实验进行了探究。

关键词：遗传算法；TSP问题；遗传操作

中图分类号：TP18 文献标识码：A 文章编号：2096-4706（2019）04-0010-03

Exploration of Solving TSP Problem Based on Genetic Algorithms

YUE Pengqi

（Liaoning Normal University Haihua College，Shenyang 110167，China）

Abstract：Genetic algorithm plays an important role in solving TSP problem. This paper starting with the basic principles and steps of genetic algorithm，briefly describes the basic principles and steps of genetic algorithm，and then analyses the solution of TSP problem based on genetic algorithm，including TSP problem modeling，genetic algorithm design of TSP problem，coding method，operator selection，single point crossover，mutation operator，other parameters，etc. ，finally，the experiment of TSP based on genetic algorithm is explored from two aspects of selection factor analysis and algorithm test analysis.

Keywords：genetic algorithm；TSP problem；genetic operation

0 引言

旅行商问题（TSP问题）是诸多领域中存在的、多种复杂问题的集中概括。在解决此类问题的过程中，研究者不能借助全局搜索算法确定此类问题的最优解。为确定此类算法的最优解与次优解，一些研究者开始将遗传算法应用于TSP问题的解决过程之中。遗传算法是建立在自然界生物适者生存、优胜劣汰的遗传机制基础之上的全局优化算法。这一算法具有良好的自组织性、自适应性与自学习性。现阶段遗传算法已经开始在组合优化问题、机器学习问题及自适应控制问题等问题的解决过程中得到应用。利用遗传算法的基本思想与优化原理，构建解决TSP问题的遗传算法程序，有助于降低TSP问题的解决难度。

1 遗传算法的基本原理与算法步骤

1.1 遗传算法的基本原理

遺传算法是一种基于全局优化的随机搜索算法。通过对这一算法的基本原理进行分析，发现此种算法可以对自然界生物的自然选择与遗传变异过程进行有效模拟，进而在融入适者生存等进化机制的基础上，让群体进化到最优解。

在应用于实际问题解决过程以后，人们可以利用基于遗传算法的随机方式生成若干个与某一问题有关的个体，构建初始种群。在初始种群建构完成以后，研究者需要根据问题的实际情况构建适应度函数，并对每一个个体的适应度进行考量，以淘汰一些适应度较低的个体。在经过选择操作、交叉操作和变异操作等一系列遗传操作以后，研究者可以在新一代更优秀的种群形成以后对新一代种群进行处理，进而确定问题的最优解与近似最优解。一般情况下，遗传算法主要由以下内容构成：（1）个体编码；（2）适应度函数设计；（3）遗传操作设计；（4）控制参数的确定。个体编码是确定初始种群的重要方式。遗传算法的控制参数需要包含种群大小、最大进化代数、交叉概率、变异概率及终止条件等信息。

1.2 遗传算法的基本步骤

在实际应用过程中，遗传算法的基本步骤主要涉及到以下几方面内容：（1）数据初始化处理；（2）适应度的计算；（3）遗传操作的实施；（4）终止条件的判断。数据初始化过程可以被看作是最大进化代数的生成过程与种群大小的设置过程，这一过程也是初始群体的建构过程。适应度计算过程是对群体中所包含的各个个体的适应度进行计算的过程。在遗传操作方面，研究者在遗传算法应用于实际问题解决过程以后，可以借助于选择运算、交叉运算及变异运算等运算方式确定下一代群体。根据遗传算法的实际特点，选择操作要建立在群体中的个体适应度评估机制的基础之上。基于个体适应度评估的选择操作可以让算法中选用的优秀个体遗传到下一代，或借助配对交叉的方式，将一些产生的个体遗传到下一代。在交叉操作应用以后，研究者可以根据交叉概率完成父代个体的部分结构重组，进而生成新的个体。变异操作建立在变异概率的基础之上，此种操作方式可以让研究者对选中的个体串的基因值进行调整，以形成新的个体。在进化代数达到研究者预先设置的最大进化代数以后，遗传算法可以将进化过程中得到的具有最大适应度的个体视为输出最优解，此时研究者需要终止计算，完成结果的输出。

2 基于遗传算法的TSP问题的解决方式

2.1 TSP问题建模

一般情况下，TSP问题可以通过以下内容进行表述，一片区域内分布有N个城市，区域内每个城市之间都有一定的距离，一位旅行商需要访问这些城市，要求每个城市都要访问到，且每个城市只能访问一次，旅行商访问结束后需要返回出发的城市，如何安排旅行商的访问路线，让旅行商所进过的路径的总长度最短。

根据问题的实际内容，研究者首先需要对城市进行编号，如0，1，……n-1。在编号完成以后，研究者可以从不同城市的距离信息入手，构建二维数组，TSP问题的数学模型需要包含总路程长度、总城市数量和两个不同城市之间的距离等信息。

2.2 TSP问题遗传算法设计

初始化群体和适应度函数（含终止条件）的设定是TSP问题遗传算法设计中的重要内容。根据前文论述，编码方法是出于问题研究需要而随机产生的初始群体。与之相关的适应度函数多采用求取函数最大值的函数。根据TSP问题的特点，适应度与滚动条的路径之间具有正相关关系，即个体的适应度越小，个体的路径越短。在解决TSP问题的过程中，与游历城市的数量及与问题内容有关的惩罚系数函数也是不可忽视的内容。

2.3 编码方式

遗传基因编码在遗传算法应用过程中发挥着较为重要的作用。在遗传算法应用于TSP问题解决过程以后，编码可以被看作是交叉操作与变异操作的实用性的主要影响因素。根据TSP问题的实际情况，研究者可以构建一种以顺序表示的遗传基因编码方法。在顺序表示的遗传编码应用于TSP问题解决过程以后，研究者可以按照一定次序，将旅行商行程中所要经过的城市编成顺序表，如用数字0～9代表旅行商的旅行路径。在旅行路径确定以后，以下编码方式可以应用于TSP问题的处理过程中：（1）轮盘赌选择法；（2）随机联赛选择法；（3）期望值选择法。其中轮盘赌选择法是一种较为常用的选择方式。此种编码方式可以让个体的适应度转化为选中的概率。在轮盘赌选择方式应用于TSP问题处理过程以后，研究者可以将每个个体视为轮盘中的一小块扇形，扇形的大小与该染色体被选中的概率之间具有正相关关系。轮盘赌选择法在TSP问题编码处理过程中的应用可以让适应度较大的个体编程轮盘中扇形面积较大的个体，即适应度较强的个体转化为轮盘中扇形面积较大的个体以后，使一些优质个体进入下一代群体的概率有所增加，故而轮盘赌选择法的应用，可以让算法更为趋近最优解。

2.4 算子选择

算子选择过程是从旧有种群中选择生命力较强的个体位串，构建新的种群的过程。这一过程可以被看作是个体根据特定的适值函数完成自身复制的过程。在遗传算法中，适值函数主要指人们所期望的最大效益的某种量度，这一过程是模仿自然选择现象的过程，如根据达尔文的适者生存理念，相对强势的个体可以在下一代中产生一个或多个子孙，在遗传算法应用于实际问题解决过程以后，算子选择可以被看作个体繁衍下一代的过程。因此，遗传算法可以被看作是达尔文适者生存理念应用于计算机技术领域的产物。根据前文论述，轮盘赌选择法可以让算法更为趋近最优解。但是在TSP问题的解决过程中，遗传算法的全局收敛性也是研究者不可忽视的内容。群体的个体多样性可以被看作是遗传算法的全局收敛性的主要影响因素。在算子选择过程中为遗传算法的全局收敛性提供保障，可以在增加个体在种群中的分布区域的基础上实现遗传算法的改善，但是这项措施可能会让计算时间有所增加。

2.5 单点交叉

交叉算子在遗传算法中发挥着较为重要的作用。在解决TSP问题的过程中，基于路径的部分映射交叉是一些研究者关注的内容。在此种映射交叉投入使用以后，研究者需要在已经生成的父个体中选择两个杂交点，并要在完成段的交换以后，根据段内城市确定映射。根据TSP问题解决过程的实际需要，父代个体之中需要填入一些无冲突的城市。针对一些存在路径冲突的城市，研究者可以通过执行部分映射的方式，在处理冲突后获取交叉后的两后代。与之相关的顺序交叉与映射交叉操作之间具有一定的相似性。研究者仍然需要在父个体中确定两个不同的杂交点，并要在交换杂交段的基础上实现顺序交叉。在顺序交叉的实施过程中，父代个体中的城市的相对次序可以被看作其他位置的决定因素。根据遗传算法的研究现状，循环交叉在TSP问题处理过程中的应用也成为了一些研究者关注的内容。在循环交叉应用以后，研究者需要让选取的两个父个体呈现出参照与被参照的关系，在父个体城市重组工作完成以后，研究者需要在利用重组后的个体组建循环链的基础上，确定不同城市的位置。

通过映射交叉、顺序交叉与循环交叉均关注的城市位置与次序，导致对不同城市之间连接的忽视，会给TSP问题最优化方案的科学性带来不利的影响，在对城市间的位置及城市间的关系进行充分分析以后，一些研究者开始将单点交叉方式应用于此类问题的处理过程。单点交叉是研究者在个体编码串中随机设置交叉点，利用该点交换基因串的措施。根据前文所述，假设两种父代个体分别为：0265|948371，另外一组父代个体为：0539|268714。在选择的交叉点为第五个位置的情况下，研究者可以从交叉点开始，完成父代个体基因串的呼唤，此时第一组中间个体可以表示为：0265|268714，第二组中间个体可以表示为：0539|948371。中间个体中的交叉点之后的基因串中与交叉点重复的基因删除以后，研究者可以在后序补齐所缺基因，并在此基础上构建以下两种自带个体，其中，第一种子代个体可以表示为：0265、871439，第二种子代个体可以表示为0539|487126。通过对上述交叉方式的应用效果进行分析，发现此种方式可以让随机选择的处理性能有所改善。

2.6 变异算子

在遗传算法实际应用过程中，复制和交叉操作会可能会导致部分遗传信息丢失。在人工遗传系统中，变异算子可以有效避免遗传信息丢失。在一些相对简单的遗传算法中，变异主要指某个字符串及某一位的值出现的偶然改变，这种改变形式具有随机化的特点。变异可以沿着个体字符空间随机移动。在变异算子与交叉算子共同应用于TSP问题解决过程以后，变异算子可以避免过度成熟而导致的概念丢失问题。

变异可以被看作是一种特殊化的局部随机搜索形式。变异算子与选择算子或重組算子的结合，可以为遗传算法的实效性提供保障，也可以让遗传算法的局部随机搜索能力得到强化。变异算子在TSP问题解决过程中的应用可以为遗传算法的种群多样性提供保障，但是就遗传算法的实际应用情况而言，研究者需要对变异操作的变异率进行严格控制。同交叉算子相比，变异算子的设计形式具有一定的灵活性，以简单化的倒位操作为例，研究者可以借助变异算子，在父个体中随机选取截断点。在确定截断点以后，研究者可以将两点所夹的子串中的城市进行反序处理，保证算法的实用性。

2.7 其他参数

遗传算法应用于TSP问题解决过程以后，初始种群与适应度函数可以被看作与TSP问题解决方案有关的其他参数。根据TSP问题的相关内容，随机产生种群规模的数量可以被看作是初始种群，以TSP问题的目标函数值的倒数为适应度函数的适应度函数选择方式也是TSP问题处理过程中常用的适应度函数确定方式。

3 基于遗传算法的TSP问题的实验分析

3.1 选择因子分析

物流配送问题是TSP问题的反映。在物流配送过程中，相关人员需要沿着可行道路行进。与之相关的坐标系中的两点之间的距离计算不能采用直连计算的计算方式。道路的拥堵程度、物流配送车辆的行驶速度、车辆的容量空间等因素可以被看作配送工作的主要影响因素。在坐标系中，两点无法进行直连计算的情况下，研究者需要利用坐标系确定道路位置，进而在建立路径函数的基础上，完成坐标点的计算。针对配送车辆行使速度及道路拥堵程度对物资配送情况的影响，研究者也需要构建拥堵系数函数与交通信号灯限行时间函数。各个路口的实施限行情况与拥堵状况也是遗传算法应用以后不可忽视的问题。针对车辆容积的现状，研究者可以借助于旅行商问题的处理思路解决这一问题，并在对车辆将货物送到目的地以后返回转运中心装载货物，再次出发的过程进行模拟。结合问题实际情况，对遗传算法进行改进。为了让遗传算法更接近于物流配送工作的实际情况，研究者可以通过引入可变邻域所搜索的方式，解决跨道路问题难以通过编译方式获取最优号码段的问题。为提升优秀子代的选择效率，研究者也需要在改进适应度函数与选择算子的基础上生成优质子代，并从城市编码定义入手，对相关算法进行改進。

3.2 算法测试分析

遗传算法应用于物流配送TSP问题的解决过程以后，研究者也需要在道路关键点完成各个路口之间道路连接情况的邻接矩阵构建，为了确定两个路口之间的最近道路距离与最短路径，研究者可以将Dijkstra算法应用于实际计算过程之中。虽然这一算法的应用可以为主路径的有效性提供保障，但是在实际应用过程中，算法所设计的最短路径与设计最短路径之间可能存在一定的偏差，故而混合路径方案设计是解决二者偏差的可行措施。针对两个目标点距离较近时可能出现的绕路问题，研究者需要借助于一定范围内的直角路线方案，为路线方案的有效性提供保障。为保证路径结果的视觉效果在实际路径结果多次途经主干路的情况下，研究者可以通过路径图与直连结果图相结合的方式，保证路线图的美观性。

4 结论

遗传算法在实际求解过程中可以获得某一稳定的近似最优解。初始化群体和适应度函数（含终止条件）的设定是TSP问题遗传算法设计中的重要内容。以TSP问题的目标函数值的倒数为适应度函数的适应度函数选择方式也是TSP问题处理过程中常用的适应度函数确定方式。在实际环境下，算法的全局优化能力仍然是研究者所要关注的内容。在物理配送方面的TSP问题的解决过程中，选择因子的灵活应用有助于提升遗传算法的实用性。

参考文献：

[1] Chvátal V，Cook W，Dantzig G B，et al.Solution of a Large-Scale Traveling-SalesmanProblem [J].50Years of Integer Programming1958-2008，2010.

[2] John J. Grefenstette. Proceedings of the First International Conference on Genetic Algorithms and their Applications [M].S.l.：Taylor and Francis，2013.

[3] 邓慧允，张清泉.蚁群算法与遗传算法在TSP中的对比研究 [J].山西师范大学学报（自然科学版），2017，31（3）：34-37.

[4] 蒋然.改进遗传算法在TSP问题中的应用 [J].软件导刊，2016，15（12）：127-129.

[5] 陆游，何嘉.基于并行优化与访存优化遗传算法的TSP问题求解方法 [J].四川文理学院学报，2017（2）：11-17.

[6] 李月.基于遗传算法的免疫算法对TSP问题的改进与研究 [J].中国传媒大学学报（自然科学版），2017（4）：58-63.

[7] 饶卫振，王新华，金淳，等.一类求解TSP构建型算法的通用改进策略 [J].中国科学：信息科学，2015，45（8）：60-79.

[8] 史小明.浅谈MATLAB下的遗传算法优化软件设计 [J].数字技术与应用，2017（6）：146+149.

[9] 宋海声，吕耕耕，刘岸果.一种基于分层模型的TSP构建算法 [J].微型机与应用，2017，36（6）：13-15+21.

[10] 伍建伟，刘夫云，李峤.MATLAB遗传算法函数ga优化实例 [J].机械工程与自动化，2017（2）：61-63.

[11] 武海峰.基于Matlab的遗传算法程序设计探讨 [J].电脑迷，2017（1）：4.

[12] 袁明珠.Matlab遗传算法工具箱在约束非线性惩罚函数中的应用 [J].软件工程，2017，20（1）：37-39.

[13] 姚明海，王娜，赵连朋.改进的模拟退火和遗传算法求解TSP问题 [J].计算机工程与应用，2013，49（14）：60-65.

[14] 赵功勋，郭海滨，苏利.基于遗传算法的工程项目资源均衡优化及其MATLAB实现[J].工程经济，2016，26（12）：59-64.