saa394.m

用matlab语言编写模拟退火算法

% 作者ID：lxwpp
% MATLAB源码
% 使用模拟退火算法（SAA)解决0－1背包问题
% 林培科技制作完成 2004.10.26
% 同济大学CS系模式识别
% w为物品的重量，c为物品的价值，M为背包的容量



clear;
tic

w=round(rand(1,1000)*100)+1;
c=round(rand(1,1000)*100)+1;



n=size(w,2);
x=zeros(1,n); %初始解

f=0;

M=0;
for i=1:n
M=M+w(i);
end;
M=round(M*0.8);
m=0;
L=10*n; % Mapkob 链长
for i=1:n
f=f+c(i)*x(i);
m=m+w(i)*x(i);
end

t0=500; % 控制参数t的初值
t=t0;
tf=0.95; %

e=0.00001;
%程序运行的初始,此处是为了计算程序运行的时间和程序结尾的toc对应



while t>e



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);m=m+w(i);
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;
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;
end
end
end
end
t=t*tf; %衰减函数

f_max=f;
end

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