现代优化方法之模拟退火

度、降温策略、马氏链长度以及停止准则 四个方面。 此外，还包括随机数发生器。
问题的描述主要包括解空间和目标函 数两部分。解空间为所有可行解的集合， 它限定了初始解选取和新解产生的范围。 对于无约束优化问题，任一可能解即为可 行解；对于有约束优化问题，解集中还可 以包含一些不可行解，同时在目标函数中 加上惩函数，以惩罚出现的不可行解。
通常0.85 0.95，收敛条件为Tk 。
理论已证明：只要初始温度足够高，
退火过程足够慢，模拟退火算法以概率1收
敛到全局最优解。
模拟退火算法在许多领域有非常广泛 的应用，尤其适用于求解组合优化问题。 如旅行商问题(TSP)、0-1背包问题(ZKP)、 最大截问题(MCP)、独立集问题(ISP)、调 度问题(SCP)、图着色问题(GCP)等。
接受新解。具体方法是：产生0和1之间的一 个随机数r，若P(E) r，接受新解，否则拒
绝新解； (4) 重复第(2),(3)步若干次，使解接近当前温 度下的最优解，这相当于用足够慢的速度降 温，以保证在每个温度时系统都能处于当前 温度下的能量最低状态； (5) 按一定的方式降低温度，例如Tk Tk，其 中 (0,1) ； (6) 若满足收敛条件，退火过程结束，否则 k k 1 ，转(2)。
火算法是近年提出的一种适合解大规模组 合优化问题，特别是解NP完全问题的通用 有效的近似算法，与以往近似算法相比， 具有描述简单、使用灵活、运用广泛、运 行效率高和较少受初始条件限制的优点， 而且特别适合并行计算，因此具有很大的 使用价值。同时由于其讨论涉及随机分析、 马氏链理论、渐进收敛性等学科，所 以其研究还具有重要的理论意义。
模拟退火算法的求解过程如下： (1) 随机产生初始解X0，给定初始温度T0， 令k=0； (2) 随机产生新解 X k X ，并计算函数增量
E E( X k X ) E( X k )
(3) 若E 0 ，则接受新解，X k X X k ，转
(2)，否则以概率PE exp( E Tk ) 决定是否
而形成一个纯晶体，使这个系统的能量达 到其最小值。这里我们特别强调在这个物 理系统的冷却过程中，这些原子就同时的 把它们自己排列成一个纯晶体的。如果一 种金属熔液是被快速的冷却，则它不能达 到纯晶体状态，而是变成一种多晶体或非 晶体状态，系统处在这种状态时具有较高 的能量。
模拟退火算法就是模仿上述物理系统 徐徐退火过程的一种通用随机搜索技术， 可用马氏链的遍历理论给它以数学上的描 述。在搜索最优解的过程中，模拟退火除 了可以接受优化解外，还用一个随机准则 (Metropolis准则)有限地接受恶化解，并使 接受恶化解的概率逐渐趋于零，这使得算 法有可能从局部最优解中跳出，尽可能找 到全局最优解，并保证了算法的收敛性。
第三部分 现代优化方法选讲
现代优化方法包括禁忌搜索、模拟退
火、智能计算等。
神经网络
遗传算法(GA)
智能计算进化计算进化策略( ES )
进化规划(EP)
模糊逻辑
来自百度文库
其中模拟退火、神经网络和遗传算法并称
为现代优化算法中的三大杰出代表。
一、模拟退火算法 在管理科学、计算机科学、分子物理 学、生物学、超大规模集成电路设计、代 码设计、图象处理和电子工程等领域中， 存在着大量的组合优化问题。例如，货郎 担问题、最大截问题、0—1背包问题、图 着色问题、设备布局问题以及布线问题等， 这些问题至今仍未找到多项式时间算法。 这些问题已被证明是NP完全问题。
1. 模拟退火算法的物理背景 固体退火过程的物理图象和统计性质
是模拟退火算法的物理背景。在热力学与 统计物理学的研究领域中，固体退火是其 重要的研究对象。固体退火是指先将固体 加热至熔化，再徐徐冷却使之凝固成规整 晶体的热力学过程。
在高温状态下，液体的分子彼此之间 可以自由移动。如果液体徐徐冷却，它的 分子就会丧失由于温度而引起的流动性。 这时原子就会自己排列起来而形成一种纯 晶体，它们依次地朝各个方向几十亿倍于 单个原子大小的距离，这个纯晶状态就是 该系统的最小能量状态，有趣的是：对于 一个徐徐冷却的系统，当这些原子在逐渐 失去活力的同时，它们自己就同时地排列
1982年Kipatrick等人首次把固体退火 与组合极小化联系在一起，他们分别用目 标函数和组合极小化问题的解替代物理系 统的能量和状态，从而物理系统内粒子的 摄动等价于组合极小化问题中解的试探。 极小化过程就是：首先在一个高温（温度 现在就成为一个参数控制）状态下有效的 “溶化”解空间，然后慢慢地降低温度直 到系统“晶体”到一个稳定解。
例 用模拟退火算法求
f (x) x4 0.3x3 22x2 3x
的极小值。
3. 模拟退火算法的应用 模拟退火算法具有广泛的应用性，可
用于求解许多组合优化问题。根据模拟退 火算法的过程（产生新解——计算目标函 数差——判别是否接受新解——接受或舍 弃新解），在算法的实际应用中必须解决 好三个问题：第一，问题的数学描述；第 二，新解的产生和接受机制；第三，冷却 进度表的选取。冷却进度表包括：初始温
根据NP完全性理论，除非P=NP，否则所有 的NP难问题都不存在多项式时间算法。但 是，这并不意味着问题的终结。相反，由 于这类问题广泛应用性，反而刺激人们以 更大的热情对NP完全问题进行研究。
为解决这类问题，人们提出了许多近 似算法，但这些算法或过于注意个别问题 的特征而缺乏通用性，或因所得解强烈地 依赖初始解的选择而缺乏实用性。模拟退
通过以下示例，我们可以将组合优化
问题与固体退火进行类比：
组合优化问题
固体退火
解
状态
最优解
能量最低状态
费用函数
能量
2. 模拟退火算法的基本思想与算法 用传统优化算法优化多峰值函数时，
往往由于过分追求“下降”而极易陷于局 部最优解。为了克服这个缺陷，在搜索最 优解的过程中，模拟退火方法除了接受优 化解外，还根据一个随机接受准则有限地 接受恶化解，并使接受恶化解的概率逐渐 趋于零。这既可使得算法以较大概率跳出 局部最优解，又保证了算法的收敛性。