ga.m

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

                         end
                         i=m-1;%%% 全零列的个数 %%%
                         while i~=0
                             p=zerocolum(i);
                             i=i-1;
                             if p~=sonschedullen(k)
                                 for times=p+1:sonschedullen(k)
                                     sonschedul(:,times-1,k)=sonschedul(:,times,k);
                                 end      
                             end
                             sonschedullen(k)=sonschedullen(k)-1;
                         end                         
                         fprintf('首先删除全零调度后的调度表为');sonschedul(:,:,k)
                         temp1=1;
                         delet=zeros(1,1);
                         for j=1:sonschedullen(k)
                             for i=1:N
                                 if sonschedul(i,j,k)==0
                                     delet(temp1)=j;  %存放可能可以合并的调度向量
                                     temp1=temp1+1;
                                     break
                                 end
                             end
                         end 
                         delet
                         temp1=temp1-1; %temp1存放可能可以合并的列的个数
                         temp=0;     
                         zerotag=0;
                         zerocolummum=1;
                         for times=1:2
                             for pp=1:temp1-1    %进行合并
                                 if delet(pp)~=0
                                     j1=delet(pp); 
                                     for j=pp+1:temp1
                                         if delet(j)~=0
                                             j2=delet(j);
                                             combinetag=1; %标记combinetag＝1可以合并，＝0不能合并
                                             for i=1:N
                                                 if sonschedul(i,j1,k)&sonschedul(i,j2,k)
                                                     combinetag=0;
                                                     break;
                                                 end
                                             end
                                             if combinetag==1  %可能可以合并，但不知道是否有冲突，下面需要判断 
                                                 for y=1:N
                                                     temp3(y)=sonschedul(y,j1,k)+sonschedul(y,j2,k);
                                                 end 
                                                 conflicttag=0;
                                                 for y=1:N-1    %检查合并后是否有冲突，即是否有多个端口向同一个端口发送数据
                                                     for m=y+1:N
                                                         if temp3(y)==temp3(m)&temp3(y)~=0
                                                             conflicttag=1;
                                                             break   %有冲突conflicttag=1则跳出
                                                         end
                                                     end
                                                     if conflicttag==1
                                                         break
                                                     end  
                                                 end
                                                 if conflicttag==0    %没有冲突conflicttag=0则合并
                                                     fprintf('可以合并的列是');j1,j2
                                                     for y=1:N
                                                         sonschedul(y,j1,k)=temp3(y);
                                                         sonschedul(y,j2,k)=0;
                                                     end 
                                                     fprintf('合并一次后的列向量如下');
                                                     sonschedul(:,j1,k)
                                                     sonschedul(:,j2,k)
                                                     for y=1:N
                                                         sonschedul(y,j2,k)=0;
                                                     end
                                                     delet(j)=0;
                                                     zerocolum(zerocolummum)=j2;
                                                     zerocolummum=zerocolummum+1;
                                                     fprintf('合并后的向量');sonschedul(:,:,k)
                                                     temp1=temp1-1;
                                                     temp=temp+1;  %记录删除的向量的个数
                                                 end
                                             end
                                         end      
                                     end
                                 end
                             end
                         end%for times
                         for p=1:zerocolummum-1
                             for i=1:N
                                 if zerocolum(p)+1<=sonschedullen(k)
                                     for j=zerocolum(p)+1:sonschedullen(k)
                                         sonschedul(i,j-1,k)=sonschedul(i,j,k);
                                     end
                                 end
                             end
                         end
                         goodschedullen(crossindividual(k))=sonschedullen(k)-temp;
                         for i=1:N
                             for j=1:sonschedullen(k)-temp
                                 goodschedul(i,j,crossindividual(k))=sonschedul(i,j,k);                                 
                             end
                         end
                         fprintf('最终的调度表如下');goodschedul(:,:,crossindividual(k)) 
                         fprintf('最终的调度表长度');goodschedullen(crossindividual(k))                         
                         fprintf('删除并合并后的所有调度为');goodschedul,goodschedullen
                     else
                         %%% 增加不足调度，调度表的长度可能改变
                         lackT=T-tempT;%%%不足的流量矩阵
                         lackT
                         %%%%%%%%%%%        重新对lackT进行BV分解          %%%%%%%%%%%%
                         %%%%%%%%%%%   将得到的调度追加在不足调度的之后     %%%%%%%%%%%%
                         %%%%%%%%%%%%%%        并增加调度表的长度           %%%%%%%%%%%
                         if sonschedullen(z)>=sonschedullen(k)   
                             for j=1:sonschedullen(k)
                                 goodschedul(:,j,crossindividual(k))=sonschedul(:,j,k);
                             end
                         else
                             for j=1:sonschedullen(z)+templenth(z)                             
                                 goodschedul(:,j,crossindividual(k))=sonschedul(:,j,k);
                             end
                         end
                         goodschedullen(crossindividual(k))=sonschedullen(k);%需加上增加的列的个数
                         fprintf('未增加不足调度时的调度表为');goodschedul,goodschedullen
                         [appendschedul,appendschedullen]=bv(lackT);%%% 对不足调度矩阵lackT进行BV分解
                         t=goodschedullen(crossindividual(k));
                         if t+appendschedullen>timesmaxschedullen
                             for i=timesmaxschedullen+1:t+appendschedullen
                                 goodschedul(:,i,:)=0;%%%%对调度表扩容防止追加调度时列下标过界
                             end
                         end                      
                         for i=1:appendschedullen
                             goodschedul(:,t+i,crossindividual(k))=appendschedul(:,i);
                         end
                         goodschedullen(crossindividual(k))=goodschedullen(crossindividual(k))+appendschedullen;
                         fprintf('增加不足调度后');goodschedul,goodschedullen                         
                         timesmaxschedullen=goodschedullen;%%由于交叉的次数t可能大于1，每次交叉后都可能增大goodschedullen
                                                           %%%所以记下该值，防止追加调度时列下标过界                                                           %%%时
                     end    
                 end%for k 
             end %if  
         end %for t
         %%%%%%%%    一次遗传过程中的交叉完成，实际交叉次数为realcrosstimes    %%%%%%%%     
         %%%%%%%  得到交叉后的调度表为goodschedull，调度表长度为goodschedullen %%%%%%% 
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
         %%%%      变异操作，设置变异概率mutprobability=0.2       %%%%%
         %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
         mutprobability=0.2;
         mutmumber=mutprobability*POPULATIONS;%%% 计算变异个体数目 %%%  
         fprintf('估计最大进行变异次数');round(mutmumber) 
         realmuttimes=0;  %%% 预赋值实际进行的变异次数=0 %%%
         mutindividual=nan;
         t=0;
         while t~=round(mutmumber)  %%% 产生t个不同的变异个体  %%%
             t=t+1;
             mutindividual(t)=unidrnd(POPULATIONS);
             sametag=0;
             if t>1
                 for i=1:t-1
                     if mutindividual(t)==mutindividual(i);
                         sametag=1;
                         break;
                     end
                 end
             end
             if sametag==1
                 t=t-1;
             end
         end
         mutindividual  
         for i=1:t %%% 进行t次变异 %%%
             randmumber=rand(1);   
             if randmumber<mutprobability %%%% 符合变异条件 %%%%  
                 mutpartner=unidrnd(POPULATIONS);%%% 选择变异伴侣
                 while mutpartner==mutindividual(i)
                     mutpartner=unidrnd(POPULATIONS);
                 end
                 mutpartner
                 %%% 选择两个变异点 %%%   
                 mutcolum(1)=unidrnd(goodschedullen(mutindividual(i)));
                 mutcolum(2)=unidrnd(goodschedullen(mutpartner));  
                 fprintf('交叉的列为');mutcolum
                 %%% 选择两个变异交换点
                 for j=1:2      
                     mutpoint(j)=unidrnd(N);
                 end  
                 while mutpoint(2)==mutpoint(1)
                     mutpoint(2)=unidrnd(N);
                 end
                 fprintf('交叉的行是');mutpoint 
                 %判断两个变异点是否合适交换而不违反约束条件，否则重新产生变异点
                 c1=mutindividual(i);
                 c2=mutpartner;
                 varible=zeros(4,2);
                 varible(:,1)=goodschedul(:,mutcolum(1),c1);
                 varible(:,2)=goodschedul(:,mutcolum(2),c2);  
                 for j=1:2
                     temp=varible(mutpoint(j),1);
                     varible(mutpoint(j),1)=varible(mutpoint(j),2);
                     varible(mutpoint(j),2)=temp;
                 end 
                 sametag=0;
                 for j=1:2
                     for k=1:N-1
                         for m=k+1:N
                             if varible(k,j)==varible(m,j)&varible(k,j)~=0  
                                 sametag=1;
                             end
                         end
                     end
                     if sametag==1
                         break;
                     end     
                 end
                 fprintf('变异前的两个调度是');
                 goodschedul(:,mutcolum(1),c1),goodschedul(:,mutcolum(2),c2) 
                 if sametag==0%%%% 变异成功 %%%%%%%%%  
                     realmuttimes=realmuttimes+1;
                     goodschedul(:,mutcolum(1),c1)=varible(:,1);
                     goodschedul(:,mutcolum(2),c2)=varible(:,2);
                     fprintf('变异后的两个调度是');
                     goodschedul(:,mutcolum(1),c1),goodschedul(:,mutcolum(2),c2) 
                 else
                     fprintf('变异冲突失败\n');
                 end     
             else
                 fprintf('随机数小于变异概率\n');
             end%if
         end%for i
         fprintf('实际变异次数是');realmuttimes 
         for i=1:POPULATIONS
             for j=1:goodschedullen(i)
                 schedul(:,j,i)=goodschedul(:,j,i);
                 schedullen(i)=goodschedullen(i);
             end
         end
         schedul,schedullen
         %%%%%% 遗传操作结束，重新计算各个个体的抖动  %%%%%%
         lateraveragejitt=0;             
         for i=1:POPULATIONS
             jitter(i)=jit(schedul(:,:,i),schedullen(i),T); 
             lateraveragejitt=lateraveragejitt+jitter(i);  
         end   
         lateraveragejitt=lateraveragejitt/POPULATIONS;   
         %% 找每一代群体中最适应个体bestindividual(generations),其抖动最小
         %leastjit(generations)=jitter(1);         
         %for i=2:POPULATIONS  
             %if jitter(i)<leastjit(generations)
                 %leastjit(generations)=jitter(i);
             %end
         %end    
         if generations>1
             if lateraveragejitt<=gajitter(generations-1)                 
                 gajitter(generations)=lateraveragejitt; 
             else
                 gajitter(generations)=gajitter(generations-1);
                 %leastjit(generations)=leastjit(generations-1);
             end
         else
             if lateraveragejitt<=initialgajitter                
                 gajitter(generations)=lateraveragejitt; 
             else
                 gajitter(generations)=initialgajitter;
                 %leastjit(generations)=initialleastjit;
             end                
         end  
   end%for generations
   y0=[initialgajitter];
   if generations>0
       for i=2:generations+1;
           y0(i)=gajitter(i-1);
           %y1(i)=leastjit(i-1);
       end
   end
   y0
  gajitter=y0(generations+1)