遗传算法TSP的matlab求解分析

马骏

【摘 要】TSP（旅行商问题）是一个经典的组合优化问题，是一个非连续的参数变化问题，其不能用传统的牛顿法去计算分析。遗传算法是一种可以用于解决含有离散变量的优化求解问题。本文通过遗传算法，针对TSP，借助matlab编写运行程序，详细论述程序的编码与实现，并进行案例结果分析验证。分析结果表明本文利用遗传算法原理所编写的程序非常好的得到了优化结果，表明了算法程序的正确性与可行性及遗传算法对旅行商问题的有效性。

【关键词】遗传算法；旅行商问题；matlab程序；编码；交叉

中图分类号： TP301.6 文献标识码： A 文章编号： 2095-2457（2018）16-0037-002

DOI：10.19694/j.cnki.issn2095-2457.2018.16.016

【Abstract】TSP（Traveling Salesman Problem） is classic optimization problem， and its parameters are discontinuous，so it cannot be solved by traditional Newton method.This article use Genetic Algorithm to edit a encodeprocedure based on matlabfor TSP（Traveling Salesman Problem），The encode procedure was expounded.The analysis shows that the code can get very good optimization results which means the correctness and practicability of the code and the effectiveness of the GA to TSP.

【Key words】Genetic algorithm；Traveling salesman problem；Matlab code；Encode；Crossover

0 前言

遺传算法是一种通过模拟生物界进化规律演化而来的随机搜索方法，遗传算法在运算过程中直接对个体对象进行操作，而不需要任何导数、梯度等信息[1-2]，因此，遗传算法对于存在多峰性、非线性、非连续、不可微函数的优化问题是个很好的优化手段[3]。

TSP问题就是一个非连续的，不存在导数或者梯度信息的优化问题。TSP问题可以简单地描述为：有n个城市，一个人从某个城市出发依次访问这些城市，最后又回到出发城市，如何选定访问路线使得路程最短[4]。对于TSP问题重难点在于如何巡回编码，以及通过什么样的方式进行交叉运算以避免非法子代。

本文通过遗传算法，借用Matlab编辑算法程序，对TSP问题机型分析计算。

1 基于旅行商问题的遗传算法matlab程序

1.1 群体初始化

编码采用城市的遍历次序，如6个城市的TSP：3-4-5-1-2-6可以编码为[3 4 5 1 2 6]。程序首先对各城市之间的间距矩阵dmatrix、迭代次数NG、交叉概率Pc、变异概率Pm进行赋值。

num=size（dmatrix，2）；%个体数据数，即城市数

for i=1：NP

popm（i，：）=randperm（num）； %种群初始化

end

1.2 定义适值函数

一般在求解最优解问题时，目标函数可以是求解最大值，也可以是求解最小值。但是在基本遗传算法里，适值函数[5]（目标值）越大，其被选择的概率越大，也就是越容易得到最优值。因此如果是求解最小值的优化问题时，需要作相应改变，将目标函数的最小值问题转换为适值函数的最大值问题，这里取总路程的倒数作为适值函数。

function L=shizhi（r，dmatrix，num）

Lmax=0；

for i=1：num-1

Lmax=Lmax+dmatrix（r（i），r（i+1））；

end

Lmax=Lmax+dmatrix（r（1），r（num））；

L=1/Lmax；

1.3 选择操作

使用模拟赌盘操作，用来确定交叉双亲。

Lall=sum（L）；

gailv=L/Lall； %选取概率

leiji（1）=gailv（1）；

for i=2：NP

leiji（i）=leiji（i-1）+gailv（i）；

end %概率累计

for i=1：NP

r=rand； %随机生成0～1的随机数

for j=1：NP

if r<=leiji（j）；

father（i，：）=popm（j，：）；

break；

end

end

end %按累计概率选择父代

1.4 交叉操作

为了避免传统的单点交叉或者双点交叉造成的非法子代，本程序采用由Goldberg和Lingle提出的部分交叉映射PMX[6]的方法进行交叉操作，

for i=1：2：NP

crossover=rand；

a=round（rand*（NP-1））+1；

b=round（rand*（NP-1））+1；

while a==b%防止a与b相等

b=round（rand*（NP-1））+1；

end

if crossover<=Pc；%选择双亲

father1=father（a，：）；

father2=father（b，：）；

k=round（rand*（num-1））+1；%隨机选择交叉位置

m=round（rand*（num-2））+1；

while k==m

m=round（rand*（num-1））+1；

end

minshu=min（k，m）；

maxshu=max（k，m）；

s1=father1（minshu：maxshu）；

s2=father2（minshu：maxshu）；

f1=father1；

f2=father2；

for j=minshu：maxshu%执行部分映射交叉操作

for h=1：num

if father1（h）==f2（j）

father1（h）=father1（j）；

end

if father2（h）==f1（j）

father2（h）=father2（j）；

end

end

end

father1（minshu：maxshu）=s2；

father2（minshu：maxshu）=s1；

son（i，：）=father1；

son（i+1，：）=father2；

else

son（i，：）=father（a，：）；

son（i+1，：）=father（b，：）；

end

end

1.6 变异操作

变异操作位于交叉操作之后，变异的方法有很多，这里采用互换变异的方法，即随机地选择两个位置，并将两个位置上的城市相互交换。

for i=1：num

mutation=rand；

if mutation<=Pm；

c=round（rand*（num-1））+1；

g=round（rand*（num-1））+1；

h=round（rand*（num-1））+1；

while g==h

h=round（rand*（num-1））+1；

end

mid=son（c，g）；

son（c，g）=son（c，h）；

son（c，h）=mid；

end

end

2 结果分析

将上述遗传算法的主要程序内容加以整合，组成完成的计算程序。分别以5个城市、10个城市、20个城市的TSP问题进行校验计算。结果如下图表所示。

分析发现，遗传算法对于规模较大的问题的求解往往难以做到唯一性，由于遗传算法带有随机性成分，其分析结果也有所不同，需要多次分析选取最优结果，上述分析结果是多次实验分析后较好的结果。

从上图表可以看出，遗传算法对于求解TSP有很好的适用性，TSP中，个体数越少，遗传算法循环次数则越少，个体数越多，则需要更多次的循环迭代才能达到收敛。

3 结论

所编写的程序成功的计算了上述TSP问题，并且结果符合性很好。通过计算分析，可以发现初始种群数NP、迭代代数NG、交叉概率Pc、变异概率Pm对于TSP问题的结果有影响，对于城市数目（下转第122页）（上接第38页）较小的优化，可以取较小的NP和NG，而对于城市数目较大的优化，则需要较大的NG和NP才能达到收敛。在一般遗传算法中Pc取值0.6～1.0左右和Pm取值0.05～0.10左右，但是对于该TSP问题，则需要取较小Pc（0.4）和较大的Pm（0.2）才能更容易得到最优解和更快得到最优解。因此，在实际计算分析时，需要根据相应问题，来选择合适的优化参数。

【参考文献】

[1]高媛.非支配排序遗传算法（NSGA）的研究与应用[D].浙江：浙江大学信息科学与工程学院.

[2]赖宇阳.isight参数优化理论与实力详解[M].北京：北京航空航天大学出版社，2012：138-142.

[3]龚纯，王正林.精通MATLAB最优化计算[M].北京：电子工业出版社，2009：313.

[4]玄光南，程润伟.遗传算法与工程设计[M].北京：科学出版社，2000：82-83.

[5]李飞，白艳萍.用遗传算法求解旅行商问题[M].中北大学学报，2007，28（1）：49-52.

[6]Goldberg，D.&R.Lingle.Alleles;，loci and the traveling salesman problem in Grefenstette.154-159.