模拟退火算法和应用.pdfVIP

~oosOz)总第979觏 伍薜技术协作信息 论文 递营 模拟退火算法和应用 ●潘 蔚 摘 要：模拟退火算法．算法是基于MenteCado迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化 问题之间的相似性。模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找 目标函数的全局最优解，即在局部 优解能概率性地跳 出并最终趋于全局最优。模拟退火算法是一种通用的优化算法。 关键词：模拟退火算法；全局最优 一 、 引言 1．随机产生一个初始最优点，以它作为当前最优点，并计算 目标函数 模拟退火算法最早是针对组合优化提出的，其 目的在于：(1)为具有NP 值。 复杂性的问题提供有效的近似求解算法；(2)克服优化过程陷人局部极小；(3) 2．设置初始温度：0—1、0。 克服初值依赖性。模拟退火算法的基本思想出于物理退火过程。 3．设置循环记数器初值：t—l。 简单而言，物理退火过程由以下三部分组成： 4．对当前最优点作一随机变动，产生一新的最优点，计算新的且标函数 1．加温过程。其 目的是增强粒子的热运动 ，使其偏离平衡位置。 值，并计算 目标函数值的增量 △。 2．等温过程。物理学的知识告诉我们，对于周围环境交换热量而温度不变 5．如果 △0，则接受该新产生的最优点为当前最优点； 的封闭系统，系统状态的自发变化总是朝 自由能减少的方向进行 ，当自由能 如果 △I0，则以概率P=exp(一A／0)接受该新产生的最优点为当前 达到最小时，系统达到平衡态。 最优点。 3．冷却过程。其 目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐 6．如果 I终止步数，则：￡+1+1，转向第④步。 下降，从而得到低能的晶体结构。 7．如果未达到冷却状态，则 ：0一T(1)，转向第③步； 模拟退火算法的构成要素如下： 如果已达到冷却状态，则 ：输出当前最优点，计算结束。 (1)有哪些信誉好的足球投注网站空间n。 在模拟退火算法中，降温的方式对算法有很大影响。如果温度下降过快， 有哪些信誉好的足球投注网站空间也称状态空间，它由可行解的集合所组成，其中一个状态X就 可能会丢失极值点；如果温度下降过慢 ，算法的收敛速度又大大降低。其中 代表一个可行解。 具有代表性的有： 能量函数也就是需要进行优化计算的目标函数，其最小点为所求的 (1)经典退火方式 ：降温公式为：T(1)：— ；特点是温度下降很缓慢，因 … 鼓 优 群 。 tg／t+I) (31状态转移规则P。 此，算法的收敛速度也是很慢。 状态转移规则是指从一个状态(一个可行解)向另一个状态(另 卜4N (2)快速退火方式 降温公式为：T(t)：_!0l__；这种退火方式的特点是在 ： 行解)的转移概率，它与当前的温度参数T有关。 HOtt (4)冷却进度