模拟退火算法的求解过程如下： (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 ) 决定是否 接受新解。具体方法是：产生0和1之间的一 个随机数r，若P(E ) r，接受新解，否则拒
④小生境淘汰运算：将第③步得到的 M个个体和 第②步所记忆的 N 个个体合并在一起，得到一个 含有M+N个个体的新群体。对这M+N个个体， 求出每两个个体 X i和 X j之间的Hamming距离 d ij 。 当 d ij L 时，比较个体 X i和 X j的适应度大小， 并对其中适应度较低的个体处以罚函数； ⑤根据这M+N个个体的新适应度对各个个体进行 降序排序，记忆前N个个体； ⑥终止条件判断：若不满足终止条件，则将第⑤ 步排序中的前M个个体作为新的下一代群体，然
解，若接受，用新解代替当前解，同时修 正目标函数值，否则当前解与目标函数值 保持不变。 下面仅对几个典型的组合优化问题给 出算法描述，以揭示其建立数学模型和新 解产生装置的基本方法。
(1) 旅行商问题（tsp） 设有n个城市和距离矩阵 D dij ，其中 d ij表示 城市 i 到城市 j 的距离， i,j=1,… ， n ，则问题是寻 找遍访每个城市恰好一次的一条回路，且其路径 长度为最短。 求解的模拟退火算法描述如下： ① 解空间 解空间S可表为{1,2，…，n}的所有循环排列 的集合，即
通常 0.85 0.95，收敛条件为Tk 。 理论已证明：只要初始温度足够高， 退火过程足够慢，模拟退火算法以概率1收 敛到全局最优解。
模拟退火算法在许多领域有非常广泛 的应用，尤其适用于求解组合优化问题。 如旅行商问题(TSP)、0-1背包问题(ZKP)、 最大截问题(MCP)、独立集问题(ISP)、调 度问题(SCP)、图着色问题(GCP)等。 例 用模拟退火算法求
火算法是近年提出的一种适合解大规模组 合优化问题，特别是解NP完全问题的通用 有效的近似算法，与以往近似算法相比， 具有描述简单、使用灵活、运用广泛、运 行效率高和较少受初始条件限制的优点， 而且特别适合并行计算，因此具有很大的 使用价值。同时由于其讨论涉及随机分析、 马氏链理论、渐进收敛性等学科，所 以其研究还具有重要的理论意义。
f (d
u 1 v 1
d
u v 1
) (d
u 1 u
d
v v 1
)
int d[11][11]={{0,3,93,66,13,100,25,33,9,57,19}, {24,0,33,77,42,21,16,45,34,21,109}, {45,107,0,81,36,16,4,28,25,37,62}, {139,90,80,0,56,7,44,56,20,91,75}, {18,64,188,33,0,11,25,96,5,57,43}, {3,88,18,46,92,0,55,33,20,91,7}, {44,26,33,27,84,39,0,101,9,72,36}, {11,39,24,98,103,76,54,0,50,63,99}, {77,82,67,19,30,42,56,9,0,88,28}, {12,133,32,69,21,52,87,66,43,0,55}, {92,32,81,73,44,24,64,15,77,9,0}};
而形成一个纯晶体，使这个系统的能量达 到其最小值。这里我们特别强调在这个物 理系统的冷却过程中，这些原子就同时的 把它们自己排列成一个纯晶体的。如果一 种金属熔液是被快速的冷却，则它不能达 到纯晶体状态，而是变成一种多晶体或非 晶体状态，系统处在这种状态时具有较高 的能量。
模拟退火算法就是模仿上述物理系统 徐徐退火过程的一种通用随机搜索技术， 可用马氏链的遍历理论给它以数学上的描 述。在搜索最优解的过程中，模拟退火除 了可以接受优化解外，还用一个随机准则 (Metropolis准则)有限地接受恶化解，并使 接受恶化解的概率逐渐趋于零，这使得算 法有可能从局部最优解中跳出，尽可能找 到全局最优解，并保证了算法的收敛性。
S 1 ,, n 1 ,, n 为 1,2,, n的循环排列
其中每一循环排列表示遍访n个城市的一条回路， j j 表示在第i个次序访问城市j，并约定 n1 1。 初始解可选为（1,2，…，n）。 ② 目标函数 此时的目标函数为访问所有城市的路径长度 之和，即
v v f d d d d d d u v 1 i i 1 v v 1 i 1 i i u 1 i u 1 u 1 v u 1 u
计算。特别地，当问题为对称的，即距离矩阵 D d ij 为对称矩阵时，上式可简化为
非数值并行算法
——模拟退火算法 康立山 《科学出版社》
排挤小生境遗传算法改进研究
1、排挤小生境遗传算法及其改进 日本学者提出了一种基于罚函数的排挤小生 境遗传算法，其基本思想是： 首先比较群体中每两个个体之间的距离，若 这个距离小于预先指定的距离 L ，再比较两者的 适应度，并对其中适应度较小的个体施加一个较 强的罚函数，极大地降低其适应度。这样，对于 在距离 L 之内的两个个体，其中较差的个体经处
1. 模拟退火算法的物理背景 固体退火过程的物理图象和统计性质 是模拟退火算法的物理背景。在热力学与 统计物理学的研究领域中，固体退火是其 重要的研究对象。固体退火是指先将固体 加热至熔化，再徐徐冷却使之凝固成规整 晶体的热力学过程。
在高温状态下，液体的分子彼此之间 可以自由移动。如果液体徐徐冷却，它的 分子就会丧失由于温度而引起的流动性。 这时原子就会自己排列起来而形成一种纯 晶体，它们依次地朝各个方向几十亿倍于 单个原子大小的距离，这个纯晶状态就是 该系统的最小能量状态，有趣的是：对于 一个徐徐冷却的系统，当这些原子在逐渐 失去活力的同时，它们自己就同时地排列
新解的产生和接受可分为四个步骤： 第一，给出新解的变换方法，得到一个产 生装置，以从当前解产生一个新解；第二， 计算新解和当前解的目标函数差，由于目 标函数差仅由变换部分产生，因此，通常 按增量计算目标函数差；第三，判断新解 是否被接受，判断的依据是Metropolis准则， 对于有约束优化问题往往还伴随有新解可 行性的判断；第四，接受或舍弃新
通过以下示例，我们可以将组合优化 问题与固体退火进行类比： 组合优化问题 固体退火 解 状态 最优解 能量最低状态 费用函数 能量
2. 模拟退火算法的基本思想与算法 用传统优化算法优化多峰值函数时， 往往由于过分追求“下降”而极易陷于局 部最优解。为了克服这个缺陷，在搜索最 优解的过程中，模拟退火方法除了接受优 化解外，还根据一个随机接受准则有限地 接受恶化解，并使接受恶化解的概率逐渐 趋于零。这既可使得算法以较大概率跳出 局部最优解，又保证了算法的收敛性。
第三部分 现代优化方法选讲
现代优化方法包括禁忌搜索、模拟退 火、智能计算等。
神经网络 遗传算法(GA) 智能计算进化计算进化策略( ES ) 进化规划( EP) 模糊逻辑
其中模拟退火、神经网络和遗传算法并称 为现代优化算法中的三大杰出代表。
一、模拟退火算法 在管理科学、计算机科学、分子物理 学、生物学、超大规模集成电路设计、代 码设计、图象处理和电子工程等领域中， 存在着大量的组合优化问题。例如，货郎 担问题、最大截问题、 0 — 1 背包问题、图 着色问题、设备布局问题以及布线问题等， 这些问题至今仍未找到多项式时间算法。 这些问题已被证明是NP完全问题。
1982年Kipatrick等人首次把固体退火 与组合极小化联系在一起，他们分别用目 标函数和组合极小化问题的解替代物理系 统的能量和状态，从而物理系统内粒子的 摄动等价于组合极小化问题中解的试探。 极小化过程就是：首先在一个高温（温度 现在就成为一个参数控制）状态下有效的 “溶化”解空间，然后慢慢地降低温度直 到系统“晶体”到一个稳定解。
后转到第③步；若满足终止条件，则输出计算结 果，算法结束。 本文对上述算法做了两处改进。 第一，原算法用Hamming距离来衡量两个个体的 远近程度。我们认为这是不妥的，因为即使海明 距离很小的两个个休，其实际距离也可能很大。 本文采用欧氏距离来衡量个体的远近程度。 第二，原算法在进行小生境运算时采用的是通常 的（1+1）淘汰。Goldberg指出，在小生境的竞争 选择机制中，(μ+λ)选择机制具有较强的选择压，
度、降温策略、马氏链长度以及停止准则 四个方面。 此外，还包括随机数发生器。 问题的描述主要包括解空间和目标函 数两部分。解空间为所有可行解的集合， 它限定了初始解选取和新解产生的范围。 对于无约束优化问题，任一可能解即为可 行解；对于有约束优化问题，解集中还可 以包含一些不可行解，同时在目标函数中 加上惩函数，以惩罚出现的不可行解。
可有效地提高种群的多样性。(μ+λ)选择允许μ个 父代个体和λ个子代个体共同竞争，确定性地选 择高适应值个体进入新的种群。仿真实验表明， 用(μ+λ)竞争选择能大大提高种群的多样性，产生 较快的收敛速度。综合考虑计算速度和计算量， 本文采用（2+2）竞争选择机制。 为了定量描述改进后算法维持种群多样性的 能力以及收敛速度的提高程度，我们采用下列函 数表示种群的多样性程度
根据NP完全性理论，除非P=NP，否则所有 的NP难问题都不存在多项式时间算法。但 是，这并不意味着问题的终结。相反，由 于这类问题广泛应用性，反而刺激人们以 更大的热情对完全问题进行研究。 为解决这类问题，人们提出了许多近 似算法，但这些算法或过于注意个别问题 的特征而缺乏通用性，或因所得解强烈地 依赖初始解的选择而缺乏实用性。模拟退
f ( x) x 4 0.3x 3 22 x 2 3x