www.pudn.com > gatree.zip > gatree.m, change:2011-11-21,size:2733b


function []=gatree(position,maxstep,num,eliminate) 
 
% position为点位置坐标,为n*2矩阵 
% maxstep为最大迭代次数 
% num为群体规模 
% eliminate为淘汰率应选在0,1之间 
 
% n为点数目 
n=size(position,1); 
 
% edges为边矩阵,第一个分量为边长度,后两个为连接的两个点的编号,ee为计数器 
edges=[]; 
ee=1; 
for i=1:n 
    for j=i+1:n 
        edges(ee,1)=sqrt((position(i,1)-position(j,1))^2+(position(i,2)-position(j,2))^2); 
        edges(ee,2)=i; 
        edges(ee,3)=j; 
        ee=ee+1; 
    end 
end 
 
%fitness为每个个体的适应度 
fitness=[]; 
 
%gene为种群基因,一行表示一个个体的基因 
%行长度为边数,1表示选择此边,0表示不选此边 
gene=zeros(num,ee-1); 
 
%f0为计算适应度时需要用的一个参量 
f0=(n-1)*max(edges(:,1)); 
 
%对种群进行初始化 
for i=1:num 
    %n个点的图必有n-1条边连接,所以每个个体基因中应有n-1个1 
    temp=randperm(ee-1); 
    temp1=zeros(1,ee-1); 
    temp1(1,temp(1,1:n-1))=1; 
    gene(i,:)=temp1; 
     
    %对此解用gabfs进行宽搜,若不联通返回0,则继续构造直到满足要求 
    while gabfs(gene(i,:),edges,n)==0 
        temp=randperm(ee-1); 
    temp1=zeros(1,ee-1); 
    temp1(1,temp(1,1:n-1))=1; 
    gene(i,:)=temp1; 
    end 
 
    %用gafitness函数进行初始基因的适应度 
    fitness(i,1)=gafitness(temp1,edges,f0); 
end 
 
%循环maxstep代 
for i=1:maxstep 
    %队适应度值进行从大到小排序,并对个体顺序进行相应调整 
    [u,v]=sort(-fitness(:,1)); 
    gene=gene(v,:); 
    fitness=-u; 
     
    %记录每一时间步的最有最适应度值 
    bestfit(i)=fitness(1); 
     
    %计算保留个体数量 
    res=ceil(num*(1-eliminate)); 
    gene=gene(1:res,:); 
    fitness=fitness(1:res,:); 
     
    %对保留个体进行赌轮选择决定繁育 
    p=fitness./sum(fitness); 
    p=cumsum(p); 
     
    %利用gabirth函数繁育新个体 
    for j=res+1:num 
        tep=find(p>rand); 
        gene(j,:)=gabirth(gene(tep(1),:)); 
        %对新个体进行检验,直到其满足使图连通为止 
        while gabfs(gene(j,:),edges,n)==0 
            gene(j,:)=gabirth(gene(tep(1),:)); 
        end 
         
        %计算新个体的适应度 
        fitness(j,1)=gafitness(gene(j,:),edges,f0);             
    end 
end 
 
%将适性函数转换为最小生成树权值和 
minsumedges=f0-bestfit; 
 
%画出点的位置  
plot(position(:,1),position(:,2),'*'); 
hold on 
 
%因为已对基因做了排序,gene中第一个基因即为适应度最大的 
%画出选出的最小树中的边 
drawedges=edges(find(gene(1,:)==1),:); 
dd=size(drawedges,1); 
for i=1:dd 
plot([position(drawedges(i,2),1),position(drawedges(i,3),1)],[position(drawedges(i,2),2),position(drawedges(i,3),2)]); 
end  
title('最小生成树'); 
 
figure 
plot(minsumedges,'r'); 
tt=['每一代搜索到的最优最小生成树权值和' num2str(minsumedges(end))]; 
title(tt) 
xlabel('繁育代数') 
ylabel('最优最小生成树权值和')