模拟退火旅行商问题 matlab 博客,Matlab学习系列36模拟退火算法.docx

深藏阁楼爱情的钟 2023-01-14 15:57 125阅读 0赞

36. 模拟退火算法一、算法原理1. 爬山算法介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。2. 模拟退火算法爬山法是完完全全的贪心法，每次都鼠目寸光地选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图1为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最大值A。　关于爬山算法与模拟退火，有一个有趣的比喻：　　爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。　　模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。模拟退火算法是一种随机算法，并不一定能找到全局的最优解，可以比较快的找到问题的近似最优解。如果参数设置得当，模拟退火算法搜索效率比穷举法要高。3. 模拟退火算法描述记表示状态下的目标函数值。若，即移动后得到更优解，则总是接受该移动若，即移动后的解比当前解要差，则以一定的概率接受移动，而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定。　　这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。　　根据热力学的原理，在温度为T时，出现能量差为的降温的概率为，表示为：其中k为一个常数，且。该公式说白了就是：温度越高，出现一次能量差为的降温的概率就越大；温度越低，则出现降温的概率就越小。又由于总是小于0(否则就不叫退火了)，因此，所以的函数取值范围是(0,1) 。　　随着温度T的降低，会逐渐降低。　　我们将一次向较差解的移动看做一次温度跳变过程，我们以概率来接受这样的移动。Metropolis提出的模拟退火数学模型：假设材料处于状态时的能量为，材料在温度T下从状态转化到的概率为：其中，为玻尔兹曼常数，该式表明：若，则以概率1接受状态的转变；否则，以概率接受状态的转变。可以证明，当温度降至很低时，温度下降十分缓慢，使得这每个温度都有足够多次的状态转移，使之在每一个温度下达到热平衡，则全局最优解将以概率1被找到。因此，模拟退火算法所得解依概率收敛到全局最优解。二、算法步骤(1)令，即开始退火的初始温度，随机生成一个初始解，并计算目标函数值；(2) 令等于冷却进度表中的下一个值；(3) 根据当前解随机生成邻解(新解)，计算相应的目标函数值，得到；(4) 根据Metropolis准则判断新解是否被接受：若，则新解被接受，作为新的当前解；若，则新解按概率被接受，其中为当前温度；(5) 在温度下，重复执行步骤(3)和(4)；(6) 判断是否已达到，若是，则终止算法；否则转到步骤(2)继续执行。注1. 初始解的生成：通常是以一个随机解作为初始解，并保证理论上能够生成解空间中任意的解。也可以是一个经挑选过的较好的解，这种情况下，初始温度应当设置的较低；初始解不宜“太好”，否则很难从这个解的邻域跳出。注2. 邻解生成函数：邻解生成函数应尽可能保证产生的侯选解能够遍布解空间。邻域应尽可能的小：能够在少量循环步中充分探测，但每次的改变不应该引起太大的变化。注3. 初始温度如何确定?初始温度应该设置的尽可能的高，以确保最终解不受初始解影响，但过高又会增加计算时间。均匀抽样一组状态，以各状态目标值的方差为初温。如果能确定邻解间目标函数(COST函数)的最大差值，就可以确定出初始温度T0，以使初始接受概率足够大。可由随机产生一组状态的最大目标值差来替代。在正式开始退火算法前，可进行一个升温过程确定初始温度：逐渐增加温度，直到所有的尝试尝试运动都被接受，将此时的温度设置为初始温度。由经验给出，或通过尝试找到较好的初始温度。注4. 等温步数如何确定?等温步数也称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目，通常取决于解空间和邻域的大小。等温过程是为了让系统达到平衡，因此可通过检验目标函数的均值是否稳定(或连续若干步的目标值变化较小)来确定等温步数。等温步数受温度的影响。高温时，等温步数可以较小，温度较小时，等温步数要大，随着温度的降低，增加等温步数。有时为了考虑方便，也