ga_inter.m

遗传算法的小程序

% GA.m
% 生成初始种群
tic
M=[1	2	3	4	5	6	7	8	9	10;1	3	5	10	4	2	7	6	8	9;2	1	4	3	9	6	8	7	10	5;2	3	1	5	7	9	8	4	10	6;3	1	2	6	4	5	9	8	10	7;
    3	2	6	4	9	10	1	7	5	8;2	1	4	3	7	6	10	9	8	5;3	1	2	6	5	7	9	10	8	4;1	2	4	6	3	10	7	8	5	9;2	1	3	7	9	10	6	4	5	8];
       % M为各工件工序对应的机器号矩阵
pt=[29	78	9	36	49	11	62	56	44	21 ;43 90	75	11	69	28	46	46	72	30;91 85	39	74	90	10	12	89	45	33;81 95 71	99	9	52	85	98	22	43;14  6 22	61	26	69	21	49	72	53;
    84  2 52	95	48	72	47	65	6	25;46 37 61	13	32	21	32	89	30	55;31 86 46	74	32	88	19	48	36	79;
    76 69 76	51	85	11	40	89	26	74 ;85	13	61	7	64	76	7	52	90	45 ];    % pt为各工件工序对应的加工时间矩阵
[n,m]=size(M);                                        % n为工件数  % m为机器数
solution=zeros(1,n*m);
remainwork=zeros(1,n);
times=zeros(1,n);
for i=1:n
    remainwork(i)=sum(pt(i,:));
end
for j=1:n*m                          %选用优先规则MWKR（即剩余工作量最多的工件优先）来生成初始解
    for i=1:n 
        if remainwork(i)==max(remainwork)
            solution(j)=i;
            times(i)=times(i)+1;
            remainwork(i)= remainwork(i)-pt(i,times(i));
            break;
        end
    end
end
L=length(solution);        
popsize=20;                                      % popsize为种群规模
Nchange=200;                                      % Nchange为生成初始种群时第一个染色体的基因随即交换次数        
chrompop=repmat(solution,popsize,1);              % chrompop为初始种群
for i=2:popsize
    for t=1:Nchange                              % 将chrom_1中的基因随机交换Nchange次得到一个新的染色体
        changerand=ceil(L*rand(1,2));            % 生成随机数来生成染色体种群
        temp=chrompop(i,changerand(1));
        chrompop(i,changerand(1))=chrompop(i,changerand(2));
        chrompop(i,changerand(2))=temp;
    end
end

% 给出迭代步数，调用decomyque.m对每个染色体解码，求得适应度值
iteration=10;                                        % iteration为总迭代次数
fitness=zeros(1,popsize);                             % fitness为chrompop中染色体的适应值数组
maxfitness=zeros(1,iteration);
MAKESPAN=zeros(1,iteration);
const_a=2;
const_b=0.01;
for s=1:popsize
    fitness(s)=decomyque(chrompop(s,:),M,pt);
end
bestfitness=max(fitness);
s=find(fitness==bestfitness);
best_solution=chrompop(min(s),:);
for K=1:iteration
    maxfitness(K)=max(fitness);
    MAKESPAN(K)=-log(maxfitness(K)/const_a)/const_b;
    
    % 以下为选择操作
    selectset=zeros(popsize,L);                 % 定义选择操作后染色体种群为selectset
    selectfitness=zeros(1,popsize);                                
    dividesum=cumsum(fitness)/sum(fitness);
    for s=1:popsize
        selectrand=rand
        if  selectrand<dividesum(1)
          selectset(s,:)=chrompop(1,:);
          selectfitness(s)=fitness(1);
          continue;
        end
        for s_1=2:popsize
            if dividesum(s_1-1)<selectrand&selectrand<dividesum(s_1)
               selectset(s,:)=chrompop(s_1,:);
               selectfitness(s)=fitness(s_1);
               break;
            end
        end
    end
    if  bestfitness<=max(selectfitness)
        bestfitness=max(selectfitness);
        s=find(selectfitness==max(selectfitness));
        best_solution=selectset(min(s),:);
    else
        randnumber=ceil(rand*popsize);
        selectset(randnumber,:)=best_solution;
        selectfitness(randnumber)=bestfitness;
    end
    
    % 以下为交叉操作
    crossset=zeros(popsize,L);                                     %定义交叉后染色体群为crossset
    crossfitness=zeros(1,popsize);
    average_fitness=sum(selectfitness)/popsize;
    diversity=sum((selectfitness-average_fitness).^2)/(popsize-1);
    if diversity>10000
        poscross=0.7;
    else poscross=0.9-0.00002*diversity;
    end
    matchrand=randperm(popsize);                                   %生成随机数以便于染色体配对
    for s=1:popsize/2
        crossrand=rand;                                           %生成随机数，决定是否交叉
        if crossrand>=poscross                                    %若随机数大于交叉概率则不交叉，直接放入crossset中    
            crossset(s,:)=selectset(matchrand(s),:);
            crossfitness(s)=selectfitness(matchrand(s));
            crossset(popsize+1-s,:)=selectset(matchrand(popsize+1-s),:);
            crossfitness(popsize+1-s)=selectfitness(matchrand(popsize+1-s));
        else                                                       %若随机数crossrand小于交叉概率则进行交叉
            wayrand=rand;                                          %若随机数crossrand小于0.5则采用双性交叉
            if wayrand<=0.5                                             
            crossset(s,:)=selectset(matchrand(s),:);
            crossset(popsize+1-s,:)=selectset(matchrand(popsize+1-s),:);
            elementrand=randperm(L);                               %生成随机数，定义前后交叉点
            x1=min(elementrand(1:2));                               
            x2=max(elementrand(1:2));
            A=crossset(s,x1:x2);                                    %将染色体分别赋给A,B
            B=crossset(popsize+1-s,x1:x2);
            binarycross;                                            %调用函数binarycross.m进行双性交叉
            crossset(s,x1:x2)=A;
            crossset(popsize+1-s,x1:x2)=B;
            crossfitness(s)=decomyque(crossset(s,:),M,pt);
            crossfitness(popsize+1-s)=decomyque(crossset(popsize+1-s,:),M,pt);
          else
                crossset(s,:)=selectset(matchrand(s),:);
                crossset(popsize+1-s,:)=selectset(matchrand(popsize+1-s),:);
                s_1=randperm(L);
                s_2=randperm(L);
                s_1(5:L)=[];
                s_2(5:L)=[];
                r_1=sort(s_1);
                r_2=sort(s_2);
                tempset_1=crossset(s,r_1(1):r_1(2));
            if r_1(3)-r_1(2)==1
                crossset(s,r_1(1):(r_1(1)+r_1(4)-r_1(3)))=crossset(s,r_1(3):r_1(4));
                crossset(s,r_1(1)+r_1(4)-r_1(3)+1:r_1(4))=tempset_1;
            else
                tempset_2=crossset(s,r_1(2)+1:r_1(3)-1);
                crossset(s,r_1(1):(r_1(1)+r_1(4)-r_1(3)))=crossset(s,r_1(3):r_1(4));
                crossset(s,(r_1(1)+r_1(4)-r_1(3)+1):(r_1(1)+r_1(4)-r_1(2)-1))=tempset_2;
                crossset(s,(r_1(1)+r_1(4)-r_1(2)):r_1(4))=tempset_1;
            end
            tempset_1=crossset(popsize+1-s,r_2(1):r_2(2));
            if r_2(3)-r_2(2)==1
                crossset(popsize+1-s,r_2(1):(r_2(1)+r_2(4)-r_2(3)))=crossset(popsize+1-s,r_2(3):r_2(4));
                crossset(popsize+1-s,(r_2(1)+r_2(4)-r_2(3)+1):r_2(4))=tempset_1;
            else
                tempset_2=crossset(popsize+1-s,r_2(2)+1:r_2(3)-1);
                crossset(popsize+1-s,r_2(1):(r_2(1)+r_2(4)-r_2(3)))=crossset(popsize+1-s,r_2(3):r_2(4));
                crossset(popsize+1-s,(r_2(1)+r_2(4)-r_2(3)+1):(r_2(1)+r_2(4)-r_2(2)-1))=tempset_2;
                crossset(popsize+1-s,(r_2(1)+r_2(4)-r_2(2)):r_2(4))=tempset_1;
            end
            crossfitness(s)=decomyque(crossset(s,:),M,pt);
            crossfitness(popsize+1-s)=decomyque(crossset(popsize+1-s,:),M,pt);
          end
        end
    end
if bestfitness<=max(crossfitness)
    bestfitness=max(crossfitness);
    s=find(crossfitness==max(crossfitness));
    best_solution=crossset(min(s),:);
else
    randnumber=ceil(rand*popsize);
    crossset(randnumber,:)=best_solution;
    crossfitness(randnumber)=bestfitness;
end


% 以下为变异操作
    average_fitness=sum(crossfitness)/popsize;
    diversity=sum((crossfitness-average_fitness).^2)/(popsize-1);
    mutationset=zeros(popsize,L);                   % 定义变异后的染色体种群为mutationset
    mutationfitness=zeros(1,popsize);
    if diversity>10000
        posmutation=0.1;
    else
        posmutation=0.2-0.00001*diversity;
    end
    for s=1:popsize
       randnumber=rand;                              % 生成随机数
       if randnumber>=posmutation                    % 若随机数比变异概率大，则不产生变异，直接将染色体放入mutationset中
          mutationset(s,:)=crossset(s,:);
          mutationfitness(s)=crossfitness(s);
       else                                          % 若随机数比变异概率小，则进行变异,本方案采用三种变异方式：交换、逆序、插入
           tempsolution=repmat(crossset(s,:),3,1);
           tempfitness=zeros(1,3);
           r=randperm(L);                                  %变异方式之一：交换
           tempset=tempsolution(1,r(1));
           tempsolution(1,r(1))=tempsolution(1,r(2));
           tempsolution(1,r(2))=tempset;
           
           r=randperm(L);                                   %变异方式之一：逆序
           x1=min(r(1),r(2));
           x2=max(r(1),r(2));
           tempsetA=tempsolution(2,x1:x2);
           tempsetB=zeros(1,length(tempsetA));
           for s_1=1:length(tempsetA)
               tempsetB(length(tempsetA)+1-s_1)=tempsetA(s_1);
           end
           tempsolution(2,x1:x2)=tempsetB;
           
           r=randperm(L);                                   %变异方式之一：插入
           x1=min(r(1),r(2));
           x2=max(r(1),r(2));
           tempset=tempsolution(3,x1+1:x2-1);
           tempsolution(3,x2-1)=tempsolution(3,x1);
           tempsolution(3,x1:x2-2)=tempset;
           for s_1=1:3
               tempfitness(s_1)=decomyque(tempsolution(s_1,:),M,pt);
           end
           if posmutation==0.2
              s_1=find(tempfitness==min(tempfitness));
              mutationset(s,:)=tempsolution(min(s_1),:);
              mutationfitness(s)=min(tempfitness);
           else
              s_1=find(tempfitness==max(tempfitness));
              mutationset(s,:)=tempsolution(min(s_1),:);
              mutationfitness(s)=max(tempfitness);
           end
       end
    end
    if bestfitness<=max(mutationfitness)
    bestfitness=max(mutationfitness);
    s=find(mutationfitness==max(mutationfitness));
    best_solution=mutationset(min(s),:);
    else
    randnumber=ceil(rand*popsize);
    mutationset(randnumber,:)=best_solution;
    mutationfitness(randnumber)=bestfitness;
    end

    
     tempset=find(mutationfitness==bestfitness);
  if length(tempset)>1
     for s=1:(length(tempset)-1)  
           r=randperm(L);                                   
           x1=min(r(1),r(2));
           x2=max(r(1),r(2));
           tempsetA=mutationset(tempset(s),x1:x2);
           tempsetB=zeros(1,length(tempsetA));
           for s_1=1:length(tempsetA)
               tempsetB(length(tempsetA)+1-s_1)=tempsetA(s_1);
           end
           mutationset(tempset(s),x1:x2)=tempsetB;
           mutationfitness(tempset(s))=decomyque(mutationset(tempset(s),:),M,pt);
   end
 end
     if bestfitness<=max(mutationfitness)
    bestfitness=max(mutationfitness);
    s=find(mutationfitness==max(mutationfitness));
    best_solution=mutationset(min(s),:);
    else
    randnumber=ceil(rand*popsize);
    mutation(randnumber,:)=best_solution;
    mutationfitness(randnumber)=bestfitness;
    end
         
    
    % 以下将得到的染色体种群lastset赋给chrompop，重新进行新的迭代
    chrompop=mutationset;
    fitness=mutationfitness;
end
bestvalue=-log(bestfitness/const_a)/const_b;
K=1:iteration;
plot(K,MAKESPAN)
toc