论文模拟退火算法Word格式文档下载.docx
《论文模拟退火算法Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《论文模拟退火算法Word格式文档下载.docx（11页珍藏版）》请在冰点文库上搜索。
在我们的现实生活中存在着大量的多目标优化问题，对于背包问题（KnapsackProblem）：
在实际中经常要同时考虑多个目标，如价值最大、容量最大等多方面的因素。
目标之间往往出现冲突性。
这就需要我们如何在多个目标中寻找一个合理的解去解决一个比较复杂的问题。
1.3发展趋势
背包问题在国外研究得比较早，范围也比较广,Dantzing在20世纪50年代第一个进行了开放性研究，利用贪婪算法求得了背包问题最优解的上界。
1974年，horowitz和salmi利用分支界限法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。
接着，balas和zemel提出了背包问题的“核”思想，是背包问题的研究有了较大的进展。
十九世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，就如遗传算法已经在背包问题上得到较好的应用，而蚁群算法等仿生算法也在组合优化问题上得到了不错的应用。
背包问题（KnapsackProblem）是运筹学中的一个经典组合优化问题，也是数学与计算机学界公认的一个NP问题。
同时，背包问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。
目前
求解背包问题的主要方法有模拟退火算法、递归法、动态规划法、分支定界法、等指数级方法。
对于用模拟退火算法对求解背包组合优化问题来做在满足模拟退火算法全局收敛性的情况下，对求解NP完全问题是非常有效的。
在实际生活中，很多问题经过简化处理后均可转化为背包问题，对背包问题求解方法的研究具有重要的应用价值。
人们在努力寻找大维数最优化算法的同时，构造出了许多近似求解法，如遗传算法、贪婪法、粒子群算法、蚁群算法等，特别是提出了如模拟退火等用统计方法近似求解背包问题的随机算法，为人们求解背包问题开辟了新的途径。
2理论基础
2.1模拟退火算法基本原理
模拟退火（simulatedannealing,SA）算法的思想最早是由Metropolis等提出的，其出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性，模拟退火算法是一种通用的优化算法，其物理退火过程主要由加温过程、等温过程、冷却过程这三部分组成，其中，加温过程对应算法的设定初温，等温过程对应算法的Metropolis抽样过程，冷却过程对应控制参数的下降。
这里能量的变化就是目标函数，要得到的最优解就是能量最低态，Metropolis准则是SA算法收敛于全局最优解的关键，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的情况。
模拟退火算法可以用以求接不同的非线性问题，对不可微且不连续的函数优化，能以较大概率球的全局优化解，该算法具有较强的全局收敛性、隐含并行性及广泛的适应性，并且能处理不同类型的优化设计变量，他不需要任何的辅助信息，对目标函数和约束函数没有任何的要求，用Metropolis算法并适当地控制温度下降的过程，在优化问题中竞争力较强，本文研究的是基于模拟退火算法的背包问题算法。
模拟退火算法可以分解为解空间、目标函数和初始解三部分。
2.1.1模拟退火的基本思想
模拟退火是一种通用的概率算法，主要用于在一个大的空间内寻找命题的最优解。
模拟退火的原理与金属退货的原来相近，都是将热力学的理论套用到统计学上，将搜寻空间内的没一点，把它想象成空气内的分子，分子的能量，就是它本身的动能；
而搜寻到的没一点，也像空气分子一样带有能量，以表示对该点的合理程度。
我们先以搜寻空间内一个任意点作为算法的起始点，每一步先选择一个相邻点，然后在计算从现有位置到达相邻点的概率。
（1）初始解：
取初始温度
足够大，令
，任取初始解
，确定每个
时的迭代次数，即Metropolis链长
（2）对当前温度
和
，重复步骤（3）～（6）.
（3）对当前解
随机扰动产生一个新解
。
（4）计算
的增量
其中
是
代价函数。
（5）若
，则接受
作为当前的解，即
；
否则计算
的接受概率
，即随机产生（0,1）区间上均匀分布
若
，也接受
作为新的当前解，
否则保留当前解
（6）如果满足终止条件则输出当前作为最优解，结束程序。
终止条件通常取为连续若干个新解都没有接受时终止算法。
（7）
逐渐减少，且
，然后转第2步。
2.1.2模拟退火算法的步骤
第一部是由一个产生函数从当前解产生一个位于解空间的新解；
为便于后续的计算和接受，减少算法好时，通常选择有当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的领域结构，因而对冷却进度表的选取有一定的影响。
第二步是计算与新解所对应的目标函数差。
因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。
事实表明，对大多数而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是Metropolis准则：
若
则接受
作为新的当前解
，否则以概率
接受
第四步是当新解被确定接受时，用心接代替当前解，这只需将当前解中对应于产生新解时的变换部分得以实现，同时修正目标函数即可。
此时，当前解实现了一次迭代。
可在此基础上开始下一轮实验。
而当前解被判定为舍弃时，则在原当前解的基础上继续下一轮实验。
模拟图火算法与初始值无关，算法求得的解与初始解状态
（是算法迭代的起点）无关；
模拟退火算法具有渐进收敛性，已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法；
模拟退火算法具有并行性。
2.2背包问题的描述
背包问题（KnapsackProblem）是经典的NP完全问题，即假设有m种物品，每种物品都有一个重量用
（
）表示，一个价值用
）（
）,同时有一个背包，其容量为
先从m种物品中选取若干件，使其重量之和小于等于背包的容量，且价值和为最大，其中要求
都是整数，定义
为变量：
即问题的模型可以表示如下：
max
其中
3模型求解
模拟退火算法是基于MenteCarlo迭代求解策略的一种机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解中能概率出并最终趋于全局最优。
3.1模拟退火算法的求解步骤
（1）随机给定初始状态
，选择合适的退火策略，给定足够高的初始温度；
（2）产生新解在
的邻域选取
，并计算
，
为目标函数；
（3）如果
或
为新的状态，否则以概率
接受；
（4）重复2、3步，直至系统达到平衡状态；
（5）缓慢降低温度
，重复2～5步，知道收敛条件满足为止。
3.2改进前的模拟退火算法
（1）解空间
初始解一般为
（2）目标函数
最大价值的目标函数为：
max
（3）新解的产生
随机选取物品，若
不在背包中，则将其直接放入背包中，或者从包中随机随机取出另一物品
，若
已在背包中，则将其取出，并随机装入另一物品
（4）背包的价值差和重量差
根据新解产生的三种可能，相应的背包价值差为：
相应的背包重量为：
其中
为当前状态下背包重量
（5）接受准则
由于背包问题是有约束的最优化问题，所以本文采用的是扩充Metropolis准则即：
其中
为温度的控制参数
4数值实验
运用模拟退火算法求解背包问题的有效性，本文在Matlab环境下选择了一组数据进行试验，数据用标准模拟退火算法，如下：
设有20种物品和一个背包，即把背包的最大承重量为618，其中各种物品的重量分别为
=（5538115363849414949162738834448218773183）,各物品的价值分别为
=（108843391726715666532575862484391951）,求解怎样把物品装入包里，使得价值量最大且承重量最大。
4.1模型求解
常数a=0.95,结合以上的数据和matalb软件求解装入背包中的物品的最大价值量和最大的承重量，程序在附录中，程序运行后得到的最优解为：
=11111111111111110111，最优值
=1171，则背包中物品重量为
=617，从而得出来的解中可知装入背包中的物品第十六种没有被取到。
5模型的评价与推广
模型的优点：
（1）计算简单，通用；
（2）鲁棒性强，适于并行出理；
（3）可用于求解复杂的非线性优化问题，便于编程。
缺点:
（1）收敛速度慢，执行时间长；
（2）算法性能初始值有关及参数敏感等缺点；
因为有着这些缺点，则可以对它进行改进，是收敛速度较快，有效性较强，及背包问题也可以用其它的算法进行计算，而模拟退火算法也可推广到求解TSP等问题。
6参考文献
[1]梁国宏，张生，黄辉，何尚录.一种改进的模拟退火算法求解背包问题，1～3,2007.8.
[2]许小勇，基于改进模拟退火算法求解背包问题，1～2,2008.12.
[3]史峰，王辉，郁磊，胡斐，智能算法，北京航空航天大学出版社，2011.7.
[4]刘洋.求解背包问题的混合遗传算法[J].华侨大学学报：
自然科学版，2003.23.
[5]曾国清.背包问题的遗传算法[J].高校理科研究，2006.3
资料仅供参考!
!
升级会员 