论文模拟退火算法.doc

1 引言
模拟退火算法的背景
模拟退火算法来源于对固体退火过程的模拟,将固体加热到足够高的温度,使分子成随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。根据Metropolis准则,粒子在温度T时趋于平衡的概率为,其中E为温度T是的内能,为内能的改变量,k为Boltzman常数,
用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,及可得到解组合优化问题的模拟退火算法:由初始解的控制参数初始值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t的值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括参数的初值t及衰减因子、每个t值时的迭代次数L和停止条件S。
背包问题的基本概念
背包问题(Knapsack Problem)是一个NP完全问题,在实际的工程中有着广泛的应用,目前求解背包问题的主要方法有模拟退火算法、贪婪算法、遗传算法等,还包括许多算法。
背包问题(Knapsack Problem)是指假定某人拥有大量的物品,重量各不相同,此人通过秘密的选择一部分物品并将它们放到背包中来加密消息,例如给定种物品和1个背包,知道某物品的重量和价值,并且背包的最大容量也是已知的,要求选择物品装入背包中,是选中的物品的总重量不超过背包的最大容量,但装入背包的物品的总价值最大。它是一种典型的组合优化问题,已证明背包问题是一个NP-hard问题,基于智能优化算法求解背包问题,是近年来刚刚兴起的热门问题。在我们的现实生活中存在着大量的多目标优化问题,对于背包问题(Knapsack Problem):在实际中经常要同时考虑多个目标,如价值最大、容量最大等多方面的因素。目标之间往往出现冲突性。这就需要我们如何在多个目标中寻找一个合理的解去解决一个比较复杂的问题。
发展趋势
背包问题在国外研究得比较早,范围也比较广,Dantzing在20世纪50年代第一个进行了开放性研究,利用贪婪算法求得了背包问题最优解的上界。
1974年,horowitz和salmi利用分支界限法解答背包问题,并提出了背包问题的可分性,指出了求解该问题的一条新途径。接着,balas和zemel提出了背包问题的“核”思想,是背包问题的研究有了较大的进展。
十九世纪九十年代以后,随着生物仿生技术和网络技术的飞速发展,各种模拟生物物理规律的并行近似算法不断涌现,就如遗传算法已经在背包问题上得到较好的应用,而蚁群算法等仿生算法也在组合优化问题上得到了不错的应用。
背包问题(Knapsack Problem)是运筹学中的一个经典组合优化问题,也是数学与计算机学界公认的一个NP问题。同时,背包问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解背包问题的主要方法有模拟退火算法、递归法、动态规划法、分支定界法、等指数级方法。
对于用模拟退火算法对求解背包组合优化问题来做在满足模拟退火算法全局收敛性的情况下,对求解NP完全问题是非常有效的。
在实际生活中,很多问题经过简化处理后均可转化为背包问题,对背包问题求解方法的研究具有重要的应用价值。人们在努力寻找大维数最