fc0.m

完全图哈密尔顿圈的遗传模拟退火算法matlab通用源程序

%完全图哈密尔顿圈的遗传模拟退火算法matlab通用源程序 
%2007-10-27 10:31:14 
  
% maxpop 给定群体规模
% pop 群体
% newpop 种群
%t0 初始温度
function [codmin,finmin]=fc0(cc,v0,t0)
N=length(cc(1,:));
%定群体规模
if N>50
    maxpop=2*N-20;
end
if N<=40
    maxpop=2*N;
end
%产生初始群体
pop=zeros(maxpop,N);
pop(:,1)=v0;
finmin=inf;
codmin=0;
for i=1:maxpop
    Ra=randperm(N);
    Ra(find(Ra==v0))=Ra(1);
    Ra(1)=v0;
    pop(i,:)=Ra;
end
t=t0;
while t>0
    %用模拟退火产生新的群体 
    pop=fc1(maxpop,pop,N,cc,v0,t);
    %转轮赌选择种群 
    f=zeros(1,maxpop);
    for i=1:maxpop
        for j=1:N-1
            x=pop(i,j);
            y=pop(i,j+1);
            fo1=cc(pop(i,j),pop(i,j+1));
            f(i)=f(i)+fo1;
        end
        f(i)=f(i)+cc(pop(i,1),pop(i,N));
    end
    fmin=min(f);
    for i=1:maxpop
        if fmin==inf&f(i)==inf
            dd=inf;
        end
        if fmin~=inf|f(i)~=inf
        dd=fmin-f(i);
        end
        ftk(i)=exp(dd/t);
    end
    [fin1,cod]=sort(-ftk);
    fin=abs(fin1);
    %f(cod(1))
    if f(cod(1))<finmin %记录当代最优解
        finmin=f(cod(1));
        codmin=pop(cod(1),:);
    end
    for i=1:maxpop
        RR=rand(1);
        cod2=find(fin>=RR);
        % cod
        newpop(i,:)=pop(cod(cod2(end)),:);
    end
    %单亲繁殖
    if N>32
        jmax=round(N/9);
    end
    if N<=32
        jmax=2;
    end
    if mod(jmax,2)
        jmax=jmax-1;
    end
    for i=1:maxpop
        for j=1:2:jmax
            nn=randperm(N);
            x=nn(j);
            y=nn(j+1);
            if newpop(i,x)==v0|newpop(i,y)==v0
            continue;
            end
            box1=newpop(i,x);
            newpop(i,x)=newpop(i,y);
            newpop(i,y)=box1;
        end 
    end
    %变异 Pc 
    Pc=0.02; 
    for i=1:maxpop
        R1=rand(1);
        if Pc>R1
            for j=1:2:jmax+2
                nn=randperm(N);
                x=nn(j);
                y=nn(j+1);
                if newpop(i,x)==v0|newpop(i,y)==v0
                    pop(i,:)=newpop(i,:);
                    continue;
                end
                box1=newpop(i,x);
                newpop(i,x)=newpop(i,y);
                newpop(i,y)=box1;
                pop(i,:)=newpop(i,:); 
            end
        end
    end
    %温度下降
    t=t-0.1;
end
%子程序：用模拟退火产生新的群体 
function pop=fc1(maxpop,pop,N,cc,v0,t) 
ff(N-1)=0;
f=0;
pop1=zeros(maxpop,N);
for i=1:maxpop
    for j=1:N-1
        x=pop(i,j);
        y=pop(i,j+1);
        ff(j)=cc(pop(i,j),pop(i,j+1));
        pop1(i,:)=pop(i,:);
        nn=randperm(N);
        x=nn(1);
        y=nn(2);
        pop1=pop;
        if pop(i,x)==v0|pop(i,x)==v0
            continue
            box1=pop(i,x);
            pop1(i,x)=pop1(i,y);
            pop1(i,y)=box1;
        end
        ff1(j)=cc(pop1(i,j),pop1(i,j+1));
     end
    f=sum(ff);
    f1=sum(ff1);
    if f==inf&f1==inf
        dd=inf;
    end
    if f~=inf|f1~=inf
        dd=f-f1;
    end
 
    Aij=min(1,exp(dd/t));
    Pacept=rand(1);
    if Aij>Pacept
        pop(i,:)=pop1(i,:);
    end
end