saa 0－1背包问题 .m

模拟退火matlab源码

%  使用模拟退火算法（SAA）解决0－1背包问题 


clear; 
w=[6 5 3 2 1 1];            %物品重量 
c=[61 59 31 21 15 5];       %物品价值 

M=10;                       % 背包总容量 

x=[0 0 0 0 0 0];            % 初始解 
[mm,n]=size(x); 
f=0; 
m=0; 
L=10*n;                     % Mapkob 链长 
for i=1:n 
    f=f+c(i)*x(i); 
    m=m+w(i)*x(i); 
end 

t0=200;                     % 控制参数t的初值       
t=t0; 
tf=0.9;                     %  
s0=0; 
s1=1; 
tic                         % 程序运行的初始,此处是为了计算程序运行的时间和程序结尾的toc对应 
   

while s0~=s1                %   产生新解 
  
   
flag=0; 
    for k=1:L 
        i=round(rand*(n-1))+1; 
        if x(i)==0 
            if m+w(i)<=M 
                x(i)=1;f=f+c(i);flag=1; 
            else 
                j=round(rand*(n-1))+1; 
                while x(j)==0 
                    j=round(rand*(n-1))+1; 
                end 
                df=c(i)-c(j);dm=w(i)-w(j); 
                if m+dm<=M                               % 接受准则 
                    if (df>0)|(exp(df/t)>rand) 
                    x(i)=1;x(j)=0;f=f+df;m=m+dm;flag=1; 
                    end 
                end 
            end 
        else 
            j=round(rand*(n-1))+1; 
            while x(j)==1 
                j=round(rand*(n-1))+1; 
            end 
            df=c(j)-c(i);dm=w(j)-w(i); 
            if m+dm<=M  
                 if (df>0)|(exp(df/t)>rand) 
                x(i)=0;x(j)=1;f=f+df;m=m+dm;flag=1; 
                 end 
            end 
        end 
    end 
    t=t*tf;                                               %衰减函数 
    if flag==0 
        s0=s0+1; 
    else 
        s0=0; 
    end 
 f_max=f; 
end 

f_max 
toc                        %程序运行的结尾，得出运行的时间