遗传算法求解TSP问题实验报告

实验目的加深对逻辑程序运行机理的理解，掌握MATLAB语言的特点、熟悉其编程环境，同时为后面的人工智能程序设计做好准备。1、熟悉MATLAB语言编程环境的使用；2、了解MATLAB语言中常量、变量的表示方法；3、了解利用MATLAB进行事实库、规则库的编写方法；实验环境计算机哈尔滨工程大学计算机学院实验室预习要求实验前应阅读实验指导书，了解实验目的、预习MATLAB语言的相关知识。实验内容1、学习使用MATLAB，包括进入MATLAB主程序、编辑源程序、修改环境目录、退出等基本操作。2、在MATLAB集成环境下调试运行简单的MATLAB程序，如描述亲属关系的MATLAB程序或其他小型演绎数据库程序等。实验方法和步骤步骤一针对TSP问题，确定编码。可采用十进制编码法，对城市进行编号，每个城市分别用1到n之间不同的整数表示，n个整数的一个排列就代表了旅行商问题。步骤二针对TSP问题，适应度函数可定义为：其中d（ci，ci+1）表示相邻城市之间的距离。步骤三针对TSP问题，确定交叉规则。对于采用整数编码表示的染色体，可以有以下交叉规则：（1）常规交叉法设有父代1和父代2，交配后产生子代1和子代2。随机选取一个交配位，子代1交配位之前的基因选自父代1交配位之前的基因，交配位之后的基因，从父代2中按顺序选取那些没有出现过的基因。子代2也进行类似的处理。交叉位（黑色所示为交叉位）父代1：12345678父代2：52173864子代1：12345786子代2：52173468步骤四确定变异规则，以下三种变异规则可任选一种。（1）基于位置的变异：该方法随机地产生两个变异位，然后将第二个变异位上的基因移动到第一个变异位之前。如假定变异位为2和5，对整数编码的TSP问题，变异前后的变化为：变异前：12345编译后：15234（2）基于次序的变异：该方法随机地产生两个变异位，然后交换这两个变异位上的基因。如假定变异位为2和5，对整数编码的TSP问题，变异前后的变化为：变异前：12345编译后：15342步骤五根据选定的编码、遗传操作实现基本遗传算法（1）根据在搜索空间U上定义一个适应度函数f(x)，确定种群规模N，交叉率Pc和变异率Pm，代数T。（2）随机产生U中的N个个体s1,s2,…,sN，组成初始种群S={s1,s2,…,sN}，置代数计数器t=1。（3）计算S中每个个体的适应度f()（4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。（5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1。（6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2。（7）按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3。（8）将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3。示例程序functiongaTSPclear;CityNum=30;[dislist,Clist]=tsp(CityNum);inn=100;%初始种群大小gnmax=1000;%最大代数pc=0.8;%交叉概率pm=0.8;%变异概率%产生初始种群fori=1:inns(i,:)=randperm(CityNum);end[f,p]=objf(s,dislist);gn=1;whilegn<gnmax+1forj=1:2:innseln=sel(s,p);%选择操作scro=cro(s,seln,pc);%交叉操作scnew(j,:)=scro(1,:);scnew(j+1,:)=scro(2,:);smnew(j,:)=mut(scnew(j,:),pm);%变异操作smnew(j+1,:)=mut(scnew(j+1,:),pm);ends=smnew;%产生了新的种群[f,p]=objf(s,dislist);%计算新种群的适应度%记录当前代最好和平均的适应度[fmax,nmax]=max(f);ymean(gn)=1000/mean(f);ymax(gn)=1000/fmax;%记录当前代的最佳个体x=s(nmax,:);drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;%pause;endgn=gn-1;figure(2);plot(ymax,'r');holdon;plot(ymean,'b');grid;title('搜索过程');legend('最优解','平均解');end%------------------------------------------------%计算适应度函数function[f,p]=objf(s,dislist);inn=size(s,1);%读取种群大小fori=1:innf(i)=CalDist(dislist,s(i,:));%计算函数值，即适应度endf=1000./f';%计算选择概率fsum=0;fori=1:innfsum=fsum+f(i)^15;endfori=1:innps(i)=f(i)^15/fsum;end%计算累积概率p(1)=ps(1);fori=2:innp(i)=p(i-1)+ps(i);endp=p';end%--------------------------------------------------functionpcc=pro(pc);test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n);end%--------------------------------------------------%“选择”操作functionseln=sel(s,p);inn=size(p,1);%从种群中选择两个个体fori=1:2r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;%选中个体的序号endend%------------------------------------------------%“交叉”操作functionscro=cro(s,seln,pc);bn=size(s,2);pcc=pro(pc);%根据交叉概率决定是否进行交叉操作，1则是，0则否scro(1,:)=s(seln(1),:);scro(2,:)=s(seln(2),:);ifpcc==1c1=round(rand*(bn-2))+1;%在[1,bn-1]范围内随机产生一个交叉位c2=round(rand*(bn-2))+1;chb1=min(c1,c2);chb2=max(c1,c2);middle=scro(1,chb1+1:chb2);scro(1,chb1+1:chb2)=scro(2,chb1+1:chb2);scro(2,chb1+1:chb2)=middle;fori=1:chb1whilefind(scro(1,chb1+1:chb2)==scro(1,i))zhi=find(scro(1,chb1+1:chb2)==scro(1,i));y=scro(2,chb1+zhi);scro(1,i)=y;endwhilefind(scro(2,chb1+1:chb2)==scro(2,i))zhi=find(scro(2,chb1+1:chb2)==scro(2,i));y=scro(1,chb1+zhi);scro(2,i)=y;endendfori=chb2+1:bnwhilefind(scro(1,1:chb2)==scro(1,i))zhi=find(scro(1,1:chb2)==scro(1,i));y=scro(2,zhi);scro(1,i)=y;endwhilefind(scro(2,1:chb2)==scro(2,i))zhi=find(scro(2,1:chb2)==scro(2,i));y=scro(1,zhi);scro(2,i)=y;endendendend%--------------------------------------------------%“变异”操作functionsnnew=mut(snew,pm);bn=size(snew,2);snnew=snew;pmm=pro(pm);%根据变