维普资讯 http://www.cqvip.com 第２４卷第１期 ２００７年３月 广东工业大学学报 Ｊｏｕｒｎａｌ ｏｆ Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ Ｖｏ１．２４ Ｎｏ．１ Ｍａｒｃｈ ２００７ 基于贝叶斯网络下的遗传算法 陈锡枢 （肇庆学院数学系，广东肇庆５２６０６１） 摘要：概率推理的基础是贝叶斯理论，它允许对任意的概率陈述作反向推导．利用概率论中的定理，将贝叶斯理论 移植到遗传算法上，拓展了遗传算法的应用范围． 关键词：概率；贝叶斯理论；遗传算法 中图分类号：ＴＰ１８ 文献标识码：Ａ 文章编号：１００７—７１６２（２００７）０１－００１９－０３ 引言 且Ｕ．Ｂ ＝ｎ，若Ｐ（Ｂ ）＞０， １，２，…，ｎ，则对任一事 目前遗传算法所涉及的主要领域有自动控制、 件Ａ有 组合优化、图像处理、信号处理、人工生命、机器学 Ｐ（Ａ）＝∑Ｐ（Ｂ ）Ｐ（Ａ ｌＢｉ）． 习、交通运输、设备布局、车间调度、进化神经网络、 模糊模式识别、多目标优化、模糊优化、可靠性设计、 引理３（贝叶斯公式 ） 设 ， ，…， 是样 网络设计与路径问题等许多更新、更工程化的应用． 本空间ｎ的一个分割，即 ， ，…， 互不相容， 研究热点主要集中在收敛性证明、新型高效的遗传 且Ｕ．Ｂ ＝ｎ，若Ｐ（Ａ）＞０，Ｐ（Ｂ ）＞０， １，２，…，ｎ， 算子设计、遗传算法与局部优化算法的结合、遗传算 则 法在各领域的应用研究、软计算与计算智能中的遗 传算法．但在人工智能的研究中，往往有成千上万个 Ｐ（Ｂ ｌＡ）： ， １，２，…， ， 变量，每个变量又以不可预测的方式影响其他的变 Ｐ（ ）Ｐ（Ａ｝ ） 量，若每个变量以一般的选择、交叉、变异的遗传操 特别地，当凡＝１时，有Ｐ（Ａ｝ ）＝ ． 作，是不可能实现优化的．本论文以贝叶斯网络按概 率传播方法，将群体（问题的解）一代一代地优化和 推理，并逐渐逼近最优解．这样，既保持遗传算法的 ２贝叶斯网络 优点，又能对不确定性命题进行推理和搜索，拓展了 ２．１贝叶斯理论简介 遗传算法． 概率推理的基础是贝叶斯理论，它允许对任意 １ 基本原理 的概率陈述作反向推导． 例如，当看到屋外的草坪是湿的，想知道昨天是 引理１（条件概率） 设事件 的概率Ｐ（ ）＞ 否下雨了，而现在仅仅知道如果昨天下雨了，今天的 ０，则在事件Ｂ已发生的条件下事件Ａ的条件概率 草坪是湿的概率，贝叶斯理论则可以帮助从已知的 等于事件ＡＢ的概率除以事件 的概率所得的商： 知识反向推导了未知的结论． Ｐ（Ａ Ｉ Ｂ）： ． 若Ａ表示事件“昨天下雨”； 表示事件“草坪 是湿的”； ｌＡ表示事件“在Ａ事件发生的前提下， 推论１：Ｐ（ＡＢ）＝Ｐ（Ａ ｌ）Ｐ（ ）＝Ｐ（Ｂ ｌ Ａ）Ｐ（Ａ）． 事件发生”，即 ｝Ａ表示“如果昨天确实下雨了，今 推论２：当事件Ａ、 相互时， 天的草坪是湿的”． Ｐ（ＡＢ）＝Ｐ（Ａ｝ ）Ｐ（ ）＝Ｐ（Ａ）Ｐ（ ）． 引理２（全概率公式¨ ） 设 ， ，…， 是样 由贝叶斯理式Ｐ（Ａ Ｉ Ｂ）： ， 本空间ｎ的一个分割，即 ，， ，…， 互不相容， 可以从条件概率Ｐ（Ｂ｝Ａ）以及事件Ａ和 发生的概 收稿日期：２００６ ０９—１５ 基金项目：广东省自然科学基金（０４３００１６７） 作者简介：陈锡枢（１９６３．），男，讲师，主要研究方向为计算智能 维普资讯 http://www.cqvip.com 广东工业大学学报 第２４卷 率Ｐ（Ａ）和Ｐ（Ｂ）得到Ｐ（Ａ ｌ 的概率值． Ｐ（Ａ ｆ 表示“表示在发生日事件的前提下，Ａ 事件发生的概率”，即表示“草坪已经湿了的情况 下，昨天下雨的概率．” 可见，这一反向推理特征，极大地帮助了在贝叶 斯网络中进行类似人类的推理活动． ２．２贝叶斯网络 中的０．０１０ ９５９的物理意义是：在任何一天中，报警 系统拉响的概率是０．０１０ ９５９．“数据２”的物理意 义是“报警”被拉响的条件下事件组的概率，由引理 ３（贝叶斯公式）算出（例如：０．００９ ３８１／０．０１０ ９５９＝ ０．８５６ ００９），表１中“１”表示该列所有的数值相加． ２．３结果分析 当警报被拉响的时候，即使不知道是由于地震 还是由于人室盗窃所引起的，仍然可以肯定，有 给定一系列命题及它们之间的因果关系（用 “ ”导致“ ”的形式），可以将其表示为图的结构， 并在图上进行概率推理，并称该结构为贝叶斯网络． 例如，当你工作的时候，接到邻居电话，告诉你 们家的防盗铃响了．而凑巧的是，你知道防盗系统除 了窃贼外，在发生地震的时候也会报警．当然，可以 认为是地震，而不是窃贼触发防盗铃． 给出３命题组成的贝叶斯网络，如图１，从图中 可以明显地看出“入室盗窃”和“地震”都能触发 “警报”． 图１贝叶斯网络 首先计算发生地震或者入室盗窃的概率．假定 现你住在一个相对安全的地方，以日表示“人室盗 窃”、以 表示“地震”，设以下是一组较合理的概 论值： Ｐ（Ｂ）＝０．００１，表示“入室盗窃”的概率，则 Ｐ（ ）＝１—０．００１＝０．９９９，表示“不入室盗窃”的概 率；． Ｐ（Ｅ）＝０．００２，表示“地震”的概率，则Ｐ（Ｅ）＝ ０．９９８，表示“不地震”的概率． 在各种情况组合下，计算警报被拉响的条件概 率（可以通过各种方式测试防盗系统，或者参考历 史数据），设得到了如表１所列的概率值． 表１ 在各种情况下报警的可能性 表１中“数据１”的物理意义是组合事件发生且 报警的概率，“报警的概率”一栏的乘上事件组发生的 概率，女日０．０１×（１—０．０００ ２）×０．９４＝０．００９ ３８１；表１ ８５．６％的机会是因为人室盗窃，５．２８％的可能是因 为地震，９．１％的可能是什么也没有发生，还有 ０．０１８ ２％的可能是两者同时发生了． 假定得到消息，刚刚发生了一起地震，那么 Ｐ（Ｅ）＝“地震的概率”＝１，Ｐ（Ｅ）＝“不地震的概 率”＝０，同理计算得表２． 表２在各种情况下报警的可能性 表２表明，现在有９９．６７％的可能是由于地震 触发了报警系统，同时，只有０．３２６ ９％的可能是因 为人室盗窃．等等． ３ 贝叶斯网络拓展了遗传算法的应用 ３．１ 遗传算法及算法的流程 遗传算法（Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ）ｔ ３１是一类借鉴生 物界的进化规律（适者生存，优胜劣汰遗传机制）演 化而来的随机化搜索方法．它是由美国的Ｊ．Ｈｏｌｌａｎｄ 教授１９７５年首先提出的．遗传算法模拟达尔文的遗 传选择和自然淘汰的生物进化过程的计算模型．它 的思想源于生物遗传学和适者生存的自然规律，是 具有“生存＋检测”的迭代过程的搜索算法．其中， 选择、交叉和变异构成了遗传算法的遗传操作；参数 编码、初始群体的设定、适应度函数的设计、遗传操 作设计、控制参数设定５个要素组成了遗传算法的 核心内容．作为一种新的全局优化搜索算法，遗传算 法以其简单通用、鲁棒性强、适于并行处理以及高 效、实用等显著特点，在各个领域得到了广泛应用， 取得了良好效果，并逐渐成为重要的智能算法之一， 其遗传演算法的流程可由图２形象地表示． ３．２贝叶斯网络拓展了遗传算法 一般遗传算法是一个以目标函数为依据，通过 维普资讯 http://www.cqvip.com 第１期 群体 陈锡枢：基于贝叶斯网络下的遗传算法 遗传算法 ２１ Ⅲ皿皿皿 Ｉ 一［ 夏］ ’ ’［ Ｉ Ｐ（ ｌＡ）： ， ＿ｌ＇２，３＇４． ∑Ｐ（Ｂ Ｐ（Ａ ） 得到最终的置信度值（即Ｂａｙｌ的值）为 Ｐ（Ｂ．１ Ａ）＝ —］ ［二堑口［孕］ ’ｒ————————————————Ｊ ［ 丽 选择 Ｑ５ Ｑｘ丽而 等 ５ ＋Ｑ０ ７ ×５ Ｑ ３＋Ｑ Ｑ６１ ｘ １ ＋ ５Ｑ Ｑ４ ｘ １ ，－－Ｑ４２３’ 同理得：Ｐ（ ２ ｌ Ａ）＝０．３８１，Ｐ（ ３ ｌ Ａ）＝０．１０３， 图２遗传演算法的流程 对个体施加选择、交叉、变异的遗传操作，实现群体 内个体结构重组的迭代过程．但在人工智能的研究 中，观察事物时，往往有成千上万个变量（如个体、 时间、天气、环境等），每个变量以不可预测的方式 影响其他的变量，若每个变量以选择、交叉、变异的 遗传操作，是不可能实现的．若以贝叶斯网络按概率 传播方法，将群体（问题的解）一代一代地以优化和 推理，并逐渐逼近最优解．这样，既保持遗传算法的 优点，又能对不确定性命题进行推理和搜索，从而拓 展了遗传算法． 例如，在一起案件破获过程中，知道４个嫌疑犯 当中必定有一人是真正的罪犯，假设上述置信节点 是对４个嫌疑犯犯罪动机、可能作案条件的定量分 析，通过计算，将知道谁是最可疑的罪犯． 破案第一步： 网络节点包含３个量：７ｒ １、Ｂａｙｌ、 １，如图３ 所示． １ Ｂａｙ １ ｌ 先验概率 ０．５ ０．４２３ ０．５０ 后验概率 ０－３ ０ ３８ｌ ０．７５ ０．１ ０ ｌ０３ ０．６ｌ ０．１ ０ ０９１ ０．５４ 圈３ 网络节点的先验概率和后验概率 ７ｒ１代表先验知识１：来源于对４个嫌疑犯的了 解，假设嫌疑犯１以前曾经坐过牢，那么他的犯罪可 能性将远大于其他三者．假定４个嫌疑犯自 １值分 别为０．５、０．３、０．１、０．１（相当于贝叶斯公式的 Ｐ（Ｂ ），ｉ＝１，２，３，４），这里，嫌疑犯１犯罪的可能性 最大． １代表后验知识１：如果在现场找到一把手， 上面有罪犯的指纹，对上述４个嫌疑犯分别作指纹 鉴定，得到匹配结果分别为０．５０、０．７５、０．６１、０．５４ （相当于贝叶斯公式的Ｐ（Ａ『 ）， ｌ，２，３，４）． Ｂａｙｌ表示对４个嫌疑犯犯罪可能性的真实置 信度．利用贝叶斯公式 Ｐ（ ｌ Ａ）＝０．０９１ 破案第２步： 算法：选择将破案第一步的Ｂａｙｌ的值遗传给 ７ｒ２，如图４所示． ２ Ｂａｙ ２ ２ 先验概率 ０．４２３ ００９ ０．１０ 后验概率 ０－３８ｌ ０．６９ ０．７５ ０．１０３ ０．１０ ０．４５ ０．０９ｌ ０ｌ２ ０．５９ 图４ Ｂａｙｌ的值遗传给 ２后的先验概率和后验概率 ２２代表后验知识２，如果在现场找到各方面人 证，对上述４个嫌疑犯分别作鉴定，得到匹配结果分 别为０．１０、０．７５、０．４５、０．５９．Ｂａｙ２的值按Ｂａｙｌ的计 算方法取得． 破案第３步： 算法：选择将破案第二步的Ｂａｙ２的值遗传给 ７ｒ３．……． 结果分析：在这起案件破获过程中，给出的数据 都是对嫌疑犯罪犯动机、可能作案条件的定量分析， 若每个变量以一般的数学算法的选择、交叉、变异作 精确的迭代，是不可能实现的．而利用贝叶斯网络， 将概率从一个置信节点的 向量遗传给子节点，得 到子节点的 向量；或者将它的 向量反向遗传给 给它的父节点，得到父子节点的 向量．破获案件就 得心应手了． ４ 结束语 人工智能的研究中，对于遗传算法所涉及的 信号处理、模糊模式识别、多目标优化、模糊优 化、可靠性设计等较复杂结构，若通过对个体施 加选择、交叉、变异的遗传操作，难以实现群体内 个体结构重组的迭代．可用贝叶斯网络，按概率 传播方法，将群体（问题的解）一代一代地优化和 推理，并逐渐逼近最优解． （下转第３９页） 维普资讯 http://www.cqvip.com 第１期 熊旋，等：一种ＲＣＳ计算的新方法 ３９ ［３］Ｓ Ｍ ＲＡＯ，Ｄ ＲＷｉｌｔｏｎ．Ｅｌｅｃｔｒｏｍａｇｎｅｔｉｃ ｓｃａｔｔｅｒｉｎｇ ｂｙ ｓｕｒ ｍａｇｎｅｔｉｃｓ，１９９４，１４（１）：３３—６２． ｆａｃｅｓ ｏｆ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ａｎｔｅｎｎａｓ ａｎｄ ［５］Ｎ Ｇ Ａｌｅｘｏｐｏｕｌｏｓ．Ｆｕｎｄａｍｅｎｔａｌ ｓｕｐｅｒｓｔｒａｔｅ（ｃｏｖｅｒ）ｅｆｅｃｔｓ Ｐｒｏｐａｇａｔｉｏｎ，１９８２，３０（５）：４０９—４１８． ｏｎ ｐｒｉｎｔｅｄ ｃｉｒｃｕｉｔ ａｎｔｅｎｎａｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓ：ｏｎ Ａｎｔｅｎｎａｓ ［４］Ｋ Ａ Ｍｉｃｈａｌｓｋｉ，Ｃ Ｇ Ｈｓｕ．Ｒｃｓ ｃｏｍｐｕｔａｔｉｏｎ ｏｆ ｃｏａｘ．１ｏａｄｅｄ ａｎｄ Ｐｒｏｐａｇａｔｉｏｎ，１９８４，３２（８）：８０７－８１６． ｍｉｃｒｏｓｔｒｉｐ ｐａｔｃｈ ａｎｔｅｎｎａｓ ｏｆ ａｒｂｉｔｒａｒｙ ｓｈａｐｅ［Ｊ］．Ｅｌｅｃｔｒｏ－ Ａ Ｎｏｖｅｌ Ｍｅｔｈｏｄ ｆｏｒ Ｅｖａｌｕａｔｉｎｇ ｔｈｅ ＲＣＳ ｏｆ Ｍｉｃｒｏｓｔｒｉｐ Ａｎｔｅｎｎａ ＸＩＯＮＧ Ｘｕａｎ ，ＨＥ Ｘｉｕ．１ｉａｎ。 （１．Ｆａｃｕｌｔｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｉｒｎｇ，Ｇｕａｎｇｄｏｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｇｕａｎｇｚｈｏｕ ５ １０００６，Ｃｈｉｎａ； ２．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃｓ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｉｃ ｏｆ Ｓｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ １０００８０，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｍｅｔｈｏｄ ｆｏｒ ａｎａｌｙｚｉｎｇ ｔｈｅ ＲＣＳ ｏｆ ｍｉｃｒｏｓｔｒｉｐ ａｎｔｅｎｎａ ｗｉｔｈ ｔｈｅ ＭＯＭ ｉｓ ｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｅ ｐａｐｅｒ．Ａｓ ｔｈｅ ａｄｄｉｔｉｏｎａｌ ｍｏｄｅ ｂａｓｉｓ ｆｕｎｃｔｉｏｎ ｉｓ ｉｎｔｒｏｄｕｃｅｄ，ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｔｈｅ ｐｉｎ ｃａｎ ｂｅ ａｎａｌｙｚｅｄ ｃｏｒｒｅｃｔｌｙ。Ａ ｎｏｖｅｌ ｍｅｔｈｏｄ ｉｓ ｐｒｏ． ｐｏｓｅｄ ｔｏ ｃｏｍｐｕｔｅ ｔｈｅ ＲＣＳ ｏｆ ａｒｂｉｔｒａｒｉｌｙ ｌｏａｄｅｄ ｍｉｃｒｏｓｔｒｉｐ ａｎｔｅｎｎａ ｕｓｉｎｇ ｔｈｅ ｓｃａｔｔｅｒ ｉｆｅｌｄ ｏｆ ｔｈｅ ｍｉｃｒｏｓｔｒｉｐ ａｎｔｅｎｎａ ｏｆ ｔｗｏ ｄｉｆｅｒｅｎｔ ｌｏａｄｓ．Ｎｕｍｅｒｉｃａｌ ｒｅｓｕｌｔｓ ｖａｌｉｄａｔｅ ｔｈｅ ｍｅｔｈｏｄ ｉｎ ｔｈｅ ｐａｐｅｒ． Ｋｅｙ ｗｏｒｄｓ：ｍｉｃｒｏｓｔｒｉｐ ａｎｔｅｎｎａ；ｒａｄａｒ ｃｒｏｓｓ ｓｅｃｔｉｏｎ（ＲＣＳ）；ａｒｂｉｔｒａｒｙ ｌｏａｄ （上接第２１页） 参考文献： ［２］茆诗松．概率论与数理统计教程［Ｍ］．北京：高等教育出 ［１］陈魁．应用概率统计［Ｍ］．北京：清华大学出版社，２００３ 版社，２００４． Ｔｈｅ Ｇｅｎｅｔｉｃ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ｂａｙｅｓｉａｎ Ｎｅｔ ＣＨＥＮ Ｘｉ．ｓｈｕ （Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｍａｔｈｅｍａｔｉｃｓ，Ｚｈａｏｑｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈａｏｑｉｎｇ ５２６０６１，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅｏｒｙ ｏｆ Ｂａｙｅｓｉａｎ ｉｓ ｔｈｅ ｂａｓｅ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ ｉｎｆｅｒｅｎｃｅ．Ｉｔ ｉｓ ｐｅｒｍｉｔｔｅｄ ｔｏ ｉｎｆｅｒ ｒｅｖｅｒｓｅｌｙ ａｎｙ ｐｒｏｂａｂｉｌｉｔｙ ｓｔａｔｅｍｅｎｔｓ．Ｗｉｔｈ ｔｈｅ ｈｅｌｐ ｏｆ ｔｈｅ ｔｈｅｏｒｅｍｓ ｏｆ ｐｒｏｂａｂｉｌｉｔｙ ｔｈｅｏｒｙ，ｔｈｉｓ ａｒｔｉｃｌｅ ｔｒａｎｓｆｅｒｓ ｔｈｅ ｔｈｅｏｒｙ ｏｆ Ｂａｙｅｓｉａｎ ｔｏ ｔｈｅ ｇｅ． ｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ａｎｄ ｔｈｅｎ ｅｘｐａｎｄｓ ｔｈｅ ａｐｐｌｉｃａｂｌｅ ｓｃｏｐｅ ｏｆ ｔｈｅ ｌａｔｔｅｒ． Ｋｅｙ ｗｏｒｄｓ：ｐｒｏｂａｂｉｌｉｔｙ；ｔｈｅｏｒｙ ｏｆ Ｂａｙｅｓｉａｎ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ
