D0I:10.13374/j.issm1001-053x.2001.01.050 第23卷第1期 北京科技大学学报 Vol.23 No.1 2001年2月 Journal of University of Science and Technology Beijing Feb.2001 一种新的模糊遗传算法 李擎)郑德玲》唐勇)陈占英) 1)北京科技大学信息工程学院,北京1000832)冶金部自动化研究院,北京100071 摘要将模糊控制思想引人到遗传算法中,进行交叉概率P和变异概率P的整定工作,并 在此基础上提出了一种基于模糊控制的遗传算法一模糊遗传算法.仿真结果表明:该算法不 仅能提高解的质量,而且能加速解的收敛速度 关健词遗传算法;模糊控制;交叉概率;变异概率 分类号TP273.4 1P。,Pm采用模糊控制的必要性 为每代群体的平均适应度值;?为待交叉的2 个串中适应度较大的个体的适应度值:f为待变 遗传算法中的交叉概率P和变异概率Pm的 异串的适应度值. 合理选择将直接影响到遗传算法的收敛速度和 以上3条规则是人们在确定P。,P值时经 解的质量.在简单遗传算法SGA(Simple Genetic 常要用到的定性知识.在这3条规则中存在着 Algorithm)中,P.和P.值在整个遗传进程中保持 许多模糊概念(如(f-)“较大”,P。应取“较 不变,这使得遗传算法在应用过程中产生了一 小”的值等),而这些模糊概念又很难用传统的 些问题(如收敛速度慢、出现未成熟收敛现象 数学方法来度量.为了更好地处理规则中的模 等).目前,专家学者们认识到:如果P。,Pm值能 糊信息,我们认为有必要引人模糊控制技术,即 随着遗传进程而自适应地变化,那么这种有自 采用模糊控制方法来完成P。,P的确定过程. 组织性能的遗传算法将具有更高的鲁棒性、全 模糊控制器最基本的形式是1种称为“查 局最优性和更快的收敛速度,经过研究,人们已 询表”方式的模糊控制器),这种控制器将模糊 经提出了多种确定P。,P值的算法巴.虽然这些 控制规则转化为1个查询表,离散地将输人、输 算法的形式不同,但它们的基本控制思想是相 出之间的数值对应关系存储在计算机中.在实 同的,归纳起来有以下3条: 际应用过程中,人们可以根据输人量的大小,通 (1)当(f-f)较小时,说明f的值相对较大, 过查表直接确定所需的输出量,而不再进行模 为保证算法的稳定性,P和P应取较小的值;相 糊化、模糊推理,再到清晰化这一整套计算.该 反,当(f一f)较大时,说明f的值相对较小,为 方法大大减少了模糊控制过程的时间,具有结 加快算法的进程,P和Pm应取较大的值. 构简单、使用方便等特点 (2)当(”-刀较小时,P应取较大的值.这样 做的原因是为了淘汰进化过程中出现的劣质个 2基于模糊控制的遗传算法(FGA) 体;相反,当(-)较大时,P则应取较小的值. 2.1P。查询表的确定过程 这样做的原因则是为了防止适应度值高的优秀 (I)输人、输出变量的选择.为使FGA算法 个体在进化过程中遭到破坏. 具有更加广泛的适用性,将输人进行如下归一 (3)当(f-)较小时,Pm应取较大的值.之所 化处理:即令: 以这样做,也是为了淘汰适应度值低的个体;相 反,当(f-)较大时,P则应取较小的值.这样做 头在光 (1) 的原因同样是为了保护优秀个体 其中:f为每代群体中最小的适应度值 这里,fx为每代群体中最大的适应度值:了 经过以上变换,P查询表中的输入变成了 收稿日期:200006-18李肇男,29岁,博士 和f,经过归一化处理,FGA算法将适用于应用 *国家自然科学基金资助项目N0.69772014) 遗传算法的所有优化问题.为方便起见,我们将
第 23 卷 第 1期 2 0 0 1 年 2 月 北 京 科 技 大 学 学 报 JO u r n a l o f U n vi e rs tiy o f s e i e n e e a n d 介 c h n o le gy B e ji i n g 、 勺 1 . 2 3 N O 一 1 F e b 。 2 00 1 一种新的模糊遗传算法 李 擎 ” 郑德玲 ” 唐 勇 ” 陈 占英 2 , 1月匕京科技大学信息工程学院 , 北京 1 0 0 83 2胎金部自动化研究院 , 北京 10 0 0 71 摘 要 将模糊控制 思想 引入到遗传算法 中 , 进行交叉概 率只和变 异概率凡的整 定工 作 , 并 在此基础 上提 出了一种 基于模糊控制的遗传算法— 模糊 遗传算法 . 仿真结果表明 : 该算法不 仅能提高解 的质 量 , 而 且能 加速解的收敛速度 . 关键词 遗传算法 ; 模 糊控制 ; 交叉概率 ; 变 异概率 分 类号 T P 2 7 3 + . 4 I cP , mP 采用模糊控制 的必要性 遗传算 法 中的交叉 概率只和 变异概 率mP 的 合理选择将直接影 响到遗传算法 的收敛速度和 解 的质量 . 在简单遗传 算法 S G A (is mP le G en et ic lA g ior th n l ) 中 , cP 和mP 值 在整个 遗传 进程 中保持 不变 , 这使得遗传算法 在应用过 程 中产 生了 一 些 问题 (如收敛 速度慢 、 出现未成 熟收敛 现象 等 ) . 目前 , 专家学 者们认识到 : 如果 cP , mP 值能 随着遗传 进程而 自适应地 变化 , 那 么 这 种有 自 组织性 能的 遗传算 法将具 有更高 的鲁棒性 、 全 局最优性 和更快的收敛速度 . 经过研究 , 人们 已 经提 出了 多种确定 cP , mP 值 的算法 【1] . 虽然 这些 算法 的形式 不 同 , 但它们 的基本控 制思想 是相 同的 , 归纳起 来有 以 下 3 条 : ( l) 当以孤 男 一了)较小 时 , 说明又的值相对较大 , 为保证算法 的稳 定性 , cP 和mP 应取较小 的值 ; 相 反 , 当帆 公 一了)较 大时 , 说 哪的值相对较小 , 为 加快算法 的进程 , cP 和 mP 应取较 大的值 . (2 )当汀 ,一力较 小时 , cP 应取较 大 的值 . 这样 做的 原因是 为 了淘汰进化过程 中出 现的劣质个 体 ;相 反 , 当了 ,一力 较大 时 , cP 则应 取较小 的值 . 这样做 的原因则是为 了 防止适应度值高 的优秀 个体在进化 过程 中遭到破坏 . (3 ) 当了一力较小 时 , mP 应 取较 大的值 . 之所 以 这样做 , 也是为 了 淘汰适应度值 低的个体 ; 相 反 , 当了一力较 大时 , mP 则应取较小的值 . 这样做 的原 因 同样是 为 了保 护优 秀个 体 . 这 里 , 忘 为每 代群体 中最大 的适 应度值 了 收 稿 日期 : 2 0 0刁 -6 18 李擎 男 , 29 岁 , 博士 * 国家自然 科学 基金 资助 项目困 。 ` 6 9 7 7 20 14) 为每代群体 的平均适应 度值 ; f 为待交叉 的 2 个 串中适应度较 大的个体 的适应度 值 了为待变 异 串的适 应度值 . 以上 3 条规则是人 们在确定只 , mP 值 时经 常要用 到的定性 知识 . 在这 3 条 规则 中存在着 许多模糊 概念 (如帆 似 一f ) “ 较大 ” , mP 应取 “ 较 小 ” 的值等 ) , 而这些模糊 概念又 很难 用传统 的 数学方 法来度量 . 为 了更 好地处理规 则 中的模 糊 信息 , 我们认为有必要引人模 糊控制技术 , 即 采用模糊 控制方 法来完成 cP , mP 的确定过程 . 模糊控 制器最 基本 的形式 是 1 种称为 “ 查 询表 ” 方式 的模 糊控制器 `习 , 这种 控制器将模糊 控制规则转化 为 1 个查询表 , 离散地将输人 、 输 出之 间的数值对 应关 系存 储在计算机 中 . 在实 际应 用过程 中 , 人们可 以根据输人量的大小 , 通 过 查表 直接确定 所需 的输 出量 , 而不再进行模 糊 化 、 模 糊推理 , 再到清 晰化这一 整套计算 . 该 方 法大大 减少 了模 糊控制过 程 的 时间 , 具有结 构简单 、 使 用方便 等特点 . 2 基于模糊控制的遗传算法 (F G )A 2 . I cP 查询表的确定过程 ( 1) 输入 、 输 出变量 的选 择 . 为使 F G A 算法 具有 更加广 泛 的适用 性 , 将 输人进行 如下归一 化处 理 : 即令 : 厂 _ 玉虹立 - J a l _ [ j 口 . x J m in ( l ) 其 中 : fm , 为每代 群体 中最 小 的适应 度值 . 经过 以 上变换 , cP 查询表 中的输人变成 了大 和兀 , 经过归 一化处理 , F G A 算法将适用 于应用 遗传算法 的所有优化 问题 . 为方便起见 , 我们将 DOI: 10. 13374 /j . issn1001 -053x. 2001. 01. 050
●86· 北京科技大学学报 2001年第1期 输人变量记为FC和FA,输出变量记为PC 大).由于文中应用“查询表”方式的模糊控制 (2)输人、输出变量的语言值及其隶属度函 器,所以必须对输人、输出变量的论域离散化, 数的确定.经过(1)式的归一化处理:输人变量 离散后输人变量FC的隶属度函数可用表1加 FC的取值范围为(-1,1),即FC的基本论域 以描述. X=(-1,1).根据实际情况,将FC的语言值取为 同样,经过离散化处理后,输入变量FA和 8个,分别为ES(极小);VS(非常小);S(小);RS 输出变量PC的隶属度函数如表2和表3所示, (较小);M(中等);RB(较大);B(大);VB(非常 (3)模糊规则表的建立.根据前面的定性知 表1输入变量FC的隶属度函数4 Table 1 The membership function of the input variable FC f FC (-1,0)0 0.10.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 ES 1 0 0 0 0 0 0 0 0 0 0 0 VS 0 1 0.4 0 0 0 0 0 0 0 0 0 S 0 0 0.6 0.8 0.2 0 0 0 0 0 0 0 RS 0 0 0 0.2 0.8 0.6 0 0 0 0 0 0 M 0 0 0 0 0 0.4 1 0.4 0 0 0 0 RB 0 0 0 0 0 0 0 0.6 0.8 0.2 0 0 日 0 0 0 0 0 0 0 0 0.2 0.8 0.6 0 VB 0 0 0 0 0 0 0 0 0 0 0.4 1 注:表中“1.0”表示一个比1稍小一点的实数 表2输入变量FA的隶属度函数μ Table 2 Table 1 The membership function of the input variable FA 后 FA 0* 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 VS 1 0.4 0 0 0 0 0 0 0 0 0 0.6 0.8 0.2 0 0 0 0 0 0 RS 0 0 0.2 0.8 0.6 0 0 0 0 M 0 0 0 0.4 1 0.4 0 0 0 0 RB 0 0 0 0 0 0 0.6 0.8 0.2 0 0 B 0 0 0 0 0 0 0.2 0.8 0.6 0 VB 0 0 0 0 0 0 0 0 0.4 注:表中0”表示一个比0稍大一点的实数;“1.0”表示1个比1稍小一点的实数 表3输出变量PC的隶属度函数丛 able 3 The membership function of the ouput variable PC PC 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0° ES 0 0 0 9 0 0 0 0 0 VS 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 RS 0 0 0 0 0 0 0 0 0 SS 0 0 0 0 0 0 0 0 0 0 M 0 0 0 0 1 0 0 0 0 0 SB 0 0 0 0 0 1 0 0 0 0 RB 0 0 0 0 0 0 1 0 0 0 B 0 0 0 0 0 0 0 1 0 0 VB 0 0 0 0 0 0 0 0 1 0 EB 0 0 0 0 0 0 0 0 0 0 1 注:表中“1.0”表示待交叉个体进行交叉操作时,其交叉点位于第1,2位基因之间
8 6 . 北 京 科 技 大 学 学 报 2 0 01 年 第 1 期 输 人变量记 为 F C 和 AF , 输 出变量记 为 P C (2 ) 输人 、 输 出变量 的语 言值及其隶 属度 函 数的确定 . 经过 ( l) 式 的归一化处理 : 输 人变量 F C 的取 值范 围为 卜 1 , 1) , 即 F C 的基本 论 域 X = ( 一 l , 1) . 根 据实 际情 况 , 将 F C 的语 言值取为 8 个 , 分 别为 E S ( 极小 ) ; V S ( 非 常小 ) ; S ( 小 ) ; R S ( 较小 ) ; M ( 中等 ) ; RB ( 较 大 ) ; B ( 大 ) ; V B ( 非 常 大 ) . 由于文 中应用 “ 查询表 ” 方式 的模糊控制 器 , 所 以必须对 输人 、 输 出变量 的论域离散化 , 离散后 输人变量 F C 的隶属度 函 数可 用表 1 加 以描述 . 同样 , 经过离散化 处理后 , 输 入变量 FA 和 输 出变量 P C 的隶属度 函 数如表 2 和 表 3 所示 . (3 ) 模糊 规则表 的建立 . 根据前 面 的定性知 表 1 输入 变 t F C 的隶 属度 函 数 产 aT b l e 1 T h e m e m b e r s h i P fu n ict o n o f t h e i n P u t v a ir a b l e F C E S n ē1 ù on 0 ù 0 n ù 0 0 ù 0 0 nUO ù 0 0 0 0 . 4 0 . 6 0 0 . 8 0 . 2 0 . 2 0 . 8 0 . 6 o0 n à 1 0 00 .064 0 0 .028 0 0 .082 0 .046 I 0 C ù 00 ” 0 nU一U Vs 5 sRMBR B V B 0 0 0 0 0 U U U U U U . 0 4 1 . 4 注 : 表 中 ` ,l . 0 一 ” 表示一 个比 1稍 小一 点的实 数 表 2 输入 变 t F A 的 隶属 度 函数 产 介 b le 2 aT b l e 1 T h e m e m b e sr h iP fu n e ti o n o f t h e i n P u t v a ir a b l e F A V S 0 . 4 0n 0 0 nU n O ù 1 0 . 6 0 . 8 0 . 2 0 . 8 n ù 0 ù U n ù n 0 . 6 0 . 4 0 . 4 0 . 6 0 . 8 0 . 2 0 . 2 ù且n ù 0 0 n nU 0 . 2 0 0 nU nn O ù ù 00 sRMBR 0 . 8 0 . 6 V B 0 0 0 0 0 0 0 0 0 0 . 4 1 注 : 表中 ` ,0祖 表示 一个 比 O稍 大一点 的 实数 ; “ 1 . 0 一” 表示 l 个比 1稍 小一点 的实 数 表 3 输出变 t P C 的隶 属度 函 数 产 a b l e 3 T h e m e m b e sr hiP fu n e tot n o f th e o u P u t v a ir a b l e P C E S V S 0 1 0 0 0 0 0 0 0 0 0 5 0 0 1 0 0 0 0 0 0 0 0 R S 0 0 0 1 0 0 0 0 0 0 0 5 5 0 0 0 0 1 0 0 0 0 0 0 M 0 0 0 0 0 1 0 0 0 0 0 SB 0 0 0 0 0 0 1 0 0 0 0 R B 0 0 0 0 0 0 0 1 0 0 0 B O 0 0 0 0 0 0 0 1 0 0 V B 0 0 0 0 0 0 0 0 1 0 E B 0 0 0 0 0 0 0 0 0 0 1 注 : 表 中’,l . ’0 ” 表示待交叉个体进行交叉操作 时 , 其交叉点位于第 1 , 2 位基 因之间
VoL23 No.1 李整等:一种新的模糊遗传算法 87· 识以及本人在确定P。值时得到的体会,对查询 则X,Y,Z上的模糊集可分别用1个12,11,11维 表中用到的模糊规则进行了总结,共得到了35 的模糊向量加以表示,而描述模糊35条控制规 条规则,如表4所示. 则的模糊关系R是一个12×11行11列的矩阵. 表4P查询表所对应的模糊规则表 (5)清晰化算法的确定.在这里,采用最大 Table 4 Fuzzy rules of the P.inquiry table 隶属度法进行清晰化计算.若输出模糊语言值 FC 向量中只有1个最大值,则取对应于该最大模 FA ES VS S RS M RB B VB 糊语言值的精确值作为清晰量(因为输出语言 VS ES ES 一 值对应的模糊集为单点模糊集).若输出模糊语 ES ES 言值向量中有多个最大值,则取对应于这些最 RS SS ES ES 大模糊语言值精确量的平均值作为清晰量. M EB SB M RS ES ES (6)控制(查询)表的建立.根据前面介绍的 RB B RB SS VS ES ES ? 模糊化、模糊推理以及清晰化算法,对X,Y中 VB B SB RS ES ES VB EB VB B M RS S ES 元素的所有组合全部计算出相应的P值,就得 注:-表示此处规则不存在 到了表5所示的P控制(查询)表. 这些规则可写成下列条件语句形式: 表5P控制(查询)表 如果FC是A,和FA是B那么PC是C. Table 5 P.control(inquiry)table 其中:i=1,2,…,8;j=1,2,…,7;0≤i-j≤2;AB,Cg 是定义在FC,FA,PC论域X,Y,Z上的模糊集. f1,000.10.20304050.607080910 由于天-天=会去,所以-人e0训, 0 0- 0.1 0.20 结合前面所定义的输人、输出变量的隶属函数, 0.2 0.200 一 经过分析可知模糊规则表中某些位置上的C, 0.3 0.40.20.20 (-23)不存在,它对应于表4中划“-”的部分 0.4 0.40.20.20 0 0.51.0°0.60.50.50.30.30 (4)模糊推理算法的确定.我们采用MN- 0.6 0.80.70.70.40.40.10 MAX法作为模糊推理合成算法.以上35条规 0.7 0.80.70.70.40.40.100 则最终可以用一个模糊关系R进行描述,即: 0.8 0.90.80.80.60.60.30.20.20 R=UA×BXCy, 0.9 0.90.80.80.60.60.30.20.200- (i=1,2,…,8;j=1,2,,7;0≤i-j≤2) (2) 1.0 1.0°0.90.90.70.70.50.40.40.20.20 R的隶属函数为: 注:一表示没有这种情况出现 4(f,f,P)=Y4(f)A4af)Λ4e(P)(3) 2.2Pm查询表的确定过程 8盐 式中,方∈X,f∈Y,P.∈Z 同理,令: 当输人变量FC,FA分别取模糊集A,B时, (6) 输出变量PC的语言值可根据如下模糊推理合 可以仿照P控制(查询)表的生成过程得到 成算法得到: P控制(查询)表6. PC=(AxB)oR (4) 2.3FGA算法的收敛性问题 PC的隶属函数为: 关于FGA算法的收敛性,给出如下定理 urc (P.)=v ur(ff P)uf )nu(f (5) 定理1:FGA是全局收敛的 设输入、输出变量经过离散化处理后的论域 证明:当'=f时,由(1)式可知,f=6,此 为: 时查表得到的P。=O; X={(-1,0),0,0.1,0.2,0.3,0.4,0.5,0.6,0.7, 当f=f时,由(1)式可知,=,此时查表 得到的Pm=0. 0.8,0.9,1.0; Y={00.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0-} 因此,在任意时刻飞,状态A()中对应于最大 Z={0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0; 适应度值f的最优个体将不参与交叉、变异操 作,即FGA能将进化过程中发现的最优个体进
V b L2 3 N O 一 l 李擎 等 :一 种新 的模糊遗 传算 法 . 8 7 . 识 以及 本人在 确定 Pc 值 时得到 的体会 , 对 查询 表 中用 到 的模糊 规则进行 了 总结 , 共得 到 了 35 条规则 , 如表 4 所示 . 表 4 cP 查询 表所 对应 的模糊规 则 表 aT b le 4 F u z z y r u les o f t h e cP i n q u i yr at b l e F C F A 一 E S V S 5 R S M RB B V B sRsEsEs sE一SE s sE一 sE一VsSR sEsRsB sEM5BR B sE VB 55 sB B E B Vs 5 sRMBR B V B V B E B 注 : 一 表示此处规则不 存在 则X , Y , Z 上 的模糊集 可分别用 1 个 1 2 , n , n 维 的模 糊 向量加 以 表示 , 而描述模糊 35 条控制规 则 的模糊关系 R 是一 个 12 xl l 行 n 列 的矩 阵 . ( 5) 清晰化算 法的确定 . 在这里 , 采 用最大 隶属 度法进 行清 晰化 计算 . 若 输 出模糊语 言值 向量 中只有 1 个 最大值 , 则 取对应 于该最 大模 糊语 言值 的精 确值作 为清晰量 (因为输 出语 言 值对应 的模 糊集为单点模糊 集 ) . 若输 出模糊语 言值 向量 中有 多个最大值 , 则 取对应于 这些最 大模糊语 言值 精确量 的平 均值作 为清晰量 . (6 ) 控制 (查询 )表的建立 . 根据前面介绍 的 模糊化 、 模 糊推理 以 及清 晰化 算法 , 对 x , Y 中 元素 的所 有组合 全部计算 出相应 的cP 值 , 就得 到了 表 5 所示 的cP 控制 (查 询)表 . 这些 规则可 写成下列 条件语句形 式 : 如果 F C 是 A ` 和 FA 是 Bj 那 么 PC 是 q . 其 中 : i = 1 , 2 , … , ;8 j = 1 , 2 , … , ;7 0 夕一` ;2 法 , 马 , q 是定义 在 F C , FA , P C 论域 X , Y , Z 上 的模 糊集 . 山 二 厂 _ , _ 五生二乙 . 。 ; , 、 , , _ , 一 「八 们 由 于石一 关 = 尹牛拭卜 , 所 盯 一 关 E 〔0, 1] , 囚 “ “ “ J “ 忘 一 瓜 ’ ,/ , W . J O c L一 ’ 结合前面所定义的输入 、 输出变量的隶属 函数 , 经过 分 析可 知模 糊 规则 表 中某 些 位 置上 的 q i( 一 j 全 3) 不存在 , 它对应于表 4 中划 “ 一 ” 的部分 . ( 4 ) 模糊推理 算法 的确定 . 我们 采用 M刀平 M A X 法作为模糊 推理合 成算法 . 以上 35 条规 则最终可 以用 一个模糊关系 R 进行 描述 , 即 : 表 S cP 控制 (查 询 )表 aT b le 5 cP e o n tor l ( in q u iyr ) t a b l e 关 0 . 1 0 . 2 0 . 3 0 . 4 0 . 5 0 6 0 . 7 0 . 8 0 . 9 1 . 0 0 ) 0 0 0 . 2 0 0 . 2 0 R = u A ` x 尽 x q , , J i( = 1 , 2 , … , ;8 j = 1 , 2 , … , ;7 0 系 一 j ` 2) (2 ) 0 . 4 0 . 2 0 . 2 0 0 . 4 0 . 2 0 2 0 0 . 0 . 6 0 . 5 0 . 5 0 . 3 0 . 8 0 . 7 0 . 7 0 . 4 0 . 8 0 . 7 0 . 7 0 . 4 0 . 9 0 . 8 0 . 8 0 . 6 0 . 9 0 . 8 0 . 8 0 . 6 1 . 0 . 0 . 9 0 . 9 0 . 7 0 一 一 一 _ _ _ 0 . 3 0 一 一 一 一 一 0 . 4 0 . 1 0 一 一 一 一 0 . 4 0 . 1 0 0 一 一 一 0 . 6 0 . 3 0 . 2 0 . 2 0 一 一 0 . 6 0 . 3 0 . 2 0 . 2 0 0 一 0 . 7 0 . 5 0 . 4 0 . 4 0 . 2 0 . 2 0 ,1 2 凡j … OC ù 0 8 ? 0 1 R 的隶属函 数 为 : 脚 以 沂 只) = 注 : 一表 示没有这种情况 出现 卜慕 ,产认 ) A肉以 ) A “ 。 c(P ) ( 3 ) ` 了一` 2 式 中 ,不 任 X, 不 任 Y, cP E .Z 当输人 变量 F C , FA 分别取 模糊集 A , B 时 , 输 出变量 P C 的语 言值可根 据如下模 糊推理 合 成算法得 到 : .2 2 mP 查询表的确定过程 同理 , 令 : 子 = 一 工上工一 J m 了 _ 了 J ~ 一 J m in ( 6 ) P C = (A x B) o R PC 的隶属 函 数 为 : 产cP c(P ) = _ v _ 脚以 抓 只)八脚以 )人脚伏 交霆李 设输 入 、 输 出变量 经过离散 化处理后 的论域 为 : X = { (一 1 , 0 ) , 0 , 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 , 0 . 5 , 0 . 6 , 0 . 7 , 0 . 8 , 0 . 9 , 1 . 0 一 } : Y= { 0 + , 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 , 0 . 5 , 0 . 6 , 0 . 7 , 0 . 8 , 0 . 9 , 1 . 0 一 } Z 二 { 0 , 0 . 1 , 0 . 2 , 0 . 3 , 0 . 4 , 0 . 5 , 0 . 6 , 0 . 7 , 0 . 8 , 0 . 9 , 1 . 0 * } : 可 以 仿 照cP 控制 (查询 )表 的生成过 程得到 mP 控 制 (查询 )表 .6 .2 3 F G A 算法的收敛性问题 关 于 FG A 算法 的收敛 性 , 给 出如 下定理 . 定 理 1 : F G A 是全 局收敛 的 . 证 明 : 当 f’ = 儿 公 时 , 由 ( l) 式可知 沂 二 关 , 此 时查表得 到的cP 二 ;0 当厂二 儿 盯 时 , 由( l) 式 可知 沂 = fm , 此时查表 得 到的mP = .0 因此 , 在任 意时刻 k , 状态双k) 中对应于 最大 适应度 值关 奴 的最优个体将不 参与交叉 、 变异操 作 , 即 F G A 能将进化 过程 中发现 的最优个体进 ó 、 了、户. 4 ù 了、J .、才了
·88- 北京科技大学学报 2001年第1期 行保存 针对以上函数,我们选用30位二进制编码, 表6P控制(查询)表 每个变量10位.x=-5.12对应着10位二进制码 Table 6 P.control (inquiry)table 串全为0的情况,x=5.12对应着10位二进制码 串全为1的情况.群体规模N取为50.采用SGA, (-1,0)00.10.20.30.40.50.60.70.80.91.0 OMSGA时,P取为0.6,Pm取为0.1. 0 0一- 为了更好地说明问题,便于对各种算法进行 0.1 0.10-- 比较,我们还使用了Srinivas和Patanik提出的自 0.2 0.100- 适应遗传算法AGA(Adaptive Genetic Algorithm) 0.3 0.10.10.10- 对(T)式进行优化,AGA算法确定P.,Pm的数学表 0.4 0.10.10.100- 0.50.50.20.20.20.10.10-- 达式如下: 0.6 0.30.30.30.10.10.10- P=kC.-f-刀r≥7 fO,所以我们可以得出结论:FGA也是 种算法.此外,应用FGA算法进行优化时,子在 全局收敛的 2.4FGA算法的应用实例 前半程的增长速度比后半程的增长速度快一些, 这恰恰符合查询表中P.,P值的分布情况,即前 我们以经常被国内外学者用于优化测试的 半程较小,f较大,P。,P取较大值,所以于的 函数Fx): Fx)= 增长速度快一些;而后半程子较大,£较小,P。, (-5.12≤x≤5.12) (7) m1 P取较小值,所以手的增长速度慢一些. 以最大值的确定为例来讨论FGA算法是否具有 表8中f,GEN,T的意义如前所述.由表 优越性. 可以看出:除SGA算法外,其他3种算法均收敛 表74种算法对x)优化时∫随进化代数的变化情况 Table 7 The variety of f at different evolutionary generation T GEN 15 30 45 60 75 90 105 120 135 SGA 35.76 43.63 51.82 49.35 57.01 63.52 65.64 60.34 67.87 OMSGA 39.96 46.53 43.18 50.39 58.72 66.23 59.70 68.58 71.36 AGA 40.36 49.28 52.49 56.17 53.68 61.33 67.74 71.22 74.56 FGA 51.63 63.48 67.27 69.73 73.57 73.03 73.99 75.06 75.84 表84种算法对F(x)优化时扩随进化代数的变化情况 Table 8 The variety offat different evolutionary generation T GEN 15 30 45 60 75 90 105 120 135 SGA 63.76 66.85 70.62 61.25 66.71 69.38 76.39 71.05 67.26 OMSGA 66.36 69.53 69.53 69.53 77.03 77.03 77.03 77.03 78.64 AGA 57.65 70.14 70.14 70.14 71.35 74.57 78.64 78.64 78.64 FGA 60.86 67.86 75.38 78.64 78.64 78.64 78.64 78.64 78.64
. 88 . 北 京 科 技 大 学 学 报 2 0 0 1 年 第 l 期 行保存 . 表 6 mP 控 制 (查 询) 表 aT b l e 6 几 co n t or l ( in q u i口) at b le ( 一 1 , 0 ) 0 0 . 1 0 . 2 0 . 3 儿 0 . 4 0 . 5 0 . 6 0 . 7 0 . 8 0 . 9 1 . 0 - 、 , 0 了了 09 了ù 、.了吸、 cmPP +0 0 一 一 一 一 一 一 一 一 一 一 0 . 1 0 . 1 0 一 一 一 一 一 一 一 一 一 .0 2 0 . 1 0 0 一 一 一 一 一 一 一 一 .0 3 0 . 1 0 . 1 0 . 1 0 一 一 一 一 一 一 一 .0 4 0 . 1 0 . 1 0 . 1 0 0 一 一 一 一 一 一 0 . 5 0 . 5 0 . 2 0 . 2 0 . 2 0 . 1 0 . 1 0 一 一 一 一 一 0 . 6 0 . 3 0 . 3 0 . 3 0 . 1 0 . 1 0 . 1 0 一 一 一 一 0 . 7 0 . 3 0 . 3 0 . 3 0 . 1 0 . 1 0 . 1 0 0 一 一 一 0 . 8 0 . 4 0 . 3 0 . 3 0 . 2 0 2 0 . 1 0 . 1 0 . 1 0 一 一 0 . 9 0 . 4 0 . 3 0 . 3 0 . 2 0 2 0 . 1 0 . 1 0 , 1 0 0 一 1 . 0 · 0 . 5 0 . 4 0 . 4 0 . 3 0 , 3 0 . 2 0 . 1 0 . 1 0 . 1 0 . 1 0 注 : 一 表示没有这种情 况 出现 所 以 , 可 以 认为 , F G A 事 实上就是具 有另外 一种表 现形式 的 O M S G A (叩t im um m a 五it a i n l n g s 而p l e g e n iet e a l g o ir ht m ) 【, , , 由文献 〔l] 可 知 , O M S G A 是全局 收敛 的 . 同 时 由于尸 > O , 所 以 我们 可以 得 出结论 : F G A 也是 全局收敛 的 . .2 4 F G A 算法的应用 实例 我们 以经 常被 国 内外学 者用于优 化测试的 函数声飞未) fl2 : 针对 以 上函 数 , 我们选用 30 位二进制 编码 , 每个 变量 10 位 . 戈 = 一 5 . 12 对应着 10 位 二进制码 串全 为 O 的情况 , xt = 5 . 12 对 应着 10 位 二进制码 串全 为 1 的情况 . 群体 规模刀取 为 50 . 采用 s G A , O M S G A 时 , cP 取为 .0 6 , mP 取为 0 . 1 . 为 了更好地说 明问题 , 便 于对各种算法进行 比较 , 我们 还使用 了 S irn iv as 和 p a 加nL 议 提出的 自 适应遗传算 法 4[] A G A (A d a p it ve G e en ict lA g ior t加rn ) 对 (7 )式 进行优化 , A G A 算法确定cP , mP 的数学表 达式如下 : 一 {之呱 - 一 {之呱 - 其 中 : k , = 棍“ 1 ,鹅 = 瓜 优化 结果如 表 7 一 力 f , 七 了 f ` < f 一 力 f 七 了 f < f 5 . , 表 8 所示 . 表 7 中 f 的意 尸以 毖 ) 二 艺对 ( 一 5 . 12 簇 为 ` 5 . 12 ) ( 7 ) 以最大值 的确定 为例来讨论 F G A 算法是否 具 有 优越性 . 义如 前所述 , G E N 表示 进化代数 , T (巧 p e )表示 算法 的种类 . 由表 7 可以看 出 : 在相同的进化代数下 , FG A 算法 的值 比其他 3 种算法 的值要 大一些 , 这说 明 F G A 算法 的收敛性 ( 解 的质 量 )确 实高于 其他 3 种算法 . 此 外 , 应 用 F G A 算法进 行优化 时 J 在 前半程 的增长 速度 比后半程 的增长速度快一些 , 这恰恰符合 查询表 中cP , mP 值 的分 布情况 , 即前 半程了较小 , 关较 大 , cP , mP 取较大值 , 所 以 了的 增 长速度快 一些 ; 而后 半程 了较大 , 不较小 , cP , mP 取较小值 , 所 以 了的增长 速度慢一些 . 表 8 中儿 . , G NE , T 的意义如前所述 . 由表 可 以 看 出 : 除 S G A 算法外 , 其 他 3 种算法 均收敛 表 7 4 种 算法 对尸以)优 化 时了随进化 代数 的 变化 情况 aT b le 7 T h e v a r i e yt o f f a t d i月免er n t ve o lu it o n a yr g e n e ar t i o n G E N T 一 15 30 4 5 60 7 5 9 0 1 0 5 1 2 0 13 5 4 7147567 8436587 0 2 ù`内jf, . `U . 0 … 气081 à 6 7t了 2 657973 74609 内j丹j , à ō、 ù`,j 636173 o 一月n 了`二,R 矛, 咤6 ù . … 7 八0 ù I 内」J 勺ùō、` à à气 ,了 9 1/ 内 凡 j `é内J, 1 SG A 49560 7 O M SG A A G A F G A 3 5 . 7 6 4 3 . 6 3 3 9 . 9 6 4 6 . 5 3 4 0 . 3 6 4 9 . 2 8 5 1 . 6 3 63 . 4 8 5 1 . 82 4 3 . 18 5 2 . 4 9 6 7 . 2 7 表 8 4 种算法对尸以)优化 时凡 万 随 进化 代数 的变 化情 况 介b le 8 T h e v a ir e yt o f 忘 a t d l月免er n t ve o l u iot n a yr g e n e r a iot n T 一 15 3 0 4 5 6 0 7 5 90 105一120 13 5 SG A 6 3 . 7 6 6 6 . 8 5 7 0 . 62 6 1 . 2 5 6 6 7 1 6 9 , 38 7 6 . 39 7 1 . 0 5 6 7 . 2 6 O M SG A 6 6 . 3 6 69 . 5 3 6 9 . 5 3 6 9 . 5 3 7 7 . 0 3 7 7 . 0 3 7 7 . 0 3 7 7 . 03 7 8 . 6 4 A G A 5 7 . 6 5 7 0 . 14 7 0 . 1 4 70 . 14 7 1 . 3 5 7 4 . 5 7 7 8 . 6 4 7 8 . 6 4 7 8 . 64 F G A 60 . 8 6 6 7 . 8 6 7 5 . 3 8 7 8 . 64 7 8 . 64 7 8 . 6 4 7 8 . 6 4 7 8 . 6 4 7 8 . 6 4
Vol.23 No.1 李整等:一种新的模糊遗传算法 89· 到了全局最优解,但3者收敛到了全局最优解的 加快收敛速度 进化代数有所不同.根据我们记录的数据,OM 参考文献 SGA需要133代,AGA需要96代,而FGA仅需要 54代.这说明了FGA算法的收敛速度确实较快. 】恽为民.遗传算法的全局收敛性和计算效率分析. 控制理论与应用,1996(4):455 3结论 2陈国良,王煦法,庄镇泉,等.遗传算法及其应用. 北京:人民邮电出版杜,1996 经过以上的理论分析和实例验证,我们可以 3窦振中.模糊逻辑控制技术及其应用.北京:北京 航空航天大学出版社,1994 得出以下2点结论: 4 Scrinvas M,Patnaik L M.Adaptive Probabilities of (I)FGA算法是一种具有全局收敛性的遗传 Crossover and Mutation in Genetic Algorithms.IEEE 算法. Trans SMC,1994,24(4):656 (2)FGA算法不仅能提高解的质量,同时还能 A New Kind of Fuzzy Genetic Algorithm LI Qing,ZHENG Deling,TANG Yong,CHEN Zhanying" 1)Information Engineering School,USTBeijing,Beijing 100083,China 2)Automation Research Institute of the Ministry of Metallurgical Industry,Beijing 100071,China ABSTRACT The fuzzy control method is mixed into the genetic algorithm to adjust the probabilities of crossover and mutation.A new improved genetic algorithm named the fuzzy genetic algorithm(FGA)is pro- posed.Simulation results show that FGA is very efficiency for the quality of the solution is improved and the convergent speed of the solution is accelerated. KEY WORDS genetic algorithm;fuzzy control;crossover probability;mutation probability
V b】 一 2 3 N 0 . 1 李 擎等 : 一种 新 的模糊 遗传 算法 . 8 , . 到 了全局最优 解 , 但 3 者收敛到了 全局最优解 的 进化代数有 所不 同 . 根据 我们记 录的数据 , O M - S G A 需要 13 代 , A G A 需要 % 代 , 而 F G A 仅需要 54 代 . 这说 明了 F G A 算 法的收敛速 度确实较快 . 3 结论 经 过 以上 的理论分析 和实 例验证 , 我们可以 得 出以 下 2 点结 论 : ( 1) F G A 算 法是一种 具有全局 收敛性 的遗传 算法 . (2 )F G A 算法不仅能提高解 的质量 , 同时还 能 加快 收敛速度 . 参 考 文 献 l 挥 为民 . 遗传算法 的全局 收敛性 和计算效率分析 . 控制理论与应用 , 19 % (4 ) : 4 5 2 陈国 良 , 王 煦 法 , 庄镇泉 , 等 . 遗传算法及其应用 . 北京 : 人 民邮电 出版社 , 19 % 3 窦振 中 . 模糊逻 辑控制技 术及其应用 . 北 京 : 北京 航空 航天大学 出版社 , 19 94 4 S c n n v as M , P川匕a让 L M . A d atP i v e P r o b a bl lit e s o f C r o s s vo er an d M Uat i o n in G e n e t i e A lg o ir ht m s . IE E E 肠斑” S M C , 199 4 , 24 ( 4) : 6 56 A N e w 兀n d o f F uz yZ G e n e t i e A l g o ir t h m LI Qign 伙 Z月E N G eD lign l), AT N G oY gn 伙 C月 E万 hZ a 即止心 , 1刀刘比mr 毗on E n g in e ir n g s c h o l , U S T B e ij in g s B e ij ign l X() 0 8 3 , C玩匕a 2 ) A u t o m at ion R e s e ar c h I n s tiot t e of ht o M in 抬 ytr of M e因I也乡喇 玩d us 匀i B iej 吨 10 0 71 , C h in a A B S T R A C T hT e fu 乙守 e o n tr o l m e ht o d 1 5 m ix e d int o het g e n e t l c a lg o ir ht m ot adj us t ht e Pr o b ab ilit e s o f c r o s s o V e r an d m u t a t i o n · A ne w l m p r o v e d g e n et i e a l g ior Ul l l l nam e d ht e fu Z y g e n e t i c a l g o ir ht m (F G A ) i s nor - P o s e d . S iln u l at ion r e su lt s s h ow ht at F G A 1 5 ve yr e if e i e n cy for ht e ql 坦11yt o f ht e s o lut i o n 1 5 加P r o v e d an d het c o n v e r g e n t sP e e d o f ht e s o l iut on 1 5 a e e e ler aet d . K E Y W O R D S g en it o al g ior t hm ; 九z 叮 c o n tr o ;l cor s vo er Pr o b ab il iyt ; m ut at l on Pr o b ab il iyt