遗传算法（GA）在旅行商问题（TSP）中的应用

摘 要：旅行推销员问题（Traveling Saleman Problem，TSP）又被译为旅行商问题，简称为TSP，是最基本的路由问题，问题是在寻找从起点单一的旅客，所有给出需求点之后，最后回到最小路径成本的起源。最早的旅行商问题数学规划是由Dantzig（1959）等提出。文章通过遗传算法及三交换启发交叉（THGA），较好的解决了点数较多时最优解的查询，算法结构简明，可用于大规模点阵的最优路径问题。

关键词：遗传算法；最优路径；旅行商问题；C++指针

1 概述

“旅行商问题”常被称为“旅行推销员问题”，指的是需要有一个推销员拜访多个地点，如何找到时间来访问每个地点，然后返回到最短路径的起点。规则是简单的，但增加了位置的数量后，解决极为复杂。以42个地点举例，以确定是否要列出所有最好的旅游路线，然后计算总路径大，几乎难以计数。多年来全球数学家竭尽全力，试图找到一个高效的算法。在文章中，基于遗传算法寻求TSP问题的更优解决。

2 遗传算法介绍

2.1 遗传算法的机理

在遗传算法中，优化问题的解决方案被称为个体，它可表示为染色体或基因串。染色体通常可以表示为一个简单的字符串或数字串，这个过程称为编码处理。算法随机生成一定数量的个体。在每一代均可以被评估，并通过计算获得适应度值。之后个体和群体组成的下一代。这个过程是通过交配（crossover）和突变（mutation）来实现。根据一项新的个体适应选择，这个过程被重复：每个个体进行评价，计算两个个体的适合度进行交配，然后突变，形成第三代。周而复始，直到终止条件出现。

2.2 遺传算法的实施步骤

（1）选择一个编码；给出一个有N个染色体的出事群体pop，t：=1。

（2）对群体pop（t）中每一个染色体计算它的适应函数fi=fitness（popi（t））。

（3）若停止的规则满足，则算法会停止；否则，计算概率

，i=1，2，…，N，

并以概率的分布（9）从pop（t）随机选染色体来构成一个新种群

NewPOP（t+1）={popi（t）1j=1，2，…，N}

（4）通过交配得到一个拥有N个染色体的CrossPOP（t+1）。

（5）用一个较小概率p，将一个染色体一个基因发生突变，形成MutePOP（t+1）；t：=t+1，一个新的群体POP（t）=MutePOP（t）产生；返回2步。

3 遗传算法求解旅行商问题

3.1 编码

由于遗传算法不能直接处理空间数据的问题，所以我们要质疑的空间数据被映射到数据串型空间的遗传结构，而基因型字符串变换算法程序结构可以处理基因数据的空间。例如，计算现在北京，广东，天津，新疆四个城市，但算法不直接处理与北京，广东，天津，新疆，这些数据，所以我们给他们编号，北京（0），广东（1），天津（2），新疆（3），路径（广东→新疆→北京→天津）可以将其表示为一个字符串结构型数据（1302）。

（1）二进制编码化，基因代码用0、1表示。例如：基因A：01100100011 （代表一个个体的染色体）

（2）编码的互换（用于解决排序）。例如旅行商问题中，一串新的基因编码用来表示遍历的城市顺序，如：6783401295，表示这九个城市中，要先经过城市6，再经过城市7，依此类推。

（3）值的编码。在值的编码中，每以个基因就是一串新值。这些新值可以是与问题相关的任何值。

3.2 适应度函数和选择

遗传算法是好还是坏的适应度函数值来评估一个个体的，适应度函数值越大，质量越好。在本实施例中，采用的适应度比例法是遗传算法是最常见基本的选择方法，即选择每个单独的概率成正比其适应值。

3.3 交叉的过程

生物的进化是生物基因重组的中心作用，遗传算法是核心操作系统交叉，即所谓的交指结构的两个或更多亲本部分由个体重组操作代替生成一个新的个体。

文章采用匹配交叉（PMX）法：先随机产生两个新的交叉点，再定义这两点间区域为匹配区域，并交换两个父代匹配区域。

父代A项：132 | 468 | 7638

父代B项：983 | 567 | 3694

变换为：

TEMP A项： 132 | 567 | 7638

TEMP B项： 983 | 468 | 3694

对于 TEMP A、TEMP B中匹配区域以外出现数码的重复，要依据匹配区域内的位置进行逐一替换。匹配关系：1<——>5 3<——>6 7<——>0

子代A项：532 | 567 | 0668

子代B项：986 | 468 | 6394

3.4 变异

变异性是指特定基因编码的字符串被替换为另一种基因突变的概率值的基础上，对各个值，以形成一个新的个体。GA的变异操作是产生新个体辅助方法，它决定了GA局部搜索的能力，同时还能保持种群的多样性。

基本位变异算指随机分配到一个单独的代码串或几个基因的某些突变操作。用于通过如果值为0的原始基因位点的突变，然后将它变成一个突变操作所需的二进制个体表示为1；即1到0，0到1。

变异前：

010001010010100010000

变异后：

001001010001010010001

3.5 其他运行参数选择

GA运行参数应根据具体的问题进行选择处理，并固定，算法参数到目前为止，没有一个为所有的应用领域的GA理论能适用。下面是使用GA参数时，一般建议的方法：

（1）交叉率的选择。交叉率一般应该会比较大，推荐会使用85%-96%。（2）变异率的选择。变异率一般应该会比较小，一般使用0.4%-1%最好。（3）遗传运算终止进化代数。个人的想法是设置一个计数器，如果变异连续几代出现最佳个体n值相同（严格来说应该是，最好的个体适应连续的N-代后代种群<=父最优适应个性）即可终止运作。

4 试验及结果分析

实验：

采用的算法各参数设计为：种群规模70，交叉概率0.9，变异概率0.1，保留比例0.6，最大代数20。用上述算法对一个有15个真实城市和真实距离旅行商问题进行求解，要求合理安排行程路线，使总的旅行距离最短。

程序结果最优路径为：

6→13→9→2→4→3→14→5→7→10→8→11→0→1→12→6路径总长度为：15825

计算总耗时：54.735秒

5 结束语

（1）随着迭代次数递增，优化结果会逐渐接近最优解，并在最佳值附近来回波动。

（2）交叉概率Pc值均对优化结果的影响较大，从0.8选择值的范围为1.0，可以得到更好的优化效果；突变起到支撑作用，变异概率值只要得到适当，不会对优化结果造成太大影响。

（3）初始种群的选取对优化结果有较大的影响。

参考文献

[1]郭靖扬.旅行商问题概述电子科技大学光电信息学院[J].大众科技，2006.

[2]王海龙，周辉仁，魏颖辉.基于遗传算法的一类旅行商问题研究[J].计算机应用，2009.

[3]王大志，汪定伟，闫杨.一类旅行商问题的计算及仿真分析[J].系统仿真学报，2009.

[4]周辉仁，唐万生，魏颖辉.基于GA的最小旅行时间的旅行商问题研究[J].计算机应用研究，2009.

[5]吕佳，邢秋霞，陆静.改进的二叉树编码遗传算法及其在多旅行商中的应用[J].内蒙古科技与经济，2010.

作者简介：李和壁（1987，11-），男，内蒙古乌兰察布人，兰州交通大学，硕士研究生在读，研究方向：交通运输规划与管理。