组会模板

xzeng

标题：张谋钊-2016.6.13组会-并行多目标进化算法（请用该标题替换“组会模板”）
报告人：张谋钊
摘要（简介）：相比于基于梯度的优化算法，演化算法可以较好的处理一些难以获得梯度信息的复杂优化问题。但与此同时，演化算法往往需要较大的计算量（例如，大量的函数值评估次数）才能在这些复杂优化问题上获得不错的表现。较大的计算量导致演化算法有时会相对耗时，这成为演化算法能够大量投入工程应用的瓶颈之一。随着计算机体系结构的发展使得并行计算有了可能，以及演化算法自身具有可并行的特性，利用并行计算技术加速演化算法对复杂问题的求解，使得这一瓶颈有了解决的可能。本次组会我将同大家分享并行演化算法相关的文章。
1. 针对单目标演化算法提出一种自适应的动态Island模型。文中指出：如果一处理器上的种群子集产生了一个更好的解，则应减小迁徙间隔时间（migration interval）使这个解可以尽快传递给其他处理器，帮助提高算法收敛速度；反之，则应增大迁徙间隔时间，减小频繁传输带来的计算量。为此，文章提出A、B两种策略。A策略为：若在一次迁徙间隔时间内种群子集未产生更好解，则将迁徙间隔时间翻倍，否则，重置为单位时间；B策略为：使用“迁徙间隔时间减半”的策略替换A策略中“重置为单位时间”的策略。文章从理论上分析了固定迁徙间隔时间与使用A、B两种策略自适应调整迁徙间隔时间的算法性能，并证明了其自适应调整策略的有效性。
2. 基于Pareto多目标优化解决最优子集选择问题的算法POSS（Pareto Optimization for Subset Selection），提出了POSS的并行版本PPOSS（parallel POSS，PPOSS）。PPOSS算法将种群中的每个个体产生新解并估计其适应函数值的过程分配到不同的处理器中计算，再汇总到主机中更新种群。文章从理论上论述了在处理器个数少于可选子集变量个数的情况下，PPOSS的运行时间将趋近于线性；在处理器个数充裕的情况下，PPOSS的运行时间将会随着处理器个数的增加而不断降低直至某个常数。实验验证了PPOSS能够有效加速POSS。

参考论文：
[1] GECCO 2014上，Andrea Mambrini 和Dirk Sudholt的文章，Design and Analysis of Adaptive Migration Intervals in Parallel Evolutionary Algorithms，(文章链接)
[2] 发表在IJCAI 2016，来自Chao Qian，Jing-Cheng Shi，Yang Yu，Ke Tang和Zhi-Hua Zhou的文章：Parallel Pareto Optimization for Subset Selection(文章链接)

报告的PPT请见