论文模拟退火算法.doc

1 引言1.1 模拟退火算法的背景模拟退火算法来源于对固体退火过程的模拟，将固体加热到足够高的温度，使分子成随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。根据Metropolis准则,粒子在温度T时趋于平衡的概率为，其中E为温度T是的内能，为内能的改变量，k为Boltzman常数，用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，及可得到解组合优化问题的模拟退火算法：由初始解的控制参数初始值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t的值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表（Cooling Schedule）控制，包括参数的初值t及衰减因子、每个t值时的迭代次数L和停止条件S。1.2 背包问题的基本概念背包问题（Knapsack Problem）是一个NP完全问题，在实际的工程中有着广泛的应用，目前求解背包问题的主要方法有模拟退火算法、贪婪算法、遗传算法等，还包括许多算法。背包问题（Knapsack Problem）是指假定某人拥有大量的物品，重量各不相同，此人通过秘密的选择一部分物品并将它们放到背包中来加密消息，例如给定种物品和1个背包，知道某物品的重量和价值，并且背包的最大容量也是已知的，要求选择物品装入背包中，是选中的物品的总重量不超过背包的最大容量，但装入背包的物品的总价值最大。它是一种典型的组合优化问题，已证明背包问题是一个NP-hard问题，基于智能优化算法求解背包问题，是近年来刚刚兴起的热门问题。在我们的现实生活中存在着大量的多目标优化问题，对于背包问题（Knapsack Problem）：在实际中经常要同时考虑多个目标，如价值最大、容量最大等多方面的因素。目标之间往往出现冲突性。这就需要我们如何在多个目标中寻找一个合理的解去解决一个比较复杂的问题。1.3 发展趋势背包问题在国外研究得比较早，范围也比较广,Dantzing在20世纪50年代第一个进行了开放性研究，利用贪婪算法求得了背包问题最优解的上界。1974年，horowitz和salmi利用分支界限法解答背包问题，并提出了背包问题的可分性，指出了求解该问题的一条新途径。接着，balas和zemel提出了背包问题的“核”思想，是背包问题的研究有了较大的进展。十九世纪九十年代以后，随着生物仿生技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，就如遗传算法已经在背包问题上得到较好的应用，而蚁群算法等仿生算法也在组合优化问题上得到了不错的应用。背包问题（Knapsack Problem）是运筹学中的一个经典组合优化问题，也是数学与计算机学界公认的一个NP问题。同时，背包问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解背包问题的主要方法有模拟退火算法、递归法、动态规划法、分支定界法、等指数级方法。对于用模拟退火算法对求解背包组合优化问题来做在满足模拟退火算法全局收敛性的情况下，对求解NP完全问题是非常有效的。在实际生活中，很多问题经过简化处理后均可转化为背包问题，对背包问题求解方法的研究具有重要的应用价值。人们在努力寻找大维数最优化算法的同时，构造出了许多近似求解法，如遗传算法、贪婪法、粒子群算法、蚁群算法等，特别是提出了如模拟退火等用统计方法近似求解背包问题的随机算法，为人们求解背包问题开辟了新的途径。2 理论基础2.1 模拟退火算法基本原理模拟退火（simulated annealing,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 背包问题的描述背包问题(Knapsack Problem)是经典的NP完全问题，即假设有m种物品，每种物品都有一个重量用()表示，一个价值用() (),同时有一个背包，其容量为。先从m种物品中选取若干件，使其重量之和小于等于背包的容量，且价值和为最大，其中要求和都是整数，定义为变量： 即问题的模型可以表示如下： max 其中 3 模型求解 模拟退火算法是基于Mente Carlo迭代求解策略的一种机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解中能概率出并最终趋于全局最优。3.1 模拟退火算法的求解步骤 (1)随机给定初始状态，选择合适的退火策略，给定足够高的初始温度； (2)产生新解在的邻域选取，并计算，为目标函数； (3)如果或则接受为新的状态，否则以概率接受； (4)重复2、3步，直至系统达到平衡状态； (5)缓慢降低温度，重复25步，知道收敛条件满足为止。3.2 改进前的模拟退火算法(1)解空间 初始解一般为(2)目标函数 最大价值的目标函数为： max (3)新解的产生随机选取物品，若不在背包中，则将其直接放入背包中，或者从包中随机随机取出另一物品，若已在背包中，则将其取出，并随机装入另一物品；(4)背包的价值差和重量差 根据新解产生的三种可能，相应的背包价值差为： 相应的背包重量为： 其中为当前状态下背包重量的增量 (5)接受准则 由于背包问题是有约束的最优化问题，所以本文采用的是扩充Metropolis准则即： 其中为温度的控制参数4 数值实验运用模拟退火算法求解背包问题的有效性，本文在Matlab环境下选择了一组数据进行试验，数据用标准模拟退火算法，如下：设有20种物品和一个背包，即把背包的最大承重量为618，其中各种物品的重量分别为=(55 38 11 53 63 84 94 14 94 91 62 73 88 34 44 82 18 77 31 83),各物品的价值分别为=(10 8 8 43 39 17 26 7 15 66 65 32 57 5 86 24 84 39 19 51),求解怎样把物品装入包里，使得价值量最大且承重量最大。4.1模型求解常数a=0.95,结合以上的数据和matalb软件求解装入背包中的物品的最大价值量和最大的承重量，程序在附录中，程序运行后得到的最优解为：=1111 1111 1111 1111 0111，最优值=1171，则背包中物品重量为=617，从而得出来的解中可知装入背包中的物品第十六种没有被取到。5 模型的评价与推广 模型的优点：(1)计算简单，通用；(2)鲁棒性强，适于并行出理；(3)可用于求解复杂的非线性优化问题，便于编程。 缺点:(1)收敛速度慢，执行时间长；(2)算法性能初始值有关及参数敏感等缺点；因为有着这些缺点，则可以对它进行改进，是收敛速度较快，有效性较强，及背包问题也可以用其它的算法进