Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 基于演化设计的遗传算法在分子对接中的应用 康玲 ，王希诚 Ｋ ＡＮＧ Ｌｉｎｇ ，ＷＡＮＧ Ｘｉｃｈｅｎｇ １．大连东软信息学院计算机系，辽宁大连１１６０２３ ２．大连理工大学工业装备结构分析国家重点实验室，辽宁大连１ １６０２４ １．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉｎ Ｎｅｕｓｏｆａｆ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ，Ｄａｌｉｎ，Ｌｉａａｏｎｉｎｇ １１６０２３，Ｃｈｉｎａ ２．Ｓｔａｔｅ Ｋｅｙ Ｌａｂ ｏｆ Ｓｔｒｕｃｔｕｒａｌ Ａｎａｌｙｓｉｓ ｆｏｒ Ｉｎｄｕｓｔｒｉａｌ Ｅｑｕｉｐｍｅｎｔ，Ｄａｌｉａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｄａｌｉａｎ，Ｌｉａｏｎｉｎｇ １１６０２４，Ｃｈｉｎａ ＫＡＮＧ Ｌｉｎｇ，ＷＡＮＧ Ｘｉｃｈｅｎｇ．Ｅｖｏｌｖｅｍｅｎｔ－ｂａｓｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｏｌｅｃｕｌａｒ ｄｏｃｋｉｎｇ．Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ。２０１１。４７（２６）：１８．２０． Ａｂｓｔｒａｃｔ：Ｓｐｅｃｉｅｓ ｄｙｎａｍｉｃｓ ｍｏｄｅｌ ｉＳ ｉｎｔｒｏｄｕｃｅｄ ｉｎｔｏ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｒｅｆｌｅｃｔ ｔｈｅ ｔｒｕｅ ｓｔａｔｅ ｏｆ ｅｖｏｌｕｔｉｏｎ．ｎ ｅｖｏｌＡｖｅ． ｍｅｎｔ－ｂａｓｅｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｉｓ ｄｅｖｅｌｏｐｅｄ．Ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ，ａｎ ａｄａｐｔｉｖｅ ｓｔｒａｔｅｇｙ ｉｓ ｕｓｅｄ ｔｏ ｏｖｅｒｃｏｍｅ ｔｈｅ ｄｉｆｉｃｕｌｆｙ ｏｆ ｃｏｎ．ｔ ｉｆｍｉｎｇ ｔｒｈｅ ｃｒｏｓｓｏｖｅｒ ａｎｄ ｍｕｔａｔｉｏｎ ｐｒｏｂａｂｉｌｉｔｉｅｓ．Ｓｍａｌｌ ｐｏｐｕｌａｔｉｏｎ ｓｔｒａｔｅｇｙ ａｎｄ ｏｐｔｉｍａｌ ｓｔｒａｔｅｇｙ ｅｎｓｕｒｅ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｔｈｅ ｐｏｐｕｌａｔｉｏｎｓ ａｎｄ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｉｃｉｅｎｃｙ ｏｆ ｔｆｈｅ ａｌｇｏｒｉｈｍ．ｔＢａｓｅｄ ｏｎ ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ，ａ ｎｅｗ ｍｏｌｅｃｕｌａｒ ｄｏｃｋｉｎｇ ｐｒｏｇｒａｍ ｉｓ ｄｅｖｅｌｏｐｅｄ．Ｄｏｃｋｉｎｇ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｃａｎ ｅｆｆｅｃｔｉｖｅｌｙ ｓｏｌｖｅ ｔｈｅ ｍｏｌｅｃｕｌａｒ ｄｏｃｋｉｎｇ ｐｒｏｂｌｅｍ． Ｋｅｙ ｗｏｒｄｓ：ｓｐｅｃｉｅｓ ｄｙｎａｍｉｃｓ ｍｏｄｅｌ；ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ；ｍｏｌｅｃｕｌｒ ｄｏｃｋｉｎｇ ａ摘要：将自然界的物种动态模型引入到遗传算法当中，反映出物种的真实进化状态，开发了基于演化设计的遗传算法。算法采 用自适应策略克服了确定交叉和变异概率值的问题，利用小种群策略和最优保留策略保证了种群的多样性，改善了算法的寻优 能力，进而提高了计算效率。运用该遗传算法求解分子对接优化模型，给出基于演化设计的分子对接程序。对接实例表明，算法 能有效应用于分子对接问题中。 关键词：物种动态模型；遗传算法；分子对接 ＤＯＩ：１０．３７７８／ｊ．ｉｓｓｎ．１００２．８３３１．２０１１．２６．００６ 文章编号：１００２．８３３１（２０１１）２６．００１８．０３ 文献标识码：Ａ 中图分类号：ＴＰ３０１．６ １引言 ２０世纪８０年代以来，作为基于结构的药物设计的一类重 要方法，分子对接（ｍｏｌｅｃｕｌｒａ ｄｏｃｋｉｎｇ）－－直是计算机辅助药物 设计研究领域的热点ｎ 。它将已知三维结构的小分子化合物 ２基于演化设计的遗传算法 自然界中，“物竞天择，适者生存”。由于生存空间和自然 资源的，任何物种都不会无地增长下去，各物种通过 生存竞争与进化，得以存活或者灭亡。为了阐明自然界物种 的动态规律及调节机制，现代生态学家在提出生态学一般规 律的基础上，建立并发展了物种动态模型。 （配体）放入靶标分子（受体）的结合位点，计算小分子与生物 大分子的相互作用能，优化小分子化合物的位置、方向以及构 象，寻找其与靶标生物大分子作用的最佳结合构象 。 如何找到最佳的结合构象，从数学规划角度上就是最小 化相互作用系统的结合自由能。因此，分子对接的求解问题 本质上是一个优化问题。由于智能类算法对目标函数优化模 型的较少，可以对常规方法无法求解的复杂问题进行计 算，所以分子对接主要应用的优化方法多为智能类算法。 ２．１物种动态模型 设物种的出生率为ｂ，死亡率（包括自然死亡或者被捕 杀）为ｄ，在有限生存空间里该物种所能达到的生物总数为 三， （ 表示时刻ｔ该物种的生物群体的总数。 假设物种出生率和死亡率均为常数，则ｋ＝ｂ—ｄ为该物种 在本研究小组开发的基于信息熵的遗传算法［４－５］基础上， 将自然界的物种动态模型引入进化过程中，采用自适应策略， 的自然增长率。随着群体的增大，增长率下降。一旦群体中 生物总数达到 ，群体停止增长，即增长率为０。所以增长率 １一Ｘ／Ｌ）来描 发展了基于演化设计的自适应遗传算法，并且将它运用到分 应该是群体中生物群体总数的函数，可以用ｋ（考察时段［ｆ，ｔ＋Ａｔ】群体总量的变化，应有： 子对接优化设计当中。经对接实例测试，本文算法较之前的 述。其中，算法，在不影响计算效率的情况下，计算精度有了较为显著的 提高。 基金项目：国家重点基础研究发 Ｘ（ｔ＋Ａｔ）一ｘ（ｏ＝ｋＯ—Ｘ／Ｌ）ａＶＣ（Ｏ （１） 由此得到该物种的生物群体满足的微分方程： ＪＩ（９７３）（ｔｈｅ Ｎａｔｉｏｎａｌ Ｇｒａｎｄ Ｆｕｎｄａｍｅｎｔａｌ Ｒｅｓｅａｒｃｈ ９７３ Ｐｒｏｇｒａｍ ｏｆ Ｃｈｉｎａ ｕｎｄｅｒ Ｇｒｎｔａ Ｎｏ．２００９ＣＢ９１８５０１）。 作者简介：康玲（１９７４一），女，博士，副教授，研究领域为计算机辅助药物分子设计；王希诚（１９４６一），男，教授，博士生导师。 Ｅ－ｍａｉｈ ｋａｎｇｌｉｎｇ＠ｎｅｕｓｏｆ１．ｅｄｕ．ｃｎ 收稿日期：２０１１－０３．２８；修回日期：２０１１—０６．１３ 康玲，王希诚：基于演化设计的遗传算法在分子对接中的应用 交叉概率的高低将决定解群体的更新和搜索 （２） 研究结果表明，（３） 苦｝＝ （１一争） ， （０）＝Ｘｏ 引入常数 ＝ｋ／Ｌ，上述模型可改写为： 百ｄＸ＝ｋＸ一 速度的快慢，变异概率则是保持解群体多样性和防止过早收 敛的一种重要手段。因此，在进化过程中应该采用一种合理 的交叉概率和变异概率。 其中，右端第二项反映了群体在有限的生存空间和资源下对 自身继续增长的。 本文尝试将交叉概率和变异概率作为优化设计变量直接 参与整个优化过程，使二者的变化与目标函数直接相关。具 体做法是：假定原优化变量个数为 ，则实际交由遗传算法处 理的变量个数为ｎ＋２。在遗传进化过程中，对于参与交叉的 公式（３）为非线性方程，其平衡点不唯一。设 为正，则 当ｂ— ＜０，趋于平衡点 ＝０；当６一 ＞０，趋于平衡点 ＝（６一 ，式中下标ｅ代表平衡点。 ２．２基于演化设计的遗传算法 借鉴上述模型的思想，考虑平衡态情况下物种进化状况。 令方程中的 代表个体的实际决策变量。具体的过程如下： 假设过 僦中，共有 个个体，Ｎ个变量，令 ：ｂ—ｄ，则 鲁， ，２，…， １，２，…，Ⅳ （４） 其中， 代表第ｉ个个体的第 个实际决策变量。由此可见， 每个个体实际决策变量具有相同 值，不同的 值。在遗传 算法中，仍然令 的取值范围为（０，１］，实际决策变量 的上 下界是已知的，通过 ＝ ，（ｆ：１，２，…， ．『＝１，２，…，Ⅳ）求出 每个ｘ 相对应的 ，的上下限。在遗传算法的每个个体中，不 直接用 作为设计变量进行编码，而是用其相对应的 和 作为设计变量，进行浮点数编码，每个个体的设计变量由原来 的Ⅳ个变成Ⅳ＋１个，然后直接对这些设计变量进行遗传操 作；将式（４）当做一种修正的算术交叉算子，通过执行遗传算 子，得出相应的实际决策变量值。而对于收敛准则中的搜索 空间，本文仍以实际决策变量 的上下界来界定，利用其空间 的收缩精度，来控制遗传算法的停止。 ２．３算法的主要策略 ２．３．１ ｄ，ｌＲ＇群策略 为提高算法效率，减少计算量，在算法中引入小种群策 略，使各小种群在遗传进化过程中，进行选择变异操作。 交叉操作则在种群间进行，从而实现种群间个体的优势互补， 保证种群的多样性。 在算法引入“部落竞争”机制，以多种群交叉增加交叉的 远源性，既减少了传统方法的群体规模，又优化了新生代；将 信息熵的概念引入进化过程，通过控制解空间的收缩提高了 寻求最 辞的效率。 ２．３．２最优保留 最优Ｊ保留策略的定义形式如下： 设到第ｔ代时，群体中 ∽为最佳个体，又设Ｇ（，＋１）为新 一代群体，若Ｇ ＋１）中不存在 （ｆ），则把ｘ （ 作为ＧＯ＋１）中 的第 ＋１个个体（其中ｎ为群体大小）。 事实上，最优保留属于一种特殊的选择操作，它是将当前 解群体中适应度最高的个体完整地复制到下一代群体中。其 主要优点在于能保证遗传算法终止时得到的最后结果一定是 历代出现过的最高适应度的个体。 本文算法用当前的最优个体代替每个种群中的最差个 体，这样既充分保留了父代个体好的基因模式，又保证群体的 多样性，提高了遗传算法的寻优性能。 ２．３．３自适应策略 交叉概率和变异概率是影响遗传算法收敛的重要因素。 个体对（ｊ，．，），采用个体ｊ的交叉概率进行交叉，而每一个个体 都根据自己的变异率进行变异。这样避免了用户调试程序时 反复试验交叉和变异概率参数的苦恼。根据传统经验，这里 给定交叉概率和变异概率的变化范围分别为［０．７，１】和【０，０＿３］。 ２．３．４算法描述 步骤ｌ设置初始搜索空间，生成初始种群。 步骤２计算每个个体的适应度函数值。 步骤３执行修正的交叉操作及变异操作。 步骤４计算各个种群中每个设计变量的空间收缩因子， 确定各种群每个设计变量的搜索空间。 步骤５空间是否收缩到指定范围？若否，则修正设计变量 的上下限，确保事实上的设计变量在指定范围之内；若是，则 Ｊ眺至步骤７。 步骤６生成下一代个体；转向步骤２。 步骤７得到进化结果，算法结束。 ３分子对接实例 利用上述改进的遗传算法来求解分子对接优化模型，在 ＳＧＩ Ｏｒｉｇｉｎ ３８００环境下，采用Ｃ语言发展了一种基于演化设 计的分子对接程序ＳＤＯＣＫ。遗传算法参数设置如下：种群个 数 ：６，种群的规模Ⅳ＝３０，控制参数ｌｆ，＝１０ ，ｔＺ＝１０。，收敛 控制精度为０．０００ ００１，交叉概率和变异概率的变化范围分别 为［０．７，１］和［０，０．３】。 为测试ＳＤＯＣＫ的有效性，对３种晶体复合物结构进行复 原模拟，并同ＤＯＣＫ６．Ｉｔ １（Ｄ０ｃＫ是由美国加州旧金山分校 Ｋｕｎｔｚｄｘ组开发的第一个分子对接软件，是目前应用最为广泛 的对接软件之一）及本研究组发展的分子对接程序ＧＡｓＤｏｃｋｔ 进行比较分析。结果证实算法在保证效率的情况下，改善了 对接的精度。 实例１ １ＡＣＯ晶体复合物结构复原。 １ＡＣＯ晶体复合物中的配体具有５个可旋转键。运行本 程序，遗传进化过程迭代了４５代，耗时１．７９ ｓ，所得最优构象的 能量值为一６３．３５ ｋｃａｌ／ｍｏｌ，与晶体复合物结构中的配体构象 的均方根偏差为０．４２ Ａ。表１给出了３个程序对接结果在能量 得分、对接精度和对接时间方面的比较。 表１ １ＡＣＯ晶体复合物结构在３个对接方法下的对接结果 注：Ｅｎｅｒｇｙ Ｓｃｏｒｅ为能量得分；ＲＭＳＤ为均方差偏差。 例中，本文计算得到的配体构象与晶体复合物结构中的 构象最为接近。从对接时间上，由于ＧＡｓＤｏｃｋ与本文程序采 用类似的优化算法，因此对接时间在一个数量级上，而 ２０ ２０１１，４７（２６） ＣｏｍｐｕｔｅｒＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用 ＤＯＣＫ６．１的对接时间是它们的近千倍。这充分反映了的优化 ４结论 提出了一种基于演化设计的遗传算法，融合了物种动态 模型和信息熵概念，采用多种群和自适应策略，以空间收缩因 子作为算法的收敛准则，能有效识别最优解落入的区间，指导 优化搜索方向，加速优化收敛速度。分子对接优化方法将这 一算法的寻优效率是非常高的。 实例２ １ＭＵＰ晶体复合物结构复原。 １ＭＵＰ晶体复合物中的配体具有２个可旋转键，遗传进 化过程迭代了４０代，耗时２．３５ ｓ，所得最优构象的能量值 为一２２．３２ ｋｃａｌ／ｍｏｌ，与晶体复合物结构中的配体构象的均方 根偏差为０．５７ Ａ。用ＤＯＣＫ６．１程序计算得到的最优构象能量 得分略低于本文的结果（一２４．１６ ｋｃａｌ／ｍｏ１），但ＤＯＣＫ６．１对接 新的优化方式运用到分子对接程序中，开发了新的分子对 接程序ＳＤＯＣＫ。对接实例表明，本文提出的算法对于分子对 接问题是行之有效的。 时间很长，是本文对接时间的百倍以上。对于ＧＡｓＤｏｃｋ，对接 精度与本文较为接近，但能量得分与本文的结果有一定的差 距，这也从一个侧面反映出本文改进的遗传算法的寻优能力 优于前一版本。具体的对接结果比较见表２。 表２ １ＭＵＰ晶体复合物结构在３个对接方法下的对接结果 参考文献： ［１】Ｓｏｕｓａ Ｓ Ｆ，Ｆｅｍａｎｄｅｓ Ｐ Ａ，Ｒａｍｏｓ Ｍ Ｊ．Ｐｒｏｔｅｉｎ—ｌｉｇａｎｄ ｄｏｃｋｉｎｇ： ｃｕｒｒｅｎｔ ｓｔａｔｕｓ ａｎｄ ｆｕｔｕｒｅ ｃｈａｌｌｅｎｇｅｓ［Ｊ］．Ｐｒｏｔｅｉｎｓ，２００６，６５（１）： １５．２６． 【２】Ｋｏｌｂ Ｐ，Ｆｅｒｒｅｉｒａ Ｒ Ｓ，Ｉｒｗｉｎ Ｊ Ｊ，ｅｔ ａ１．Ｄｏｃｋｉｎｇ ａｎｄ ｃｈｅｍｏｉｎｆｏｒ— ｍａｔｉｃ ｓｃｒｅｅｎｓ ｆｏｒ ｎｅｗ ｌｉｇａｎｄｓ ａｎｄ ｔａｒｇｅｔｓ［Ｊ］．Ｃｕｒｒ Ｏｐｉｎ Ｂｉｏｔｅｃｈ， ２００９，２０：４２９—４３６． 注：Ｅｎｅｒｇｙ Ｓｃｏｒｅ为能量得分；ＲＭＳＤ为均方差偏差。 ［３］徐筱杰，候延军，乔学斌，等．计算机辅助药物分子设计［Ｍ］．北京： 化学工业出版社，２００４：３２５—３３２． 实例３ １ＴＳＤ晶体复合物结构复原。 ［４］李纯莲，王希诚，赵金城，等．一种基于信息熵的多种群遗传算法［Ｊ］ ｌ大连理工大学学报，２００４，４４（４）：５８９—５９３． ［５】Ｋａｎｇ Ｌｉｎｇ，Ｌｉ Ｈｏｎｇｌｉｎ，Ｊｉｎｇ Ｈｕａｌａｉａｎｇ，ｅｔ ａ１．Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐ— ｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐｒｏｔｅｉｎ—ｌｉｇａｎｄ ｄｏｃｋｉｎｇ［Ｊ］．Ｊ Ｃｏｍｐｕｔ １ＴＳＤ晶体复合物中的配体具有８个可旋转键，配体分子 较大，优化过程相对来说也比较长；本文经过７２代迭代，用时 １６．４１ ｓ完成了寻优过程，最终得到的配体构象与晶体复合物 配体构象的均方根偏差为１．０６ Ａ。与ＤＯＣＫ６．１、ＧＡｓＤｏｃｋ相 比较（见表３），本文软件无论是在精度还是效率方面都具有较 为明显的优势。 表３ １ＴＳＤ晶体复合物结构在３个对接方法下的对接结果 Ａｉｄｅｄ Ｍｏｌ Ｄｅｓ，２００９，２３（１）：１—１２． ［６］Ｅｗｉｎｇ Ｔ Ｊ，Ｍａｋｉｎｏ Ｓ，Ｓｋｉｌｌｍａｎ Ａ Ｇ，ｅｔ ａ１．ＤＯＣＫ４．Ｏ：ｓｅａｒｃｈ ｓｔｒａｔｅｇｉｅｓ ｆｏｒ ａｕｔｏｍａｔｅｄ ｍｏｌｅｃｕｌｒ ｄｏｃｋｉａｎｇ ｏｆ ｆｌｅｘｉｂｌｅ ｍｏｌｅ— ｃｕｌｅ ｄａｔａｂａｓｅｓ［Ｊ］．Ｊ Ｃｏｍｐｕｔ Ａｉｄｅｄ Ｍｏｌ Ｄｅｓ，２００１，１５（５）： ４１１—４２８． ［７］Ｌｉ Ｈｏｎｇｌｉｎ，Ｌｉ Ｃｈｕｎｌｉａｎ，Ｇｕｉ Ｃｈｕｎｓｈａｎ，ｅｔ ａ１．ＧＡｓＤｏｃｋ：ａ ｎｅｗ ａｐｐｒｏａｃｈ ｆｏｒ ｒａｐｉｄ ｆｌｅｘｉｂｌｅ ｄｏｃｋｉｎｇ ｂａｓｅｄ ｏｎ ａｎ ｉｍｐｒｏｖｅｄ ｍｕｌｔｉ—ｐｏｐｕｌａｔｉｏｎ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｍ［ｈＪ］．Ｂｉｏｏｒｇ Ｍｅｄ Ｃｈｅｍ Ｌｅｔｔ， 注：Ｅｎｅｒｇｙ Ｓｃｏｒｅ为能量得分；ＲＭＳＤ为均方差偏差。 ２００４，１４（１８）：４６７１－４６７６． （上接１７页） 【２］Ｌｉｕ Ｈａｉｍｉｎｇ，Ｈｕ Ｙｕｅｍｉｎｇ．Ａ ｈｅｕｒｉｓｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｒ ｍｕｌｆｔｉ・－ｈｅａｄ ｍｏｕｎｔｅｒ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２２ｎｄ ＩＥＥＥ Ｉｎｔｅｒｎａ— ｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ Ｐａｒｔ ｏｆ ＩＥＥＥ Ｍｕｌｉ—ｔ ［７］Ｈｏ Ｗ，Ｊｉ Ｐ．Ａ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｍ ｔｈｏ ｏｐｔｉｍｉｓｅ ｔｈｅ ｃｏｍｐｏｎｅｎｔ ｐｌａｃｅｍｅｎｔ ｐｒｏｃｅｓｓ ｉｎ ＰＣＢ ａｓｓｅｍｂｌｙ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ａｄｖａｎｃｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ，２００５（１）． ［８李英海，８］周建中，杨俊杰，等．一种基于阈值选择策略的改进的混合 蛙跳算法［Ｊ］．计算机工程与应用，２００７，４３（３５）：１９—２１． ［９］朱光宇．模因内三角概率选择混合蛙跳算法［Ｊ］．计算机集成制造系 统，２００９，１５（１０）：１９７９—１９８５． ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍｓ ａｎｄ Ｃｏｎｔｒｏ１．Ｓｉｎｇａｐｏｒｅ：ＩＥＥＥ Ｐｒｅｓｓ， ２００７：２７９—３８４． 【３］Ｌｅｅ Ｓ Ｈ，Ｌｅｅ Ｂ Ｈ，Ｐａｒｋ Ｔ Ｈ．Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｍｅｔｈｏｄ ｔｏ ｉｍｐｒｏｖｅ ｈｅ ｐｒｏｄｕｃｔｔｉｖｉｔｙ ｏｆ ａ ｍｕｌｔｉ—ｈｅａｄ ｓｕｒｆａｃｅ ｍｏｕｎｔｉｎｇ ｍａｃｈｉｎｅ［Ｃ］／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １９９９ ＩＥＥＥ Ｉｎｔｅｍａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｂｏｔｉｃｓ ：Ｍｉｃｈｉｇａｎ，１９９９：２１１０—２１１５ ［１０］朱光宇，林蔚清基于改进混合蛙跳算法的贴片机贴 顿序优化［Ｊ】． 中国工程机械学报，２００８，６（４）：４２８．４３２． ［１１］曾又姣，金烨．基于遗传算法的贴片机贴装顺序优化［Ｊ］．计算机集 成制造系统，２００４，１０（２）：２０５—２０８． ［４］Ｂａｒｄ Ｊ Ｆ，Ｃｌａｙｔｏｎ Ｒ Ｗ，Ｆｅｏ Ｔ Ａ．Ｍａｃｈｉｎｅ ｓｅｔｕｐ ａｎｄ ｃｏｍｐｏ— ｎｅｎｔ ｐｌａｃｅｍｅｎｔ ｉｎ ｐｒｉｎｔｅｄ ｃｉｒｃｕｉｔ ｂｏａｒｄ ａｓｓｅｍｂｌｙ［Ｊ］．Ｉｎｔ Ｊ Ｆｌｅｘ Ｍａｎｕｆ Ｓｙｓｔ，１９９４，６（１）：５－３１． ［５】Ｃｈｅｎ Ｙ Ｍ，Ｌｉｎ Ｃ Ａ ｐａｒｔｉｃｌｅ ｓｗａｒｍ ｏｐｔｉｍｉｚａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ［１２］胡以静，胡跃明，吴忻生．高速高精度贴片机的贴装效率优化方法［Ｊ］ ．电子工艺技术，２００６，２７（４）：１９１．１９６． ［１３］Ｌｉｎ Ｗｅｉｑｉｎｇ，Ｚｈｕ Ｇｕａｎｇｙｕ．Ａ ｇｅｎｅｔｉｃ ｏｐｔｉｍｉｚａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ｏｐｔｉｍｉｚｅ ｔｈｅ ｍｕｌｔｉｈｅａｄ ｓｕｒｆａｃｅ ｍｏｕｎｔ ｐｌａｃｅｍｅｎｔ ｍａｃｈｉｎｅ［Ｃ］／／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｒｏｂｏｔｉｃｓ ｎｄ Ａｐｐｌａｉｃａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ Ｐｒｅｓｓ，２００８：１００３—１０１２． ｏｐｔｉｍｉｚｅ ｃｏｍｐｏｎｅｎｔ ｐｌａｃｅｍｅｎｔ ｉｎ ｐｒｉｎｔｅｄ ｃｉｒｃｕｉｔ ｂｏａｒｄ ａｓｓｅｍｂｌｙ［Ｊ］． Ｉｎｔ Ｊ Ａｄｖ Ｍａｎｕｆ Ｔｅｃｈｎｏｌ，２００７，３５：６１０—６２０． ［６］Ｈｏ Ｗ，Ｊｉ Ｐ．Ａ ｈｙｂｒｉｄ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｈｍ ｆｔｏｒ ｃｏｍｐｏｎｅｎｔ ｓｅｑｕｅｎｃｉｎｇ ｎｄ ｆａｅｅｄｅｒ ａｒｒａｎｇｅｍｅｎｔ［Ｊ］．Ｉｎｔｅｌｌｉｇｅｎｔ Ｍａｎｕｆａｃｔｕｒｉｎｇ。２００４（１５）： ３０７．３】５． 【１４】王凌智能优化算法及其应用【Ｍ］．北京：清华大学出版社，２００１．
