test_xnodes.m

遗传算法例程：通过MATLAB

% A 0-1 programming problem Using Co-GA1

%//////////////////////////////////////////////////////////////%
nodes = 100;                                     % 节点数目
%//////////////////////////////////////////////////////////////%

NVAR = (nodes - 1).*nodes./2;                   % 链路（变量）数目

NIND = 30;                                      % 单代个体数

%//////////////////////////////////////////////////////////////%
MAXGEN = 8000;                                   % 遗传代数
%//////////////////////////////////////////////////////////////%

eff = 0.9;                                      % 单一链路正常工作概率

rthres = 0.95;                                  % 全网可靠性约束要求

nthres = 13;                                     % 节点连接数约束要求（单一节点最大通信能力）

voilthres = 5;                                  % 越界容限

%////////////////////////////////////////////////////////////////////////%
edrate = 0.1;                                   % 开始的时候按照这个概率生成各边
%////////////////////////////////////////////////////////////////////////%

gen=1;

for i = 1:NIND                                  % 生成全部满足全连通性和2-连通性的初始个体
    for j = 1:NVAR
        epos = rand(1);
        if epos > edrate
            Chrom(i,j) = 0;
        else
            Chrom(i,j) = 1;
        end
    end
    while con2check(Chrom(i,:),nodes) == 0 | wholeconcheck(Chrom(i,:),nodes) ==0
        for j = 1:NVAR
            epos = rand(1);
            if epos > edrate
                Chrom(i,j) = 0;
            else
                Chrom(i,j) = 1;
            end
        end
    end
end
esp=0.001; P=0.1; t=0;

cost = 10 + fix(unidrnd(20,nodes,nodes));       % 费用矩阵，可以修改形式

for i = 1:nodes                                 % 把费用矩阵化成对称矩阵
    for j = i:nodes
        if i == j
            cost(i,j) = 0;
        else 
            cost(j,i) = cost(i,j);
        end
    end
end

for i=1:NIND
    ObjV(i,:)=CND_Obj(Chrom(i,:),nodes,cost);
end

[R,S]=size(ObjV);
if R==1
    ObjV=ObjV';
end


for i=1:NIND
    c=0;
    feasible(i)=0;
    yviol(i,:)=CND_Voil(Chrom(i,:),nodes,eff,rthres,nthres);
    if yviol(i,:) <= voilthres;
       c=c+1;
       feasible(i)=1;
    end
end

%disp(feasible);

if c>0
    ppfirst=(NIND-c)./NIND;
    t=1;
end

tic;

for gen=1:MAXGEN
    index=unidrnd(NIND,2.*NIND,1);        % 开始协同进化计算
    for n=1:NIND
        if feasible(index(n))==1 & feasible(index(NIND+n))==1
            if ObjV(index(n))>ObjV(index(NIND+n))
                SelChmin(n,:)=Chrom(index(NIND+n),:);
            else
                SelChmin(n,:)=Chrom(index(n),:);
            end
        elseif feasible(index(n))==0 & feasible(index(NIND+n))==0
                if yviol(index(n))>yviol(index(NIND+n))
                    SelChmin(n,:)=Chrom(index(NIND+n),:);
                else
                    SelChmin(n,:)=Chrom(index(n),:);
                end
        elseif feasible(index(n))==1 & feasible(index(NIND+n))==0
            if yviol(index(NIND+n))<=esp
                if ObjV(index(n))>ObjV(index(NIND+n))
                    SelChmin(n,:)=Chrom(index(NIND+n),:);
                else
                    SelChmin(n,:)=Chrom(index(n),:);
                end
            else
                SelChmin(n,:)=Chrom(index(n),:);
            end
        elseif feasible(index(n))==0 & feasible(index(NIND+n))==1
            if yviol(index(n))<esp
                if ObjV(index(n))>ObjV(index(NIND+n))
                    SelChmin(n,:)=Chrom(index(NIND+n),:);
                else
                    SelChmin(n,:)=Chrom(index(n),:);
                end
            else
                SelChmin(n,:)=Chrom(index(NIND+n),:);
            end
        end
    end                         
    
    RecChrom = zeros(NIND,NVAR);
    cntavail = 1;
    borderflag = 0;   % 保证填充的时候不越界
    
    while sum(RecChrom(NIND,:)) == 0
        SelChmin = recombin('xovsp',SelChmin,0.25);
        SelChmin = mut(SelChmin);
        for i = 1:NIND
            if wholeconcheck(SelChmin(i,:),nodes) == 1     % 全连通检查
                RecChrom(cntavail,:) = SelChmin(i,:);
                if cntavail == NIND
                    borderflag = 1;       % 可行解（全连通解）已经填满个体矩阵，退出内层循环
                    break;
                end
                cntavail = cntavail + 1;
            end
        end
        if borderflag == 1    % 可行解已经填充满个体矩阵，退出外层循环
            break;
        end
    end
        
    SelChmin = RecChrom;    % 这时全连通的个体已经填满了SelChmin，把他们写回到原来的SelChmin里面
    
    for i = 1:NIND          % 对不满足2-连接性的个体执行修补算法
        if con2check(SelChmin(i,:),nodes) == 0
            SelChmin(i,:) = CND_Repairchrom(SelChmin(i,:),nodes,cost);
        end
    end

    for i=1:NIND
        ObjVSelmin(i,:)=CND_Obj(Chrom(i,:),nodes,cost);
    end
    [R,S]=size(ObjVSelmin);
    if R==1
       ObjVSelmin=ObjVSelmin';
    end
    
    Chrom = reins(Chrom,SelChmin);
 
    for i=1:NIND                  % 计算每一个染色体对应的Objv和Viol
        c=0;
        feasible(i)=0;
        ObjV(i,:)=CND_Obj(Chrom(i,:),nodes,cost);
        yviol(i,:)=CND_Voil(Chrom(i,:),nodes,eff,rthres,nthres);
        if yviol(i)<=voilthres
           c=c+1;
           feasible(i)=1;
        end
    end
    
    [R,S]=size(ObjV);
    if R==1
       ObjV=ObjV';
    end
    if c>0
       pp(gen)=(NIND-c)./NIND;
       t=1;
    else
        pp(gen)=1;
    end
    
    if t==1 & mod(gen,5)==0
       if pp(gen-4)<=P & pp(gen-3)<=P & pp(gen-2)<=P & pp(gen-1)<=P & pp(gen)<=P
           esp=1.1.*esp;
       elseif pp(gen-4)>P & pp(gen-3)>P & pp(gen-2)>P & pp(gen-1)>P & pp(gen)>P
              esp=0.3.*esp;
       else
              esp=esp;
       end
    end
    
    if gen>500       % 选择本次的Chrom是什么
        a=1;
        ObjVNew=[];
       for i=1:NIND
           if (feasible(i)==1)
               ObjVNew(a,:)=CND_Obj(Chrom(i,:),nodes,cost);
               Chrom1(a,:)=Chrom(i,:);
               a=a+1;
           end 
       end
    else
        ObjVNew=ObjV;
        Chrom1=Chrom;
    end
    [Y,I]=min(ObjVNew);
    Out(gen,:)=Y;
    Chromoutp(gen,:)=Chrom1(I,:);
    disp(gen);
    toc
end

[j,k]=size(Chromoutp);
for i=1:j
    VoilNew(i,:)=CND_Voil(Chromoutp(i,:),nodes,eff,rthres,nthres);
end
ChromOut=[Chromoutp,Out,VoilNew];
x=1:MAXGEN;
plot(x,Out);