clc;
clear;
t1=600; % 控制参数t1的初值
L1=150; % 马尔可夫链的长度
p=0.9; % 衰减系数
tmin=0.00000001; % t的终止准则
a=[92, 4, 43, 83, 84, 68, 92, 82, 6, 44, 32, 18, 56, 83, 25, 96, 70, 48, 14, 58]; %物品体积
c=[44, 46, 90, 72, 91, 40, 75, 35, 8, 54, 78, 40, 77, 15, 61, 17, 75, 29, 75, 63];%物品价值
b=878; % 背包总体积
sw=size(a);
n=sw(1,2);
x1=zeros(1,n);% 产生初始解
L=L1*n; % 马尔可夫链的长度
f1=0; m=0;t=t1;
g1=1;
while(t>tmin)
g1=g1+1;
for k=1:1
i=round(rand*(n-1))+1;
if x1(i)==0
if m+a(i)<=b
x1(i)=1;
f1=f1+c(i);
m=m+a(i);
else
uu=0;
for u=1:n
if x1(u)==1;
uu=uu+1;
flag1(uu)=u;
end
end
sf=size(flag1);
j=round(rand*(sf(1,2)-1))+1;
j=flag1(j);
clear flag1;
df=c(i)-c(j);
dm=a(i)-a(j);
if m+dm<=b
if (df>0)
x1(i)=1;
x1(j)=0;
f1=f1+df;
m=m+dm;
else if (exp(df/t))>rand
x1(i)=1;
x1(j)=0;
f1=f1+df;
m=m+dm;
end
end
end
end
else
uu=0;
for u=1:n
if x1(u)==0;
uu=uu+1;
flag2(uu)=u;
end
end
sf=size(flag2);
j=round(rand*(sf(1,2)-1))+1;
j=flag2(j);
clear flag2;
df=c(j)-c(i);
dm=a(j)-a(i);
if m+dm<=b
if (df>0)
x1(i)=0;
x1(j)=1;
f1=f1+df;
m=m+dm ;
else if (exp(df/t))>rand
x1(i)=0;
x1(j)=1;
f1=f1+df;
m=m+dm;
end
end
end
end
end
t=t*p; %衰减函数
f_max(1)=0;
f_max(g1)=f1; %记录每一代最优解
end
g=size(f_max);
generation=g(1,2); %所需的进化代数
lx=1:1:generation;
plot(lx,f_max,'-bo','LineWidth',1,...
'MarkerFaceColor',[1,0,0],...
'MarkerSize',3.0)
title('模拟退火算法解决0-1背包问题的进化曲线');
xlabel('进化代数(Generation)');
ylabel('总价值(Value)');
grid on
f1
x1
评论0