·244· 智能系统学报 第13卷 等构造了控制参数的自适应性方法并提出了自适 问题，评价出最优个体。SparkDECC算法在I3个 应DE算法GDE)。Wang等提出了复合DE算法 标准函数进行测试，实验结果表明该算法是有效可 (CoDE),其将精心选择的3种变异策略和3组控制 行的。 参数按照随机的方法进行组合。这些研究成果主 要集中于低维问题(30维)，然而当面向高维问题 1差分进化算法 (1000维)时，这些DE算法的性能将急剧下降，而 差分进化算法是一种仿生的群体进化算法，具 且搜索时间随着维数成指数增长，求解极为困难： 体操作如下2四。 “维灾难”问题依然存在。 1)种群初始化 为了有效求解高维优化问题，学者们提出不同 DE算法首先在[xmin,xma]范围内随机初始化 的策略，其中具有代表性的是协同进化(cooperative NP个D维向量x,的种群，其中NP为种群大小， coevolution,CC)。CC采用“分而治之”的思想，首 D为种群的维度，xmn为最小值，xmax为最大值，i∈ 先将高维复杂问题分解成低维简单的子问题；其次 [1,NP]. 对每个子问题分别进行求解：最后通过所有子问题 2)变异 解的协同机制，得到整个问题的解。Yang等提出 变异主要是通过种群中个体之间的差向量来改 的随机分组策略，可将两个相关变量以极大的概率 变个体的值。DE算法根据基准向量的选取和差分 放在同一组，在大规模优化问题中得到较精确的 向量数目不同，有多种变异操作。本文的目标向量 解。研究人员已将CC应用到多个领域，如大规模 x,主要通过最常用的变异算子产生，如式(1)。 黑盒优化问题可、SCA问题、FI算法9、CCPSO算 Vis=xn+F.(xn-xn) (1) 法、DG2算法u,然而它们在求解高维优化问题 式中：，r,2,r3∈[1，NP]且互不相同的4个随机整 时，采用串行方式求解，因此，问题求解需要较长的 数；”：为目标向量x在第g代时产生的变异向量； 计算时间，很难在有效时间内提供满意的解。近年 缩放因子F∈[0,1]。 来云计算已应用到大规模信息处理领域中，如在机 3)交叉 器学习I、蚁群算法)、CRFs算法14、差分进化算 变异后，DE算法通过交叉概率在目标向量 法516、图数据分析7、分类算法1等获得了成功。 x与变异向量”，进行交叉，产生新的试验向量4o 因此，有必要将云计算的分布式处理能力与CC的 具体操作如式(2)所示。 优势相结合，为大规模优化问题的求解提供新方法。 ∫g,rmd<CR or j=md 48= (2) 研究人员已在Google开源平台Hadoop的Map x,其他 Reduce模型之上提出了一些分布式差分进化算 式中：交叉概率CR∈[0,1]，j∈[1，D],随机数 法I9-20。实践中研究人员发现，MapReduce模型是 rnd1∈[0,1]，随机整数md2e[1,D]。 一个通用的批处理计算模型，缺乏并行计算数据共 4)选择 享的有效机制，对迭代运算无法提供有效支持。因 DE算法主要通过“贪婪”原则对个体进行选择， 此，基于MapReduce模型的差分进化算法需要通过 较优个体进入下一代。具体操作如式(3)所示。 频繁读写文件来交换数据，降低了其效率四。 uig, f(ug)≤f(xa) x.g+1= (3) Spark云平台是伯克利大学提出的分布式数据 其他 处理框架22，在许多领域获得了成功应用。Spark 式中f(化)为个体xg的适应度值。 提出了一种全新的数据抽象模型RDD(弹性分布式 DE算法通过变异、交叉、选择之后，根据循环 数据模型)。RDD模型能够有效支持迭代计算、关 代数或求解精度来结束搜索。 系查询、批处理以及流失数据处理等功能，使得 2 合作协同的云差分进化算法Spark- Spark可以应用于多种大规模处理场景。由于RDD DECC 模型基于内存计算，避免了MapReduce模型频繁读 写磁盘数据的弊端，提高了效率。 2.1 Spark云平台 本文基于Spark云平台提出了合作协同的差分 为了更加高效地支持迭代运算，Spark平台在 进化算法。SparkDECC算法采用分治”策略，将高 MapReduce云模型的基础上进行了扩展P。Spark 维优化问题按随机分组策略分解成低维子问题，并 平台提供了两个重要的抽象：RDD和共享变量。 封装成RDD;在RDD中，每个子问题独立并行进 RDD本质是一个容错的、并行的数据结构，提供了 化若干代；利用协同机制将所有子问题合并成完整 一种只读、分区记录并存放在内存的数据集合。等 [2]构造了控制参数的自适应性方法并提出了自适 应 DE 算法 (jDE)。Wang 等 [3]提出了复合 DE 算法 (CoDE)，其将精心选择的 3 种变异策略和 3 组控制 参数按照随机的方法进行组合。这些研究成果主 要集中于低维问题 (30 维)，然而当面向高维问题 (1 000 维) 时，这些 DE 算法的性能将急剧下降，而 且搜索时间随着维数成指数增长，求解极为困难， “维灾难”问题依然存在[4]。 为了有效求解高维优化问题，学者们提出不同 的策略，其中具有代表性的是协同进化 (cooperative coevolution，CC)[5]。CC 采用“分而治之”的思想，首 先将高维复杂问题分解成低维简单的子问题；其次 对每个子问题分别进行求解；最后通过所有子问题 解的协同机制，得到整个问题的解。Yang 等 [6]提出 的随机分组策略，可将两个相关变量以极大的概率 放在同一组，在大规模优化问题中得到较精确的 解。研究人员已将 CC 应用到多个领域，如大规模 黑盒优化问题[7] 、SCA 问题[8] 、FII 算法[9] 、CCPSO 算 法 [10] 、DG2 算法[11] ，然而它们在求解高维优化问题 时，采用串行方式求解，因此，问题求解需要较长的 计算时间，很难在有效时间内提供满意的解。近年 来云计算已应用到大规模信息处理领域中，如在机 器学习[12] 、蚁群算法[13] 、CRFs 算法[14] 、差分进化算 法 [15-16] 、图数据分析[17] 、分类算法[18] 等获得了成功。 因此，有必要将云计算的分布式处理能力与 CC 的 优势相结合，为大规模优化问题的求解提供新方法。 研究人员已在 Google 开源平台 Hadoop 的 Map￾Reduce 模型之上提出了一些分布式差分进化算 法 [19-20]。实践中研究人员发现，MapReduce 模型是 一个通用的批处理计算模型，缺乏并行计算数据共 享的有效机制，对迭代运算无法提供有效支持。因 此，基于 MapReduce 模型的差分进化算法需要通过 频繁读写文件来交换数据，降低了其效率[21]。 Spark 云平台是伯克利大学提出的分布式数据 处理框架[22] ，在许多领域获得了成功应用。Spark 提出了一种全新的数据抽象模型 RDD(弹性分布式 数据模型)。RDD 模型能够有效支持迭代计算、关 系查询、批处理以及流失数据处理等功能，使得 Spark 可以应用于多种大规模处理场景。由于 RDD 模型基于内存计算，避免了 MapReduce 模型频繁读 写磁盘数据的弊端，提高了效率。 本文基于 Spark 云平台提出了合作协同的差分 进化算法。SparkDECC 算法采用“分治”策略，将高 维优化问题按随机分组策略分解成低维子问题，并 封装成 RDD；在 RDD 中，每个子问题独立并行进 化若干代；利用协同机制将所有子问题合并成完整 问题，评价出最优个体。SparkDECC 算法在 13 个 标准函数进行测试，实验结果表明该算法是有效可 行的。 1 差分进化算法 差分进化算法是一种仿生的群体进化算法，具 体操作如下[23]。 1) 种群初始化 DE 算法首先在[xmin，xmax]范围内随机初始化 NP 个 D 维向量 xi 的种群，其中 NP 为种群大小， D 为种群的维度，xmin 为最小值，xmax 为最大值，i∈ [1, NP]。 2) 变异 变异主要是通过种群中个体之间的差向量来改 变个体的值。DE 算法根据基准向量的选取和差分 向量数目不同，有多种变异操作。本文的目标向量 xi 主要通过最常用的变异算子产生，如式 (1)。 vi,g = xr1 + F · ( xr2 − xr3 ) (1) 式中：i, r1 , r2 , r3∈[1, NP]且互不相同的 4 个随机整 数；vi, g 为目标向量 xi 在第 g 代时产生的变异向量； 缩放因子 F∈[0, 1]。 3) 交叉 变异后，DE 算法通过交叉概率在目标向量 xi 与变异向量 vi 进行交叉，产生新的试验向量 ui。 具体操作如式 (2) 所示。 ui, j,g = { vi, j,g, rnd1 < CR or j == rnd2 xi, j,g, 其他 (2) 式中：交叉概率 CR∈[0, 1]，j∈[1, D]，随机数 rnd1∈[0, 1]，随机整数 rnd2∈[1, D]。 4) 选择 DE 算法主要通过“贪婪”原则对个体进行选择， 较优个体进入下一代。具体操作如式 (3) 所示。 xi,g+1 = { ui,g, f ( ui,g ) ⩽ f ( xi,g ) xi,g, 其他 (3) 式中 f (xi, g ) 为个体 xi, g 的适应度值。 DE 算法通过变异、交叉、选择之后，根据循环 代数或求解精度来结束搜索。 2 合作协同的云差分进化算法 Spark￾DECC 2.1 Spark 云平台 为了更加高效地支持迭代运算，Spark 平台在 MapReduce 云模型的基础上进行了扩展[24]。Spark 平台提供了两个重要的抽象：RDD 和共享变量。 RDD 本质是一个容错的、并行的数据结构，提供了 一种只读、分区记录并存放在内存的数据集合。 ·244· 智 能 系 统 学 报 第 13 卷