·27· 计算机应用研究 2005 年 基 于 模 拟 退 火 的 混 合 遗 传 算 法 研 究 * ( 1. 温 州师范学院 数学与 信息科学学 院, 浙江 温 州 325035; 2. 温 州师范学院 计算机 科学系, 浙江 温州 325027) 周 丽 1, 黄素珍 2 摘 要: 针 对常 规遗 传算 法会 出现 早熟 现象 、局 部寻 优能 力 较差 等 不 足, 在遗 传 算 法 运 行 中 融 入模 拟 退 火 算 法 算子 , 实 现了 模拟 退火 的良 好局 部搜索 能力 与遗 传算 法 的全 局 搜 索 能 力 的结 合 。经 验 证 , 该 混 合算 法 可 以 显 著 提高 遗传 算法 的运行 效率 和优 化性 能。 关键 词: 遗 传算 法; 模拟 退火 ; 混合 算法 ; 非 线性 约束 中图 法分 类号 : TP302. 7 文献 标识 码: A 文章 编号 : 1001- 3695( 2005) 09- 0072- 02 Study of Hybrid Genetic Algorithm Based on Simulated Annealing ( 1. School of Mathematics & Information Science, Wenzhou Normal College, Wenzhou Zhejiang 325035, China; 2. Dept. of Computer Science, Wenzhou Normal College, Wenzhou Zhejiang 325027, China) ZHOU Li1, HUANG Su-zhen2 Abstract: Taking a modified Simulated Annealing algorithm as a genetic operator realized the combination of the local sear- ching ability of SA and global searching ability of GA. A new hybrid algorithm of Genetic Simulated Annealing had been designed with dynamic probability of crossover and mutation, and tested by a nonlinear function optimization. The results indi- cated the hybrid algorithm can improve significantly the efficiency of GA for solving nonlinear optimization. Key words: Genetic Algorithm( GA) ; Simulated Annealing( SA) ; Hybrid Algorithm; Nonlinear Optimization 遗传算法( Genetic Algorithm, GA) [ 1] 因 其高度的 并行处 理 能力、强鲁棒性和全局搜 索能力 而被广 泛地应 用于诸 多领域。 理论上遗传算法依“概率 1”收敛于问题的最优解, 然而实 践应 用中, 遗传算法会表现出早熟现象、局部寻优能力较差等不足。 所以一些常规遗传算法并不一 定是针 对某一 问题的 最佳求 解 方法 [ 2] 。 模拟退火( Simulated Annealing, SA) 具有 较强 的局 部寻 优 能力, 并能使搜索过程避 免陷入 局部最 优解, 但把握 整个搜 索 过程的能力不够, 不 便 于使 搜索 过 程进 入最 有 希望 的搜 索 区 域, 从而使得模拟退火的运算效率不高 [ 1] 。为了 提高 GA 的优 化性能和运行效率, 本文利用模拟退火算法与遗传算法的优势 互补, 提出基于模拟退火 的混合 遗传算 法, 并 用一个 非线性 优 化实例进行验证。 1 模拟退火混合遗传算法( SHGA) 1. 1 SHGA 的实现思想 模拟退火是一种基于热力 学的退 火机理 而建立 的随机 搜 索算法。SA 使用基于概率 的双方 向随 机搜索 技术, 当 基于 邻 域的一次操作使当前解 的质量 提高时, SA 接 收这 个被 改进 的 解, 作为新的当前解; 在相反 的情况 下, SA 以 一定 的概 率接 收 相对当前解来 说 质量 较差 的 解, 作 为新 的 当 前解。 SA 和 GA 都是概率搜索算法, 两者的优缺点正好互补。如果将两者相结 合, 互 相取 长补 短, 可开 发出 性能良 好的 新的 全局 搜索 算法。 收稿日期: 2004- 05- 25; 修返日期: 2004- 09- 12 基金项目: 温州市科技发展计划项目( G2002034-14) GA 与 SA 混合算法的实现有两种思路: 一种是在 GA 的运行中 融入 SA 的 思想, 称 为 混合 遗传 算 法; 另一 种 是在 SA 中 融 入 GA 的思想, 称为混合模拟退火算法。 本文提出的模拟退火混合 遗传算 法是将 常规的 模拟退 火 算法改良后, 作为遗传算法 的一个 独立的 算子, 置于 遗传算 法 进化过程中。其过程是随机 产生一 组初始 群体, 先通过 选择、 交叉、变异等遗传操作来产 生一组 新的个 体, 然后再 独立对 每 个新个体进行模拟退火操作, 其结 果作为 下一代 群体, 如此 反 复迭代进行, 直到满足某个终止条件为止。 1. 2 模拟退火算子 为利于混合算法的实现, 本文将 GA 的当前 进化代数作 为 SA 的退火时间。根据文献[ 3] 中提出 的模拟 退火温 度更新 函 数的启发式准则, 从而确定了 SA 的 温度更新 函数和 随机向 量 的产生方式。模拟退火操作具体步骤如下: ( 1) 设模拟退火初始温度为 T0, 遗传算法当 前群体中的 个 l ) , l 为个 体编 码串 的长 度。 当 1 , …, Xi 体 i 记为 Xi = ( Xi 前进化代数 t 对应的温度更新函数为 Te: j , …, Xi Te = To /tθ 式( 1) 中, θ≥1 为给定常数。 ( 2) 通过下式产生随机向量: Z i = ( Zi Z i j , …, Zi l) 1, …, Zi j = sig n( r1) ·Te· ( |r1 | - θ- 1) , j = 1, 2 , … , l ( 1 ) ( 2 ) 式( 2) 中, r1 为( - 1, 1) 上均匀分布 的随机数, sig n( r1 ) 为符 号 函数。 ( 3) 在 Xi 的基础上产生一个新的试探解 Yi = Xi + Zi , 并 计 算其对应的适应度 F( Yi) 和新试探解被接受的概率: 

第 9 期 周 丽等: 基于模拟退火的混合遗传算法研究 ·37· { P a = min 1, exp( f( Xi) - f( Yi ) ψ·Te ) { 式( 3) 中, ψ是对目标函数 进行适 当比例 变换的 常数。它适 合 于目标极小化。 ( 4) 产生一个( 0, 1) 上的 均匀 分布 的随 机数 r2 , 若 r2 ≤P a 则接 受 新 试 探 解, 即 置 Xi = Yi 。对 种 群 中 的 个 体 Xi ( i = 1, 2, …, M) 均进行式( 3) 、式( 4) 的操作。 ( 3) 尤其在进化后期, 个体相似性较大, 交叉率应逐渐减小, 变异率 应逐渐增大, 以增强变异作用而减轻交叉作用。笔者根据群体 中较优个体应具有相对较小的交叉率和变异率的思想, 并考虑 到交叉和变异操作在不同时期的作用, 提出了在进化过程中动 态调整个体交叉 率和 变 异率 的方 法, 称 为动 态 交叉 率和 变 异 率。计算公式如下: 1. 3 模拟退火混合遗传算法设计 动 态交叉 率 pc = ( 1) 染色体的 编码。常用 的编 码方 法是 二 进制 编码 和 实 数编码。二进制编码影响算法运行效率, 且不利于混合算法的 实现。所以本文对优化问题中的每个变量采用实数编码, 即将 其真实值作为变量的编码, 将 l 个变量的编码 按一定顺序 连接 在一起, 形成个体编码串。解码时只需将染色体各个基因座上 的基因值按序赋给相应的 变量即 可。若某一 个优化 问题有 三 个决策变量 xi ( i = 1, 2, 3) , 则个体 X: 6. 4 3 . 7 1. 0 对应决策变量取值为 x1 = 6. 4, x2 = 3. 7, x3 = 1. 0。 ( 2) 适应度评 价函数。适 应度 是遗 传算 法 中用 来度 量 个 体能达到或接近于最优解 的优良 程度。个体 适应度 函数的 构 造需与交叉、变异等算子及约束条件统筹兼顾。对于约束条件 的处理, 可采用罚函数法。由 目标函 数 f( X) 确定 个体 适应 度 评价函数 F( X) 。其公式如下: F( X) = f( X) σg( X) ( 4) 式( 4) 中, σ为罚因子, g( X) 为约束条件表达式。目标极小化问 题取“+ ”, 否则取“- ”。值得一提的是, 目标极小化时, 个体 X 适应度越小则越接近最优解, 这与常规的适应度意义不同。 ( 3) 选择操作。它 采用 正规 几 何排 序选 择 法。只涉 及 个 体适应度的大小次序关系, 并不 需要具 体数据, 所以 适应度 并 不一定要求非负, 且对目标极小化和极大化都适用。其基本思 想是先对群体中 所有个 体按 照其 适应 度大 小进 行 排序 ( 目 标 极大化时按升序排序, 目标极小 化时按 降序排 序) 。群体中 各 个体被选中的概率为 pi = q( 1 - q) r - 1 1 - ( 1 - q) M ( 5) 式( 5) 中, q 为选择最优 个体 的可 能性, 0 < q < 0. 1, r 为第 i 个 个体的排序序号, M 为群体规模。 ( 4) 交叉操作。交 叉运 算使 用 非均 匀算 术 交叉。假 设 对 B 两个个体进 行交 叉, 则 交叉 运 算 后所 产 生 的两 个 个 体 X t+ 1 X t+ 1 A = αXt B = αXt B + ( 1 - α) X t A A + ( 1 - α) Xt B ( 6) 式( 6) 中, α= exp( - α0T/t) , α0 为非 均匀 算术 交叉 系 数, T 为 遗传算法进化最大代数, t 为当前代数。 ( 5) 变异操作。变异运算使用均匀变异。在进 行 xk 向 x′k 的均匀变异操作时, x′k 为 { x′k = x k + ( Uk x k - ( xk - Uk max - x k) c2 , c1≥0. 5 max) c2 , c1 < 0. 5 ( 7) 式( 7) 中, c1 , c2 分别为[ 0, 1] 上均匀分布的随机数。 ( 6) 模拟退火操作。在交叉、变 异运算之 后进行 模拟退 火 运算, 过程如本文 1. 2 节。 ( 7) 动态交叉 率和变 异率。遗 传算 法在 群 体进 化的 不 同 时期, 交叉率或变异率始 终取相 同值不 利于遗 传算法 的进化。 A, Xt Xt 是: { { { η1· F′- Fmin F - Fmin - μ1 t T , F′≤F η1 - μ1 t T , F′> F η2 · F′- F min F - Fmin + μ2 t T , F′≤ F η2 + μ2 t T , F′> F ( 8 ) ( 9 ) 动 态变异 率 pm = 式( 9) 中, Fmin 为 群 体 中最 小 个 体适 应 值, F 为 群 体 平 均 适 应 值, F′为参与交叉操作的两个个体适应值中较小 者, η1, η2, μ1, μ2 为调整系数。式( 8) 、式( 9) 适合于目标极小化问题。 ( 8) 程序终止条 件。若当 前最 优个 体目 标 函数 值达 到 最 优值或当前代数达到最大遗传代数, 则输出最优解, 终止运行。 2 算例 以文献[ 4] 中的非线性约束优化 问题为例, 对比 验证本 文 的模拟退火混合遗传算法的有效性和实用性。 【算例】min f( x) = ( x1 - 2) 2 + ( x2 - 1) 2 s. t. { c1( x) = 0 c2( x) ≥0 式中, c1( x) = x1 - 2 x2 + 1, c2( x) = x2 x2 ∈[ - 0. 41 , 0. 92 ] 。 1 /4 - x2 2 + 1, x1∈ [ ( 10 ) ( 11 ) - 1. 82, 0 . 84] , 根据模拟退火 混合 遗 传算 法运 行 过程, 编 制 了计 算 机 程 序。其程序框图如图 1 所示。混合遗传算法的运行参数: 群 体 规模 M = 20, 终止代 数 T = 60, 罚 因子 σ= 100, 模拟 退火参 数 T0 = 15 000, ψ= 1. 5, θ= 3. 0, 动 态交 叉率 和变 异 率参 数 μ1 = μ2 = 0. 1, η1 = 1. 0, η2 = 0. 5。 设置各参数袁初始化 t饮0 产生 M 个满足约束条件的个体袁组成初始种群 P(t) 评价种群 P渊t冤的适应度 进行选择尧交叉尧变异操作 进行模拟退火操作袁得新种群 P忆(t) 将 P(t)和 P忆(t)合并成总群体 P义(t) 将 P义(t)按适应度排序袁取前 M 个作为第 t 代进化结果 t饮t+1 N 满足终止条件钥 输出结果袁终止计算 Y 图 1 模拟退火混合遗传算法程序框图 为了全面评价 SHGA 算法, 对比说明模拟退火在 SHGA 中 的作用, 本文设计了没有模拟退火 算子的遗 传算法 ( OGA) , 即 程序中不再进行模拟退火操作, 其他算子和参数均不变。由运 行过程中平均适应 度的 变化 ( 图 2) 和 最佳 适应 度 的变 化 ( 图 3) 可 知, 进 化 过 程 中 SHGA 的 种 群 整 体 性 能 优 于 OGA, 且 SHGA 能很快向最优 解方 向定 位, 而 OGA 向 最 优解 搜索 较 缓 慢; 而且最后 SHGA 收敛到 最优 解, 而 OGA 只 收敛 到次 优解。 这说明模拟退火对提高遗传算法的运行效率有显著作用。 ( 下转第 76 页 ) 

·67· 计算机应用研究 2005 年 发起的系统事件等。在系统 图中, 从上 到下代 表时间 的流逝, 事件的顺序要符合用况中所描述的事件的发生顺序。 出参与解决方案的软件类和 类中的 方法, 根据概 念模型, 设 计 者能够在定义的类中添加细节 [ 7] 。 4. 3 设计阶段 分析阶段完成以后, 就可以进入设计阶段。这个阶段将开 发一个基于面向对象的系 统逻辑 解决方 案。这个解 决方案 的 核心是要建立交互图, 用 它来展 示为了 满足系 统需求, 各个 对 象之间是如何进行相互通信的, 而通信的手段是消息传递。在 交互图建立之后, 接着要 建立的 是设计 类图, 它对要 实现的 软 件类和接口的定义进行总结。 ( 1) 协作图。交互 图能够 展示 出类 模型 中 实例 之间 的 消 息交互。UML 中定义 了两种 交 互图, 即 协 作图 和顺 序 图。两 者都描述完成一个协作的一组对象之间所发生的交互情况, 都 是基于相同的基本信息, 但强调不同的方面。顺序图展示按时 间顺序排列的交互, 它所 展示的 交互, 是在一 个协作 中对象 之 间为产生所要求的操作或 结果而 交换的 一组消 息。顺序图 不 能展示对象之间的关系。协作 图表现 的就是 参与交 互的对 象 之间的关系, 而不是 表示时 间顺序。但 是, 为 什么 在设 计阶段 只采用协作图呢? 因为协作图有异常 出色的表达能力, 能够表 达出更多的相关背景信息, 如对象间的可见性 的种类。协作图 还可轻松地表达条件逻辑和并发, 而且协作图相对顺序图来说, 空间要节省得多。协作图的建立主要是依赖于分析阶段建立的 概念模型, 根据概念模型, 设计者可以有选择地定义模型中的概 念所对应的类, 协作图就是展示这些类对象参与交互的过程。 ( 2) 类图。它说明了软件类的规格 说明和 应用程 序接口。 类图所能表达的典型信息包括: 类、关联和属性、接口及其操作 和常量、方法、属性类型信息、导航还有类或接口之间的依赖关 系。与分析阶段中的概念模型不同的是, 一个设计类图显示出 了软件实体的定义而不是 真实世 界中的 概念。建立 类图要 依 赖定义好的协作图和概念模 型, 根据协 作图, 设计者 能够识 别 ( 上 接第 73 页 ) 87654321 0 OGASHGA 50 60 30 20 运行代数 40 10 图 2 算法运行中 平均适应度变化图 1.65 1.6 1.55 15 1.45 1.4 1.350 OGASHGA 50 60 40 30 20 运行代数 10 图 猿 算法运行中 最佳适应度变化图 从运行 结 果上 看 ( 表 1) , 本 文的 SHGA 算 法 不仅 最 优 值 f( x) = 1. 397 121 优于文献[ 4, 5] 中的优化 结果, 而且本 文的最 优解严格满足约束条件 C1( x) =0, 而文献[ 4, 5] 中却均未满足。 这说明本文的基于模拟退火的混合遗传算法, 在求解效 果上具 有一定的优势, 能显著地提高 GA 的优化性能。同时本文还对其 他常用的带复杂约束的测试函数进行了验证, 均取得较好效果。 表 1 算例 运行结 果及 比较 方 法 f( x) x 1 x 2 C1( x ) C2( x ) SHGA 1 . 397121 0 . 821380 0 . 910690 0 . 000000 0 . 339310 OGA 1 . 401377 0 . 820234 0 . 902380 0 . 015474 0 . 353906 出 处 本 文 本 文 混 沌 优 化 1 . 398697 0 . 820742 0 . 910695 0 . 000109 0 . 002918 文 献 [ 4] GA 1 . 4339 0 . 8080 0. 88544 0. 037 0. 052 文 献 [ 5] 3 结束语 本文对遗传算法的改进方法进行了研究, 将模拟退火的良 5 结束语 UML 在取得巨大成功的同时, 还存在许多 问题, 用户和 教 师抱怨它内容庞大、难学难 教而且 太过复 杂; 学者认 为它缺 少 一个精练的核心和定义良好的外围, 有些语义定义得不够精确 而且带有二义性; 建模实践者认为它缺少支持自己领域建模要 求的机制; 工具开发商则因为规范本身的不确定性而产生理解 上的偏差, 它们对 UML 的自行诠释 有可能 误导用 户。UML 的 关键问题是过于庞大和复杂, 以及 在语言 体系结 构、语义等 方 面存在理论缺陷。本文对 UML 本身及与它相关的一些概念 进 行了详细的分析和比较, 说明 了如何 使用 UML 建模以 完成 一 个系统的分析和设计, 对 UML 中的各种框图进行深入的研究, 对面向对象的分析与设计有很大的指导意义。 参考文献: [ 1] 张海潘 . 软 件工程 导论 [ M] . 北京 : 清 华大学 出版 社, 1998. 1- 5. [ 2] Alun Williams [ EB / OL] . http: / / www. umlchina. com/ News / Con- tent/143 . htm, 2004- 05- 26. [ 3] 邵维忠 , 杨芙清 . 面 向对 象的 系 统设 计 [ M] . 北京 : 清 华 大 学出 版 社, 2003. 160-174 . [ 4 ] 冀振燕 . UML 系统分 析 设 计 与 应 用 案 例 [ M] . 北 京: 人 民 邮 电 出 [ 5] 版社, 2003. 3- 9. Jason T Roff. UML a Beginner’s Guide[ M] . 张 瑜. 北 京 : 清 华大 学 出版社 , 2003 . 9-13. [ 6 ] Wendy Boggs, Michael Boggs. Mastering Rational XDE[ M] . 邱 仲 潘. 北京 : 电 子工业 出版 社, 2003. 1- 7. [ 7] 拉尔曼 . UML 和模式 应用 : 面 向对 象 分析 与 设计 [ M] . 姚 淑 珍. 北 京: 机械 工业出 版社, 2002. 4 -95. 作者简介: 屈 喜龙 ( 1978 - ) , 男, 湖南 新邵人 , 博 士研 究 生, 研 究 方向 为 网 络 化制 造 的 研究 。 好局部搜索能力与遗传算法擅长的全局搜索性相互取长补短, 提出将一种有效的模拟退火算 法作为 遗传算 法的一 个独立 操 作算子, 置于遗传算法进化 过程中, 融 合为模 拟退火 混合遗 传 算法( SHGA) , 并提出了动态交叉率和变 异率的 思想。设计 了 不带模拟退 火算 子的 OSA 算 法, 以 便验 证模 拟 退 火在 SHGA 算法中的 作 用。数 值 优 化 结 果 表 明, 与 其 他 优 化 算 法 相 比, SHGA 算法可以显著提高遗传算法 的优化性能和运行效率, 对 解决非线性约束优化问题有较大的应用价值。 参考文献: [ 1 ] 周丽, 孙树 栋. 遗传 算法原 理及 应用[ M] . 北京: 国防 工业 出 版社 , 2001 . [ 2] 欧阳森 , 宋政湘 , 王 建华 , 等 . 一 种 快速 收 敛 的遗 传 算 法 [ J] . 计 算 机应用 研究, 2003, 20( 9 ) : 50- 52. [ 3] 杨若黎 , 顾基发 . 一 种高 效的模 拟 退火 全 局 优化 算 法 [ J] . 系统 工 程理论 与实践 , 1997, 17 ( 5) : 29 -35. [ 4] 骆晨钟 . 邵惠鹤 . 用 混沌 搜索求 解 非线 性 约 束优 化 问 题 [ J] . 系 统 工程理 论与实 践, 2000, 20( 8) : 54- 58 . [ 5] Homaifar A, et al. Constrained Optimization via Genetic Algorithms [ J] . Simulation, 1994 , 62 ( 4) : 242- 254. 作者简介: 周 丽( 1977- ) , 女 , 湖 北 武 汉人 , 讲 师 , 硕 士, 主 要 从 事系 统 优 化 方 法 与 预 测决 策技术 研究 ; 黄 素珍( 1973- ) , 女, 浙 江 温州 人 , 讲 师, 硕 士, 主 要 从 事计 算机算 法研 究。