基于遗传算法解决背包问题（Matlab代码实现）

       目录

💥1 概述

📚2 运行结果

🎉3 参考文献

👨‍💻4 Matlab代码

💥1 概述

通常情况下，我们必须在有限的预算内做出最佳选择，考虑在预算范围内购买杂货;打包行李旅行，同时低于行李重量限额;决定您将在小手提包中携带哪些物品;决定您将以有限的硬盘容量在计算机上保留哪些程序和文档;决定用可用的时间和精力学习哪些主题进行考试！

在商业和工业场景中，这种决策问题的例子也很多——制造工厂选择在有限的工作时间内生产什么;组建一个运动队阵容，为球员提供一些最大的预算;在受货舱最大重量和体积限制的情况下，向运输船舶填充最有利可图的内容物;销售人员将在营销预算有限的情况下访问哪些城镇。

这个谜题有一个数学名称——它被称为背包问题。之所以这么命名，是因为决策问题被想象为用最佳选择的物品填充背包（或背包、背包等）。然而，困难在于所选物品的总重量不得超过背包的最大重量容量（单一约束）。这个问题还可以扩展到两个约束 - 背包具有定义的最大承重能力和最大容积能力。添加的约束越多，找到问题的最佳解决方案就越困难。事实上，这个问题被认为是NP-Hard的找到完美解决方案所需的时间随着项目数量的增加呈指数级增长！

有时，将决策可视化很简单（杂货店购物：项目的货币成本与预算）或更抽象的（制造：花在工作上的小时数与工厂的总运行小时数）——请注意，选择可以是一组项目或一系列操作。如果任务是选择一组可能性中的一些，但不是全部，则可以以这种方式考虑任何决定。

这个问题的一个特殊变体称为0-1背包问题。在这种情况下，我们希望通过检查集合中的每个项目来最大化总利润，并决定是拿走还是离开该项目（但我们不能拿走每个项目中的一个以上）。我们还必须记住遵守以下约束：我们所选物品的总重量小于或等于我们的最大承重能力。

这些问题的约束可以通过容量比来定义——这是最大容量与所有可用项目总重量的比率。换句话说，容量比为 1 意味着您有空间容纳所有可用项目。容量比为 0.5 意味着您的背包只能容纳可用总重量的一半。容量比为 0.1 导致背包只能容纳可用物品重量的 10%。请注意，项目重量和值都不同 - 可用项目总重量的 10% 并不一定意味着可用项目总数的 10%。

📚2 运行结果

🎉3 参考文献

[1]贺毅朝,王熙照,李文斌,张新禄,陈嶷瑛.基于遗传算法求解折扣{0-1}背包问题的研究[J].计算机学报,2016,39(12):2614-2630.

👨‍💻4 Matlab代码

主函数部分代码：

% GA Parameters
gen_max = 150; % 150 Max generations
pop_size = 50; % Population size of 50
sel_no = 25; % Selection of 20 individuals for mating, each generation
mut_rate = 0.02; % Mutation rate 0<mut_rate<1 where 0.02 = 2%
elite_no = 0; % Not used yet
pen_mode = 0; % Not used yet
sel_mode = 0; % Not used yet
cap_rat = 0.65;

seed = 0; % Use your student number
[profit, weight] = genDataset(seed);

% weight_max = NaN;% Calculate weight_max, with total weight and capacity ratio...!
weight_max = cap_rat*sum(weight);% Calculate weight_max, with total weight and capacity ratio...!

% Imagine, examine, analyse - experiment...!
figure(1)
clf()
hold on
title("Plot for score analysis")
xlabel("Generations")
ylabel("Score")
% Run the GA
% Without validation
with_validation = 0;
[scores] = ga_A(gen_max, pop_size,...
    profit, weight, weight_max,...
    sel_no, mut_rate, with_validation);

plot(1:gen_max, scores, 'DisplayName', 'Best Scores(Without validate)')
% With validation
with_validation = 1;
[scores] = ga_A(gen_max, pop_size,...
    profit, weight, weight_max,...
    sel_no, mut_rate, with_validation);
plot(1:gen_max, scores, 'DisplayName', 'Best Scores(With validate)')
legend('location', 'southeast')
hold off
% ...and have fun :)