模拟退火算法解决0-1背包问题的实现
模拟退火算法解决0-1背包问题的实现
2 模拟退火算法介绍
模拟退火算法起源于固体退火原理，在这一过程中，固体首先被加热至充分高的温度，并随后以缓慢的速度冷却下来。在加热阶段，固体内部的微粒由于温度升高而呈现无序状态，在此过程中系统的内能也随之增大；而在冷却阶段，则逐渐向有序状态发展并最终达到基态，在此过程中系统的内能减至最小值。将此固体退火过程与组合优化问题相结合时，则可将内能E对应为目标函数值f，并将温度T转化为控制参数t从而形成模拟退火算法：从初始解i出发并设定初始控制参数t值后，在每一步迭代中都会执行"产生新解→计算目标函数差→决定接受或舍弃"的操作，并随着时间推移逐渐衰减t值直至终止条件满足为止。最终所得的近似最优解即为模拟退火算法所求得的结果，并基于蒙特卡罗迭代法实现的一种启发式随机搜索过程。
模拟退火算法可以分解为解空间、目标函数和初始解3部分。其基本思想是：
初始化阶段：首先设定一个充分大的初始温度T作为全局优化问题求解的基本参数；接着确定算法迭代的起始状态s作为优化过程中的关键变量；然后设定Markov链长度L作为每个温度值T对应的迭代次数；在此基础上采用指数衰减策略来确定降温因子α；最后根据预设条件终止优化过程并输出结果。
(2)对k=1，……，L做第(3)至第(6)步；
(3)产生新解s′；
(4)计算增量cost=cost(s′)-cost(s)，其中cost(s)为评价函数；
(5)若t′＜0则接受s′作为新的当前解，否则以概率exp(-t′/T)接受s′作为新的当前解；
如果达到终止条件时，则将当前解视为全局最优解并输出；然后退出程序流程。否则系统参数T逐步减小，并转而执行第二步运算。
3 思路分析
SA解决01背包问题 knapsackSa.cpp代码下载：
**
**
**
**