ga.m

使用遗传算法实现交换机的分组调度

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%        该遗传算法采用fit＝1/(1＋jitter)形式的适应度函数           %%%%%
%%%%        轮盘赌选择策略；单点交叉，pc＝0.4；pm＝0.2                 %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function gajitter=ga(T)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%         产生初始种群schedul,并计算各个个体的抖动值jitter          %%%%%
%%%%   预设种群大小=100,最后删除重复的个体，种群大小＝populationsize    %%%%%
%%%%             利用BV算法产生初始的调度表，可使吞吐量最大             %%%%%
%%%%   对T=[0,3,2,4;2,3,0,2;4,1,3,0;2,0,2,3]行或列元素之和<10而言     %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
T=[0,3,2,4;2,3,0,2;4,1,3,0;2,0,2,3];
TIMES=10;%初始估计种群大小
N=4;%端口大小
LEN=9;
         for i=1:TIMES
             [table,len,bandsize,matrixnumb]=bv(T); %BV分解得到调度表
             if i==1
                 maxlen=len;
             end
             if i>1
                 if len<maxlen                    
                     for j=(len+1):maxlen
                         table(:,j)=0;
                     end
                 end
             end             
             tempschedul(:,:,i)=table;
             tempschedullen(i)=len;  
             if len>maxlen
                 maxlen=len;
             end
         end
         %%%%%%%%%     寻找重复的个体（调度表）    %%%%%%%%%%
         %%%%    same(i)存放重复的个体的序号,共有k个    %%%%%
         for i=1:TIMES
             for j=1:TIMES
                 samemum(i,j)=0;
             end
         end
         for i=1:TIMES-1
             for j=i+1:TIMES
                 if tempschedul(:,:,i)==tempschedul(:,:,j)
                     samemum(i,j)=samemum(i,j)+1;
                 end
             end
         end
         samemum
         mum=0;
         for i=1:TIMES
             for j=1:TIMES
                 if samemum(i,j)~=0
                     mum=mum+1;
                 end
             end
         end
         k=0; %预附重复个体的个数＝0；
         if mum~=0
             k=1;
             for j=1:TIMES
                 for i=1:TIMES
                     if samemum(i,j)==1
                         same(k)=j;
                         k=k+1;
                         break;
                     end
                 end
             end
             k=k-1;
             same
         end
         %%%%%%%%%     删除重复的k个个体（调度表）    %%%%%%%%%%
         j=1;
         if k>0    
             for i=1:TIMES
                 tag=0;
                 for t=1:k
                     if i==same(t)
                         tag=1;
                         break;
                     end
                 end
                 if tag==0
                     schedul(:,:,j)=tempschedul(:,:,i);
                     schedullen(j)=tempschedullen(i);
                     j=j+1;
                 end
             end
         elseif k==0
             for i=1:TIMES
                 schedul(:,:,j)=tempschedul(:,:,i);
                 schedullen(j)=tempschedullen(i);                 
                 j=j+1;
             end
         end
         %%%产生的种群放于schedul(:,:,i), 个体的长度schedullen(i)
         temppopulations=j-1;%由于随机产生，种群大小可能并不是整10倍数  
         schedul,schedullen
         POPULATIONS=temppopulations
         fprintf('种群大小为');POPULATIONS 
     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     %%%%%%%%%%%%%%%          进行遗传操作          %%%%%%%%%%%%%%%%%%%%%%
     %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     %%%%%%%%%%%%  计算种群中各个个体的初始抖动  %%%%%%%%%%%%%% 
     beforejitter=0;
     for i=1:POPULATIONS
         jitter(i)=jit(schedul(:,:,i),schedullen(i),T); 
         beforejitter=beforejitter+jitter(i);
     end
     initialgajitter=beforejitter/POPULATIONS;%初始群体的平均抖动
     initialleastjit=jitter(1);   
     for i=2:POPULATIONS  
         if jitter(i)<initialleastjit
             initialleastjit=jitter(i);
         end
     end
     GENERATIONS=20;   %%遗传进化代数   
     for generations=1:GENERATIONS            
         %%%%%%%使种群大小为10、15、20、25等类似的数%%%%%%%%%%%%%%%%%%%%%%%%
         %temp=temppopulations;
         %gewei=mod(temp,10);
         %shiwei=temp-gewei;
         %if gewei>=5
         %   temp=shiwei+5;
         %else
          %   temp=shiwei;
         %end
         %POPULATIONS=temp;         
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %%%%%%%%%%%%      计算种群中各个个体的适应度      %%%%%%%%%%%%%%%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         totalfit=0;
         for i=1:POPULATIONS              
             fit(i)=1/(1+jitter(i));%%适应度的范围在[0,1]
             totalfit=totalfit+fit(i);
         end
         fit,totalfit                 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%       采用轮盘赌策略，选择POPULATIONS个优良个体，进入下一代        %%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %%%%%%%% 计算各个个体的被选中的概率selectprobability %%%%%%%%%%%%%%  
         for i=1:POPULATIONS             
             selectprobability(i)=fit(i)/totalfit;
         end        
         selectprobability      
         %%%%%%   计算各个个体被选中的累积概率cumulateprobability   %%%%%%%%
         cumulateprobability(1)=selectprobability(1);
         for i=2:POPULATIONS
             cumulateprobability(i)=selectprobability(i)+cumulateprobability(i-1);
         end
         cumulateprobability
         %%%%%%%%%%%%%%%%%        选择优良个体             %%%%%%%%%%%%%%%%
         for i=1:POPULATIONS
             randmumber(i)=rand(1);
         end
         randmumber
         for i=1:POPULATIONS
             for j=1:POPULATIONS
                 if randmumber(i)<=cumulateprobability(j)
                     break;
                 end
             end
             goodschedul(:,:,i)=schedul(:,:,j);
             goodschedullen(i)=schedullen(j);
         end
         goodschedul,goodschedullen%%% 选择的优良个体                
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%        采用单点交叉策略，设置交叉概率crossprobability=0.4         %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%    
         crossprobability=0.4;
         crossmumber=crossprobability*POPULATIONS;%%% 计算交换个体数目 %%%         
         maxsonschedullen=0;
         if mod(crossmumber,2)~=0    %%%%%%  使交换个体的数目为偶数  %%%%%
             crossmumber=crossmumber+1;
         end 
         sonschedullen(1,2)=zeros;
         fprintf('进行交叉次数');round(crossmumber/2)
         timesmaxschedullen=goodschedullen(1);
         realcrosstimes=0; %%% 预赋值实际进行的交叉次数＝0 %%%
         for t=1:round(crossmumber/2)  %%% 进行t次交叉 %%%
             for i=1:2
                 crossindividual(i)=unidrnd(POPULATIONS);
             end
             while crossindividual(1)==crossindividual(2)%% 保证选择的两个交叉个体不是同一个体 %%
                 for i=1:2
                     crossindividual(i)=unidrnd(POPULATIONS);
                 end
             end
             crossindividual
             randmumber=rand(1);     
             if randmumber<crossprobability %%%% 可以交叉 %%%%  
                 realcrosstimes=realcrosstimes+1;
                 for i=1:2  %%% 选择两个个体的交叉点 %%%
                     temp=goodschedullen(crossindividual(i))-1;
                     crosspoint(i)=unidrnd(temp);
                     leavelen(i)=goodschedullen(crossindividual(i))-crosspoint(i);
                 end  
                 crosspoint,leavelen
                 %%%%%%%%%%%%%%%%%%  交叉   %%%%%%%%%%%%%%%%%%%%%                 
                 for k=1:2                     
                     if k==1
                         z=2;
                     else
                         z=1;
                     end      
                     j=crosspoint(k);
                     for i=1:j
                         sonschedul(:,i,k)=goodschedul(:,i,crossindividual(k));
                     end
                     m=crosspoint(z)+1;
                     for i=j+1:j+leavelen(z)                         
                         sonschedul(:,i,k)=goodschedul(:,m,crossindividual(z));
                         m=m+1;
                     end
                     sonschedullen(k)=j+leavelen(z);
                 end 
                 sonschedul,sonschedullen                 
                 maxsonschedullen=sonschedullen(1);
                 if sonschedullen(2)>sonschedullen(1)
                     maxsonschedullen=sonschedullen(2);
                 end 
                 %%%%%%%%%%%%%      修改交叉后的子个体     %%%%%%%%%%%%
                 %%%% 完成交叉一对个体，得到的个体染色体长度可能变化 %%%%
                 for k=1:2 
                     tempT=zeros(N,N);%%%tempT临时矩阵变量
                     for i=1:N
                         for j=1:sonschedullen(k)
                             if sonschedul(i,j,k)~=0
                                 t=sonschedul(i,j,k);
                                 tempT(i,t)=tempT(i,t)+1;
                                 if tempT(i,t)>T(i,t) %%%删除多余调度
                                     sonschedul(i,j,k)=0;
                                     tempT(i,t)=tempT(i,t)-1;
                                 end
                             end
                         end%for j
                     end%for i
                     if sonschedullen(k)~=maxsonschedullen
                         for i=sonschedullen(k)+1:maxsonschedullen
                             sonschedul(:,i)=0;
                         end
                     end                      
                     fprintf('删除冗余调度后的调度表为');sonschedul(:,:,k)
                     tempT,T
                     if tempT==T
                         tag=1; %%% 没有不足调度，但可能需要合并 %%%
                     else
                         tag=0; %%%%%%   有不足调度，需增加   %%%%%%
                     end
                     for i=1:2
                         if sonschedullen(i)<goodschedullen(crossindividual(i))
                             templenth(i)=goodschedullen(crossindividual(i))-sonschedullen(i);%temp--临时
                         else
                             templenth(i)=0;
                         end
                     end
                     if tag==1
                         %%%%%%%%% 合并调度，调度表的长度也可能改变   %%%%%%%%%%%
                         %%%%%%%%%       首先删除全零列调度          %%%%%%%%%%%
                         m=1; %%%%计数器
                         for j=1:sonschedullen(k)
                             zmum=0;
                             for i=1:N
                                 if sonschedul(i,j,k)==0
                                     zmum=zmum+1;
                                 else
                                     break;
                                 end
                             end
                             if zmum==N 
                                 zerocolum(m)=j;
                                 m=m+1;
                             end