第4期 丁青锋，等：差分进化算法综述 ·437· 岛结构 中超复杂度的蛋白质结构预测问题(protein 迁徒 structure prediction,PSP),Kalegari等[)提出基于集 群信息传输接口的并行主从结构差分进化算法，利 用Toy模型重新表述二维/三维的蛋白质结构。 Kushida等[4]通过将进化算法种群分割成大小不等 的子种群（岛屿）且分配不同的控制参数，从而实现 子种群的并行进化，同时通过岛屿间的个体迁徙保 持种群的多样性；文献[85]提出基于“随机交配迁 (b)岛屿模型 徙”交换岛屿间信息和“往返行程”更新相应岛屿两 种技术的IbDE算法。Aba等[]为了平衡算法搜 索能力与开发能力之间的冲突，以种群邻居比例作 为参数建立一种自适应动态元胞模型，同时为不同 的优化问题设计相应的元胞网络；Dorronsoro等[别 提出基于元胞个体质量自我管理的邻居结构以及 按照收敛速度设置最佳的种群结构：文献[88]利用 元胞进化特性与蚁群优化解决几何约束优化问题： Lu等[s]提出基于元胞进化规则的元胞遗传算法， 并且给出了元胞进化规则选择标准从而保持种群 (c)元胞模型 的多样性；Nomant]和Dorronsoro[9)]提出线型和紧 岛结构 密型元胞邻居结构的差分进化算法；Noroozi等[] 迁徙 提出CellularDE算法解决动态优化问题，该算法将 搜索空间分布到元胞网格中但是没有考虑元胞自 身的进化。文献[93]中，等级模型算法中的种群被 分成若干个子种群，它们由各自进化并在特定时刻 进行相互通信，所提出的岛屿-主从式等级算法的 速度是线性的：Folino等[]提出一种分布遗传规划 O 算法，其种群由多个独立岛屿组成，每个岛屿种群 采用独立的元胞遗传规划算法：Herrera等[]指出 (d)等级模型（岛屿-元胞）》 等级模型的关键问题是发展了全局和局部两种种 群迁徙方式，这是基本分布式进化算法与等级分布 分段1L分段2 分段p 4 进化算法的区别：另外，这种等级模型的优点还包 括提高每个节点的效率、更多样化合作以及同质 种群池 异质的良好结合等。文献[96]提出一种分布式存 储池结构进化算法，处理器将个体从存储池中提取 执行进化操作后再放回到池中，从而克服传统分布 处理器1 处理器2 处理器p） 进化算法松散耦合、不可靠的缺陷。 4)与其他最优化算法混合 与其他最优化算法混合主要有以下3种方式： (e)水池模型 将其他最优化算法的优化算子嵌入DE算法的差分 图5典型分布式种群结构 策略以改进DE算法：将DE算法的差分策略嵌入其 Fig.5 Typical structure of distributed population 他最优化算法的优化算子以改进其他最优化算法： 文献[82]提出基于异步主从模型的多目标优 迭代过程分别由差分进化算法与其他最优化算法 化算法AMS-DEMO,用以解决同质/异质并行计算 完成，所获得种群多样性的优化算法。 机体系结构的时间密度问题：为了解决生物信息学 其中，文献[41-42]分别提出利用粒子群算子（ｂ）岛屿模型 （ｃ）元胞模型 （ｄ）等级模型（岛屿－元胞） （ｅ）水池模型 图 ５ 典型分布式种群结构 Ｆｉｇ．５ Ｔｙｐｉｃａｌ ｓｔｒｕｃｔｕｒｅ ｏｆ ｄｉｓｔｒｉｂｕｔｅｄ ｐｏｐｕｌａｔｉｏｎ 文献［８２］提出基于异步主从模型的多目标优 化算法 ＡＭＳ⁃ＤＥＭＯ，用以解决同质／ 异质并行计算 机体系结构的时间密度问题；为了解决生物信息学 中超 复 杂 度 的 蛋 白 质 结 构 预 测 问 题 （ ｐｒｏｔｅｉｎ ｓｔｒｕｃｔｕｒｅ ｐｒｅｄｉｃｔｉｏｎ，ＰＳＰ），Ｋａｌｅｇａｒｉ 等［８３］提出基于集 群信息传输接口的并行主从结构差分进化算法，利 用 Ｔｏｙ 模型重新表述二维／ 三维的蛋白质结构。 Ｋｕｓｈｉｄａ 等［８４］通过将进化算法种群分割成大小不等 的子种群（岛屿）且分配不同的控制参数，从而实现 子种群的并行进化，同时通过岛屿间的个体迁徙保 持种群的多样性；文献［８５］提出基于“随机交配迁 徙”交换岛屿间信息和“往返行程”更新相应岛屿两 种技术的 ＩｂＤＥ 算法。 Ａｌｂａ 等［８６］ 为了平衡算法搜 索能力与开发能力之间的冲突，以种群邻居比例作 为参数建立一种自适应动态元胞模型，同时为不同 的优化问题设计相应的元胞网络；Ｄｏｒｒｏｎｓｏｒｏ 等［８７］ 提出基于元胞个体质量自我管理的邻居结构以及 按照收敛速度设置最佳的种群结构；文献［８８］利用 元胞进化特性与蚁群优化解决几何约束优化问题； Ｌｕ 等［８９］ 提出基于元胞进化规则的元胞遗传算法， 并且给出了元胞进化规则选择标准从而保持种群 的多样性；Ｎｏｍａｎ ［９０］ 和 Ｄｏｒｒｏｎｓｏｒｏ ［９１］ 提出线型和紧 密型元胞邻居结构的差分进化算法；Ｎｏｒｏｏｚｉ 等［９２］ 提出 ＣｅｌｌｕｌａｒＤＥ 算法解决动态优化问题，该算法将 搜索空间分布到元胞网格中但是没有考虑元胞自 身的进化。 文献［９３］中，等级模型算法中的种群被 分成若干个子种群，它们由各自进化并在特定时刻 进行相互通信，所提出的岛屿－主从式等级算法的 速度是线性的；Ｆｏｌｉｎｏ 等［９４］ 提出一种分布遗传规划 算法，其种群由多个独立岛屿组成，每个岛屿种群 采用独立的元胞遗传规划算法；Ｈｅｒｒｅｒａ 等［９５］ 指出 等级模型的关键问题是发展了全局和局部两种种 群迁徙方式，这是基本分布式进化算法与等级分布 进化算法的区别；另外，这种等级模型的优点还包 括提高每个节点的效率、更多样化合作以及同质／ 异质的良好结合等。 文献［９６］ 提出一种分布式存 储池结构进化算法，处理器将个体从存储池中提取 执行进化操作后再放回到池中，从而克服传统分布 进化算法松散耦合、不可靠的缺陷。 ４）与其他最优化算法混合 与其他最优化算法混合主要有以下 ３ 种方式： 将其他最优化算法的优化算子嵌入 ＤＥ 算法的差分 策略以改进 ＤＥ 算法；将 ＤＥ 算法的差分策略嵌入其 他最优化算法的优化算子以改进其他最优化算法； 迭代过程分别由差分进化算法与其他最优化算法 完成，所获得种群多样性的优化算法。 其中，文献［４１－４２］分别提出利用粒子群算子 第 ４ 期 丁青锋，等：差分进化算法综述 ·４３７·