禁忌搜索法

采用禁忌搜索算法实现的背包问题

clc
k=[5;10;13;4;3;11;13;10;8;16;7;4]; 
d=[2;5;18;3;2;5;18;5;11;7;14;3]; 
restriction = 46;
num = 12;% Initialize taboo list
taboo_list = zeros(10, num);
taboo_age = 1;% Initialize current and best solutions
sol_current = randi([0 1], 1, num);
while sol_current * d > restriction sol_current = randi([0 1], 1, num);
end
E_current = -sol_current * k;
sol_best = sol_current;
E_best = E_current;% Set stopping criterion
max_iterations = 50;
iteration = 1;
t0 = 97;
tf = 3;
a = 0.95;% Main loop
while iteration <= max_iterations && E_best > -sum(k)% Generate a set of candidate solutionscandidate_solutions = zeros(100, num);for i = 1:100candidate_solutions(i,:) = sol_current; % Randomly flip some variablesidx = randperm(num, ceil(num/10)); candidate_solutions(i,idx) = ~candidate_solutions(i,idx); enddisp(['Iteration: ' num2str(iteration)]);disp(['Best solution: ' num2str(sol_best)]);% Check feasibilityfor i = 1:100while candidate_solutions(i,:) * d > restrictionidx = randperm(num, ceil(num/10)); candidate_solutions(i,idx) = ~candidate_solutions(i,idx);end% Evaluate candidate solutionsE_candidate = -candidate_solutions(i,:) * k;% Update current and best solutionsif E_candidate < E_current && ~any(all(candidate_solutions(i,:) == taboo_list, 2))E_current = E_candidate;sol_current = candidate_solutions(i,:);if E_candidate < E_best E_best = E_candidate;sol_best = candidate_solutions(i,:);endelsetaboo_list(taboo_age,:) = sol_current;taboo_age = mod(taboo_age, size(taboo_list,1)) + 1;endenddisp(['Iteration: ' num2str(iteration)]);disp(['Best solution: ' num2str(sol_best)]);disp(['Current solution: ' num2str(-sol_current * k)]);% Update iteration counter and temperatureiteration = iteration + 1;t = t0 * (tf/t0)^(iteration/max_iterations);% 
end
disp('最优解为:')
sol_best
disp('物品总价值等于:')
val=-E_best;
disp(val)
disp('背包中物品重量是')
disp(sol_best * d)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！