模拟退火算法原理及改进.pdf

模拟退火算法原理及改进.pdf 模拟退火算法是一种强大的随机搜索算法，可以应用于许多前提信息很少的问题，并能渐进地收敛于最优值。本文对SA算法进行了介绍，论述了SA算法的原理并对算法进行了改进，展示了计算实验的结果。 模拟退火算法的原理来自于物理热力学原理，综合了固体退火与组合优化之间的类似性。类似固体的复杂系统，先被加热到一个物质粒子能自由移动的很高的温度，当它慢慢冷却时，它的能量减少。如果“冷却”过程足够慢，系统将忽略局部稳定构造，达到能量最低状态，即基态。在模拟的每一步中，新解的产生按照Metropolis transition法则，一个新的状态从现有的状态中产生，这个法则能以一定的概率接受能量上升（即产生劣解）的新状态，而能量下降是优化的总目的。 模拟退火算法的改进是通过对控制参数的协调来提高SA的性能，包括初始温度的选择、温度降低策略、适当的邻域结构和终止标准等。例如，初始温度的选择可以使用以下公式：t0= ’f+lnx- 1’，其中f是函数增量的平均值，χ是初始的接受概率。 温度降低策略也是一种重要的参数，温度降低越快，陷入局部的概率就越大。然而，温度降低太慢会导致算法速度慢得不能接受。本文采用了一种快速的非线性降低法：tk= t01+kk=1, 2, 3, ⋯ ⋯ 在SA算法中，邻域结构也是一种重要的参数，退火期间，步长太小导致算法在探索相位空间效率低，太大新解总被拒绝。在持续优化时，新的等价值均一地按间距分布在以xi的坐标为中心的邻域中，沿轴的间距的一半被看作步长向量ξ。当点落在f的定义域内时，就随机产生新解。 终止标准是SA算法的另一个重要参数，内循环是单一温度下在各种条件下Marcov链的一种渐进接近全局最优的模拟实现，即循环Marcov链长次数结束。外循环取某个温度t作为算法终止标准，或者是迭代次数。 模拟退火算法是一种强大的随机搜索算法，通过对控制参数的协调，可以提高SA的性能，使其在解决组合优化问题时具有更好的效果。