1、VRP.M%遺傳算法求解vrp問(wèn)題(為選擇操作從新設(shè)計(jì)后程序)%D是距離矩陣，n為種群個(gè)數(shù)%C為停止代數(shù)，遺傳到第 C代時(shí)程序停止,C的具體取值視問(wèn)題的規(guī)模和耗費(fèi)的時(shí)間而定%m為適配值淘汰加速指數(shù),最好取為1,2,3,4,不宜太大%交叉概率Pc，變異概率Pm %R為最短路徑,Rlength為路徑長(zhǎng)度f(wàn)unction VRP%初始化demand=0 1 2 1 2 1 4 2 2;D= 0 4 6 7.5 9 20 10 16 8; 4 0 6.5 4 10 5 7.5 11 10; 6 6.5 0 7.5 10 10 7.5 7.5 7.5; 7.5 4 7.5 0 10 5 9 9 15;

2、9 10 10 10 0 10 7.5 7.5 10; 20 5 10 5 10 0 7 7 7.5; 10 7.5 7.5 9 7.5 7 0 0 10; 16 11 7.5 9 7.5 9 7 10 10; 8 10 7.5 15 10 7.5 10 10 0; n=100;C=200;m=2;Pc=0.9;Pm=0.2;R,Rlength=geneticVRP(D,demand,n,C,m,Pc,Pm);%運(yùn)算返回最優(yōu)路徑R和其總距離RlengthgeneticVRP.m%D是距離矩陣，n為種群個(gè)數(shù)%C為停止代數(shù)，遺傳到第 C代時(shí)程序停止,C的具體取值視問(wèn)題的規(guī)模和耗費(fèi)的時(shí)間而定%m為適

3、值淘汰加速指數(shù),最好取為1,2,3,4,不宜太大%交叉概率Pc,變異概率Pm%R為最短路徑,Rlength為路徑長(zhǎng)度 function R,Rlength=geneticVRP(D,demand,n,C,m,Pc,Pm) N,NN=size(D);%(31*31) farm=zeros(n,N);%用于存儲(chǔ)種群 for i=1:n % flag=0; %while flag=0 %tem=randperm(N); %隨機(jī)生成初始種群 %if validate(tem,demand,N)=1 % flag=1; %end %end farm(i,:)=randperm(N); end R=far

4、m(1,:);%一個(gè)隨機(jī)解(個(gè)體) %farm(1,:)=R; len=zeros(n,1);%存儲(chǔ)路徑長(zhǎng)度 fitness=zeros(n,1);%存儲(chǔ)適配值 counter=0; while counter<C for i=1:n len(i,1)=myLength(D,farm(i,:);%計(jì)算路徑長(zhǎng)度 end %maxlen=max(len); minlen=min(len); %fitness=fit(len,m,maxlen,minlen);%計(jì)算適應(yīng)度 rr=find(len=minlen);%返回的是在len中路徑最短的路徑坐標(biāo)(i,1) R=farm(rr(1,1),:

5、);%更新最短路徑%disp('') FARM=farm;%優(yōu)勝劣汰，nn記錄了復(fù)制的個(gè)數(shù)%選擇, K=30; aa,bb=size(FARM); FARM2=FARM; len2=len; len=sort(len); for i=1:aa tt= find(len2=len(i,1); FARM(i,:)=FARM2(tt(1,1),:); end for i=1:K j=aa+1-i; FARM(j,:)=FARM(i,:); end% 交叉操作 aa,bb=size(FARM); FARM2=FARM; for i=1:2:aa if Pc>rand&&a

6、mp;i<aa %交叉概率Pc A=FARM(i,:); B=FARM(i+1,:); A,B=intercross(A,B); FARM(i,:)=A; FARM(i+1,:)=B; end end %交叉檢驗(yàn) (可省去) for i=1:aa if myLength(D,FARM(i,:)>myLength(D,FARM2(i,:) FARM(i,:)=FARM2(i,:); end end clear FARM2 aa,bb=size(FARM); %aa=nn2 % 變異 FARM2=FARM; for i=1:aa if Pm>=rand FARM(i,:)=mut

7、ate(FARM(i,:); end end %變異檢驗(yàn)(可省略) for i=1:aa if myLength(D,FARM(i,:)>myLength(D,FARM2(i,:) FARM(i,:)=FARM2(i,:); end end clear FARM2%群體的更新 %FARM2=zeros(n-aa+1,N); %if n-aa>=1 % for i=1:n-aa % FARM2(i,:)=randperm(N);%隨機(jī)生成n-aa種群 % end % end FARM=R;FARM;%將隨機(jī)產(chǎn)生的n-aa個(gè)體加入從后面種群,將上次迭代的最優(yōu)解從前面加入種群 aa,bb

8、=size(FARM); %disp('4驗(yàn)證zong') %保持種群規(guī)模為n if aa>n FARM=FARM(1:n,:); end %disp('5驗(yàn)證zong') %更新farm farm=FARM; clear FARM %更新迭代次數(shù) counter=counter+1 ; end %結(jié)果輸出 Rlength=myLength(D,R) R Rlength=myLength(D,R)%結(jié)果輸出immuni.m% 免疫遺傳function a=immuni(a,b)m=length(a);c=zeros(m);for i=1:m c(i)=a(

9、i); c(i+1)=a(b(i,2); delete a(b(i,2); c(i+2)=a(i+3);end a=c;intercross.m%交叉算法采用部分匹配交叉%交叉算法采用部分匹配交叉function a,b=intercross(a,b)L=length(a);if L<=10 %確定交叉寬度 W=9;elseif (L/10)-floor(L/10)>=rand&&L>10 W=ceil(L/10)+8;else W=floor(L/10)+8;endp=unidrnd(L-W+1);%隨機(jī)選擇交叉范圍，從p到p+Wfor i=1:W %交叉

10、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); endmutate.mfunction a=mutate(a)L=length(a);rray=randperm(L);a(rray(1),a(rray(2)=exchange(a(rray(1),a(rray(2);myLength.m%總路徑lenfunction len=myLength(D,p)N,NN=size(D);%

11、len=D(p(1,N),p(1,1); len=0;for i=1:(N-1) len=len+D(p(1,i),p(1,i+1);end total=0 0; volume=8; demand=0 1 2 1 2 1 4 2 2; x=find(p=1); if x<9 %len=len+D(p(1,x),p(1,x+1)+D(p(1,N),1)+D(1,p(1,1)+D(p(1,x),1); %len=len+D(p(x),p(x+1)+D(p(N),1)+D(1,p(1)+D(p(x),1); len=len+D(p(x),p(x+1)+D(p(N),p(x)+D(1,p(1)+

12、D(p(x),1); else len=len+D(p(1,N),p(1,1)+D(1,p(1,1); end %len=len+D(p(x),p(x+1)+D(p(N),1)+D(1,p(1)+D(p(x),1); %len=D(1,p(1,1)+D(p(1,x),1); for i=1:x %len=len+D(p(1,i),p(1,i+1); total(1)=demand(p(1,i)+total(1); end %len=len+D(p(1,x),p(1,x+1)+D(p(1,N),1); for i=(x+1):N total(2)=demand(p(1,i)+total(2); %len=len+D(p(1,i),p(1,i+1)+D