《2022年遗传算法解决TSP问题的matlab程序 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法解决TSP问题的matlab程序 .pdf（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1.遗传算法解决TSP 问题（附 matlab 源程序）2.知 n 个城市之间的相互距离，现有一个推销员必须遍访这n 个城市，并且每个城市3.只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其4.旅行路线的总长度最短？5.用图论的术语来说，假设有一个图g=(v,e)，其中 v 是顶点集，e 是边集，设d=(dij)6.是由顶点 i 和顶点 j 之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶7.点且每个顶点只通过一次的具有最短距离的回路。8.这个问题可分为对称旅行商问题(dij=dji,任意 i,j=1,2,3，,n)和非对称旅行商9.问题(dij dji
2、,任意i,j=1,2,3，,n)。10.若对于城市 v=v1,v2,v3,vn 的一个访问顺序为t=(t1,t2,t3,ti,tn),其中11.ti v(i=1,2,3,n)，且记tn+1=t1，则旅行商问题的数学模型为：12.min l=d(t(i),t(i+1)（i=1,n）13.旅行商问题是一个典型的组合优化问题，并且是一个np 难问题，其可能的路径数目14.与城市数目 n 是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法15.求其近似解。16.遗传算法：17.初始化过程：用v1,v2,v3,vn代表所选 n 个城市。定义整数pop-size作为染色体的个数18.，并且
3、随机产生pop-size个初始染色体，每个染色体为1 到 18 的整数组成的随机序列。19.适应度 f 的计算：对种群中的每个染色体vi，计算其适应度，f=d(t(i),t(i+1).20.评价函数 eval(vi)：用来对种群中的每个染色体vi 设定一个概率，以使该染色体被选中21.的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被22.选择产生后台的机会要大，设alpha(0,1)，本文定义基于序的评价函数为eval(vi)=al 23.pha*(1-alpha).(i-1)。随机规划与模糊规划 24.选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋
4、转都为新的种群选择一个25.染色体。赌轮是按每个染色体的适应度进行选择染色体的。26.step1、对每个染色体vi,计算累计概率qi，q0=0;qi=eval(vj)j=1,i;i=1,27.pop-size.28.step2、从区间(0,pop-size)中产生一个随机数r；29.step3、若 qi-1 step4、重复 step2 和 step3 共 pop-size次，这样可以得到pop-size个复制的染色体。30.grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的31.染色体，本文采用grefenstette编码遗传算法原理及应用可以避免这种情
5、况的出现32.。所谓的 grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如：33.8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1 34.对应：35.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。36.交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到 pop-size重复以下过37.程：从 0，1中产生一个随机数r，如果 r 将所选的父代两两组队，随机产生一个位置进行交叉，如：38.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 39.6 12 3 5 6 8
6、5 6 3 1 8 5 6 3 3 2 1 1 40.交叉后为：41.8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 42.6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1 43.变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi 作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 20 页 -44.按均匀变异（该变异点xk 的取值范围为 ukmin,ukmax,产生一个 0，1 中随机数r，该点45.变异为 xk=ukmin+r(ukm
7、ax-ukmin)）操作。如：46.8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 47.变异后：48.8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1 49.反 grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作50.和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。51.循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f 的计算；是，结束遗传52.操作，跳出。53.54.55.56.matlab 代码57.58.59.60.distTSP.txt
8、61.0 6 18 4 8 62.7 0 17 3 7 63.4 4 0 4 5 64.20 19 24 0 22 65.8 8 16 6 0 66.%GATSP.m 67.function gatsp1()68.clear;69.load distTSP.txt;70.distance=distTSP;71.N=5;72.ngen=100;73.ngpool=10;74.%ngen=input(#of generations to evolve=);75.%ngpool=input(#of chromosoms in the gene pool=);%size of genepool 76.
9、gpool=zeros(ngpool,N+1);%gene pool 77.for i=1:ngpool,%intialize gene pool 78.gpool(i,:)=1 randomize(2:N)1;79.for j=1:i-1 80.while gpool(i,:)=gpool(j,:)81.gpool(i,:)=1 randomize(2:N)1;82.end 83.end 84.end 85.86.costmin=100000;87.tourmin=zeros(1,N);名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 20 页 -88.cost=zeros(1,
10、ngpool);89.increase=1;resultincrease=1;90.for i=1:ngpool,91.cost(i)=sum(diag(distance(gpool(i,:),rshift(gpool(i,:);92.end 93.%record current best solution 94.costmin,idx=min(cost);95.tourmin=gpool(idx,:);96.disp(num2str(increase)minmum trip length=num2str(costmin)97.98.costminold2=200000;costminold1
11、=150000;resultcost=100000;99.tourminold2=zeros(1,N);100.tourminold1=zeros(1,N);101.resulttour=zeros(1,N);102.while(abs(costminold2-costminold1);100)&(abs(costminold1-costmin);100)&(increase;500)103.104.costminold2=costminold1;tourminold2=tourminold1;105.costminold1=costmin;tourminold1=tourmin;106.in
12、crease=increase+1;107.if resultcostcostmin 108.resultcost=costmin;109.resulttour=tourmin;110.resultincrease=increase-1;111.end 112.for i=1:ngpool,113.cost(i)=sum(diag(distance(gpool(i,:),rshift(gpool(i,:);114.end 115.%record current best solution 116.costmin,idx=min(cost);117.tourmin=gpool(idx,:);11
13、8.%=119.%copy gens in th gpool according to the probility ratio 120.%1.1 copy twice 121.%=0.9 copy once 122.%;0.9 remove 123.csort,ridx=sort(cost);124.%sort from small to big.125.csum=sum(csort);126.caverage=csum/ngpool;127.cprobilities=caverage./csort;128.copynumbers=0;removenumbers=0;129.for i=1:n
14、gpool,130.if cprobilities(i)1.1 131.copynumbers=copynumbers+1;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 20 页 -132.end 133.if cprobilities(i)0.9 134.removenumbers=removenumbers+1;135.end 136.end 137.copygpool=min(copynumbers,removenumbers);138.for i=1:copygpool 139.for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:);
15、140.end 141.gpool(2*i+1,:)=gpool(i,:);142.end 143.if copygpool=0 144.gpool(ngpool,:)=gpool(1,:);145.end 146.%=147.%when genaration is more than 50,or the patterns in a couple are too close,do mutation 148.for i=1:ngpool/2 149.%150.sameidx=gpool(2*i-1,:)=gpool(2*i,:);151.diffidx=find(sameidx=0);152.i
16、f length(diffidx)1,207.if n=1,208.col=1;209.elseif n1,210.error(x must be a vector!break);211.end%x is a column vectorelseif m=1,212.if n=1,y=x;213.return 214.elseif n1,215.col=0;%x is a row vector endend 216.if dir=1,%rotate left or up 217.if col=0,%row vector,rotate left 218.y=x(2:n)x(1);219.elsei
17、f col=1,名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 20 页 -220.y=x(2:n);x(1);%rotate up 221.end 222.elseif dir=0,%default rotate right or down 223.if col=0,224.y=x(n)x(1:n-1);225.elseif col=1%column vector 226.y=x(n);x(1:n-1);227.end 228.end 229.%=230.function L1,L2=crossgens(X1,X2)231.%Usage:L1,L2=crossgens(X1,X
18、2)232.s=randomize(2:12);233.n1=min(s(1),s(11);n2=max(s(1),s(11);234.X3=X1;X4=X2;235.for i=n1:n2,236.for j=1:13,237.if X2(i)=X3(j),238.X3(j)=0;239.end 240.if X1(i)=X4(j),X4(j)=0;241.end 242.end 243.end 244.j=13;k=13;245.for i=12:-1:2,246.if X3(i)=0,247.j=j-1;248.t=X3(j);X3(j)=X3(i);X3(i)=t;249.end 25
19、0.if X4(i)=0,251.k=k-1;252.t=X4(k);X4(k)=X4(i);X4(i)=t;253.end 254.end 255.for i=n1:n2 256.X3(2+i-n1)=X2(i);257.X4(2+i-n1)=X1(i);258.end 259.L1=X3;L2=X4;遗传算法程序 matlab 1.遗传算法程序:名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 20 页 -2.说明:fga.m 为遗传算法的主程序;采用二进制Gray 编码,采用基于轮盘赌法的非线性排名选择,均匀交叉,变异操作,而且还引入了倒位操作!3.4.function Be
20、stPop,Trace=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options)5.%BestPop,Trace=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation)6.%Finds a maximum of a function of several variables.7.%fmaxga solves problems of the form:8.%max F(X)subject to:LB=X=UB 9.%BestPop-最优的群体即为最优的染色体群10.%Trace-
21、最佳染色体所对应的目标函数值11.%FUN-目标函数12.%LB-自变量下限13.%UB-自变量上限14.%eranum-种群的代数,取 100-1000(默认 200)15.%popsize-每一代种群的规模；此可取50-200(默认 100)16.%pcross-交叉概率,一般取 0.5-0.85之间较好(默认 0.8)17.%pmutation-初始变异概率,一般取 0.05-0.2之间较好(默认 0.1)18.%pInversion-倒位概率,一般取 0.05 0.3 之间较好(默认 0.2)19.%options-1*2矩阵,options(1)=0二进制编码(默认 0),optio
22、n(1)=0十进制编20.%码,option(2)设定求解精度(默认 1e-4)21.%22.%-23.24.T1=clock;25.if nargin0)32.error(数据输入错误,请重新输入(LBUB):);33./UB):);34.end 35.s=sprintf(程序运行需要约%.4f 秒钟时间,请稍等.,(eranum*popsize/1000);36.disp(s);37.38.global m n NewPop children1 children2 VarNum 39.40.bounds=LB;UB;bits=;VarNum=size(bounds,1);41.precis
23、ion=options(2);%由求解精度确定二进制编码长度42.bits=ceil(log2(bounds(:,2)-bounds(:,1)./precision);%由设定精度划分区间43.Pop=InitPopGray(popsize,bits);%初始化种群44.m,n=size(Pop);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 20 页 -45.NewPop=zeros(m,n);46.children1=zeros(1,n);47.children2=zeros(1,n);48.pm0=pMutation;49.BestPop=zeros(eranum,n);
24、%分配初始解空间BestPop,Trace 50.Trace=zeros(eranum,length(bits)+1);51.i=1;52.while i=eranum 53.for j=1:m 54.value(j)=feval(FUN(1,:),(b2f(Pop(j,:),bounds,bits);%计算适应度55.end 56.MaxValue,Index=max(value);57.BestPop(i,:)=Pop(Index,:);58.Trace(i,1)=MaxValue;59.Trace(i,(2:length(bits)+1)=b2f(BestPop(i,:),bounds,
25、bits);60.selectpop=NonlinearRankSelect(FUN,Pop,bounds,bits);%非线性排名选择61.CrossOverPop=CrossOver(selectpop,pCross,round(unidrnd(eranum-i)/eranum);62.%采用多点交叉和均匀交叉，且逐步增大均匀交叉的概率63.%round(unidrnd(eranum-i)/eranum)64.MutationPop=Mutation(CrossOverPop,pMutation,VarNum);%变异65.InversionPop=Inversion(MutationPo
26、p,pInversion);%倒位66.Pop=InversionPop;%更新67.pMutation=pm0+(i4)*(pCross/3-pm0)/(eranum4);68.%随着种群向前进化，逐步增大变异率至1/2 交叉率69.p(i)=pMutation;70.i=i+1;71.end 72.t=1:eranum;73.plot(t,Trace(:,1);74.title(函数优化的遗传算法);xlabel(进化世代数(eranum);ylabel(每一代最优适应度(maxfitness);75.MaxFval,I=max(Trace(:,1);76.X=Trace(I,(2:len
27、gth(bits)+1);77.hold on;plot(I,MaxFval,*);78.text(I+5,MaxFval,FMAX=num2str(MaxFval);79.str1=sprintf(进化到%d 代,自变量为%s 时,得本次求解的最优值%fn对应染色体是：%s,I,num2str(X),MaxFval,num2str(BestPop(I,:);80.disp(str1);81.%figure(2);plot(t,p);%绘制变异值增大过程82.T2=clock;83.elapsed_time=T2-T1;84.if elapsed_time(6)0 85.elapsed_tim
28、e(6)=elapsed_time(6)+60;elapsed_time(5)=elapsed_time(5)-1;86.end 87.if elapsed_time(5)1时,b(i)=mod(a(i-1)+a(i),2)104.%其中原二进制串:a(1)a(2).a(n),Gray串:b(1)b(2).b(n)105.initpop(i,:)=pop(1:end-1);106.end 107.initpop(popsize,:)=ones(1,len);%The whole one encoding individual 108.109.110.111.112.%解码113.114.fun
29、ction fval=b2f(bval,bounds,bits)115.%fval-表征各变量的十进制数116.%bval-表征各变量的二进制编码串117.%bounds-各变量的取值范围118.%bits-各变量的二进制编码长度119.scale=(bounds(:,2)-bounds(:,1)./(2.bits-1);%The range of the variables 120.numV=size(bounds,1);121.cs=0 cumsum(bits);122.for i=1:numV 123.a=bval(cs(i)+1):cs(i+1);124.fval(i)=sum(2.(
30、size(a,2)-1:-1:0).*a)*scale(i)+bounds(i,1);125.end 126.127.128.129.130.%选择操作131.%采用基于轮盘赌法的非线性排名选择名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 20 页 -132.%各个体成员按适应值从大到小分配选择概率：133.%P(i)=(q/1-(1-q)n)*(1-q)i,其中 P(0)P(1).P(n),sum(P(i)=1 134.135.function selectpop=NonlinearRankSelect(FUN,pop,bounds,bits)136.global m n 1
31、37.selectpop=zeros(m,n);138.fit=zeros(m,1);139.for i=1:m 140.fit(i)=feval(FUN(1,:),(b2f(pop(i,:),bounds,bits);%以函数值为适应值做排名依据141.end 142.selectprob=fit/sum(fit);%计算各个体相对适应度(0,1)143.q=max(selectprob);%选择最优的概率144.x=zeros(m,2);145.x(:,1)=m:-1:1;146.y x(:,2)=sort(selectprob);147.r=q/(1-(1-q)m);%标准分布基值148
32、.newfit(x(:,2)=r*(1-q).(x(:,1)-1);%生成选择概率149.newfit=cumsum(newfit);%计算各选择概率之和150.rNums=sort(rand(m,1);151.fitIn=1;newIn=1;152.while newIn=m 153.if rNums(newIn)NEWFIT(FITIN)154.selectpop(newIn,:)=pop(fitIn,:);155.newIn=newIn+1;156.else 157.fitIn=fitIn+1;158.end 159.end 160.161.162.163.164.%交叉操作165.fu
33、nction NewPop=CrossOver(OldPop,pCross,opts)166.%OldPop为父代种群，pcross 为交叉概率167.global m n NewPop 168.r=rand(1,m);169.y1=find(r=pCross);171.len=length(y1);172.if len2&mod(len,2)=1%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数173.y2(length(y2)+1)=y1(len);174.y1(len)=;175.end 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 20 页 -176.if len
34、gth(y1)=2 177.for i=0:2:length(y1)-2 178.if opts=0 179.NewPop(y1(i+1),:),NewPop(y1(i+2),:)=EqualCrossOver(OldPop(y1(i+1),:),OldPop(y1(i+2),:);180.else 181.NewPop(y1(i+1),:),NewPop(y1(i+2),:)=MultiPointCross(OldPop(y1(i+1),:),OldPop(y1(i+2),:);182.end 183.end 184.end 185.NewPop(y2,:)=OldPop(y2,:);186
35、.187.%采用均匀交叉188.function children1,children2=EqualCrossOver(parent1,parent2)189.190.global n children1 children2 191.hidecode=round(rand(1,n);%随机生成掩码192.crossposition=find(hidecode=1);193.holdposition=find(hidecode=0);194.children1(crossposition)=parent1(crossposition);%掩码为 1，父 1 为子 1 提供基因195.childr
36、en1(holdposition)=parent2(holdposition);%掩码为 0，父 2 为子 1 提供基因196.children2(crossposition)=parent2(crossposition);%掩码为 1，父 2 为子 2 提供基因197.children2(holdposition)=parent1(holdposition);%掩码为 0，父 1 为子 2 提供基因198.199.%采用多点交叉，交叉点数由变量数决定200.201.function Children1,Children2=MultiPointCross(Parent1,Parent2)202
37、.203.global n Children1 Children2 VarNum 204.Children1=Parent1;205.Children2=Parent2;206.Points=sort(unidrnd(n,1,2*VarNum);207.for i=1:VarNum 208.Children1(Points(2*i-1):Points(2*i)=Parent2(Points(2*i-1):Points(2*i);209.Children2(Points(2*i-1):Points(2*i)=Parent1(Points(2*i-1):Points(2*i);210.end 21
38、1.212.213.214.215.%变异操作216.function NewPop=Mutation(OldPop,pMutation,VarNum)217.218.global m n NewPop 219.r=rand(1,m);名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 20 页 -220.position=find(r=1 223.for i=1:len 224.k=unidrnd(n,1,VarNum);%设置变异点数，一般设置1 点225.for j=1:length(k)226.if OldPop(position(i),k(j)=1 227.OldPop(
39、position(i),k(j)=0;228.else 229.OldPop(position(i),k(j)=1;230.end 231.end 232.end 233.end 234.NewPop=OldPop;235.236.237.238.239.%倒位操作240.241.function NewPop=Inversion(OldPop,pInversion)242.243.global m n NewPop 244.NewPop=OldPop;245.r=rand(1,m);246.PopIn=find(r=1 249.for i=1:len 250.d=sort(unidrnd(n
40、,1,2);251.if d(1)=1&d(2)=n 252.NewPop(PopIn(i),1:d(1)-1)=OldPop(PopIn(i),1:d(1)-1);253.NewPop(PopIn(i),d(1):d(2)=OldPop(PopIn(i),d(2):-1:d(1);254.NewPop(PopIn(i),d(2)+1:n)=OldPop(PopIn(i),d(2)+1:n);255.end 256.end 257.end TSP 问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序%D 是距离矩阵，n 为种群个数,建议取为城市个数的12 倍，%C 为停止代数，遗传
41、到第C 代时程序停止,C 的具体取值视问题的规模和耗费的时间而定%m 为适应值归一化淘汰加速指数,最好取为 1,2,3,4,不宜太大%alpha 为淘汰保护指数,可取为 01 之间任意小数,取 1 时关闭保护功能,最好取为 0.81.0%R 为最短路径,Rlength 为路径长度名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 20 页 -function R,Rlength=geneticTSP(D,n,C,m,alpha)N,NN=size(D);farm=zeros(n,N);%用于存储种群for i=1:n farm(i,:)=randperm(N);%随机生成初始种群e
42、nd R=farm(1,:);%存储最优种群len=zeros(n,1);%存储路径长度fitness=zeros(n,1);%存储归一化适应值counter=0;while counter=alpha*rand nn=nn+1;FARM(nn,:)=farm(i,:);end end FARM=FARM(1:nn,:);aa,bb=size(FARM);%交叉和变异while aan if nnn FARM=FARM(1:n,:);%保持种群规模为n end farm=FARM;clear FARM counter=counter+1 end Rlength=myLength(D,R);fu
43、nction a,b=intercross(a,b)L=length(a);if L=rand&L10 W=ceil(L/10);else W=floor(L/10);end p=unidrnd(L-W+1);%随机选择交叉范围，从p 到 p+W for 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 function x,y=exchange(x,y)temp
44、=x;x=y;y=temp;%计算路径的子程序function 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%计算归一化适应值子程序名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 20 页 -function fitness=fit(len,m,maxlen,minlen)fitness=len;for i=1:length(len)fitness(i,1)=(1-(len(i,1)-minlen)/(maxlen-minlen+0.000
45、001).m;end 已知 n 个城市之间的相互距离，现有一个推销员必须遍访这n 个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短？用图论的术语来说，假设有一个图g=(v,e)，其中 v 是顶点集，e 是边集，设 d=(dij)是由顶点 i 和顶点 j 之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji,任意 i,j=1,2,3，,n)和非对称旅行商问题(dij dji,任意 i,j=1,2,3，,n)。若对于城市 v=v1,v2
46、,v3,vn 的一个访问顺序为 t=(t1,t2,t3,ti,tn),其中tiv(i=1,2,3,n)，且记 tn+1=t1，则旅行商问题的数学模型为：min l=d(t(i),t(i+1)（i=1,n）旅行商问题是一个典型的组合优化问题，并且是一个np 难问题，其可能的路径数目与城市数目 n 是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法求其近似解。遗传算法：初始化过程：用 v1,v2,v3,vn代表所选 n 个城市。定义整数 pop-size 作为染色体的个数，并且随机产生 pop-size 个初始染色体，每个染色体为1 到 18 的整数组成的随机序列。适应度 f 的计
47、算：对种群中的每个染色体vi，计算其适应度，f=d(t(i),t(i+1).评价函数 eval(vi)：用来对种群中的每个染色体vi 设定一个概率，以使该染色体被选中的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被选择产生后台的机会要大，设alpha(0,1)，本文定义基于序的评价函数为eval(vi)=al pha*(1-alpha).(i-1)。随机规划与模糊规划 选择过程：选择过程是以旋转赌轮pop-size 次为基础，每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。step1、对每个染色体 vi,计算累计概率 qi，q0=0;
48、qi=eval(vj)j=1,i;i=1,pop-size.step2、从区间(0,pop-size)中产生一个随机数 r；step3、若 qi-1 step4、重复 step2 和 step3 共 pop-size 次，这样可以得到pop-size 个复制的染色体。grefenstette 编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的染色体，本文采用grefenstette 编码遗传算法原理及应用可以避免这种情况的出现。所谓的 grefenstette 编码就是用所选队员在未选（不含淘汰）队员中的位置，如：8 15 2 16 10 7 4 3 11 14 6 12 9 5
49、 18 13 17 1 对应：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从到 pop-size 重复以下过程：从 0，1中产生一个随机数 r，如果 r 将所选的父代两两组队，随机产生一个位置进行交叉，如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1 交叉后为：8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 20 页
50、 -6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1 变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体 vi 作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置按均匀变异（该变异点xk 的取值范围为 ukmin,ukmax,产生一个 0，1中随机数 r，该点变异为 xk=ukmin+r(ukmax-ukmin)）操作。如：8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 变异后：8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1 反 grefenstette 编码：交叉和变异