sa_01.m

本程序是在MATLAB平台上面实现的用模拟退火算法解决01背包问题。

function [fval,route]=sa_01
clear;
disp('Welcome to my SA ');
X=[];Y=[];
num=input('please input the number: \nnum=');
weight=input('please input the weight: \nweight=');
X=input('please input the cost: \nthe example is [6 3 5 4 6]\n');
Y=input('please input the weight for each one: \nthe example is [2 2 6 5 4]\n');

t0=100;
tf=0.01;
alpha=0.87;
route=round(rand(1,num));
fval=value(route,X,Y,weight);
n=num;
L=100*n;
t=t0;
val=[];
tic;
while t>tf
    for i=1:L
        [fval_after,route_after]=exchange(route,X,Y,weight);
        if fval_after<fval
            route=route_after;
            fval=fval_after;
        elseif exp((fval-fval_after)/t)>rand
            route=route_after;
            fval=fval_after;
        else route=route;
            fval=fval;
        end
    end
    t=alpha*t;
    val=[val,1/fval];
end
fv=1/fval
plot(val);
route
toc


function fval=value(route,X,Y,weight)
weight_after=sum(route.*Y);
fval=0.1;
if weight_after<=weight
    fval=sum(route.*X);
else
    fval=fval;
end
fval=1/fval;


function [fval_after,route_after]=exchange(route,X,Y,weight)
n=length(route);
location1=ceil(n*rand);
location2=ceil(n*rand);
loc1=min(location1,location2);
loc2=max(location1,location2);
middle_route=fliplr(route(loc1:loc2));
route_after=[route(1:loc1-1) middle_route route(loc2+1:n)];
fval_after=value(route_after,X,Y,weight);