基于网格法的遗传算法及其应用

D0I:10.13374/i.issn1001053x.2002.03.077 第24卷第3期 北京科技大学学报 Vol.24 No.3 2002年6月 Journal of University of Science and Technology Beijing Jun.2002 基于网格法的遗传算法及其应用 高玉根1)王国彪”丁予展》 1)北京科技大学土木与环境工程学院，北京1000832)山东工程学院，淄博255012 摘要在基本的遗传算法(SGA)中，初始群体是随机产生的.为了增加个体的遍历性和多样 性提出一种用网格法来产生遗传算法的初始群体，并对网格法的遗传算法的优化效率进行了 定量的评价.同时与基本的遗传算法一起应用在DeJong的测试函数FI上便于进行对比.评价 结果和实验结果表明网格法在提高遗传算法的优化效率上是可行的 关键词遗传算法；网格法；优化算法 分类号 TP301.6 在遗传算法中，初始群体的遍历性和多样自己的取值范围.网格法初始化群体的基本思 性有时对算法的性能起到关键性的影响.若群 想是：把每1个变量的取值范围均匀分割，形成 体内缺乏足够的遍历性和多样性，会产生早熟 了许多等宽度小区间的边界，所有变量的小区 现象，结果导致收敛过快：若增加群体的规模来 间的边界相互交叉，形成了许多网格，网格上的 保证遍历性和多样性，则会浪费掉过多计算机 交叉点就是搜索空间的1个点；然后，再对每1 资源，结果导致计算时间过长.如何产生初始的 个搜索空间的点进行编码，形成遗传算法的个 群体一直是人们比较关注的问题之一. 体，这样构成了遗传算法的初始群体，现以二维 在基本的遗传算法中，初始群体的产生采 空间为例，设决策变量分别为x1,x,的取值范 用随机法.当群体的规模小时，用随机法产生的 围为41mm≤石1≤41mx;xz的取值范围为42mn≤2≤山2mx. 个体有时距离比较近，个体不能均匀地遍布整 现把x1x2分别均匀3等分，如图1所示，它的4 个区域，影响遗传算法的性能，如计算速度不理 条边界线相互交叉，形成16个网格点，这就是 想和提前收敛等问题.因此，为了使随机产生的 二维搜索空间的点.把这16个点编码成遗传空 个体达到所有状态的遍历和多样性，又不增加 间的16个个体，这16个个体就形成了遗传算 群体的规模.一般的解决方法是在随机法中引 法的初始群体， 用Hamming距离，以此作为控制依据来产生初 始群体四，最近有的学者提出用均匀设计的方 法来初始化群体)，其目的是使产生的个体均匀 地遍布整个区域，从而改善遗传算法的性能. 本文提出一种用网格法来产生初始的群 体，其目的也是在不加大群体规模的基础上，增 加个体的遍历性和多样性.同时也为提高遗传 图1网格法的示意图 算法的搜索效率探索一条新的途径 Fig.1 Schematic diagram of grid 1网格法的基本思想 2基于网格法的遗传算法的特点与 在用遗传算法解决优化问题时，首先要确 性能 定问题的实际决策变量，每1个变量通常都有 收稿日期200105011高玉根男，37岁，副教授，博士 2.1网格法的特点 *国家自然科学基金资助课题(No.59705010) 为了使初始群体中的个体具有多样性和遍

第 卷 第 期 3 2 4 年 月 2 2 0 0 6 北 京 科 技 大 学 学 报 O J u n a r l o U f n v i s e r t i y o S f e i e n e c n a T d e c h n o l o g y B 小 n e g 匕】 V . N 2 4 o . 3 J u n . 2 2 0 0 基于 网格法的遗传算法及其应用 高玉根 ’ ,2) 王 国彪 ” 丁 予展 ” l) 北京科技大学土木 与环境工程学院 , 北京 10 0 0 83 2 )山东工程学院 , 淄博 2 5 5 01 2 摘 要 在基本 的遗 传算法 ( s G A )中 , 初 始群体是 随机产 生 的 . 为 了增 加个体的遍历性和 多样 性提出一 种用 网格 法来 产生遗 传算法 的初始 群体 , 并对 网格法 的遗传算法 的优化效率进行 了 定量 的评价 . 同时与基本 的遗传算法 一起应用 在 D ej o ng 的测 试函数 lF 上 便于 进行对 比 . 评价 结果 和 实验结 果表 明 网格法 在提 高遗传算法 的优化效率上是 可行 的 . 关键词 遗传算 法 ; 网格法 ; 优化算法 分 类号 T P 3 0 1 . 6 在 遗传算法 中 , 初 始群 体的遍历性 和 多样 性有 时对算法 的性能起到关 键性 的影 响 【, ] . 若群 体 内缺乏足够 的遍历性和 多样性 , 会产 生早熟 现象 , 结果导致收敛过快 ;若增加群体 的规模来 保 证遍历性 和 多样性 , 则会 浪费掉过 多计 算机 资源 , 结果导致计算时间过长 . 如何产生初始 的 群体一直是 人们 比较关注 的问题之一 在基本 的遗传 算法 中 , 初始群体 的产生采 用随机法 . 当群体 的规模小时 , 用 随机法产生 的 个体有时距 离 比较近 , 个体不能均匀 地遍布整 个区 域 , 影响遗传算法 的性能 , 如计算速度不理 想和提前收敛 等问题 . 因此 , 为了使 随机产生 的 个体达到所 有状态 的遍历 和多样性 , 又不增加 群体 的规模 . 一般 的解 决方法是在 随机法 中引 用 H ~ in g 距离 , 以此 作为控制依据来 产生初 始群体 `2] . 最近有 的学 者提 出用均 匀设 计 的方 法来初 始化群体 l3] , 其 目的是使 产生的个体均匀 地遍布整个 区域 , 从而改善遗传 算法 的性能 . 本 文提 出一种 用 网格 法 来 产生 初 始 的群 体 , 其 目的也是在不加大群体规模 的基础上 , 增 加个体 的遍 历性 和 多样性 . 同时也 为提高遗传 算法 的搜索 效率探索一 条新 的途径 . 自己 的取值范 围 . 网格法初始化群体 的基本思 想是 : 把每 1 个变量 的取值范 围均匀分割 , 形成 了许 多等宽度小 区 间的边界 , 所有变 量的小 区 间的边界相互交叉 , 形成 了许多 网格 , 网格上 的 交叉 点就是搜索空 间的 1 个点 ; 然后 , 再对每 1 个搜 索空 间 的点进行编码 , 形成遗传 算法 的个 体 , 这样构成了遗传算法 的初始群体 . 现 以二维 空 间为例 , 设决策变 量分 别为 x ,丙 , x l的取值范 围为 u l m o n ` x : ` u . axtn ;瓜 的取值范 围为 u Z m: 。 ` x Z ` u Z axtn . 现把xl 为分别均 匀 3 等分 , 如 图 1 所示 , 它 的 4 条边 界线相互交叉 , 形成 16 个 网格 点 , 这就是 二维搜 索空 间的点 . 把这 16 个点编码成遗传空 间的 16 个个体 , 这 16 个个体就形 成 了遗传算 法 的初始群体 . X 2 祝 2 ~ 砚 一 amx X - 图 1 网格 法的 示意 图 F i g . 1 S e h e m a it e d i a g r a m o f g r id 1 网格法 的基本思想 在用遗传算 法解决优化 问题 时 , 首先要确 定 问题 的实 际决 策变量 , 每 1 个变量 通常都有 收稿 日期 2 0 01 刁5刁1 高玉 根 男 , 37 岁 , 副教授 , 博士 * 国家自然 科学 基金 资助课题( N .o 59 7 0 5 01 0) 2 基于 网格法的遗传算法的特点与 性能 2 . 1 网格法的特点 为了使初始群体 中的个体具有 多样性 和遍 DOI: 10. 13374 /j . issn1001 -053x. 2002. 03. 077

Vol.24 高玉根等：基于网格法的遗传算法及其应用 ·361· 历性，引入Hamming距离的随机法和均匀设计 以下公式中参数的含义请详细参阅文献[8] 法.随机法的方法简单，产生初始个体容易， 平均截止代数的公式为： Hamming准则基本保证初始群体的均匀性.但 TS,e)=ETp (1) 它有一个缺点，就是相邻整数的二进制编码可 式中，S代表一种策略；表示计算精度；T表示将 能有较大的Hamming距离，这就是所谓的Ham- T中的不同元素按从小到大的顺序排列得到的 ming悬崖，例如15和16的二进制表示为01111 集合；P,表示统计频率；M表示T集合中T的个 和10000，算法要从15改进到16则必需改变所 数. 有的位.这样产生的个体具有较好的多样性，但 截止代数分布熵(H的公式为： 遍历性稍差，不能充满整个搜索空间，这将会降 H(S.e)=-p.In(p)/In(M) (2) 低遗传算子的搜索效率.均匀设计法可以均匀 1 布点整个初始群体，群体中的个体有较好的遍 其中，M和P的含义同上；截止代数分布熵表示 历性和多样性，但产生初始点时，为了达到“均 截止代数分布的均匀程度 匀分散”的目的，有时要借助均匀设计表.网格 将TS,e)和S,)集成为一个平面测度 法在产生初始点时，把整个搜索空间均匀等分， (T,),用来作为综合评价准则，则在不同方法 个体之间间隔均匀，能布满整个搜索空间，因 下对应平面(T)上的不同点，离原点愈近的点， 此，也具有较好的遍历性和多样性.另外，网格 其对应方法的优化效率愈高 法和随机法一样，可以控制群体的规模 本文将网格法和随机法作对比，用TS,)和 2.2网格法的收敛性分析 HS,)来评价网格法的优化效率，现采用如下函 理论已证明了基本遗传算法收敛于最优解 数优化为例： 的概率小于1.显然，对于收敛概率小于1的算 max f(x,xz)=100-x-(x2-5)2 (3) 法，其应用可靠性就值得怀疑.如果希望遗传算 s.t.-3≤x1≤3； 法保证收敛，就需要对基本遗传算法进行改进， 2≤x2≤8. 如使用保留最佳个体策略.在遗传算法的理论 这2种方法都采用实数编码、最优个体保 部分中四，已经证明了使用保留最佳个体策略的 留、赌轮比例选择、一点交叉、均匀变异的方式， 遗传算法总能够以概率等于1搜索到最优解. 控制参数为：群体规模=30；计算精度ε=10‘；阈 基本的遗传算法采用的是二进制编码.文献6)] 值代数=50；终止代数=50；交叉概率p.= 认为实数编码遗传算法(FGA)的收敛性，实施最 0.600.85;变异概率pm=0.10.3.所不同的只有 优个体保留策略是收敛性必要的前提保证，还 初始群体的产生方式不同.在交叉概率和变异 给出了关于FGA2个一般性的收敛条件，同时 概率的取值范围中，网格法和随机法各独立运 也指出了FGA的收敛性与初始群体的选择无 行200次，获得的平均截止代数和截止代数分 关.网格法只影响遗传算法初始群体的产生，因 布嫡如图2所示.从图2中可以看出，网格法的 此，网格法只要采取最优个体保留策略和适当 优化效率要稍好于随机法 的遗传操作，就可以保证算法收敛 0.86 23网格法优化效率的定量评价 ·网格法 0.84 为了评价遗传算法的优化效率，DeJong”曾 蘑随机法 提出用“在线性能”和“离线性能”作为评价准 0.82 令 则，但这些评价准则适合于单次运行遗传算法 0.80 时的优化效率评价，它只考虑了遗传算法的收 ◆ 0.78 敛速度特征，没有考虑多次运行时的收敛不稳 0.76L 定性特征.要客观地评价遗传算法的优化效率， 0.2 0.40.6 0.8 1.0 必须考虑其收敛不稳定性.因此，本文采用文献 T(规一化) [8]提出的用“平均截止代数”和“截止代数分布 图2网格法和随机法优化效率的比较 嫡”2个测度来衡量基于网格法的遗传算法的 Fig.2 Comparison between grid and randomization opti- 收敛速度和收敛不稳定性.这些概念的定义和 mal efficiency

、 价 . 4 高玉根等 2 : 基于 网格法 的遗 传算法及 其应 用 一 ` I 3 历性 , 引人 H ~ ign 距离的随机法和 均匀设计 法 . 随机法 的方法简单 , 产生初 始个体容易 , H确m 吨 准则基本 保证初始群体的均匀性 , 但 它有一个缺 点 , 就是相邻整数 的二进制编码可 能有较大 的 H ~ ign 距离 , 这就是所谓 的 H am - m i ll g 悬崖#IJ , 例如 15 和 16 的二进制表示 为 0 1 1n 和 10 0 0 0 , 算法要从 lS 改进 到 16 则必需改变所 有 的位 . 这样产生的个体具有较好的多样性 , 但 遍历性稍差 , 不 能充满整个搜 索空间 , 这将会降 低遗传算 子的搜 索效率 . 均匀设计法可 以均匀 布点整个初始群 体 , 群 体 中的个体有较好 的遍 历性 和 多样性 , 但 产生初始点时 , 为 了达到 “ 均 匀分散 ” 的 目的 , 有 时要借助均匀设计表 . 网格 法在产生初始点时 , 把整个搜索空间均匀等分 , 个体之 间间隔均匀 , 能布满整 个搜索空间 , 因 此 , 也 具有较 好的遍 历性 和 多样性 . 另外 , 网格 法 和 随机法一样 , 可 以控制群体 的规模 . .2 2 网格法的收敛性分析 理论已 证明了基本遗传算法收敛于最优解 的概率小 于 1 . 显然 , 对于 收敛概率小 于 1 的算 法 , 其应用可 靠性就值得怀疑 . 如果希望遗传算 法保证收敛 , 就需要对基本遗传算法进行改进 , 如使用保 留最佳个体 策略 . 在遗传算法 的理论 部分中 `5] , 已经证明了使用保 留最佳个体策略的 遗传算 法总能够 以概率 等于 1 搜索到最优解 ` 基本 的遗传算法采用 的是二进 制编码 . 文献 [6] 认为实数编码遗传算法 (F G A )的收敛性 , 实施最 优个体保 留策 略是 收敛性必 要的前 提保证 , 还 给出了关 于 F G A Z 个一般性 的收敛条件 , 同时 也指出了 F G A 的收敛性与初始群体 的选择无 关 . 网格法只影响遗传算法初始群体的产生 , 因 此 , 网格法 只要采取最优个体保留策略和 适 当 的遗传操作 , 就可 以保证算法 收敛 . .2 3 网格法优化效率的定t 评价 为 了评价遗传算法 的优化效率 , D ej on 梦 ,曾 提出用 “ 在线性 能 ” 和 “ 离线性 能 ” 作为评价准 则 , 但这些评价准则适合于单次运行遗传算法 时的优化效率 评价 , 它只 考虑 了遗传算法 的收 敛 速度 特征 , 没有考虑多次运行时 的收敛不稳 定性特征 . 要客观地评价遗传算法的优化效率 , 必须考虑其收敛不稳定性 . 因此 , 本文采用文献 8[ l提出的用 “ 平均截止代数 ” 和 “ 截 止代数分布 嫡 ” 2 个测度来衡量基于 网格法 的遗传算法 的 收敛速度和 收敛不 稳定性 . 这些 概念 的定义 和 以下公式 中参数 的含 义请 详细参阅文献【8] . 平均截止代数 的公式 为: 联S, 日二 艺’,T ,P ` ( l ) 式 中声代表一种策略 挤表示计算精度 ; T表示将 T中的不同元素按从小 到大 的顺序排列得到 的 集 合 小 表示统 计频 率 ;刀表示 尹集 合 中’,T 的个 数 . 截止代数分布嫡 (闭 的公 式为 : (SH, 日一酗 .nI种 nI时 (2) 其 中 , 刀和夕 咬的含义 同上 ; 截止代数分布嫡表示 截止代数分布 的均匀 程度 . 将 月况习和 州尽习集 成 为 一 个 平 面 测 度 伏功 , 用来作为综合评价 准则 , 则在 不同方法 下对应平面 (兀功上的不 同点 , 离原点愈近的点 , 其对应方法 的优 化效 率愈高 . 本文将 网格法 和随机法作对 比 , 用 爪s, e) 和 (H ,S力来 评价网格法 的优化效率 , 现采用如下函 数优化 为例 : m ax 几 :声z) 二 10 0 一对一x(z 一 5 ) , ( 3 ) s , t . 一 3 匕 x 、 兰 3 ; 2 匕x Z 兰 8 . 这 2 种方法都采用实数编码 、 最优个体保 留 、 赌轮 比例选择 、 一点交叉 、 均匀变异 的方式 , 控制参数为 : 群体规模 弓;0 计算精度二 10 一 ` ; 阑 值 代 数二 50 ; 终 止 代 数二 50 ; 交 叉 概 率八 二 0 . 6 0一.0 85 ; 变异概率几二 0 . 1一.0 3 . 所不 同的只有 初始群体 的 产生方式 不 同 . 在交叉概率 和变异 概率 的取值范 围中 , 网格法和随机法各独立运 行 2 0 次 , 获得 的平 均截止代数和截止代数分 布嫡如 图 2 所 示 . 从 图 2 中可 以看 出 , 网格法 的 优化效率要稍好 于 随机法 . 0 , 8 4 0 82 . 网格法 . 随机法 , . … (T 规一化 ) 图 2 网格法 和随机 法优化效率 的 比较 瓦’g 2 C om aP 山朋 加加 e . igr d a o d ar o d o . 如行皿 o P柱 · m a l e if c i e n cy

-362· 北京科技大学学报 2002年第3期 3基于网格法遗传算法的实现步骤 4 应用实例 3.1初始群体的形成 为了验证基于网格法的遗传算法的有效 设决策变量分别为x,…x,将这些变量等 性，选择了DeJong的测试函数F1进行函数优 分为m1,m,,mn,则群体的规模为(m+1)×(m2+ 化，并与SGA进行对比.设定群体的规模pop- 1)×…×(m+1),由网格法来确定搜索空间的每一 size=64,交叉率p.0.8,变异率pm0.2,终止代 个点 数=1000.2种方法都采用实码编制.另外，两个 3.2个体的编码 方法也都采用了杰出个体保护法，也就是说， 将搜索空间的每1个点编码成遗传算法的 程序中在初始化群体上不同外，遗传算法的遗 个体（即染色体），例如将1个空间点的1个变量 传算子、控制和运行参数都相同.2种算法的运 编码为二进制串,则将二进制串按下 行结果如表1所示，从表中可以看出，2种方法 式转换为1个十进制整数： 都趋于收敛，网格法在第712代时获得的适应 x'=∑b2 i=0,…,l (4) 值，SGA则在第967代时才达到，表明网格法的 0 按下式计算这个变量x的值： 收敛速度比SGA稍微快， X=m Ums-Umin (5) 表12种算法运算结果 2-1 Table 1 Fitness of SGA and Grid running on DeJong 式中，I为二进制串长；[u,h]为变量的取值 Function F1 范围.将这1个空间点的所有分变量对应的二 算法 2 3 50100 150 进制串有序的排列起来，这就编码成一个染色 SGA60.4605.4733.1330.5480.3940.218 体（即1个体）.若采用实码编制，则直接将点作 Grid78.3363.8303.0590.3280.2270.123 为染色体 算法 250400500712 967 33遗传操作 SGA0.2180.2070.0860.0110.001 (1)赌盘选择法.记，Σf分别为群体中个 Gird 0.0670.0670.0670.0010.0007 体适应度和群体适应度的总和，则个体的选择 概率为p,=1Ef,i=1,2,,n.然后计算各个体对 结论 应的累积概率9-P；k-12,n用产生[0，刂 本文提出的用网格法来构成遗传算法的初 之间的伪随机数r和积累概率：来选择群体中 始群体，并对其算法的优化效率进行了定量评 的那1个个体进入下一代. 价，最后将它和基本的遗传算法(SGA)一起应 (2)交叉操作.设定交叉率P为定值，随机地 用到DeJong的测试函数F1上，评价结果和实 产生对应群体中每一个个体的伪随机数，选择 验结果表明，该方法用于改进遗传算法时，可以 <p的所有个体来进行交叉.交叉可以选择一点 加快收敛的速度，提高优化效率，该方法是可行 交叉、两点交叉、均匀交叉等交叉方式 的. (3)变异操作.变异以等于变异率的概率改 参考文献 变一个或几个基因.把群体中的所有个体进行 1米凯利维茨Z.周家驹，何险峰译.演化程序一遗传算 排队，对队列中的每一个基因进行顺序地编成 法和数据编码的结合M0.北京：科学出版社，2000 位号，随机地产生对应每一个基因位号的伪随 2郭立新，李成植，郑文利，等.遗传算法在机械优化设 机数.设定变异率pm为定值，当r<p时，对应的 计中的应用[].机械设计与制造，1999(1)：43 基因进行变异.变异有均匀性变异、正态性变 3高齐圣，潘德惠.基于均匀设计的遗传算法及其应用 异、非一致性变异等 J.信息与控制，1999,28(3)：236 3.4终止判据m 4潘正君，康立山，陈毓屏.演化计算M.北京：清华大 学出版社，1998 目前，遗传算法终止条件的判据主要有以 5 Rudolph G.Convergence Analysis of Canonical Genetic 下几个种：(1)判断遗传算法进化是否达到了预 Algorithms [J].IEEE Trans on Neural Network,1994,5 定的最大代数；(2)遗传算法是否找到了较优的 (1):86 个体，即问题的较优解；(3)个体的适应值是否 6林丹，李敏强，寇纪淞.基于实数编码的遗传算法的 已趋于稳定，而无改进 收敛性研究).计算机研究与发展，2000,37(11)：

. 36 2 - 北 京 科 技 大 学 学 报 2 0 02 年 第 3期 3 基于网格法遗传算法的实现步骤 .3 1 初始群体 的形成 设决策变量分别为 xl 丙 , … 几 , 将这些变量等 分 为 m , ,札 , … , m 。 , 则 群 体 的规 模 为 ( ml +l ) x( m 2+ 1 ) x … 、 m( 汁 l) , 由网格法来 确定搜索空 间的每一 个点 . .3 2 个体的编码 将搜索空 间的每 1 个点编码成遗 传算法 的 个体 (即染色体 ) , 例如将 1个 空 间点的 1 个变量 编码 为二进 制串 , 则将二进制 串按下 式转换为 1 个 十进制 整数 : x , 二 Z 反 · tZ i = 0, 二 、 l ( 4 ) 按 下式计算 这个 变量 x 的值 : x = um in+ x , · 封m ax 一 封 m访 2 `一 l ( 5 ) 式 中 , l 为二进 制串长 ; [um , , u ~ ]为变量 的取值 范围 . 将这 1 个空 间点 的所有 分变量对应 的二 进 制串有序 的排列起 来 , 这 就编码成一个染 色 体 ( 即 1个体 ) . 若采用实码编制 , 则直 接将点作 为染 色体 . .3 3 遗传操作 (1 ) 赌盘选 择法 `9] . 宝以 , 习 分别为群体 中个 体适应 度和群体适应 度的总 和 , 则个体 的选择 概率 为户 ` = 厂/艺f , i = 1 , 2 , … , n . 然后计算各个体对 k 应 的累积概率 q * 一 分 , ; “ 一 ` ,2 … .,n 用产生 0[ , ` ] 之 间的伪 随机数 : 和积 累概率 q * 来选择群体 中 的那 1 个个 体进入下一代 . (2 ) 交叉操作 . 设定交叉率尸 。为定值 , 随机地 产生对应群体 中每一个个体 的伪 随机数 ; , 选择 尸印 。 的所有个体来进行交叉 . 交叉可 以选择一点 交叉 、 两 点交叉 、 均匀交叉等 交叉方式 【 .l0] (3 )变异操作 . 变异 以 等于 变异率 的概率改 变一个 或几个基 因 . 把群体 中的所有个体进行 排 队 , 对 队列 中的每一个基 因进行顺 序地编成 位号 , 随机地产生对 应每一个基 因位号 的伪 随 机数 . 设定变异率尸 m 为定值 , 当 犷印 。 时 , 对应 的 基 因进行变 异 . 变异有 均匀性变异 、 正态性变 异 、 非一致性 变异等l’. 3 · 4 终止判据 `川 目前 , 遗传算法终止 条件的判据 主要有 以 下几个种 : ( 1) 判断遗传算法进化 是否达到 了预 定 的最 大代数 ; ( 2 ) 遗传算法是否 找到 了较优的 个体 , 即问题 的较优解 ; ( 3) 个体 的适应值是 否 已趋 于稳 定 , 而无 改进 . 4 应用 实例 为 了 验证 基 于 网 格 法 的遗 传算 法 的有效 性 , 选择 了 D ej on g 的测试 函 数 lF 进行 函数优 化 , 并 与 SG A 进行对 比 . 设定 群体 的规模 p叩 - s泳 二 64 , 交 叉率尸 c =0 . 8 , 变异 率尸 . 二。 . 2 , 终止 代 数二 10 0 . 2 种 方法都采用 实码 编制 . 另外 , 两个 方法也都 采用 了杰 出个 体保护法 〔l2] , 也就是说 , 程序 中在 初始化群体上 不 同外 , 遗 传算法 的遗 传算子 、 控制 和运行参数都相 同 . 2 种算法的运 行结果如 表 1 所示 , 从表 中可 以看 出 , 2 种方法 都趋 于收敛 , 网格法在第 71 2 代 时获得 的适应 值 , SG A 则在第 9 67 代时才达到 , 表明 网格法的 收敛速度 比 S G A 稍微快 . 表 1 2 种算 法运 算结 果 aT b le 1 F i t n es s o f S G A a o d G ir d r u n n i n g o n D eJ 0 n g F u n c it 0 0 F I 算法 1 2 3 5 0 1 0 0 1 5 0 S G A 6 0 . 4 6 0 5 . 4 7 3 3 . 1 3 3 0 . 5 4 8 0 . 3 9 4 0 . 2 1 8 G ir d 78 . 3 3 6 3 . 8 3 0 3 0 59 0 . 3 2 8 0 . 2 2 7 0 . 1 2 3 算法 2 5 0 4 0 0 50 0 7 12 9 67 S G A G idr 0 . 2 18 0 . 0 6 7 0 . 2 07 0 . 0 6 7 0 . 0 86 0 . 0 6 7 0 . 0 11 0 . 0 0 1 0 . 00 1 0 . 0 0 0 7 5 结论 本文提 出的用网格 法来构 成遗传算法的初 始群体 , 并 对其算法 的优 化效率进行 了定量评 价 , 最后将它和 基本 的遗传算法 ( SG A )一起应 用到 D e l o n g 的测试 函数 lF 上 , 评价结果 和 实 验结果表 明 , 该方法用于改进遗传算法时 , 可 以 加快 收敛 的速度 , 提高优化效率 , 该方法是可行 的 . 参 考 文 献 1 米 凯利维 茨 2 . 周 家驹 ,何险峰译 . 演化程 序一遗 传算 法和 数据 编码的结合 [M ] . 北 京 : 科学 出版社 , 2 0 0 2 郭立 新 , 李 成植 , 郑文利 , 等 . 遗传算法 在机 械优 化设 计中的应用 [J] . 机 械设计与制 造 , l9 9 9( l) : 43 3 高齐圣 , 潘德惠 . 基于均 匀设计的遗传算法 及其应 用 [ J ] . 信息与控制 , 1 9 9 9 , 2 8 ( 3) : 2 36 4 潘 正君 , 康立 山 , 陈毓屏 . 演化计算[M l . 北京: 清华大 学 出版社 , 1 9 98 5 uR d o lPh G . C o vn e gr e n e e A n al y s i s o f C an o n i e a l G e n e t i e A lg o ir t hm s [ J ] . IE E E T r an s o n N e u r a l N ewt o kr , 19 9 4 , 5 ( l ) : 8 6 6 林丹 , 李敏强 , 寇 纪淞 . 基于 实数 编码的遗传算法 的 收 敛性研究 [J] . 计算机研究与 发展 , 20 0 . 37 ( 11) :

VoL.24 高玉根等：基于网格法的遗传算法及其应用 363· 1321 ing MA,1989 7 DeJong K A.Analysis of the Behavior of a Class of Gen- 10周明，孙树栋.遗传算法原理及应用[M北京：国防 etic Adaptive Systems[D]:[Ph D thesis].Ann Arbor:Univ 工业出版社，1999 Michigan,1975 1张学良，黄玉美.遗传算法及其在机械工程中的应 8孙瑞祥，屈梁生.遗传算法优化效率的定量评价) 用).机械科学与技术，1997,16(1)：46,47 自动化学报，2000,26(4)：552 12 Pham D T,Karaboga D.Optimum Design of Fuzzy Logic 9 Goldberg D E.Genetic Algorithms in Search,Optimiza- Controllers Using Genetic Algorithms[J].J Sys Eng,1991 tion and Machine Learning[M].Addison Wesley:Read- (1):114 Genetic Algorithms Based on Grid and Its Application GAO Yugen2, WANG Guobiao DING Yuzhan 1)Civil and Environment Engineering School,UST Beijing,Beijing 100083,China 2)Shandong Institute of Technology,Zibo 255012,China ABSTRACT In Simple Genetic Algorithms(SGA),chromosomes are produced at random.In order to in- crease the popularity and diversity of individuals,a new genetic algorithms which produces chromosomes with grid is proposed,and its optimization efficiency is evaluated quantitatively.For comparision with SGA, the DeJong Function Flis used an example.Both results show that the new genetic algorithms with grid is valid for improving the optimal efficiency of genetic algorithms. KEY WORD genetic algorithms;grid;optimization algorithm 5堂望s6业es5s5理a6业ss堂ss2堂es堂SPosTenPenRonReoPesPes堂esee堂e理esa亚 Correlations Based on CFD and Their Applications in Optimization for Staggered and Parallel Plate Fin Heatsinks Jing Yang",Denpong Soodphakdee",Masud Behnia 1)Mechanical Engineering School,University of Science and Technology Beijing,Beijing 100083,China 2)School of Mechanical and Manufacturing Engineering.The University of New South Wales,Sydney 2052,Australia Abstract:Both parallel and staggered plate fin arrays have shown promise for use in high performance heat- sinks regard of its individual manufacturing costs.The geometrical and operational parameters are very im- portant to their cooling performance as heatsinks in practical applications.Fluent 5.0 commercial CFD(com- putational fluid dynamic)code is used to simulate the flow and heat transfer of those heatsinks of different realistic parameters.Based on those simulations,two correlations,concerning Nusselt number and friction factor as the functions of geometrical and operational parameters,FB(fin-base area ratio),PR'(ratio of span- wise pitch to lengthwise pitch)and Re,were developed.From the both,the performance comparisons for op- timizing geometrical and operational parameters of a fixed dimension heatsink are shown at constant pumping power and constant thermal resistance.Several optimized parameters were obtained with the discussion to various goals in real application.It demonstrates that in some particular situations,the parallel plate fin heat- sinks can out perform the staggered ones. Key words:fin heatsink;electronic cooling;CFD;optimization [Journal of University Science and Technology Beijing(English Edition)2002,9(1):25]

叭〕 1 . 2 4 高玉根 等 : 基 于 网格 法 的遗 传算 法及其 应用 . 3幻 . 13 2 1 D e j o ng K A . A na ly s i s o f ht e B e h va i o r o f a C l a s s o f G e n - e ti e A dpa t i v e Sy set m s [D ] : [ P h D ht e s i s ] . A n n A br o r: U ni v M i c h ig na , 1 9 7 5 孙 瑞祥 ,屈 梁生 . 遗传算法优化 效率的定量评价 [J] . 自动化学报 , 2 0 0 0 , 26 ( 4 ) : 5 5 2 G o ldb e gr D E . G e n at i e A l g o ir t hln s i n S e acr h , OP t而iaz - ti o n a n d M ac h ine L e am ing IM ] . A ddi s o n W 七s l e y : R e ad - i n g M A , 19 8 9 10 周明 , 孙树 栋 . 遗传算法 原理及 应用 【M ] . 北 京 : 国防 工业 出版社 , 19 9 1 张学 良 , 黄玉 美 . 遗传算法及 其在机 械工 程 中的应 用 [J] . 机 械科学 与技术 , 19 9 7 , 1 6 ( l ) : 4 6 , 4 7 1 2 P h am D T, K ar ab o g a D . O tP而 um D e s ign o f Fu Z y L o g i e C o ntr o ller s U s i gn G e n e ti e A l g o ir th m s [ J ] . J Sy s E n g , 1 9 9 1 (l ) : 1 1 4 G e n e t i e A l g o r lt h m s B a s e d o n G ir d an d It s AP P li e at i o n GA O h 心e n , , , ), 环二咬刃 G G u o b i a o l ), 石叹 N G h tz h a n , ) 1) C VI il an d Evn ior mn e in E n g in e ier n g S e h o o l , U S T B e ij ign , B e ij ing 1 00 0 83 , C h in a Z ) S h an d o gn nI st itU t e o f eT c h n o 1 o gy’ Z ib o 2 5 5 0 1 2 , C h in a ^ B S T R A C T I n S im Pl e G e n e t i e A l g o r it知m s ( S G A ) , `:址。 m o s o m e s aer Pr o du e e d at r an d o m · I n o r d e r t o i n - e er a s e ht e POP u l ar iyt an d d i v e r s iyt o f in d i v idu a l s , a n 。,w g e n e t i e a l g o r it h m s hw i c h rP o du e e s e hr o m o s o m e s w iht igr d 1 5 rP op o s e d , an d it s o Pt im i z at i o n e if e i e n e y 1 5 e v a l u a t e d q u a n t it at i v e l y . Fo r e o m Piar s i o n w iht S G A , ht e D e j o n g F un e it o n F 1i s u s e d an e x am P l e . B o ht er s u it s s h o w ht at ht e n e w g e ent i e a lg ior t h m s w iht 幼d i s v a lid fo r lm Por v ign ht e o tP im a l e if c i e n e y o f g e n e t i e a lg o ir ht m s . K E Y WO R D g e n e t i e a l g o r it h m s : gr id : op t im i z at i o n a lg o ir t知m C o r e l at i o n s B a s e d o n C F D an d T h e i r AP P li e at i o n s i n O P t im i z at i o n fo r S t ag g e r e d an d P ar a ll e l P l at e F i n H e at s i n k s iJ 雌 aY 叮 ` ), D e塑 。馆 oS o dP h a kde e , ), 入白 s u d B he n讨 l ) M e e h an i e al Egn ien e r l n g S e h o o l , U n i v e rs ity o f S e i e n e e an d eT e hn o l o gy B e ij in g , B e ij in g 1 00 0 83 , C h ina 2 ) S e h o o l o f M e e h an i e al an d M an u俪t u r i n g E n g i n e e ir n g , tT 一e nU i v e rs ity o f N e w s o u th W自l e s , S y dn 即 2 0 5 2 , A u s t r a 】l a A b s t r a c t : B hOt P ar ll e l an d s at g g er e d Pl at e if n ar ay s h va e s h o w n Por m i s e of r u s e i n h igh P e of rm an e e h e at - s ink s r e g ar d o f it s i n d i v id u a l m anu acf trU ign e o s t s . hT e g e o m ietr e a l an d op e art i o n a l Par am et r s ar e v ery im - Po rt ant t o ht e i r e o o li n g Pe r of rm an e e a s h e at s i n k s l n rP a e t i e a l ap Pli e at i o n s . F l u e in 5 . 0 e o nu e r e i a l C F D ( e o m - Put at i o n a l fl u id 勿n am i e ) e o d e 1 5 u s e d ot s im u l at e hte fl o w an d he at tr an s fe r o f ht o s e h e at s ink s o f d i fe r e nt r e a li st i c P arm e t e r s . B a s e d o n ht o s e s i mu l at ion s , wt o e o r e l at i o n s , e o n e e m ign Nu s s e lt n 叨m b e r an d 衍 e t i o n fa c t o r a s ht e fu n c t i o n s o f g e o m e t r l c a l an d op e r at ion al Par am e t e r s , FB ( if n 一 b a s e aer a art i o ) , P R ’ (art i o o f s Pan - w i s e Pit e h t o l e n ig h w l s e P ict h ) an d R e , w e r e d e v e lop e d . F r o m ht e b o ht , ht e P e r fo mr acn e c o m Piar s on s fo r op - t iln i z in g g e o m e itr c a l an d o Pe r at i o n a l P ar am e t e r s o f a ifx e d d im e n s i o n he at s ikn ar e s h o w n at e o n s加nL t P切m Pign P ow e r an d c on s t a n t het mr a l r e s i s t a n e e . S e v e ar l o Pt而i z e d Pa r a们。 e t e r s w e er Ob at ien d w iht ht e d i s e u s s i o n t o v ar i o u s g o a l s i n er a l ap Pli e at i o n . It d e m o n s t r a t e s ht at i r l s o m e P叭i e u lar s iut iat o n s , ht e Par a ll e l Plat e if n h e at - s i n k s e an o ut P e r fo mr ht e s t a g g e er d o n e s . K ey w o r d s : ifn h e at s i n k ; e l e e tr o n l c e o o li n g : C F D : o tP im i z at i o n O[J u r n al of nU i vesr i粉 cS ien c e a n d eT c h n o l o 舒 B e ij i n尔E n gl is h 君id t i o n ) 2 0 0 2 , 9 ( l ) ` 2 5 1