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. 背包问题基础参数定义 a0.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; % 背包最大承重上限 num12; % 物品总数量 %% 2. 模拟退火算法初始化 sol_new ones(1,num); % 初始解默认全部物品装入背包 E_current inf ; % 当前解目标函数值 E_best inf; % 全局最优解目标函数值 sol_current sol_new; % 当前可行解 sol_best sol_new; % 全局最优解 t0 97; % 初始高温 tf3; % 终止最低温度 tt0; % 当前迭代温度 p1; %% 3. 模拟退火主循环 while ttf % 同一温度下迭代100次充分搜索邻域 for r1: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_newE_current E_current E_new; sol_current sol_new; if E_newE_best E_best E_new; sol_best sol_new; end else % 新解更差Metropolis准则概率性接受跳出局部最优 if randexp(-(E_new-E_current)./t) E_currentE_new; sol_current sol_new; else sol_new sol_current; % 拒绝新解保留原解 end end end % 温度指数衰减 tt.*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 初始温度越高越不容易早熟收敛​- 同温迭代次数次数越多当前温度下搜索越充分六、对比与总结算法优点缺点暴力枚举结果绝对全局最优物品数25就完全无法运行动态规划稳定精准大承重、多物品内存开销爆炸模拟退火算法收敛速度快、寻优能力强、适配大规模背包问题参数需要合理调试本次用模拟退火求解12维0-1背包快速精准找到了全局最优方案代码模块化、注释详尽可直接修改物品重量、价值、背包容量快速适配任意0-1背包场景也可以拓展到多维背包、有界背包等复杂变体。七、源码获取与使用直接复制上述完整 .m 代码新建MATLAB脚本运行即可如需扩展增加/减少物品修改、向量长度同步修改​修改背包承重修改数值​调整算法收敛速度修改、、参数博主寄语模拟退火算法不止可以求解背包问题车间调度、路径规划、TSP旅行商问题等组合优化场景都可以通用改造~觉得文章有用欢迎点赞收藏关注后续更新遗传算法、粒子群算法求解背包问题对比