CADCAM 遗传算法实例.doc

旅行商问题:一个旅行商需要访问5个城市，在任意路线的两个城市之间有一个关联的费用（例如公里数、航空费用等）。找出一个费用最少的路 径：从一个城市出发，经过所有其他的城市一次且仅一次，然后回到出发点，城市编号为1,2,.,5。给定种群规模N=100，进化代数T=20，交叉率Pc=0.95，变异率Pm=0.08。1、问题分析本问题中一个旅行商要访问5个城市，寻找费用最少的路径。因为费用一般与路途长远成成一定比例，这里我们不妨将城市之间的距离代替为旅行城市之间的费用，这样旅行费用最少问题我们可以化为一个寻找一条最短的遍历5个城市的最短路径, 即搜索自然数子集W= 1 ,2 ,3, 4, 5 ( W的元素表示对5个城市的编号) 的一个排列( W) = V1 , V2 , V3, V4, V5 , 使length = d ( Vi , Vi+1) + d ( V1 , V5)取最小值, 式中的d ( Vi , Vi+1) 表示城市Vi 到城市Vi + 1的距离.2、 算法基本流程3.基因个体编码方法由于遗传算法不能直接处理问题空间的数据，所以我们必须将问题空间的数据映射成遗传空间的基因型串结构数据，而算法程序是可以处理遗传空间的基因型串结构数据的。比如现在要计算北京、天津 武汉、西安、拉萨这五个城市的一条最优路径，但算法程序不能够直接处理北京、天津、武汉、西安、拉萨这些数据，所以我们得给它们编上号，北京（0）、天津（1）、武汉（2）、西安（3）、拉萨（4），路径（天津西安北京武汉拉萨）可以表示成基因型串结构数据（13024），这样算法程序只要直接处理它们的编号就行了。本例采用互换编码在旅行商问题中，一串基因编码用来表示遍历的城市顺序，如：23451，表示五个城市中，先经过城市2，再经过城市3，依此类推。4.初始种群产生方法路径编码是最直观的方式，以城市序号作为遗传基因。在本例中，我们用一个N维向量来表示一个个体，N是城市总数，元素表示城市遍历顺序，以最后一个到达的城市为结束。则群体用一个N * POP的矩阵表示，POP为群体中的人口（个体数）。初始群体在空间中自动生成。5.适应度计算方法 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。本例中，遍历各城市路径之和越小越好，由于暂时无法先验估计收敛性和目标结果，所以以一个参数，最大遗传代数作为程序结束控制。6、遗传算子设计（1）、选择（selection）：选择或复制操作是为了从当前群体中选出优良的个体， 使它们有机会作为父代为下一代繁殖子孙。个体适应度越高，其被选择的机会就越多。此处采用与适用度成比例的概率方法进行选择。具体地说，就是首先计算群体中所有个体适应度的总和（），再计算每个个体的适应度所占的比例（），并以此作为相应的选择概率。（2）、交叉操作：交叉操作是遗传算法中最主要的遗传操作。简单的交叉（即一点交叉）可分两步进行：首先对种群中个体进行随机配对;其次，在配对个体中随机设定交叉处，配对个体彼此交换部分信息。（3）、变异：变异操作是按位（bit）进行的，即把某一位的内容进行变异。变异操作同样也是随机进行的。一般而言，变异概率都取得较小。变异操作是十分微妙的遗传操作，它需要和交叉操作配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。7、 程序%主程序%初始化a=0 0;123 78;345 567;1234 1221;788 423;%a：假定的5个城市的坐标 n=100;%n：种群个数T=20;%C：停止代数m=1;%m：适配值淘汰加速指数Pc=0.95;%Pc：交叉概率Pm=0.85;%Pm： 变异概率D=distance(a);%生成距离矩阵R,Rlength=GeneTSP(D,a,n,T,m,Pc,Pm);%返回值：最优路径R ，总距离Rlength-%子程序（.h文件）%GeneTSP.h%D：距离矩阵%n：种群个数%a：5个城市的坐标，在初始化时设定%T:停止代数%m:适值淘汰加速指数,不宜太大(5以下)%Pc：交叉概率%Pm：变异概率%R：最短路径，Rlength：路径长度 function R,Rlength=GeneTSP(D,a,n,T,m,Pc,Pm) N,NN=size(D); %(5*5) farm=zeros(n,N); %存储种群 for i=1:n farm(i,:)=randperm(N); end R=farm(1,:); %一个随机解(个体) scatter(a(:,1),a(:,2),x) title(城市坐标图) text(0,0,北京) text(123,78,天津) text(345,567,西安) text(1234,1221,拉萨) text(788,423,武汉) ;%画出所有点,a(:,1):X坐标,a(:,2):Y坐标 hold on pause(1) %画出随机解得路径图 figure; plotaiwa(a,R) title(随机初始化结果) text(0,0,北京) text(123,78,天津) text(345,567,西安) text(1234,1221,拉萨) text(788,423,武汉) ; hold on pause(1) %输出随机的解得路径和总距离 disp(初始种群中的一个随机值:) Rlength=myLength(D,R) %计算各个个体总距离和适配置 len=zeros(n,1);%存储路径长度 fitness=zeros(n,1); %存储适配值 counter=0; while counterrand&i=rand FARM(i,:)=mutate(FARM(i,:); end end FARM=R;FARM;%将随机产生的n-aa个体加入从后面种群,将上次迭代的最优解从前面加入种群 aa,bb=size(FARM); %保持种群规模为n if aan FARM=FARM(1:n,:); end %更新farm farm=FARM; clear FARM %更新迭代次数 counter=counter+1 ; end %结果输出 Rlength=myLength(D,R) figure plotaiwa(a,R) title(遗传算法求解结果) text(0,0,北京) text(123,78,天津) text(345,567,西安) text(1234,1221,拉萨) text(788,423,武汉);%画图 disp(迭代次数T); disp(T); disp(迭代后结果); Rlength=myLength(D,R)%结果输出-%distance.h%计算邻接矩阵%输入参数a是中国5个城市的坐标%输出参数D是无向图的赋权邻接矩阵function D=distance(a)c,d=size(a); %此例中c=5,d=2D=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); endend-%myLength.h%总路径lenfunction 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-%plotaiwa.h%绘制路径示意图 R记录路径%a：假定的5个城市的坐标%R：最短路径function plotaiwa(a,R)scatter(a(:,1),a(:,2)hold onplot(a(R(1),1),a(R(5),1),a(R(1),2),a(R(5),2)hold onfor 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 onend-%cross.h%交叉算法采用部分匹配交叉function a,b=cross(a,b)L=length(a);W=3p=unidrnd(L-W+1);%随机选择交叉范围，从p到p+Wfor 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 -%mutate.h%变异算法function a=mutate(a)L=length(a);rray=randperm(L);a(rray(1),a(rray(2)=exchange(a(rray(1),a(rray(2);-%exchange.h%交换函数 function m,n=exchange(m,n) c=m; m