智能算法-邹久礼-s20110112-2003版本

基于遗传算法的TSP算法

机械电子工程 邹久礼 S20110112

1理论基础：

TSP（TRAVELING SALESMAN PROBLEM,旅行商问题）是典型的NP完全问题，即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长，到目前为止还未找到一个多项式时间的有效算法。

TSP问题可描述为：已知N个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次仅且一次，最后回到出发城市，如何安排行程才能使所走的路线最短。简言之，就是寻找一条最短的遍历N个城市的路径，或者说搜索自然子集

X={1,2,3….,N}(X的元素表示对N个城市的编号)的一个排列

，取最

小值，其中表示城市VI到城市

VI+1的距离。

TSP问题并不仅仅是旅行商的问题，其他许多的NP完全问题也可以归纳为TSP问题，如邮路问题，装配线上的螺母问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义。

2实际应用举例

2.1 问题描述：

假定某旅行商要游览14个城市，并且知道14个城市的位置坐标如表4-1所列。寻找

出一条最短的遍历14各城市的路径。

表1 14个城市的位置坐标

城市编号X坐标Y坐标城市编号X坐标Y坐标116.4796.1817.296.29216.4794.44916.397.38320.0992.541014.0598.12422.3993.371116.5397.38525.2397.241221.5295.5962296.051319.4197.13720.4797.021420.0992.55 2.2解决思路及步骤

2.2.1算法流程

遗传算法TSP问题的流程图如图1所示： 实际问题参数集 编码 初始种群 计算适应度 选择适应度高的染色体 交叉 进化逆转 新种群 代数满足 终止条件 解码 改善或解决实际问题

图1 遗传算法TSP问题的求解流程图 2.2.2遗传算法的实现

（1）

码

采用整数排列编码方法。对于N个城市的TSP问题，染色体分为N段，其中每一段为对应城市的编号，如对10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10}，则

就是一个合法的染色

体。 （2）

群初始化

在完成染色体编码以后，必须产生一个初始种群作为起始解，所以首先要决定其实种群的数目，初始化种群的数目一般根据经验得到，一般情况下种群的数量视城市规模的大小而确定，其取值在50~200之间浮动。 （3）

应度函数

设K1|K2|…|KI|…|KN|为一个采用证书编码的染色体，

为城市KI到城市KJ

距离，则该个体的适应度为:

即适应度函数恰好走遍N个城市，再回到出发城市的距离的倒数。优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质。

（4）选择操作

选择操作即从旧群体中以一定概率选择个体到新群体中，个体被选中的概率跟适应度值有关系，个体适应度值越大，被选中的概率也越大。

（5）交叉操作

采用部分映射杂交，确定交叉操作的父

代样本两组，每组重复一下过程（假定城市数是10）：

编

① 产生两个[1,10]区间的随机整数R1，R2，确定两个位置，对两位置的中间数据进行交叉，如R1=4，R2=7

交叉为：

种

② 交叉后，同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字（带*位置）采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射。结果为

适

（6）变异操作

变异策略采取随机选取两个点，将其兑换位置。产生两个[1,10]范围的随机整数R1，R2，确定两个位置，将其对换位置，如R1=4，R2=7。 9 5 1|6|3 8|7|10 4 2 变

异后为：9 5 1|7|3 8|6|10 4 2 （7）进化逆转操作

为改善遗传算法的局部搜索能力，在选择、交叉、变异之后引进连续多次的进化逆转操作。这里的进化是指逆转算子的单方向性，即只有经逆转后，适应度值有提高的才接受下来，否则逆转无效。产生两个[1,10]区间内的随机整数R1，R2，确定两个位置，将其对换位置，如如R1=4，R2=7。9 5 1|7 3 8|6 10 4 2 进化逆转化为：9 5 1|8 3 7|6

10 4 2。

对每个个体进行交叉变异，然后代入适转操作。循环操作：判断是否满足设定的最大遗传代数MAXGEN,不满足则跳入适应度值应度函数进行评估，X选择出适应度值大的个体进行下一代的交叉和变异以及进化逆

3 MATLAB程序实现

3.1 种群初始化

种群初始化函数INITPOP的代码： FUNCTION CHROM=INITPOP(NIND) %% 初始化种群 %输入：

% NIND：种群大小

% N： 个体染色体长度（这里为城市的个数） %输出： %初始种群

FUNCTION CHROM=INITPOP(NIND,N) CHROM=ZEROS(NIND,N);%用于存储种群 FOR I=1:NIND

CHROM(I,:)=RANDPERM(N);%随机生成初始种群 END

3.2适应度函数

求种群个体的适应度函数FITNESS的代码：

FUNCTION FITNV=FITNESS(LEN) %% 适配值函数 %输入：

%个体的长度（TSP的距离） %输出：

的计算；否则，结束遗传操作。

%个体的适应度值

FUNCTION FITNV=FITNESS(LEN) FITNV=1./LEN; 3.3 选择操作

选择函数SELECT的代码： FUNCTION SELCH=SELECT(CHROM

FITNV,GGAP) %% 选择操作 %输入 %CHROM 种群 %FITNV 适应度值 %GGAP：代沟 %输出

%SELCH 被选择的个体 FUNCTION

SELCH=SELECT(CHROM,FITNV,GGAP) NIND=SIZE(CHROM,1);

NSEL=MAX(FLOOR(NIND*GGAP+.5),2); CHRIX=SUS(FITNV,NSEL); SELCH=CHROM(CHRIX,:); 其中，函数SUS的代码为：

FUNCTION NEWCHRLX=SUS(FITNV,NSEL) % 输入:

%FITNV 个体的适应度值 %NSEL 被选择个体的数目 % 输出:

，

%NEWCHRIX 被选择个体的索引号 FUNCTION NEWCHRIX = SUS(FITNV,NSEL) [NIND,ANS] = SIZE(FITNV); CUMFIT = CUMSUM(FITNV);

TRIALS = CUMFIT(NIND) / NSEL * (RAND + (0:NSEL-1)');

MF = CUMFIT(:, ONES(1, NSEL)); MT = TRIALS(:, ONES(1, NIND))'; [NEWCHRIX, ANS] = FIND(MT < MF & [ ZEROS(1, NSEL); MF(1:NIND-1, :) ] <= MT);

[ANS, SHUF] = SORT(RAND(NSEL, 1)); NEWCHRIX = NEWCHRIX(SHUF); 3.4 交叉操作

交叉操作函数RECOMBIN的代码： FUNCTION SELCH=RECOMBIN(SELCH,PC) %% 交叉操作 % 输入

%SELCH 被选择的个体 %PC 交叉概率 %输出：

% SELCH 交叉后的个体

FUNCTION SELCH=RECOMBIN(SELCH,PC) NSEL=SIZE(SELCH,1); FOR I=1:2:NSEL-MOD(NSEL,2) IF PC>=RAND %交叉概率PC

[SELCH(I,:),SELCH(I+1,:)]=INTERCROSS(SELCH(I,:),SELCH(I+1,:)); END

END

其中，函数INTERCROSS的代码是： FUNCTION [A,B]=INTERCROSS(A,B) %输入：

%A和B为两个待交叉的个体 %输出：

%A和B为交叉后得到的两个个体 FUNCTION [A,B]=INTERCROSS(A,B) L=LENGTH(A);

R1=RANDSRC(1,1,[1:L]); R2=RANDSRC(1,1,[1:L]); IF R1~=R2 A0=A;B0=B; S=MIN([R1,R2]); E=MAX([R1,R2]); FOR I=S:E A1=A;B1=B; A(I)=B0(I); B(I)=A0(I); X=FIND(A==A(I)); Y=FIND(B==B(I)); I1=X(X~=I); I2=Y(Y~=I); IF ~ISEMPTY(I1) A(I1)=A1(I); END

IF ~ISEMPTY(I2) B(I2)=B1(I); END

END END

3.5 变异操作

变异操作函数MUTATE的代码： %% 变异操作 %输入：

%SELCH 被选择的个体 %PM 变异概率 %输出：

% SELCH 变异后的个体

FUNCTION SELCH=MUTATE(SELCH,PM) [NSEL,L]=SIZE(SELCH); FOR I=1:NSEL IF PM>=RAND R=RANDPERM(L);

SELCH(I,R(1:2))=SELCH(I,R(2:-1:1)); END END

3.6 进化逆转操作

进化逆转操作函数REVERSE的代码： FUNCTION SELCH=REVERSE(SELCH,D) %% 进化逆转函数 %输入

%SELCH 被选择的个体 %D 个城市的距离矩阵 %输出

%SELCH 进化逆转后的个体 FUNCTION SELCH=REVERSE(SELCH,D) [ROW,COL]=SIZE(SELCH);

OBJV=PATHLENGTH(D,SELCH); %计算路径长度

SELCH1=SELCH; FOR I=1:ROW

R1=RANDSRC(1,1,[1:COL]); R2=RANDSRC(1,1,[1:COL]); MININVERSE=MIN([R1 R2]); MAXINVERSE=MAX([R1 R2]);

SELCH1(I,MININVERSE:MAXINVERSE)=SELCH1(I,MAXINVERSE:-1:MININVERSE); END

OBJV1=PATHLENGTH(D,SELCH1); %计算路径长度

INDEX=OBJV1

SELCH(INDEX,:)=SELCH1(INDEX,:); 3.7 画路线轨迹图

画出所给路线的轨迹图函数DRAWPTATH的代码：

FUNCTION DRAWPTATH(CHROM,X) %% 画路径函数 %输入

% CHROM 待画路径 % X 各城市坐标位置

R=[CHROM(1,:) CHROM(1,1)]; %一个随机解(个体) FIGURE; HOLD ON

PLOT(X(:,1),X(:,2),'O','COLOR',[0.5,0.5,0.5])

PLOT(X(CHROM(1,1),1),X(CHROM(1,1),2),'RV','MARKERSIZE',20) FOR I=1:SIZE(X,1)

TEXT(X(I,1)+0.05,X(I,2)+0.05,NUM2STR(I),'COLOR',[1,0,0]); END A=X(R,:); ROW=SIZE(A,1); FOR I=2:ROW [ARROWX,ARROWY]

=

DSXY2FIGXY(GCA,A(I-1:I,1),A(I-1:I,2));%坐标转换

ANNOTATION('TEXTARROW',ARROWX,ARROWY,'HEADWIDTH',8,'COLOR',[0,0,1]); END HOLD OFF XLABEL('横坐标') YLABEL('纵坐标') TITLE('轨迹图') BOX ON

3.8 遗传算法主函数:

主函数名为GE-TSP,代码如下： CLEAR CLC CLOSE ALL

LOAD CITYPOSITION1;%个城市坐标位置 NIND=100; %种群大小 MAXGEN=200;

PC=0.9; %交叉概率 PM=0.05; %变异概率

GGAP=0.9; %代沟(GENERATION GAP) D=DISTANSE(X); %生成距离矩阵 N=SIZE(D,1); %(34*34) %% 初始化种群

CHROM=INITPOP(NIND,N); %% 在二维图上画出所有坐标点 % FIGURE

% PLOT(X(:,1),X(:,2),'O'); %% 画出随机解的路线图 DRAWPATH(CHROM(1,:),X) PAUSE(0.0001)

%% 输出随机解的路线和总距离 DISP('初始种群中的一个随机值:') OUTPUTPATH(CHROM(1,:));

RLENGTH=PATHLENGTH(D,CHROM(1,:)); DISP(['总距离：',NUM2STR(RLENGTH)]); DISP('~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~') %% 优化 GEN=0; FIGURE; HOLD ON;BOX ON XLIM([0,MAXGEN]) TITLE('优化过程') XLABEL('代数') YLABEL('最优值')

OBJV=PATHLENGTH(D,CHROM); %计算路线长度

PREOBJV=MIN(OBJV); WHILE GEN

OBJV=PATHLENGTH(D,CHROM); %计算路线长度 %

FPRINTF('%D %1.10F\\N',GEN,MIN(OBJV))

LINE([GEN-1,GEN],[PREOBJV,MIN(OBJV)]);PAUSE(0.0001) PREOBJV=MIN(OBJV); FITNV=FITNESS(OBJV); %% 选择

SELCH=SELECT(CHROM,FITNV,GGAP); %% 交叉操作

SELCH=RECOMBIN(SELCH,PC); %% 变异

SELCH=MUTATE(SELCH,PM); %% 逆转操作

SELCH=REVERSE(SELCH,D); %% 重插入子代的新种群

CHROM=REINS(CHROM,SELCH,OBJV); %% 更新迭代次数 GEN=GEN+1 ; END

%% 画出最优解的路线图

OBJV=PATHLENGTH(D,CHROM); %计算路线长度

[MINOBJV,MININD]=MIN(OBJV);

DRAWPATH(CHROM(MININD(1),:),X) %% 输出最优解的路线和总距离 DISP('最优解:')

P=OUTPUTPATH(CHROM(MININD(1),:)); DISP(['

总

距

离

：

',NUM2STR(OBJV(MININD(1)))]); DISP('-------------------------------------------------------------') 其中用到的调用函数如下：

①计算距离函数DISTANSE，其代码如下：

%% 计算两两城市之间的距离 %输入 A 各城市的位置坐标 %输出 D 两两城市之间的距离 FUNCTION D=DISTANSE(A) ROW=SIZE(A,1); D=ZEROS(ROW,ROW); FOR I=1:ROW FOR J=I+1:ROW

D(I,J)=((A(I,1)-A(J,1))^2+(A(I,2)-A(J,2))^2)^0.5;

D(J,I)=D(I,J); END END

②输出路线函数OUTPUTPATH，其代码如下：

%% 输出路径函数 %输入：R 路径

FUNCTION P=OUTPUTPATH(R)

R=[R,R(1)]; N=LENGTH(R); P=NUM2STR(R(1)); FOR I=2:N

P=[P,'—>',NUM2STR(R(I))]; END DISP(P)

③计算个体路线长度函数PATHLENGTH，其代码如下：

%% 计算各个体的路径长度 % 输入：

% D 两两城市之间的距离 % CHROM 个体的轨迹

FUNCTION LEN=PATHLENGTH(D,CHROM) [ROW,COL]=SIZE(D); NIND=SIZE(CHROM,1); LEN=ZEROS(NIND,1); FOR I=1:NIND

P=[CHROM(I,:) CHROM(I,1)];

4 结果分析

优化前的一个随机路线轨迹如图2所示

图2 随机路线图

I1=P(1:END-1); I2=P(2:END);

LEN(I,1)=SUM(D((I1-1)*COL+I2)); END

④重插入子代得到新种群的函数REINS，其代码如下： %% 重插入子代的新种群 %输入：

%CHROM 父代的种群 %SELCH 子代种群 %OBJV 父代适应度 %输出

% CHROM 组合父代与子代后得到的新种群FUNCTION CHROM=REINS(CHROM,SELCH,OBJV) NIND=SIZE(CHROM,1); NSEL=SIZE(SELCH,1); [TOBJV,INDEX]=SORT(OBJV);

CHROM=[CHROM(INDEX(1:NIND-NSEL),:);SELCH];

初始种群中的一个随机值:

2—>14—>1—>4—>6—>13—>12—>5—>7—>3—>11—>9—>8—>10—>2 总距离：52.8204

优化后的路线图如图3所示

图3 最优解路线图

最优解:

9—>10—>1—>2—>14—>3—>4—>5—>6—>12—>7—>13—>8—>11—>9 总距离：29.3405

优化迭代图如图4所示：

图4 遗传算法进化过程图

由进化图可以看出，优化前后路径长度得到很大改进，80代以后路径长度已经保持不变了，可以认为已经是最优解了，总距离由优化前的52.8204变为29.3045，减为原来的41.0%。

5 遗传算法的改进

上述程序中，对遗传算法做了以下两处改进。

①使用精英策略

子代种群中的最优个体永远不会比父

代最优的个体差，这样使得父代的好的个体不至于由于交叉或者变异操作而丢失。

②使用进化逆转操作

在本文的编码中，每一个染色体即对应一个TSP环游，如果染色体码串的顺序发生变化，则环游路径也随之改变。因此，TSP问题解的关键地方就是码串的顺序。对照稳重的交叉算子，可以发现，纵使两个亲代完全相同，通过交叉，仍然会产生不同于亲代的子代，且子代的码串排列顺序与亲代有较大差异。交叉算子的这种变异效果所起的作用有两个方面，一方面它能起到维持群体内一定的多样性的作用，避免陷入局部最优解；但是另一方面，它却不利于子代继承亲代的较多信息，特别是当进化进入到后期，群体空间中充斥着大量的高适应度个体，交叉操作对亲代的较优基因破坏很大，使子代难以继承到亲代的优良基因，从而使交叉算

子的搜索能力大大降低。

同交叉算子相比较，逆转算子能使子代继承亲代的较多信息。假设码串为123456789，在2和3,6和7之间发生两处断裂在逆转插入，则新码串为12-6543-789，此时子代中12段、6543段、789段与亲代对应片段顺序完全一样（6543与3456顺序对于环游路径长度来说是等价的），只是在断裂点的两端环游次序发生变化，而且本文中逆转是单方向的，即只接受朝着好的方向的逆转，因此它搜索最优解的能力强于交叉算子。

6 算法的局限性

针对问题规模N比较小时，得到的一般都是最优解；当规模比较大时，一般只能得到的近似解。这时可以通过增大种群大小和增加最大遗传代数使得优化值更接近最优解。

本文来源：https://www.bwwdw.com/article/1hox.html