第十一章 模拟退火算法与人工 免疫算法简介 本章对目前常用的几种智能优化计算 算法作简单介绍，以使读者对它们有个基本 认识内容包括神经网络、遗传算法、模拟 退火算法和神经网络混合优化学习策略 12.1 模拟退火算法 模拟退火算法(simulated annealing,简 称SA)的思想最早是由Metropolis等 (1953)提出的，1983年Kirkpatrick等将 其用于组合优化SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法， 其出发点是基于物理中固体物质的退火过 程与一般组合优化问题之间的相似性 模拟退火算法模拟退火算法在某一初温下，伴随温度参 数的不断下降，结合概率突跳特性在解空 间中随机寻找目标函数的全局最优解，即 在局部优解能概率性地跳出并最终趋于全 局最优解模拟退火算法是一种通用的优 化算法，目前已在工程中得到了广泛应用 模拟退火算法12.1.1 物理退火过程和Metropolis准则 简单而言，物理退火过程由以下三部分组成： ⑴加温过程其目的是增强粒子的热运动，使其偏 离平衡位置当温度足够高时，固体将溶解为液 体，从而消除系统原先可能存在的非均匀态，使 随后进行的冷却过程以某一平衡态为起点。
溶解 过程与系统的熵增过程联系，系统能量也随温度 的升高而增大 模拟退火算法⑵等温过程物理学的知识告诉我们，对于 与周围环境交换热量而温度不变的封闭系 统，系统状态的自发变化总是朝自由能减 少的方向进行，当自由能达到最小时，系 统达到平衡态 ⑶冷却过程目的是使粒子的热运动减弱并 渐趋有序，系统能量逐渐下降，从而得到 低能的晶体结构 模拟退火算法Metropolis等在1953年提出了重要性采样 法，即以概率接受新状态具体而言，在 温度t,由当前状态i产生新状态j，两者的能 量分别为 ，若 则接受新状 态j为当前状态；否则，若概率 大于 区间内的随机数则仍旧接受新状 态j为当前状态，若不成立则保留i为当前状 态，其中k为Boltzmann常数 模拟退火算法这种重要性采样过程在高温下可接受与当前 状态能量差较大的新状态，而在低温下基 本只接受与当前能量差较小的新状态，而 且当温度趋于零时，就不能接受比当前状 态能量高的新状态这种接受准则通常称 为Metropolis准则 模拟退火算法12.1.2 模拟退火算法的基本思想和步骤 1983年Kirkpatrick等意识到组合优化与物理退火 的相似性，并受到Metropolis准则的启迪，提出 了模拟退火算法。
模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法，其出 发点是基于物理退火过程与组合优化之间的相似 性，SA由某一较高初温开始，利用具有概率突 跳特性的Metropolis抽样策略在解空间中进行随 机搜索，伴随温度的不断下降重复抽样过程，最 终得到问题的全局最优解 模拟退火算法标准模拟退火算法的一般步骤可描述如下：⑴给定初温 ，随机产生初始状态 ，令 ； ⑵Repeat:①Repeat产生新状态 ； 模拟退火算法Until 抽样稳定准则满足； ②退温 ，并令 ； Until 算法终止准则满足； ⑶输出算法搜索结果 模拟退火算法12.1.3 模拟退火算法关键参数和操作的设 定 从算法流程上看，模拟退火算法包括三函数 两准则，即状态产生函数、状态接受函数 、温度更新函数、内循环终止准则和外循 环终止准则，这些环节的设计将决定SA算 法的优化性能此外，初温的选择对SA算 法性能也有很大影响 模拟退火算法⑴状态产生函数 设计状态产生函数（邻域函数）的出发点应 该是尽可能保证产生的候选解遍布全部的 解空间。
通常，状态产生函数由两部分组 成，即产生候选解的方式和候选解产生的 概率分布 模拟退火算法⑵状态接受函数 状态接受函数一般以概率的方式给出，不同 接受函数的差别主要在于接受概率的形式 不同设计状态接受概率，应该遵循以下 原则： ①在固定温度下，接受使目标函数值下降的 候选解的概率要大于使目标值上升的候选 解的概率； 模拟退火算法②随温度的下降，接受使目标函数值上升的 解的概率要逐渐减小； ③当温度趋于零时，只能接受目标函数值下 降的解 状态接受函数的引入是SA算法实现全局搜索 的最关键的因素，SA算法中通常采用 min[1,exp(-△C/t)]作为状态接受函数 模拟退火算法⑶初温初始温度、温度更新函数、内循环终止准则 和外循环终止准则通常被称为退火历程 (annealing schedule)实验表明，初温 越大，获得高质量解的几率越大，但花费 的计算时间将增加因此，初温的确定应 折衷考虑优化质量和优化效率，常用方法 包括： 模拟退火算法①均匀抽样一组状态，以各状态目标值的方 差为初温 ②随机产生一组状态，确定两两状态间的最 大目标值差 ，然后依据差值，利用一 定的函数确定初温。
譬如 ，其中 为初始接受概率 ③利用经验公式给出 模拟退火算法⑷温度更新函数 温度更新函数，即温度的下降方式，用于在 外循环中修改温度值 目前，最常用的温度更新函数为指数退温函 数，即，其中且其大小可以不断变化 模拟退火算法⑸内循环终止准则 内循环终止准则，或称Metropolis抽样稳定 准则，用于决定在各温度下产生候选解的 数目在非时齐SA算法理论中，由于在每 个温度下只产生一个或少量候选解，所以 不存在选择内循环终止准则的问题 模拟退火算法而在时齐SA算法理论中，收敛条件要求在每 个温度下产生候选解的数目趋于无穷大， 以使相应的马氏链达到平稳概率分布，显 然在实际应用算法时这是无法实现的常 用的抽样准则包括： ①检验目标函数的均值是否稳定； ②连续若干步的目标值变化较小；③按一定的步数抽样 模拟退火算法⑹外循环终止准则外循环终止准则，即算法终止准则，用于决 定算法何时结束设置温度终值是一种简 单的方法SA算法的收敛性理论中要求温 度终值趋于零，这显然不合实际通常的 做法是： 模拟退火算法①设置终止温度的阈值； ②设置外循环迭代次数； ③算法收敛到的最优值连续若干步保持不变 ；④检验系统熵是否稳定。
12.1.4 神经网络权值的混合优化学习策略 鉴于GA、SA的全局优化特性和通用性，即 优化过程无需导数信息，我们可以基于实 数编码构造BPSA、BPGA混合优化学习策 略，以提高前向网络学习的速度、精度， 特别是避免陷入局部极小的能力 12.1.4 神经网络权值的混合优化学习策略4.1 BPSA混合学习策略 在BPSA混合学习策略中，采用以BP为主框 架，并在学习过程中引入SA策略这样做 ，既利用了基于梯度下降的有指导学习来 提高局部搜索性能，也利用了SA的概率突 跳性来实现最终的全局收敛，从而可提高 学习速度和精度 BP-SA混合学习策略的算法步骤如下： 神经网络权值的混合优化学习策略⑴ 随机产生初始权值 ，确定初温 ，令 ⑵ 利用BP计算 利用SA进行搜索： ① 利用SA状态产生函数产生新权值 ， ，其中 为随机扰动 神经网络权值的混合优化学习策略② 计算 的目标函数值与 的目标函 数值之差 ③ 计算接受概率 ④ 若 ，则取 ；否则 保持不变。
神经网络权值的混合优化学习策略(4) 利用退温函数 进行退温，其中 为退 温速率 若 对应的目标函数满足要求精度 ，则终 止算法并输出结果；否则，令 ，转 步骤⑵ 神经网络权值的混合优化学习策略4.2 BPGA混合学习策略 神经网络的连接权包含着神经网络系统的全部知 识反向传播的BP神经网络(back propagation network)的学习算法是基于梯 度下降的，因而具有以下缺点：网络训练速度 慢、容易陷入局部极小值、全局搜索能力差等 而遗传算法的搜索遍及整个解空间，因此容 易得到全局最优解，而且遗传算法不要求目标 函数连续、可微，甚至不要求目标函数有显函 数的形式，只要求问题可计算神经网络权值的混合优化学习策略因此，将擅长全局搜索的遗传算法和局部寻 优能力较强的BP算法结合起来，可以避免 陷入局部极小值，提高算法收敛速度，很 快找到问题的全局最优解 BP算法和遗传算法结合训练神经网络权重的 主要步骤为： 神经网络权值的混合优化学习策略(1) 以神经网络节点之间的连接权重和节点 的阈值为参数，采用实数编码采用三层 神经网络，设输入节点数为p，输出节点数 为q，隐层节点数为r，则编码长度n为：（10-4-1 ） 神经网络权值的混合优化学习策略(2)设定神经网络节点连接权重的取值范围 ,产生相应范围的均匀分布随机数赋给基因 值，产生初始群体；(3)对群体中个体进行评价。
将个体解码赋 值给相应的连接权(包括节点阈值)，引入 学习样本计算出学习误差E，个体的适应度 定义为：. （10-4-2 ） 神经网络权值的混合优化学习策略(4)对群体中的个体执行遗传操作： ① 选择操作采用比例选择算子，若群体规 模为M，则适应度为的个体被选中进入下 一代的概率为：. （10-4-3 ） 神经网络权值的混合优化学习策略② 交叉操作由于采用实数编码，故选择算 术交叉算子父代中的个体 和 以交叉概 率 进行交叉操作，可产生的子代个体为 ：（10-4-4） 和（10-4-5） 其中a为参数 神经网络权值的混合优化学习策略③ 变异操作 采用均匀变异算子个 体 的各个基因位以变异概率 发生变异 ，即按概率用 区间中的均匀分布随 机数代替原有值 ⑸ 引入最优保留策略 神经网络权值的混合优化学习策略⑹ 判断满足遗传算法操作终止条件否？不满 足则转步骤⑶否则转步骤⑺ ⑺ 将遗传算法搜索的最优个体解码，赋值给 神经网络权重(包括节点阈值)，继续采用 BP算法优化神经网络的权重和阈值。
神经网络权值的混合优化学习策略4.3 GASA混合学习策略 采用三层前馈网络，GA和SA结合训练神经 网络权重的步骤如下： ⑴ 给定模拟退火初温 ，令 ； ⑵ 以神经网络节点之间的连接权重和节点的 阈值为参数，采用实数编码采用三层神 经网络，设输入节点数为p，输出节点数为 q，隐层节点数为r，则编码长度n为： 神经网络权值的混合优化学习策略（10-4-6） ⑶ 设定神经网络节点连接权重的取值范围 ，产生相应范围的均匀分布随机数赋给基因值 ，产生初始群体； ⑷ 对群体中个体进行评价将个体解码赋值给 相应的连接权(包括节点阈值)，引入学习样本 计算出学习误差E，个体的适应度定义为：. （10-4-7 ） 神经网络权值的混合优化学习策略⑸ 对群体中的个体执行遗传操作： ① 选择操作采用比例选择算子，若群体规模 为M，则适应度为 的个体 被选中进入下 一代的概率为：. （10-4-8） 神经网络权值的混合优化学习策略② 交叉操作由于采用实数编码，故选择 算术交叉算子。
父代中的个体 和 以交 叉概率 进行交叉操作，可产生的子代个 体为：（10-4-9） 和（10-4-10） 其中a为参数 神经网络权值的混合优化学习策略③ 变异操作采用均匀变异算子个 体 的各个基因位以变异概率 发生变异 ，即按概率 用区间 中的均匀分 布随机数代替原有。