ga.m.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=100;                                      % 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=100;                                        % 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);
    sumfitness=sum(fitness);                                
    cumsumfitness=cumsum(fitness);
    dividesum=cumsumfitness/sumfitness;
    selectrand=rand(1,popsize);                 % 随机生成popsize个随机数，从chrompop中选出染色体
    for s=1:popsize
        if  selectrand(s)<dividesum(1)
          selectset(s,:)=chrompop(1,:);
          selectfitness(s)=fitness(1);
        end
        for s_1=2:popsize
            if dividesum(s_1-1)<selectrand(s)&selectrand(s)<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>400
        poscross=0.7;
    else poscross=0.9-0.0005*diversity;
    end
  if K<ceil(iteration/3)                                          %前面1/3次迭代全部采用双性交叉
    matchrand=randperm(popsize);                                   %生成随机数以便于染色体配对
    crossrand=rand(1,popsize/2);                                   %生成随机数，决定是否交叉
    for s=1:popsize/2
        if crossrand(s)>=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                                                       %若随机数小于交叉概率则进行交叉
            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);
        end
    end
elseif K>ceil(iteration/3)&K<ceil(2*iteration/3)                    %中间1/3次迭代中将要双性交叉和单性交叉混用
    matchrand=randperm(popsize);                                   %生成随机数以便于染色体配对
    crossrand=rand(1,popsize/2);                                   %生成随机数，决定是否交叉
    yescross=find(crossrand<poscross);
    nocross=find(crossrand>=poscross);
    if length(yescross)==0                                          %表明此时没有一对染色体要交叉                                           
        crossset=selectset;
        crossfitness=selectfitness;
    elseif length(nocross)==0                                        %表明此时所有染色体均要交叉（一半采用单性交叉，一半双性交叉）
        for s=1:ceil(0.5*(popsize/2))                                    %这半部分采用单性交叉
            crossset(s,:)=selectset(matchrand(s),:);
            crossset(popsize+1-s,:)=selectset(matchrand(popsize+1-s),:);
        r_1=randperm(L);
            r_2=randperm(L);
            r_1(5:L)=[];
            r_2(5:L)=[];
            for s_1=1:3                                            
                for s_2=(1+s_1):4
                    if r_1(s_1)>r_1(s_2)
                        temp=r_1(s_1);
                        r_1(s_1)=r_1(s_2);
                        r_1(s_2)=temp;
                    end
                end
            end
            for s_1=1:3
                for s_2=(1+s_1):4
                    if r_2(s_1)>r_2(s_2)
                        temp=r_2(s_1);
                        r_2(s_1)=r_2(s_2);
                        r_2(s_2)=temp;
                    end
                end
            end
            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
        for s=(ceil(0.5*(popsize/2))+1):popsize/2                 %这部分采用双性交叉
            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);
        end
    else                                                           %此时一部分将要进行交叉，另一部分不交叉 
        if length(yescross)==1                                     %此时只有一对染色体将要进行交叉，采用双性交叉方式
            crossset(yescross(1),:)=selectset(matchrand(yescross(1)),:);
            crossset(popsize+1-yescross(1),:)=selectset(matchrand(popsize+1-yescross(1)),:);
            elementrand=randperm(L);                           %生成随机数，定义前后交叉点
            x1=min(elementrand(1:2));                               
            x2=max(elementrand(1:2));
            A=crossset(yescross(1),x1:x2);                                    %将染色体分别赋给A,B
            B=crossset(popsize+1-yescross(1),x1:x2);
            binarycross;
            crossset(yescross(1),x1:x2)=A;
            crossset(popsize+1-yescross(1),x1:x2)=B;
            crossfitness(yescross(1))=decomyque(crossset(yescross(1),:),M,pt);
            crossfitness(popsize+1-yescross(1))=decomyque(crossset(popsize+1-yescross(1),:),M,pt);
            for s=1:length(nocross)
                crossset(nocross(s),:)=selectset(matchrand(nocross(s)),:);
                crossset(popsize+1-nocross(s),:)=selectset(matchrand(popsize+1-nocross(s)),:);