基于遗传算法的旅行商问题求解方案
摘要
采用MATLAB，对TSP问题进行基于遗传算法的求解。TSP 问题是典型的NP完全问题，通过MATLAB进行遗传算法编程，从而有效提出一个较好的TSP解，实现对问题的解答。进而讨论遗传算法的特点，以及对本问题的可行性。
关键词： TSP问题 遗传算法
一．问题重述
假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该
问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。
二．遗传算法（GA）概述
遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。
三．问题分析
TSP问题就是寻找一条最短的遍历n 个城市的最短路径, 即搜索自然数
子集W= { 1 ,2 , ⋯, n} ( W的元素表示对n 个城市的编号) 的一个排列 π( W) = { V1 , V2 , ⋯, Vn} , 使len = ∑ d ( Vi , Vi+1) + d ( V1 , Vn)取最小值, 式中的d ( Vi , Vi+1) 表示城市Vi 到城市Vi + 1的距离.
遗传算法是具有“生成+检测”的迭代过程的搜索算法。它的基本处理流程如图1所示。由此流程图可见，遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择（Selection）、交叉（Crossover）和变异（Mutation）是遗传算法的3个主要操作算子，它们构成了所谓的遗传操作（genetic operation），使遗传算法具有了其它传统方法所没有的特性。遗传算子包含如下6个基本因素：
（1） 参数编码：由于遗传算法不能直接处理解空间的解数据，因此必须通过编
码将它们表示成遗传空间的基因型串结构数据。
（2） 生成初始群体：由于遗传算法的群体型操作需要，所以必须为遗传操作准
备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机
1
方法产生。
（3） 适应度评估检测：遗传算法在搜索进化过程中一般不需要其他外部信息，
仅用适应度（fitness）值来评估个体或解的优劣，并作为以后遗传操作的依据。
（4） 选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体，
使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和（f），再计算每个个体的适应度所占的比例（fi，并以此作为相应的选择概率P。 f）
s（5） 交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉（即一
点交叉）可分两步进行：首先对种群中个体进行随机配对;其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。
（6） 变异：变异操作是按位（bit）进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率Pm都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。
这6个要素构成了遗传算法的核心内容，其流程如图1所示。
编码和初始种群生成种群中个体适应度的检测评估选 择交 叉变 异图1 遗传算法的基本流程
遗传算法解题的基本步骤如下：
Step1：参数设置及种群初始化； Step2：对不可行解进行贪婪修复； Step3：适应度评价； Step4：轮盘赌选择；
2
Step5：交叉； Step6：变异；
Step7：对不可行解进行贪婪修复； Step8：适应度评价；
Step9：终止条件判断，若未达到终止条件，则转到Step4； Step10：输出结果。
开始 参数设置 种群初始化 对不可行解进行贪婪修适应度评价 轮盘赌选择，用选择出的个体构成的种群替代旧的交叉 变异 对不可行解进行贪婪修适应度评价 是否满足终止条输出结果 结束 3
图2 遗传算法具体步骤
四．程序源代码
%遗传算法求解旅行商问题 %初始化
a=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;... 3238 1229;4196 1044;4312 790;28 570;1927 1970;2562 1756;... 2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;... 3780 2212;3676 2578;1537 2838;2745 2931;3429 1908;3507 2376;... ];%a：假定的24个城市的坐标
n=100;%n：种群个数 C=200;%C：停止代数
m=2;%m：适配值淘汰加速指数,不宜太大 Pc=0.9;%Pc：交叉概率 Pm=0.2;%Pm： 变异概率
D=distance(a);%生成距离矩阵
[R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm);
%返回值：最优路径R
% 总距离Rlength
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %D：距离矩阵 %n：种群个数
%a：31个城市的坐标，在初始化时设定 %C:停止代数
%m:适值淘汰加速指数,不宜太大(5以下) %Pc：交叉概率 %Pm：变异概率
%R：最短路径，Rlength：路径长度
function [R,Rlength]=GeneTSP(D,a,n,C,m,Pc,Pm)
[N,NN]=size(D); %(31*31)
farm=zeros(n,N); %存储种群
%随机生成初始种群，随机产生从1到N的N个初始值，例如, RANDPERM(6) ,可能结果为：[2 4 5 6 1 3]. for i=1:n
4
farm(i,:)=randperm(N); end
R=farm(1,:); %一个随机解(个体)
scatter(a(:,1),a(:,2),'x'); %画出所有点,a(:,1):X坐标,a(:,2):Y坐标 hold on pause(1)
%画出随机解得路径图 figure;
plotaiwa(a,R); hold on pause(1)
%输出随机的解得路径和总距离
disp('初始种群中的一个随机值:') Rlength=myLength(D,R)
%计算各个个体总距离和适配置 len=zeros(n,1);%存储路径长度 fitness=zeros(n,1);%存储适配值 counter=0;
while counterlen(i,1)=myLength(D,farm(i,:));%计算路径长度 endminlen=min(len);
rr=find(len==minlen);%返回的是在len中路径最短的路径坐标(i,1) R=farm(rr(1,1),:);%更新最短路径
FARM=farm;%优胜劣汰，nn记录了复制的个数 %选择 K=23;
[aa,bb]=size(FARM); FARM2=FARM; len2=len;
[len]=sort(len); for i=1:aa
tt= find(len2==len(i,1)); FARM(i,:)=FARM2(tt(1,1),:); end
for i=1:K j=aa+1-i;
FARM(j,:)=FARM(i,:);
end %交叉操作
5
[aa,bb]=size(FARM); FARM2=FARM;
for i=1:2:aa if Pc>rand&&i[A,B]=cross(A,B);%交叉算法采用部分匹配交叉 FARM(i,:)=A; FARM(i+1,:)=B;end end
%变异
FARM2=FARM; for i=1:aa
if Pm>=rand FARM(i,:)=mutate(FARM(i,:)); end end
FARM=[R;FARM];%将随机产生的n-aa个体加入从后面种群,将上次迭代的最优解从前面加入种群
[aa,bb]=size(FARM);
%保持种群规模为n if aa>n
FARM=FARM(1:n,:); end %更新farm farm=FARM; clear FARM
%更新迭代次数
counter=counter+1 ; end
%结果输出
Rlength=myLength(D,R) figure
plotaiwa(a,R)%画图
disp('迭代次数c'); disp(C);
disp('迭代后结果');
Rlength=myLength(D,R)%结果输出
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6
%计算邻接矩阵
%输入参数a是中国31个城市的坐标 %输出参数D是无向图的赋权邻接矩阵
function D=distance(a)
[c,d]=size(a);%此例中c=24,d=2 D=zeros(c,c);%申请一个0阵 for i=1:c for j=i:c
bb=(a(i,1)-a(j,1)).^2+(a(i,2)-a(j,2)).^2;
D(i,j)=bb^(0.5);%计算第i个城市到j城市的距离 D(j,i)=D(i,j); end end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %总路径len
function len=myLength(D,p) [N,NN]=size(D);
len=D(p(1,N),p(1,1)); for i=1:(N-1)
len=len+D(p(1,i),p(1,i+1)); end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %绘制路径示意图 R记录路径 %a：假定的24个城市的坐标 %R：最短路径
function plotaiwa(a,R)
scatter(a(:,1),a(:,2),'x') hold on
plot([a(R(1),1),a(R(24),1)],[a(R(1),2),a(R(24),2)]) hold on
for i=2:length(R) x0=a(R(i-1),1); y0=a(R(i-1),2); x1=a(R(i),1); y1=a(R(i),2); xx=[x0,x1]; yy=[y0,y1]; plot(xx,yy) hold on end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %交叉算法采用部分匹配交叉
function [a,b]=cross(a,b)
7
L=length(a);
if L<=10 %确定交叉宽度 W=9;
elseif ((L/10)-floor(L/10))>=rand&&L>10 W=ceil(L/10)+8; else
W=floor(L/10)+8; end
p=unidrnd(L-W+1);
%随机选择交叉范围，从p到p+W
% UNIDRND Random arrays from the discrete uniform distribution. % R = UNIDRND(N) returns an array of random numbers chosen uniformly % from the set {1, 2, 3, ... ,N}. The size of R is the size of N. %
% R = UNIDRND(N,MM,NN,...) or R = UNIDRND(N,[MM,NN,...]) returns an
% MM-by-NN-by-... array. for i=1:W
%交叉
x=find(a==b(1,p+i-1)); y=find(b==a(1,p+i-1));
[a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1)); [a(1,x),b(1,y)]=exchange(a(1,x),b(1,y)); end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %变异算法
function a=mutate(a) L=length(a);
rray=randperm(L);
[a(rray(1)),a(rray(2))]=exchange(a(rray(1)),a(rray(2)));
五．运行结果
初始种群中的一个随机值: Rlength =
3.0138e+004 Rlength =
1.5077e+004 迭代次数c 200
迭代后结果 Rlength =
1.5077e+004
8
图3 24个城市坐标图
9
图4 随机初始化结果
图5 遗传算法求解结果
初始种群中的一个随机值: Rlength =
8.1881e+004 Rlength =
2.8217e+004 迭代次数c 400
迭代后结果 Rlength =
2.8217e+004
10
图6 36个城市坐标图
11
图7 随机初始化结果
图8 遗传算法求解结果
六．结果分析
由遗传算法对以上两种情况的求解（24城市和36城市），可以看出，用遗传算法来求解TSP问题是可行的。用遗传算法求解时，增加迭代次数，可以得到更加优良的结果，但是会需要更长的时间，即一个优良的结果往往是以时间为代价的，这种情况要依据具体问题具体分析，平衡两者在问题求解时的比重。另外，对选择算法进行优化，会提高遗传算法的性能，这些都需要在实践中不断积累和广泛涉猎优良算法。最后，遗传算法得到的未必是最优解，我们可以根据需要进行多次求解，从而比较得出符合要求的结果。
12
