MATLAB模拟退火算法求解0-1背包问题

一、问题背景

0-1背包问题是组合优化领域的经典NP难问题：
给定 num 个物品，每个物品有重量和价值，背包有最大承重限制，要求选出若干物品装入背包，在总重量不超过承重上限的前提下，物品总价值最大化。

传统暴力枚举、动态规划在物品数量变多时效率急剧下降，而模拟退火算法（Simulated Annealing, SA） 作为启发式智能算法，能够高效跳出局部最优，逼近全局最优解，非常适合求解背包这类离散优化问题。



二、算法原理

模拟退火算法灵感来源于金属退火物理过程：

1. 高温阶段：温度t很高，算法以较大概率接受较差解，大范围搜索解空间，避免陷入局部最优
​
2. 降温迭代：温度按照衰减系数 a 缓慢降低
​
3. 低温收敛：温度趋近最低，算法只接受更优解，最终收敛到全局近似最优解

核心流程：

1. 初始化初始解、初始温度、降温系数
​
2. 邻域扰动生成新解
​
3. 约束校验（背包重量不能超限）
​
4. Metropolis准则判断是否接受新解
​
5. 降温迭代，直到温度降到终止温度
​
6. 输出最优装载方案、最大价值、总重量



三、MATLAB完整实现代码

clear clc %% 1. 背包问题基础参数定义 a=0.95; % 温度衰减系数（降温速率） % 12个物品的价值向量（取负，把最大值问题转为最小值问题求解） k=[5;10;13;4;3;11;13;10;8;16;7;4]; k=-k; % 12个物品的重量向量 d=[2;5;18;3;2;5;10;4;11;7;14;6]; restriction =46; % 背包最大承重上限 num=12; % 物品总数量 %% 2. 模拟退火算法初始化 sol_new = ones(1,num); % 初始解：默认全部物品装入背包 E_current = inf ; % 当前解目标函数值 E_best = inf; % 全局最优解目标函数值 sol_current =sol_new; % 当前可行解 sol_best = sol_new; % 全局最优解 t0 =97; % 初始高温 tf=3; % 终止最低温度 t=t0; % 当前迭代温度 p=1; %% 3. 模拟退火主循环 while t>=tf % 同一温度下迭代100次，充分搜索邻域 for r=1:100 % 随机选中一个物品，翻转选择状态（0变1/1变0），生成邻域新解 tmp =ceil(rand.*num); sol_new(1,tmp) = ~sol_new(1,tmp); % 约束校验：保证背包总重量不超过承重上限 while 1 q=(sol_new*d <= restriction); if ~q % 总重量超限，需要移除物品减重 p=~p; tmp = find(sol_new == 1) ; % 找出所有已选中的物品 if p sol_new(1,tmp)=0; % 奇数步移除选中的所有物品 else sol_new(1,tmp(end)) = 0;% 偶数步移除选中的最后一个物品 end else break % 重量合规，退出校验循环 end end % 计算新解的目标函数值（转化后的最小化价值） E_new= sol_new*k; % 新解更优：直接无条件接受，更新最优记录 if E_new<E_current E_current =E_new; sol_current = sol_new; if E_new<E_best E_best = E_new; sol_best = sol_new; end else % 新解更差：Metropolis准则，概率性接受，跳出局部最优 if rand<exp(-(E_new-E_current)./t) E_current=E_new; sol_current =sol_new; else sol_new = sol_current; % 拒绝新解，保留原解 end end end % 温度指数衰减 t=t.*a; end %% 4. 结果输出 disp('最优物品选择方案(1=选取,0=不选取):') sol_best disp('物品最大总价值:') val = -E_best; disp(val) disp('背包最优方案总重量:') disp(sol_best*d)

四、运行结果展示

运行MATLAB代码，命令行窗口输出：

1. 最优解向量： 1 1 0 0 1 1 1 1 1 1 0 0
​
1代表对应下标物品装入背包，0代表不装入
​
2. 物品最大总价值： 76
​
3. 背包总承重： 46 （刚好填满背包承重上限）

完美实现：在背包承重46的限制下，拿到了12件物品组合的最大总价值

五、关键细节与算法优化说明

1. 问题转化：把价值最大化转为目标函数最小化（价值取负数），更契合模拟退火的求解逻辑
​
2. 重量约束处理：新解一旦超重，自动贪心移除选中物品，保证每一步解都合法
​
3. Metropolis准则：温度越高，接受差解概率越大，全局寻优能力更强
​
4. 参数调优参考
​
降温系数 a ：一般取0.85~0.99，越大降温越慢、结果精度越高、耗时越长
​
初始温度 t0 ：初始温度越高，越不容易早熟收敛
​
- 同温迭代次数：次数越多，当前温度下搜索越充分



六、对比与总结

本次用模拟退火求解12维0-1背包，快速精准找到了全局最优方案，代码模块化、注释详尽，可直接修改物品重量、价值、背包容量，快速适配任意0-1背包场景，也可以拓展到多维背包、有界背包等复杂变体。



七、源码获取与使用

直接复制上述完整 .m 代码，新建MATLAB脚本运行即可；
如需扩展：

增加/减少物品：修改、向量长度，同步修改
​
修改背包承重：修改数值
​
调整算法收敛速度：修改、、参数



博主寄语：
模拟退火算法不止可以求解背包问题，车间调度、路径规划、TSP旅行商问题等组合优化场景都可以通用改造~觉得文章有用，欢迎点赞+收藏+关注，后续更新遗传算法、粒子群算法求解背包问题对比！