基本信息

• 题目：Distributed evolutionary algorithms and their models: A survey of the state-of-the-art
• 作者：Gong Y-J, Chen W-N, Zhan Z-H
• 期刊：Applied Soft Computing
• 时间：2015.09
• 链接：Distributed evolutionary algorithms and their models: A survey of the state-of-the-art - ScienceDirect
• 关键字：分布式进化计算；协同进化计算；进化算法；全局优化；多目标优化

---

摘要

• 本文对最先进的分布式进化算法和模型进行了综述
  • 人口分布模型具有主从、岛、蜂窝、分层和池架构，可在人口、个体或操作级别并行化进化任务
  • 维数分布模型包括协同进化和多智能体模型，它们侧重于降维
  • 洞察模型，例如同步、同质性、通信、拓扑、加速、还介绍和讨论了优点和缺点
• 还重点介绍了该领域的最新热点，包括基于云和 MapReduce 的实现、基于 GPU 和 CUDA 的实现、分布式进化多目标优化和实际应用
• 还讨论了许多未来的研究方向

---

正文

• 分布式进化算法框架如下图所示：
  • 基本进化算法包括：遗传算法GA，进化规划EP，进化策略ES，遗传规划GP和差分进化DE。此外蚁群算法ACO和粒子群优化PSO与进化算法具有相同特征，故也包含在内
  • 分布式进化模型用来并行化处理算法，包括：常用主从/岛屿/细胞模型，另外层次/池/协同进化/多代理模型也被广泛接受
  • 设计好模型后，采用不同的编程环境，包括Java、MPI、MapReduce等
  • 最后用于部署的物理平台，包括集群、网格、P2P网络、云和GPU

---

下面介绍分布式进化模型

主从模型：

• 主节点进行交叉/变异/选择，把个体发给从节点进行适应度评估，从节点评估好再发送给主节点,如下图所示

• 缺点：当适应度评估时间小于主从通信时间时，因为主从通信时间导致效率低下。
• 为了解决这个缺点，有两种主从模型的变体：
  • 从节点不仅评估适应度，还有更新任务
  • 每个从节点包含一个子群，主节点从从节点接收最佳个体并把全局最佳信息发送给所有从节点
• 总结：当适应度评估时间远大于主从通信时间时，使用主从模型效果很好

岛屿模型：

• 把种群分成多个子种群，每个子种群对应一个处理器，个体会按照设定的时间间隔迁移到另一个岛

• 岛屿模型节省时间，提高EA的全局搜索能力，不同岛屿中的个体可以向不同方向进化，保证种群多样性
• 缺点：通信频率低时，算法收敛速度很慢，并且迁移范围对算法性能影响很大

细胞模型：

• 每个个体排列在网格上，只能与相邻的个体竞争和交配

• 可以采用并行计算来评估每个染色体的适应度，并且在局部进行交叉/变异/选择到相邻的邻居
• 优点：显著提高对所有染色体的评估速度
• 缺点：需要一个大规模的集群来处理

混合模型：

• 多种分布式模型组合，例如岛屿+主从模型等

• 岛主从模型：
  • 种群划分成多个子种群，在不同的节点定期进行迁移通信
  • 对于每个子群，每个主节点会把单独的评估任务发送到从节点
  • 优点：减少了主从模型中单个主节点的依赖性
• 岛细胞模型：
  • 如图所示，提高了扩展性和容错性
• 岛岛模型：
  • 实现两种迁移方式：可在本地迁移和全局迁移
  • 优点：提高了每个节点的效率

泳池模型：

• 泳池是一个长度为n的全局共享数组，表示种群中n个个体。然后根据节点个数划分泳池成多个段，每个段对应一个节点。每个节点可以读取任意段中的个体，但是只能往自己段里写。
• 优化过程中，节点可以随机选不同段中的个体进行操作，如果生成的后代比自己段中的适应度更好就写回自己的段中

• 难点在于如何实现一个资源池，如数据库系统，MapReduce等

协同进化模型：

• 根据节点数量划分每个节点上的向量，确定主变量，其余为从变量
• 在主变量上进行进化操作，从变量不变。评估时计算整个向量的适应度。通信阶段，更新其次变量

多代理模型：

• 把分布式进化模型视为n个玩家玩策略游戏的系统，每个玩家有一个收益函数，该函数取决于自己和有限邻居的行为，每个玩家都会选择最大收益的行为

---

结论

本文是一篇综述，对每个分布式进化模型及其特点都做了简要概述和点评

---

参考文献

[29] B. Dorronsoro, G. Danoy, A J. Nebro, P. Bouvry, Achieving super-linear per formance in parallel multi-objective evolutionary algorithms by means of cooperative coevolution, Comput. Oper Res. 40(6)(2013)1552-1563
[44] M. Garcia-arenas, J-J. Merelo, A M. Mora, P. Castillo, G. Romero, J. L, ]. Laredo. Assessing speed-ups in commodity cloud storage services for distributed evo lutionary algorithms, in: IEEE Congress on Evolutionary Computation(CEC), 2011,pp.304-3
[65] F.M.Johar, F.A. Azmin, M K. Suaidi, A.S. Shibghatullah, B H Ahmad, S.N.Salleh,M.Z. AA. Aziz, M. Md Shukor, A review of genetic algorithms and parallel genetic algorithms on graphics processing unit(GPU), in: 2013 IEEE Interna tional Conference on Control System, Computing and Engineering (CCSCE) 2013,pp.264-269
[72] X. Li, X Yao, Cooperatively coevolving particle swarms for large scale opti mization, IEEE Trans. Evol. Comput. 16(2)(2012)210-224
[97] M. Pedemonte, S. Nesmachnow, H. Cancela, A survey on parallel ant colony optimization, Appl. Soft Comput. 11(8)(2011)5181-5197