遗传算法求解vrp问题(为选择操作从新设计后程序)

1、VRP.M%遗传算法求解vrp问题(为选择操作从新设计后程序)%D是距离矩阵，n为种群个数%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定%m为适配值淘汰加速指数,最好取为1,2,3,4,不宜太大%交叉概率Pc，变异概率Pm %R为最短路径,Rlength为路径长度function 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);%运算返回最优路径R和其总距离RlengthgeneticVRP.m%D是距离矩阵，n为种群个数%C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定%m为适

3、值淘汰加速指数,最好取为1,2,3,4,不宜太大%交叉概率Pc,变异概率Pm%R为最短路径,Rlength为路径长度 function R,Rlength=geneticVRP(D,demand,n,C,m,Pc,Pm) N,NN=size(D);%(31*31) farm=zeros(n,N);%用于存储种群 for i=1:n % flag=0; %while flag=0 %tem=randperm(N); %随机生成初始种群 %if validate(tem,demand,N)=1 % flag=1; %end %end farm(i,:)=randperm(N); end R=far

4、m(1,:);%一个随机解(个体) %farm(1,:)=R; len=zeros(n,1);%存储路径长度 fitness=zeros(n,1);%存储适配值 counter=0; while counter<C for i=1:n len(i,1)=myLength(D,farm(i,:);%计算路径长度 end %maxlen=max(len); minlen=min(len); %fitness=fit(len,m,maxlen,minlen);%计算适应度 rr=find(len=minlen);%返回的是在len中路径最短的路径坐标(i,1) R=farm(rr(1,1),:

5、);%更新最短路径%disp('') FARM=farm;%优胜劣汰，nn记录了复制的个数%选择, 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 %交叉检验 (可省去) 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 %变异检验(可省略) 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);%随机生成n-aa种群 % end % end FARM=R;FARM;%将随机产生的n-aa个体加入从后面种群,将上次迭代的最优解从前面加入种群 aa,bb

8、=size(FARM); %disp('4验证zong') %保持种群规模为n if aa>n FARM=FARM(1:n,:); end %disp('5验证zong') %更新farm farm=FARM; clear FARM %更新迭代次数 counter=counter+1 ; end %结果输出 Rlength=myLength(D,R) R Rlength=myLength(D,R)%结果输出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);%随机选择交叉范围，从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