《TSP问题的遗传算法求解》由会员分享，可在线阅读，更多相关《TSP问题的遗传算法求解（17页珍藏版）》请在金锄头文库上搜索。
1、TSP问题的遗传算法求解一、问题描述假设有一个旅行商人要拜访N个城市，要求他从一个城市出发，每个城市最多拜访一次，最后要回到出发的城市，保证所选择的路径长度最短。二、算法描述（一）算法简介（遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过模拟自然进化过程搜索最优解。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择个体，并借助于自然遗传学
2、的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。摘自百度百科）。（二）遗传算子遗传算法中有选择算子、交叉算子和变异算子。选择算子用于在父代种群中选择进入下一代的个体。交叉算子用于对种群中的个体两两进行交叉，有Partial-MappedCrossover、OrderCrossover、Position-basedCrossover等交叉算子。变异算子用于对种群中的个体进行
3、突变。（三）算法步骤描述遗传算法的基本运算过程如下：1.初始化：设置进化代数计数器t=0、设置最大进化代数T、交叉概率、变异概率、随机生成M个个体作为初始种群P2.个体评价：计算种群P中各个个体的适应度3.选择运算：将选择算子作用于群体。以个体适应度为基础，选择最优个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代4.交叉运算：在交叉概率的控制下，对群体中的个体两两进行交叉5.变异运算：在变异概率的控制下，对群体中的个体两两进行变异，即对某一个体的基因进行随机调整6.经过选择、交叉、变异运算之后得到下一代群体P1。重复以上1-6，直到遗传代数为T，以进化过程中所得到的具有最大适应度个
4、体作为最优解输出，终止计算。三、求解说明（一）优化目标给定二维数据intpos用于存储各个城市的坐标，采用欧式距离代表城市之间的距离。利用遗传算法，找到不重复遍历所有城市的路径中，所走距离最短的路径。（二）选择算子选择算子采用轮盘赌选择，以每个个体的适应度为基础，为每个个体计算累积概率。第1页，共6页个体1、2、3、4的个体适应度如上图所示。适应度计算规则：染色体代表的路径实际距离作为个体的适应度，如下（distencexy表示城市x到y的距离）染色体0213，适应度为distence02+distence21+distence13+distence30qa表示个体a的累积概率，如上图所示个体
5、1、2、3、4的累积概率分别为0.14、0.53、0.69、1随机生成一个0到1的浮点数f，若qaf=qb，则个体b被选中。（三）交叉算子1.Partial-MappedCrossover（部分映射交叉）第2页，共6页2.OrderCrossover（顺序交叉）第3页，共6页3.Position-basedCrossover（基于位置的交叉）（四）变异算子变异算子随机进行多次，每次在个体基因序列中选择两个位置的基因进行交换。第4页，共6页四、参考资料基于遗传算法求解TSP问题（JAVA）用遗传算法求解TSP问题五、源代码functionga_TSP%mainlyamendedbyChenZhe
6、n,20122016CityNum=35;%youchanchoose10,35,50,75dislist,Clist=tsp(CityNum);inn=35;%gnmax=500;%最大代数pc=0.8;%交叉概率pm=0.8;%变异概率%产生初始种群s=zeros(inn,CityNum);fori=1:inns(i,:)=randperm(CityNum);end,p=objf(s,dislist);gn=1;ymean=zeros(gn,1);ymax=zeros(gn,1);xmax=zeros(inn,CityNum);第5页，共6页scnew=zeros(inn,CityNum)
7、;smnew=zeros(inn,CityNum);whilegngnmax+1forj=1:2:innseln=sel(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)=10
8、00/mean(f);ymax(gn)=1000/fmax;%记录当前代的最佳个体x=s(nmax,:);xmax(gn,:)=x;drawTSP(Clist,x,ymax(gn),gn,0);gn=gn+1;endmin_ymax,index=min(ymax);第6页，共6页drawTSP(Clist,xmax(index,:),min_ymax,index,1);figure(2);plot(ymax,r);holdon;plot(ymean,b);grid;title(搜索过程);legend(最优解,平均解);fprintf(遗传算法得到的最短距离:%.2fn,min_ymax);f
9、printf(遗传算法得到的最短路线);disp(xmax(index,:);end%-%计算所有种群的适应度functionf,p=objf(s,dislist)inn=size(s,1);%读取种群大小f=zeros(inn,1);fori=1:innf(i)=CalDist(dislist,s(i,:);%计算函数值，即适应度endf=1000./f;%取距离倒数%根据个体的适应度计算其被选择的概率第7页，共6页fsum=0;fori=1:innfsum=fsum+f(i)15;%让适应度越好的个体被选择概率越高endps=zeros(inn,1);fori=1:innps(i)=f(i
10、)15/fsum;end%计算累积概率p=zeros(inn,1);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;第8页，共6页n=round(rand*99)+1;pcc=test(n);end%-%“选择”操作functionseln=sel(p)seln=zeros(2,1);%从种群中选择两个个体，最好不要两次选择同一个个体fori=1:2r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)0j=j+1;endseln(i)=j;%选中个体的序号ifi=2&j=seln(i-1)%若相同就再选一次r=rand;%产生一个随机数prand=p-r;j=1;whileprand(j)0
