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

基于遗传算法的TSP算法机械电子工程邹久礼S201101121理论基础：TSP（TRAVELINGSALESMANPROBLEM,旅行商问题）是典型的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各城市的路径。表114个城市的位置坐标城市编号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.552.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。951|6|38|7|1042变异后为：951|7|38|6|1042（7）进化逆转操作为改善遗传算法的局部搜索能力，在选择、交叉、变异之后引进连续多次的进化逆转操作。这里的进化是指逆转算子的单方向性，即只有经逆转后，适应度值有提高的才接受下来，否则逆转无效。产生两个[1,10]区间内的随机整数R1，R2，确定两个位置，将其对换位置，如如R1=4，R2=7。951|738|61042进化逆转化为：951|837|61042。对每个个体进行交叉变异，然后代入适应度函数进行评估，X选择出适应度值大的个体进行下一代的交叉和变异以及进化逆转操作。循环操作：判断是否满足设定的最大遗传代数MAXGEN,不满足则跳入适应度值的计算；否则，结束遗传操作。3MATLAB程序实现3.1种群初始化种群初始化函数INITPOP的代码：FUNCTIONCHROM=INITPOP(NIND)%%初始化种群%输入：%NIND：种群大小%N：个体染色体长度（这里为城市的个数）%输出：%初始种群FUNCTIONCHROM=INITPOP(NIND,N)CHROM=ZEROS(NIND,N);%用于存储种群FORI=1:NINDCHROM(I,:)=RANDPERM(N);%随机生成初始种群END3.2适应度函数求种群个体的适应度函数FITNESS的代码：FUNCTIONFITNV=FITNESS(LEN)%%适配值函数%输入：%个体的长度（TSP的距离）%输出：%个体的适应度值FUNCTIONFITNV=FITNESS(LEN)FITNV=1./LEN;3.3选择操作选择函数SELECT的代码：FUNCTIONSELCH=SELECT(CHROM，FITNV,GGAP)%%选择操作%输入%CHROM种群%FITNV适应度值%GGAP：代沟%输出%SELCH被选择的个体FUNCTIONSELCH=SELECT(CHROM,FITNV,GGAP)NIND=SIZE(CHROM,1);NSEL=MAX(FLOOR(NIND*GGAP+.5),2);CHRIX=SUS(FITNV,NSEL);SELCH=CHROM(CHRIX,:);其中，函数SUS的代码为：FUNCTIONNEWCHRLX=SUS(FITNV,NSEL)%输入:%FITNV个体的适应度值%NSEL被选择个体的数目%输出:%NEWCHRIX被选择个体的索引号FUNCTIONNEWCHRIX=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(MTMF&[ZEROS(1,NSEL);MF(1:NIND-1,:)]=MT);[ANS,SHUF]=SORT(RAND(NSEL,1));NEWCHRIX=NEWCHRIX(SHUF);3.4交叉操作交叉操作函数RECOMBIN的代码：FUNCTIONSELCH=RECOMBIN(SELCH,PC)%%交叉操作%输入%SELCH被选择的个体%PC交叉概率%输出：%SELCH交叉后的个体FUNCTIONSELCH=RECOMBIN(SELCH,PC)NSEL=SIZE(SELCH,1);FORI=1:2:NSEL-MOD(NSEL,2)IFPC=RAND%交叉概率PC[SELCH(I,:),SELCH(I+1,:)]=INTERCROSS(SELCH(I,:),SELCH(I+1,:));ENDEND其中，函数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]);IFR1~=R2A0=A;B0=B;S=MIN([R1,R2]);E=MAX([R1,R2]);FORI=S:EA1=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);ENDIF~ISEMPTY(I2)B(I2)=B1(I);ENDENDEND3.5变异操作变异操作函数MUTATE的代码：%%变异操作%输入：%SELCH被选择的个体%PM变异概率%输出：%SELCH变异后的个体FUNCTIONSELCH=MUTATE(SELCH,PM)[NSEL,L]=SIZE(SELCH);FORI=1:NSELIFPM=RANDR=RANDPERM(L);SELCH(I,R(1:2))=SELCH(I,R(2:-1:1));ENDEND3.6进化逆转操作进化逆转操作函数REVERSE的代码：FUNCTIONSELCH=REVERSE(SELCH,D)%%进化逆转函数%输入%SELCH被选择的个体%D个城市的距离矩阵%输出%SELCH进化逆转后的个体FUNCTIONSELCH=REVERSE(SELCH,D)[ROW,COL]=SIZE(SELCH);OBJV=PATHLENGTH(D,SELCH);%计算路径长度SELCH1=SELCH;FORI=1:ROWR1=RANDSRC(1,1,[1:COL]);R2=RANDSRC(1,1,[1:COL]);MININVERSE=MIN([R1R2]);MAXINVERSE=MAX([R1R2]);SELCH1(I,MININVERSE:MAXINVERSE)=SELCH1(I,MAXINVERSE:-1:MININVERSE);ENDOBJV1=PATHLENGTH(D,SELCH1);%计算路径长度INDEX=OBJV1OBJV;SELCH(INDEX,:)=SELCH1(INDEX,:);3.7画路线轨迹图画出所给路线的轨迹图函数DRAWPTATH的代码：FUNCTIONDRAWPTATH(CHROM,X)%%画路径函数%输入%CHROM待画路径%X各城市坐标位置R=[CHROM(1,:)CHROM(1,1)];%一个随机解(个体)FIGURE;HOLDONPLOT(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)FORI=1:SIZE(X,1)TEXT(X(I,1)+0.05,X(I,2)+0.05,NUM2STR(I),'COLOR',[1,0,0]);ENDA=X(R,:);ROW=SIZE(A,1);FORI=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]);ENDHOLDOFFXLABEL('横坐标')YLABEL('纵坐标')TITLE('轨迹图')BOXON3.8遗传算法主函数:主函数名为GE-TSP,代码如下：CLEARCLCCLOSEALLLOADCITYPOSITION1;%个城市坐标位置NIND=100;%种群大小MAXGEN=200;PC=0.9;%交叉概率PM=0.05;%变异概率GGAP=0.9;%代沟(GENERATIONGAP)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('~~~~~~~~~~