·252· 智能系统学报 第13卷 表7的结果显示，随着维度的增加，算法的求 [6]YANG Z,TANG K,YAO X.Large scale evolutionary o- 解性能下降，搜索时间成倍增长。SparkDECC算法 ptimization using cooperative coevolution[]].Information 在f、5、5、6、、fio、fi、fi2、fs等10个函数的最 sciences,2008,178(15):2985-2999 优值都优于其他3种算法，但在和6两个函数的 [7]MEI Y,OMIDVAR M N,LI X,et al.A competitive divide- 最优值都劣于其他3个算法，4种算法在函数。上 and-conquer algorithm for unconstrained large-scale black- 的结果相似。OXDE、CoDE和jDE3种算法在 box optimization[J].ACM transactions on mathematical software,2016,42(2):13. 13个测试函数的维度扩展到5000时的运行时间分 [8]GUAN X,ZHANG X,WEI J,et al.A strategic conflict 别是25.15天、16.68天和16.85天。SparkDECC算 avoidance approach based on cooperative coevolution-ary 法的运行时间为4.71天，大大提升了算法的收敛时 with the dynamic grouping strategy[J].International journal 间。实验结果显示，SparkDECC算法在5000维的 of systems science,2016,47(9):1995-2008. 整体性能优于其他3种算法，具有很好的可扩展性。 [9]HU X M,HE F L,CHEN W N,et al.Cooperation coevolu- 4结束语 tion with fast interdependency identification for large scale optimization[J].Information sciences,2017,381:142-160. 本文利用新型的迭代云计算模型，提出新的基 [10]LI X,YAO X.Cooperatively coevolving particle swarms 于Spark的合作协同云差分进化算法(SparkDECC)。 for large scale optimization[J].IEEE transactions on evolu- SparkDECC算法按随机分组策略将高维问题分解 tionary computation,2012,16(2):210-224. 成多个同维的低维子问题，将每个子问题与RDD [11]OMIDVAR M N,YANG M,MEI Y,et al.DG2:a faster 模型中的分区一一对应，每个子问题并行执行DE and more accurate differential grouping for large-scale 算法，子问题独立进化若干代后，更新最优个体，提 black-box optimization[J.IEEE transactions on evolution- ary computation,2017,21(6):929-942 高种群的多样性。利用Scala语言在Spark云模型 [12]MENG X,BRADLEY J,YUVAZ B,et al.Mllib:machine 上实现了SparkDECC,通过13个标准测试函数的 learning in apache spark[J].Journal of machine research, 对比实验，结果表明SparkDECC求解精度高，速度 2015,17(34):1235-1241. 快，可扩展性好。此外，选择6个测试函数进行加 [13]王诏远，王宏杰，邢焕来，等.基于Spark的蚁群优化算法 速比实验，实验结果表明加速比与分区数量几乎是 [).计算机应用，2015,35(10y:2777-2780. 线性的，加速效果良好。后续工作将在SparkDECC WANG Zhangyuan,WANG Hongjie,XING Huanlai,et al. 的基础上探索新的分组策略，并不断改进其协同机 An implement of ant colony optimization based on spark[J]. 制，提高算法的收敛效率和求解精度。 Journal of computer applications,2015,35(10):2777- 参考文献： 2780. [14朱继召，贾岩涛，徐君，等.SparkCRF:一种基于Spark的 [1]STORN R.PRICE K.Differential evolution-a simple and 并行CRFs算法实现.计算机研究与发展，2016,53(8)： efficient heuristic for global optimization over conti-nuous 1819-1828 spaces[J].Journal of global optimization,1997,11(4): ZHU Jizhao,JIA Yantao,XU Jun,et al.SparkCRF:a par- 341-359 allel implementation of crfs algorithm with spark[J].Journ- [2]BREST J,GREINER S,BOSKOVIC B,et al.Self-adapting al of computer research and development,2016,53(8): cont-rol parameters in differential evolution:a comparati-ve 1819-1828 study on numerical benchmark problems[J.IEEEtransac- [15]DENG C,TAN X,DONG X,et al.A parallel version of tions on evolutionary computation,2006,10(6):646-657. differential evolution based on resilient distributed datasets [3]WANG Yong,ZHANG Qingfu.Differential evolution with model[C]//Bioinspired Computing-Theories and Applica- composite trial vector generation strategies and co-ntrol tions.Springer,Berlin,Heidelberg,2015:84-93. parameters[J].IEEE transactions on evolutionary computa- [16]TEIJEIRO D,PARDO X C,GONZALEZ P,et al.Imple- tion,2011,2(15)55-66. menting Parallel Differential Evolution on Spark[C]// [4]FRANS V D B,ENGELBRECHT A P.A cooperative ap- European Conference on the Applications of Evolutionary proach to particle swarm optimization[J].IEEE transactions Computation.Springer International Publishing,2016: on evolutionary computation,2004,8(3):225-239. 75-90. [5]POTTER M A,De JONG K A.A cooperative coevolution- [17刀王虹旭，吴斌，刘肠.基于Spak的并行图数据分析系统 ary approach to function optimization[].Lecture notes in [).计算机科学与探索，2015,99y:1066-1074 computer science,1994,866:249-257 WANG Hongxu,WU Bin,LIU Yang.Parallel graph data表 7 的结果显示，随着维度的增加，算法的求 解性能下降，搜索时间成倍增长。SparkDECC 算法 在 f1、f2、f5、f6、f7、f8、f10、f11、f12、f13 等 10 个函数的最 优值都优于其他 3 种算法，但在 f3 和 f9 两个函数的 最优值都劣于其他 3 个算法，4 种算法在函数 f10 上 的结果相似。OXDE、CoDE 和 jDE 3 种算法在 13 个测试函数的维度扩展到 5 000 时的运行时间分 别是 25.15 天、16.68 天和 16.85 天。SparkDECC 算 法的运行时间为 4.71 天，大大提升了算法的收敛时 间。实验结果显示，SparkDECC 算法在 5 000 维的 整体性能优于其他 3 种算法，具有很好的可扩展性。 4 结束语 本文利用新型的迭代云计算模型，提出新的基 于 Spark 的合作协同云差分进化算法 (SparkDECC)。 SparkDECC 算法按随机分组策略将高维问题分解 成多个同维的低维子问题，将每个子问题与 RDD 模型中的分区一一对应，每个子问题并行执行 DE 算法，子问题独立进化若干代后，更新最优个体，提 高种群的多样性。利用 Scala 语言在 Spark 云模型 上实现了 SparkDECC，通过 13 个标准测试函数的 对比实验，结果表明 SparkDECC 求解精度高，速度 快，可扩展性好。此外，选择 6 个测试函数进行加 速比实验，实验结果表明加速比与分区数量几乎是 线性的，加速效果良好。后续工作将在 SparkDECC 的基础上探索新的分组策略，并不断改进其协同机 制，提高算法的收敛效率和求解精度。 参考文献： STORN R, PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over conti-nuous spaces[J]. Journal of global optimization, 1997, 11(4): 341–359. [1] BREST J, GREINER S, BOSKOVIC B, et al. Self-adapting cont-rol parameters in differential evolution: a comparati-ve study on numerical benchmark problems[J]. IEEEtransac￾tions on evolutionary computation, 2006, 10(6): 646–657. [2] WANG Yong, ZHANG Qingfu. Differential evolution with composite trial vector generation strategies and co-ntrol parameters[J]. IEEE transactions on evolutionary computa￾tion, 2011, 2(15): 55–66. [3] FRANS V D B, ENGELBRECHT A P. A cooperative ap￾proach to particle swarm optimization[J]. IEEE transactions on evolutionary computation, 2004, 8(3): 225–239. [4] POTTER M A, De JONG K A. A cooperative coevolution￾ary approach to function optimization[J]. Lecture notes in computer science, 1994, 866: 249–257. [5] YANG Z, TANG K, YAO X. Large scale evolutionary o￾ptimization using cooperative coevolution[J]. Information sciences, 2008, 178(15): 2985–2999. [6] MEI Y, OMIDVAR M N, LI X, et al. A competitive divide￾and-conquer algorithm for unconstrained large-scale black￾box optimization[J]. ACM transactions on mathematical software, 2016, 42(2): 13. [7] GUAN X, ZHANG X, WEI J, et al. A strategic conflict avoidance approach based on cooperative coevolution-ary with the dynamic grouping strategy[J]. International journal of systems science, 2016, 47(9): 1995–2008. [8] HU X M, HE F L, CHEN W N, et al. Cooperation coevolu￾tion with fast interdependency identification for large scale optimization[J]. Information sciences, 2017, 381: 142–160. [9] LI X, YAO X. Cooperatively coevolving particle swarms for large scale optimization[J]. IEEE transactions on evolu￾tionary computation, 2012, 16(2): 210–224. [10] OMIDVAR M N, YANG M, MEI Y, et al. DG2: a faster and more accurate differential grouping for large-scale black-box optimization[J]. IEEE transactions on evolution￾ary computation, 2017, 21(6): 929–942. [11] MENG X, BRADLEY J, YUVAZ B, et al. Mllib: machine learning in apache spark[J]. Journal of machine research, 2015, 17(34): 1235–1241. [12] 王诏远, 王宏杰, 邢焕来, 等. 基于 Spark 的蚁群优化算法 [J]. 计算机应用, 2015, 35(10): 2777–2780. WANG Zhangyuan, WANG Hongjie, XING Huanlai, et al. An implement of ant colony optimization based on spark[J]. Journal of computer applications, 2015, 35(10): 2777– 2780. [13] 朱继召, 贾岩涛, 徐君, 等. SparkCRF: 一种基于 Spark 的 并行 CRFs 算法实现[J]. 计算机研究与发展, 2016, 53(8): 1819–1828. ZHU Jizhao, JIA Yantao, XU Jun, et al. SparkCRF: a par￾allel implementation of crfs algorithm with spark[J]. Journ￾al of computer research and development, 2016, 53(8): 1819–1828. [14] DENG C, TAN X, DONG X, et al. A parallel version of differential evolution based on resilient distributed datasets model[C]//Bioinspired Computing-Theories and Applica￾tions. Springer, Berlin, Heidelberg, 2015: 84–93. [15] TEIJEIRO D, PARDO X C, GONZÁLEZ P, et al. Imple￾menting Parallel Differential Evolution on Spark[C]// European Conference on the Applications of Evolutionary Computation. Springer International Publishing, 2016: 75–90. [16] 王虹旭, 吴斌, 刘旸. 基于 Spark 的并行图数据分析系统 [J]. 计算机科学与探索, 2015, 9(9): 1066–1074. WANG Hongxu, WU Bin, LIU Yang. Parallel graph data [17] ·252· 智 能 系 统 学 报 第 13 卷