【智能系统】云环境下求解大规模优化问题的协同差分进化算法

第13卷第2期 智能系统学报 Vol.13 No.2 2018年4月 CAAI Transactions on Intelligent Systems Apr.2018 D0:10.11992/tis.201706053 云环境下求解大规模优化问题的协同差分进化算法 谭旭杰'，邓长寿，吴志健，彭虎'，朱鹊桥 (1.九江学院信息科学与技术学院，江西九江332005,2.武汉大学软件工程国家重点实验室，湖北武汉430072,3.中 国人民解放军93704部队) 摘要：差分进化是一种求解连续优化问题的高效算法。然而差分进化算法求解大规模优化问题时，随着问题维数 的增加，算法的性能下降，且搜索时间呈指数上升。针对此问题，本文提出了一种新的基于Spark的合作协同差分进 化算法(SparkDECC)。SparkDECC采用分治策略，首先通过随机分组方法将高维优化问题分解成多个低维子问题， 然后利用Spark的弹性分布式数据模型，对每个子问题并行求解，最后利用协同机制得到高维问题的完整解。通过 在13个高维测试函数上进行的对比实验和分析，实验结果表明算法加速明显且可扩展性好，验证了SparkDECC的 有效性和适用性。 关键词：差分进化：大规模优化：协同进化：弹性分布式数据集：云计算 中图分类号：TP301文献标志码：A文章编号：1673-4785(2018)02-0243-11 中文引用格式：谭旭杰，邓长寿，吴志健，等.云环境下求解大规模优化问题的协同差分进化算法J.智能系统学报，2018,13(2： 243-253. 英文引用格式：TAN Xujie,,DENG Changshou,,WUZhijian,,etal.Cooperative differential evolution in cloud computing for solving large-scale optimization problems CAAI transactions on intelligent systems,2018,13(2):243-253. Cooperative differential evolution in cloud computing for solving large- scale optimization problems TAN Xujie',DENG Changshou',WU Zhijian',PENG Hu',ZHU Queqiao' (1.School of Information Science and Technology,Jiujiang University,Jiujiang 332005,China,2.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072,China;3.People's Liberation Army of China 93704) Abstract:Differential evolution is an efficient algorithm for solving continuous optimization problems.However,its performance deteriorates quickly and the runtime grows exponentially when differential evolution is applied to solve large-scale optimization problems.To overcome this problem,a novel cooperative coevolution differential evolution based on Spark(called SparkDECC)was proposed.The strategy of separate processing is used in SparkDECC.Firstly, the large-scale problem is decomposed into several low-dimensional sub-problems by using the random grouping strategy;then each sub-problem can be tackled in a parallel way by taking advantage of the parallel computation capab- ility of the resilient distributed datasets model in Spark;finally the optimal solution of the entire problem is obtained by using cooperation mechanism.The experimental results on 13 high-dimensional functions show that the new algorithm has good performances of speedup and scalability.The effectiveness and applicability of the proposed algorithm were verified. Keywords:differential evolution;large-scale optimization;coevolution;resilient distributed dataset;cloud computing 差分进化算法(differential evolution,DE)是一 收稿日期：2017-06-13. 种基于实数编码的全局优化算法”，因其简单、高效 基金项目：国家自然科学基金项目(61364025,61763019：武汉大 学软件工程国家重点实验室开放基金项目(SKLSE20I2- 以及具有全局并行性等特点，近年来已成功应用到 09-39):九江学院科研项目(20I3KJ30.2014KJYB032): 江西省教育厅科技项目(G161076,GJ161072). 工业设计和工程优化等领域。研究人员对DE算法 通信作者：邓长寿.E-mail:csdeng@jju.edu.cn. 进行了改进和创新并取得了一些成果。比如Brest

DOI: 10.11992/tis.201706053 云环境下求解大规模优化问题的协同差分进化算法 谭旭杰1 ，邓长寿1 ，吴志健2 ，彭虎1 ，朱鹊桥3 （1. 九江学院 信息科学与技术学院，江西 九江 332005; 2. 武汉大学 软件工程国家重点实验室，湖北 武汉 430072; 3. 中 国人民解放军 93704 部队） 摘 要：差分进化是一种求解连续优化问题的高效算法。然而差分进化算法求解大规模优化问题时，随着问题维数 的增加，算法的性能下降，且搜索时间呈指数上升。针对此问题，本文提出了一种新的基于 Spark 的合作协同差分进 化算法 (SparkDECC)。SparkDECC 采用分治策略，首先通过随机分组方法将高维优化问题分解成多个低维子问题， 然后利用 Spark 的弹性分布式数据模型，对每个子问题并行求解，最后利用协同机制得到高维问题的完整解。通过 在 13 个高维测试函数上进行的对比实验和分析，实验结果表明算法加速明显且可扩展性好，验证了 SparkDECC 的 有效性和适用性。 关键词：差分进化；大规模优化；协同进化；弹性分布式数据集；云计算 中图分类号：TP301 文献标志码：A 文章编号：1673−4785(2018)02−0243−11 中文引用格式：谭旭杰, 邓长寿, 吴志健, 等. 云环境下求解大规模优化问题的协同差分进化算法[J]. 智能系统学报, 2018, 13(2): 243–253. 英文引用格式：TAN Xujie, DENG Changshou, WU Zhijian, et al. Cooperative differential evolution in cloud computing for solving large-scale optimization problems[J]. CAAI transactions on intelligent systems, 2018, 13(2): 243–253. Cooperative differential evolution in cloud computing for solving large￾scale optimization problems TAN Xujie1 ，DENG Changshou1 ，WU Zhijian2 ，PENG Hu1 ，ZHU Queqiao3 (1. School of Information Science and Technology, Jiujiang University, Jiujiang 332005, China; 2. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China; 3. People's Liberation Army of China 93704) Abstract: Differential evolution is an efficient algorithm for solving continuous optimization problems. However, its performance deteriorates quickly and the runtime grows exponentially when differential evolution is applied to solve large-scale optimization problems. To overcome this problem, a novel cooperative coevolution differential evolution based on Spark (called SparkDECC) was proposed. The strategy of separate processing is used in SparkDECC. Firstly, the large-scale problem is decomposed into several low-dimensional sub-problems by using the random grouping strategy; then each sub-problem can be tackled in a parallel way by taking advantage of the parallel computation capab￾ility of the resilient distributed datasets model in Spark; finally the optimal solution of the entire problem is obtained by using cooperation mechanism. The experimental results on 13 high-dimensional functions show that the new algorithm has good performances of speedup and scalability. The effectiveness and applicability of the proposed algorithm were verified. Keywords: differential evolution; large-scale optimization; coevolution; resilient distributed dataset; cloud computing 差分进化算法 (differential evolution，DE) 是一 种基于实数编码的全局优化算法[1] ，因其简单、高效 以及具有全局并行性等特点，近年来已成功应用到 工业设计和工程优化等领域。研究人员对 DE 算法 进行了改进和创新并取得了一些成果。比如 Brest 收稿日期：2017−06−13. 基金项目：国家自然科学基金项目 (61364025，61763019)；武汉大 学软件工程国家重点实验室开放基金项目 (SKLSE2012- 09-39)；九江学院科研项目 (2013KJ30，2014KJYB032)； 江西省教育厅科技项目 (GJJ161076，GJJ161072). 通信作者：邓长寿. E-mail：csdeng@jju.edu.cn. 第 13 卷第 2 期 智 能 系 统 学 报 Vol.13 No.2 2018 年 4 月 CAAI Transactions on Intelligent Systems Apr. 2018

·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 卷

第2期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·245· Broadcast是一种共享变量，将数据缓存在每个结点 而，随着种群规模的增加，CC框架所需时间快速增 上，不再需要传递数据，减少通信开销，提高通信性 加。为了提高CC框架的收敛速度，将云计算的优 能。Spark平台的API为RDD提供了两种算子：转 势与CC框架相结合，提出了基于Spark的合作协 换算子(Transformations)和动作算子(Actions),其 同进化算法-SparkDECC算法。 中，转换算子都是惰性的，对RDD分区的每个数据 SparkDECC算法首先将高维问题按随机分组 执行相同的操作，并返回新的RDD:而动作算子将 方法分解成若干个低维子问题，一个子问题对应一 触发RDD上的运算，并将值返回给主控结点。RDD 个子种群，保留每个子问题在完整问题的位置信 内部实现机制基于迭代器，使得数据访问更高效， 息；按key,值将低维子种群分发到RDD中相应的 避免了中间结果对内存的消耗，使迭代计算更加高 分区，每个分区中的子种群并行执行DE算法的变 效快速。 异、交叉、选择等操作，其中子种群在计算个体适应 DE是一种基于群体的进化算法，具有内在并 度值时，选取上一轮的最优个体合作组成完整的种 行性的特点。因此，DE能与Spark的并行性充分融 群并进行局部寻优。低维子种群在对应的分区中进 合。Spark在主控结点通过Parallelize方法将种群 化若干代后，按照其位置信息合并成新的完整种 并行初始化，并采用键-值的方式存放在内存中，即： 群，并通过全局搜索返回最优个体。SparkDECC算 [key,valued.i=1,2,....m (4) 法的流程图如图2所示。 式中：m是子种群的数目；key,是整数，表示第i个 initial 子种群的编号；vaue,是第i个子种群。DE在Spark 子问题1 Kk.V> 上的具体实现如图1所示。 子问题2 KKV DE Pop key: key 子问题N KKV map collect Parallelize N 是否结束 [keyi,value] [key:,value.] [keyvalue] 将 图2 SparkDECC算法流程图 map Fig.2 Flowchart of SparkDECC algorithm 群 key ,value,] keyz,value,] 分 SparkDECC算法的具体步骤如下。 区 1)初始化参数：种群规模NP、缩放因子F、交 collect 叉概率CR、问题的维度D、子问题的维度DimSub、 RDD 子种群数M=D/DimSub、子种群的位置信息sub- 种 N 群 script、分区数Num、进化代数Gen、子种群合并轮 、是否结束 数Cycles; Y 2)初始化种群Pop,通过cachet0将数据存放在 输出最优值 内存中； 结束 3)获取种群最优个体向量bestInd、最优值best; 4)将控制合并轮数的变量c赋值为0： 图I基于Spark的DE算法 5)判断合并轮数c是否小于等于Cycles,若 Fig.1 DE based on spark 是，则循环结束；否则，继续： Spark将内存中的数据按“键-值”对的方式抽象 6)变量c自动加1； 成RDD,并根据key,值将子种群分区保存在不同的 T)利用parallelize方法将Pop按随机分组策略 结点上。利用RDD的并行操作算子对各子种群并 分解成M个低维的子种群，将子种群的位置信息存 行进化若干代，再通过collect算子合并生成新的种 放subscript中，并按key值将子种群分发到相应 群。循环结束后通过动作算子reduce获取整个种 分区； 群的最优值。 8)通过broadcast变量将Pop广播至每个结点； 2.2 SparkDECC算法 9)各子种群并行进化Gen代，具体的计算过 CC框架处理大规模优化问题优势明显。然 程为：

Broadcast 是一种共享变量，将数据缓存在每个结点 上，不再需要传递数据，减少通信开销，提高通信性 能。Spark 平台的 API 为 RDD 提供了两种算子：转 换算子 (Transformations) 和动作算子 (Actions)，其 中，转换算子都是惰性的，对 RDD 分区的每个数据 执行相同的操作，并返回新的 RDD；而动作算子将 触发 RDD 上的运算，并将值返回给主控结点。RDD 内部实现机制基于迭代器，使得数据访问更高效， 避免了中间结果对内存的消耗，使迭代计算更加高 效快速。 DE 是一种基于群体的进化算法，具有内在并 行性的特点。因此，DE 能与 Spark 的并行性充分融 合。Spark 在主控结点通过 Parallelize 方法将种群 并行初始化，并采用“键–值”的方式存放在内存中，即： [keyi ,valuei],i = 1,2,··· ,m (4) 式中：m 是子种群的数目；keyi 是整数，表示第 i 个 子种群的编号；valuei 是第 i 个子种群。DE 在 Spark 上的具体实现如图 1 所示。 Spark 将内存中的数据按“键–值”对的方式抽象 成 RDD，并根据 keyi 值将子种群分区保存在不同的 结点上。利用 RDD 的并行操作算子对各子种群并 行进化若干代，再通过 collect 算子合并生成新的种 群。循环结束后通过动作算子 reduce 获取整个种 群的最优值。 2.2 SparkDECC 算法 CC 框架处理大规模优化问题优势明显。然 而，随着种群规模的增加，CC 框架所需时间快速增 加。为了提高 CC 框架的收敛速度，将云计算的优 势与 CC 框架相结合，提出了基于 Spark 的合作协 同进化算法-SparkDECC 算法。 SparkDECC 算法首先将高维问题按随机分组 方法分解成若干个低维子问题，一个子问题对应一 个子种群，保留每个子问题在完整问题的位置信 息；按 keyi 值将低维子种群分发到 RDD 中相应的 分区，每个分区中的子种群并行执行 DE 算法的变 异、交叉、选择等操作，其中子种群在计算个体适应 度值时，选取上一轮的最优个体合作组成完整的种 群并进行局部寻优。低维子种群在对应的分区中进 化若干代后，按照其位置信息合并成新的完整种 群，并通过全局搜索返回最优个体。SparkDECC 算 法的流程图如图 2 所示。 SparkDECC 算法的具体步骤如下。 1) 初始化参数：种群规模 NP、缩放因子 F、交 叉概率 CR、问题的维度 D、子问题的维度 DimSub、 子种群数 M=D/DimSub、子种群的位置信息 sub￾script、分区数 Num、进化代数 Gen、子种群合并轮 数 Cycles； 2) 初始化种群 Pop，通过 cache() 将数据存放在 内存中； 3) 获取种群最优个体向量 bestInd、最优值 best； 4) 将控制合并轮数的变量 c 赋值为 0; 5) 判断合并轮数 c 是否小于等于 Cycles，若 是，则循环结束；否则，继续； 6) 变量 c 自动加 1; 7) 利用 parallelize 方法将 Pop 按随机分组策略 分解成 M 个低维的子种群，将子种群的位置信息存 放 subscript 中，并按 key 值将子种群分发到相应 分区； 8) 通过 broadcast 变量将 Pop 广播至每个结点； 9) 各子种群并行进化 Gen 代，具体的计算过 程为： key1 [key1 ,value1 ] [key2 ,value2 ] [keym,valuem] Parallelize key2 keym [key1 ,value1 '] [key2 ,value2 '] [keym,valuem'] map collect RDD ᭛॒㏿᲋ N ㏿᲋ 䒿ܦᰬфը Y ᄲ ⻹ 㓐 ܲ ࡦ Ꭲ ᰠ ᫜ ၼ ⻹ 㓐 … … … 图 1 基于 Spark 的 DE 算法 Fig. 1 DE based on spark initial ܲ㼏 collect k1 ,v1! k2 ,v2! … … kM,vM! DE map ၼ䬚䷄1 ᭛॒㏿᲋ N best reduce ၼ䬚䷄2 ၼ䬚䷄N Pop Y 图 2 SparkDECC 算法流程图 Fig. 2 Flowchart of SparkDECC algorithm 第 2 期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·245·

·246· 智能系统学报 第13卷 ①变异操作，执行式(1)： 的。函数的详细说明详见文献[25]。 ②交叉操作，执行式(2)： 3.2实验设置 ③选择操作，执行式(3)，其中子种群在计算适 本实验采用Spark云模型，每个节点的配置如下： 应度值时，按照其位置信息替换掉bestInd中的部 64 bit corei?7CPU主频3.4GB,内存8GB,Ubuntul3.10 分解。 操作系统，安装使用Hadoop22.2.0和Spark1.2.0,编 10)利用collect动作算子将所有低维子种群按 程环境为ntel山IDEA14.l.2,使用Scala和Java语言。 协同机制合并成完整种群，并更新Pop; 为了验证SparkDECC的性能以及影响其性能 II)对Pop进行全局搜索并返回最优个体bestInd; 的各个因素，实验时SparkDECC中问题的维度 12)转到5)： D=1000,子问题的维度DimSub=100,问题规模 l3)循环结束，通过reduce返回最优值best。 NP=100,F=0.5,CR=0.9,每个子种群独立运行的代 在上述SparkDECC算法中，包含两个循环，即 数MaxGen=-100,合并轮数Cycles=50。为了验证 6)、10)。外循环6)控制问题的全局优化，内循环 SparkDECC算法的可扩展性，将问题的维度D扩展 10)控制子问题的局部优化。 到5000，其他参数保持不变。 上述算法的时间复杂度主要集中在10)，其主 3.3实验结果与分析 要功能是在Num个分区中同步并行优化M个低维 表1为SparkDECC与OXDE、CoDE、jDE、 子问题。一个低维子问题的时间复杂度为O(Mx PSO2刃算法的平均最优值和标准方差的结果对比。 NP),M个低维子问题在一个分区里按串行方式进 5种算法的参数设置一致，各算法独立运行25次。 化Gen代，运行Cycles轮的时间复杂度为O(MxNP× 采用了Wilcoxon秩和检验方法对4种算法的实验 Gen×Cycles)。在上述算法中，略去其他步的时间复 结果进行了统计分析，显著性水平为0.05，其中，“_” 杂度。因此，SparkDECC算法在每个分区的时间复 表示劣于，+”表示优于，“≈”表示相当于。 杂度为O(MxNPxGenxCycles)/Num。 表1中，SparkDECC与其他3种DE算法进行 3 数值实验与分析 对比，结果表明，SparkDECC在f、5、f6、fio~fi3共 7个函数能快速收敛到最优结果，实验数据优于其 3.1测试问题 他3种算法；SparkDECC算法在5、f和6等3个 为了测试SparkDECC算法求解大规模优化问 函数的收敛出现了停滞，实验结果弱于其他算法； 题的性能，本文选取了文献[25]中13个测试函数进 在不可分解函数上各算法的运行效果相当；方要 行实验。其中~为单模函数，f:为多模函数， 劣于DE,优于OXDE和CoDE;带噪声函数5的实 ∫和5为不可分解的函数，其他函数都是可分解 验结果劣于CoDE,优于jDE,与OXDE相当。 表1 SparkDECC、OXDE、CoDE、jDE、PSO算法的平均值、标准差和Vilcoxon秩的检验结果 Table 1 Comparison of SparkDE,OXDE,CoDE,jDE and PSO algorithms for solving the results OXDE (mean+std) CoDE (mean+std) jDE (mean+std) PSO(mean+std) SparkDECC (mean+std) 4.76×102±1.67×102-1.50x10±1.74×105-2.46x10±1.23×103-2.30x10±2.79x10- 5.85x10±1.62×101B 5.27x10'6.89x100-8.89x109.74×101-1.74×100±8.62x1010+ 7.16×10±3.30x10- 6.60x10±1.00×107 5 1.54x106±2.33×105+4.50x106.12×10*3+7.54×10±1.48×10+8.68×10t86.51×10”-5.31×10*7±7.20×106 f 2.59x10±1.84×100=2.67×10±1.95x10=5.04x104.58×10≈4.01x10±7.98x100- 9.76×10±2.22×10 2.28×10±7.08×103- 2.39×10±2.12×102=2.18×103±2.21×102≈9.23x102±1.29×102 1.62x10±1.62×102 7.86×105±8.86x102-5.26×106.26×101-1.06×10±2.98x105-2.30x10±1.29x105 1.60×10±4.73×10 5.68×10±7.25×10≈9.06×10±1.03x10+2.91×10±1.60x101-3.48x1013±3.87×102- 3.62×10±1.67×10 4.17×10±7.27x102+-1.89x10±5.14×105+-4.19×10±3.18×10+-1.34×10±4.51×103+ -6.11×10±1.18×103 4.94×102±5.32×10+ 4.59x10±2.10×102+2.98×10±4.03×10+2.33×10±1.35×105- 1.10x10“±3.93×10 io 6.49x10±2.79×10-2.25x10±1.82×10-5.12×10±7.06x10-2.15×10'±3.77×102- 4.55×10±8.16×109 5.02×10±1.19x10°-7.70x1032.29×102-8.91×10±7.39×10-5.75×102±4.15×101- 3.54×10“±1.03×1014 2 3.01×100±7.11x10-1-5.75×1024.85×102-1.32x10±2.20x106-6.99×10t2±7.75x10*1_ 7.46×10±2.58×103 1.94×10±3.40x102- 1.15x102±7.53×101- 1.14x10*7±8.17×106-7.87×102±8.78×10 8.79x10±3.04×103 + 8/3/2 7/42 7/4/2 12/1/0

① 变异操作，执行式 (1)； ② 交叉操作，执行式 (2)； ③ 选择操作，执行式 (3)，其中子种群在计算适 应度值时，按照其位置信息替换掉 bestInd 中的部 分解。 10) 利用 collect 动作算子将所有低维子种群按 协同机制合并成完整种群，并更新 Pop； 11) 对 Pop 进行全局搜索并返回最优个体 bestInd； 12) 转到 5)； 13) 循环结束，通过 reduce 返回最优值 best。 在上述 SparkDECC 算法中，包含两个循环，即 6)、10)。外循环 6) 控制问题的全局优化，内循环 10) 控制子问题的局部优化。 上述算法的时间复杂度主要集中在 10)，其主 要功能是在 Num 个分区中同步并行优化 M 个低维 子问题。一个低维子问题的时间复杂度为 O(M× NP)，M 个低维子问题在一个分区里按串行方式进 化 Gen 代，运行 Cycles 轮的时间复杂度为 O(M×NP× Gen×Cycles)。在上述算法中，略去其他步的时间复 杂度。因此，SparkDECC 算法在每个分区的时间复 杂度为 O(M×NP×Gen×Cycles)/Num。 3 数值实验与分析 3.1 测试问题 为了测试 SparkDECC 算法求解大规模优化问 题的性能，本文选取了文献[25]中 13 个测试函数进 行实验。其中 f1~f8 为单模函数，f9~f13 为多模函数， f4 和 f5 为不可分解的函数，其他函数都是可分解 的。函数的详细说明详见文献[25]。 3.2 实验设置 本实验采用 Spark 云模型，每个节点的配置如下： 64 bit corei7 CPU，主频 3.4 GB，内存 8 GB，Ubuntu13.10 操作系统，安装使用 Hadoop2.2.0 和 Spark1.2.0，编 程环境为 IntellJ IDEA14.1.2，使用 Scala 和 Java 语言。 为了验证 SparkDECC 的性能以及影响其性能 的各个因素，实验时 SparkDECC 中问题的维度 D=1 000，子问题的维度 DimSub=100，问题规模 NP=100，F=0.5，CR=0.9，每个子种群独立运行的代 数 MaxGen=100，合并轮数 Cycles=50。为了验证 SparkDECC 算法的可扩展性，将问题的维度 D 扩展 到 5 000，其他参数保持不变。 3.3 实验结果与分析 表 1 为 SparkDECC 与 OXDE[26] 、CoDE、jDE、 PSO[27]算法的平均最优值和标准方差的结果对比。 5 种算法的参数设置一致，各算法独立运行 25 次。 采用了 Wilcoxon 秩和检验方法对 4 种算法的实验 结果进行了统计分析，显著性水平为 0.05，其中，“–” 表示劣于，“+”表示优于，“≈”表示相当于。 表 1 中，SparkDECC 与其他 3 种 DE 算法进行 对比，结果表明，SparkDECC 在 f1、f5、f6、f10~f13 共 7 个函数能快速收敛到最优结果，实验数据优于其 他 3 种算法；SparkDECC 算法在 f3、f8 和 f9 等 3 个 函数的收敛出现了停滞，实验结果弱于其他算法； 在不可分解函数 f4 上各算法的运行效果相当；f2 要 劣于 jDE，优于 OXDE 和 CoDE；带噪声函数 f7 的实 验结果劣于 CoDE，优于 jDE，与 OXDE 相当。 表 1 SparkDECC、OXDE、CoDE、jDE、PSO 算法的平均值、标准差和 Wilcoxon 秩的检验结果 Table 1 Comparison of SparkDE, OXDE, CoDE, jDE and PSO algorithms for solving the results F OXDE (mean±std) CoDE (mean±std) jDE (mean±std) PSO (mean±std) SparkDECC (mean±std) f1 4.76×10+2±1.67×10+2－ 1.50×10–5±1.74×10–5－ 2.46×10–6±1.23×10–5－ 2.30×10+6±2.79×10+4－ 5.85×10–13±1.62×10–13 f2 5.27×10+1±6.89×10+0－ 8.89×10–1±9.74×10–1－ 1.74×10–10±8.62×10–10 + 7.16×10+4±3.30×10+4－ 6.60×10–7±1.00×10–7 f3 1.54×10+6±2.33×10+5 + 4.50×10+4±6.12×10+3 + 7.54×10+4±1.48×10+4 + 8.68×10+8±6.51×10+7－ 5.31×10+7±7.20×10+6 f4 2.59×10+1±1.84×10+0 ≈ 2.67×10+1±1.95×10+0 ≈ 5.04×10+1±4.58×10+0 ≈ 4.01×10+2±7.98×10+0－ 9.76×10+1±2.22×10–1 f5 2.28×10+4±7.08×10+3－ 2.39×10+3±2.12×10+2 ≈ 2.18×10+3±2.21×10+2 ≈ 9.23×10+12±1.29×10+12－ 1.62×10+3±1.62×10+2 f6 7.86×10+3±8.86×10+2－ 5.26×10+1±6.26×10+1－ 1.06×10+4±2.98×10+3－ 2.30×10+6±1.29×10+5－ 1.60×10–1±4.73×10–1 f7 5.68×10+0±7.25×10–1 ≈ 9.06×10–1±1.03×10–1 + 2.91×10+1±1.60×10+1－ 3.48×10+13±3.87×10+12－ 3.62×10+0±1.67×10–1 f8 –4.17×10+5±7.27×10+2 + –1.89×10+5±5.14×10+3 + –4.19×10+5±3.18×10–1 + –1.34×10+5±4.51×10+3 + –6.11×10+4±1.18×10+3 f9 4.94×10+2±5.32×10+1 + 4.59×10+3±2.10×10+2 + 2.98×10+0±4.03×10+0 + 2.33×10+6±1.35×10+5－ 1.10×10+4±3.93×10+1 f10 6.49×10+0±2.79×10–1－ 2.25×10+0±1.82×10–1－ 5.12×10+0±7.06×10–1－ 2.15×10+1±3.77×10–2－ 4.55×10–8±8.16×10–9 f11 5.02×10+0±1.19×10+0－ 7.70×10–3±2.29×10–2－ 8.91×10–1±7.39×10–1－ 5.75×10+2±4.15×10+1－ 3.54×10–14±1.03×10–14 f12 3.01×10+0±7.11×10–11－ 5.75×10–2±4.85×10–2－ 1.32×10+6±2.20×10+6－ 6.99×10+12±7.75×10+11－ 7.46×10–4±2.58×10–3 f13 1.94×10+3±3.40×10+2－ 1.15×10+2±7.53×10+1－ 1.14×10+7±8.17×10+6－ 7.87×10+12±8.78×10+11－ 8.79×10–4±3.04×10–3 –/+/≈ 8/3/2 7/4/2 7/4/2 12/1/0 ·246· 智 能 系 统 学 报 第 13 卷

第2期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·247· SparkDECC与PSO算法的结果对比，实验 这8个函数)，选取了各算法独立运行20次中的平 结果表明SparkDECC算法除函数外其他都 均收敛数据，收敛取值以10为底的对数形式，曲线 优于PSO,说明SparkDECC算法总体性能优于 图如图3所示。从图3可以看出SparkDECC算法 PSO。 的收敛能力较强，在函数f、fo:上的收敛曲线呈 函数收敛曲线图主要用来表示算法求解最优值 直线下降，收敛性能强；函数5、6、人：在进化的前期 的一种趋势走向，函数曲线下降得越快，收敛性能 有很好的收敛速度，但在后期出现了一定程度的局 越好。为了比较4种不同DE算法在、、5、6、、 部收敛；函数∫，，在整个进化过程中处于局部收 、1、:等函数的收敛性能（受篇幅限制，仅选择 敛，收敛性能弱，收敛效果要劣于其他算法。 10 8.0 1.5 SakDEC℃ --OXDE 7.0 DE 0 6.5 ooooooooooebo8oooooo SparkDECC 6.0 -OXDE 5.5 -10 D一DE 米一CoDE 5.0 米 米米 5×106 米来 -15 4.5 3 ×10 函数评价次数 函数评价次数 (a)f (b)月 SparkDECC 10净 OXDE iDE SparkDECC R eOXDE D一DE ·CoDE 米一米米 米 ×10 0 2 3 4 3 ×10 函数评价次数 函数评价次数 (c) (d)f 2 米 一米 米 米一米米 0 999999e9o9oo6g0000 2 SparkDECC 2 -OXDE -a SparkDECC iDE eOXDE 米一心0)日 EPPEDPEDPPDDD D一DE CoDE 5*10s 1 3 5x10 函数评价次数 函数评价次数 (e) (⑤fio 99eee9e0eee9999界 SBDDDDDDDDDDDDDDDDDDDDD 0 米一米米米 总 米 米 义 5 SparkDECC OXDE 0 OXDE jDE D一iDE CoDE 米一CoDE -10 ×10 0 1 3 4 5*10s 函数评价次数 函数评价次数 (g)f (h)/ 图3收敛图 Fig.3 Convergence graph

SparkDECC 与 PSO 算法的结果对比，实验 结果表 明 SparkDECC 算法除函 数 f8 外其他都 优于 PSO，说明 SparkDECC 算法总体性能优于 PSO。 函数收敛曲线图主要用来表示算法求解最优值 的一种趋势走向，函数曲线下降得越快，收敛性能 越好。为了比较 4 种不同 DE 算法在 f1、f3、f5、f6、f9、 f10、f11、f13 等函数的收敛性能 (受篇幅限制，仅选择 这 8 个函数)，选取了各算法独立运行 20 次中的平 均收敛数据，收敛取值以 10 为底的对数形式，曲线 图如图 3 所示。从图 3 可以看出 SparkDECC 算法 的收敛能力较强，在函数 f1、f10、f11 上的收敛曲线呈 直线下降，收敛性能强；函数 f5、f6、f13 在进化的前期 有很好的收敛速度，但在后期出现了一定程度的局 部收敛；函数 f3，f9 在整个进化过程中处于局部收 敛，收敛性能弱，收敛效果要劣于其他算法。 SparkDECC OXDE jDE CoDE 2 0 −2 −4 −6 −8 0 1 2 3 4 5 (f) f10 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ SparkDECC OXDE jDE CoDE 0 1 2 3 4 5 (g) f11 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ 5 0 −5 −10 ×106 ᪜⁍䃰У᪜ܩ 10 5 0 −5 −10 −150 1 2 3 4 5 (a) f1 ը᪜ܩ౳᎟ SparkDECC OXDE jDE CoDE 8.0 7.5 7.0 6.5 6.0 5.5 5.0 4.5 0 1 2 3 4 5 (b) f3 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ SparkDECC OXDE jDE CoDE 0 1 2 3 4 5 (c) f5 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ 10 8 6 4 SparkDECC OXDE jDE CoDE 0 1 2 3 4 5 (d) f6 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ 6 4 2 0 SparkDECC OXDE jDE CoDE 1 2 3 4 5 (e) f9 ×106 ᪜⁍䃰У᪜ܩ ը᪜ܩ౳᎟ 4 3 2 1 0 SparkDECC OXDE jDE CoDE 0 1 2 3 4 5 (h) f13 ը᪜ܩ౳᎟ ×106 ᪜⁍䃰У᪜ܩ 10 5 0 SparkDECC OXDE jDE CoDE 图 3 收敛图 Fig. 3 Convergence graph 第 2 期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·247·

·248· 智能系统学报 第13卷 综合以上实验数据分析表明，SparkDECC算法 均时间。实验时单峰函数选取了、方和5，多峰函 能有效地求解大规模优化问题，提高了DE算法的 数选取了f、,和3。针对这6个高维优化函数， 收敛精度和收敛速率。 设定了3种不同的评价次数即5E6、2.5E6和5E5, 加速比2是衡量算法并行性的有效指标，其定 分别独立执行10次。图4的加速比表明，SparkDECC 义如式（⑤）所示。 算法在测试高维优化函数上，随着分区数的增加， T.(1) S(M）=T.M 算法执行时间逐渐减少，加速效果越好。当分区数 (5) 增加到5的时候，加速比几乎接近5倍，与2.2节中对 式中：T(1)代表在一个分区上独立运行k次的平均 时间复杂度的分析一致。此外，函数的加速曲线与 时间，T(Mn)代表在n个分区上独立运行k次的平 函数的评价次数关系不明显，表明了加速性能的稳定。 5 9FES=5.00×10 0-FES=5.00×10 b-FES=2.50×105 4 D-FES=2.50×10的 +-FES=5.00×10 +-FES=5.00×x10 出 3 2 3 4 分区 分区 (a)h b)3 5 e-FES=5.00×10 e-FES=5.00×109 DFES=2.50×10 -FES=2.50×10 +FES=5.00×109 +-FES=5.00x10 出 2 3 分区 分区 (c)f (d)f -e-FES=5.00×10 eFES=5.00x105 D-FES=2.50×10的 4 D-FES=2.50x10 +—FES=5.00×10 +-FES=5.00x10 3 分区 分 (e)f (⑤f加 图4加速比 Fig.4 Acceleration ratio 3.4协同方式对算法性能的影响 对比实验。这两种协同方式衍生出两种算法，即 SparkDECC算法对子种群进行局部寻优后，需 SparkDECC-1算法和SparkDECC-2算法，这两种算 要合并所有子种群并进行全局搜索。SparkDECC 法在SparkDECC算法的基础上，子种群按不同的协 算法按照原模型进行组合，整个种群保持原来的结 同方式进行组合。其中，SparkDECC-1算法在所有 构。为了分析子种群合并机制对SparkDECC算法 子种群组合之前，首先将所有子种群的个体按其适 性能的影响，本文选取了两种不同的协同方式进行 应度值升序排序，最后将所有子种群按线性方式组

综合以上实验数据分析表明，SparkDECC 算法 能有效地求解大规模优化问题，提高了 DE 算法的 收敛精度和收敛速率。 加速比[28]是衡量算法并行性的有效指标，其定 义如式 (5) 所示。 S k (Mn) = Tk (1) Tk (Mn) (5) Tk (1) Tk (Mn) 式中： 代表在一个分区上独立运行 k 次的平均 时间， 代表在 n 个分区上独立运行 k 次的平 均时间。实验时单峰函数选取了 f1、f3 和 f5，多峰函 数选取了 f9、f11 和 f13。针对这 6 个高维优化函数， 设定了 3 种不同的评价次数即 5E6、2.5E6 和 5E5， 分别独立执行 10 次。图 4 的加速比表明，SparkDECC 算法在测试高维优化函数上，随着分区数的增加， 算法执行时间逐渐减少，加速效果越好。当分区数 增加到 5 的时候，加速比几乎接近 5 倍，与 2.2 节中对 时间复杂度的分析一致。此外，函数的加速曲线与 函数的评价次数关系不明显，表明了加速性能的稳定。 3.4 协同方式对算法性能的影响 SparkDECC 算法对子种群进行局部寻优后，需 要合并所有子种群并进行全局搜索。SparkDECC 算法按照原模型进行组合，整个种群保持原来的结 构。为了分析子种群合并机制对 SparkDECC 算法 性能的影响，本文选取了两种不同的协同方式进行 对比实验。这两种协同方式衍生出两种算法，即 SparkDECC-1 算法和 SparkDECC-2 算法，这两种算 法在 SparkDECC 算法的基础上，子种群按不同的协 同方式进行组合。其中，SparkDECC-1 算法在所有 子种群组合之前，首先将所有子种群的个体按其适 应度值升序排序，最后将所有子种群按线性方式组 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (a) f1 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (d) f9 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (b) f3 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (e) f11 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (c) f5 a/c䕋ߌ ࡦܲ FES=5.00×106 FES=2.50×106 FES=5.00×105 5 4 3 2 1 1 2 3 4 5 (f) f13 图 4 加速比 Fig. 4 Acceleration ratio ·248· 智 能 系 统 学 报 第 13 卷

第2期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·249· 合成完整的种群；SparkDECC.-2算法将所有子种群 f乃、f6、人、，等4个函数优于SparkDECC算法， 中的个体按随机方式组合成完整的种群。为了验 SparkDECC-2算法中的所有函数都劣于Spark- 证3种不同的SparkDECC算法的性能，选择了相同 DECC算法。总之，SparkDECC算法的其他组合方 的参数设置，分别在13个函数上独立运行20次， 式不能有效地提高算法的收敛精度，且增加了种群 实验结果如表2所示。 个体的排列组合运算，算法的运行时间随之增加。 表2的实验结果表明，SparkDECC算法在f、 因此，SparkDECC算法选择最初的协同方式合并子 5、5fof2f:等8个函数的实验结果要优 种群，维持原种群的结构，能有效提高算法的精度 于其他两种协同方式。其中，SparkDECC-l算法在 和时间。 表2 SparkDECC3种不同协同方式的实验结果 Table 2 Experimental results of SparkDECC on three different cooperative modes SparkDECC-1 (mean+std) SparkDECC-2(mean+std) SparkDECC(mean±std) 无 1.39×102±3.11×1013 3.06×10±4.79x104 5.85×103±1.62×1013 五 1.11×10±1.86×107- 4.73×10±3.65×101 6.60×10±1.00×10 5 4.96×107±9.00×106+ 8.35×10±1.62x107≈ 5.31×107±7.20×10 A 9.77x×10'±2.62×10≈ 9.95×10'±1.50x10≈ 9.76×10±2.22×10 5 1.68×10±1.63×102≈ 1.43×10*10±3.70×108- 1.62×10±1.62×102 6 5.00×102±2.24×10+ 3.05×10±5.15x104- 1.60×10±4.73x10 方 2.27×10±1.42×10≈ 2.35×10±4.63×103_ 3.62×10±1.67x101 8 -7.88×10±7.81×102+ -1.76×102.74x103 6.11×10±1.18×109 5 1.00×10±7.44×10+ 1.76×10±1.28×102≈ 1.10x10±3.93×10 fio 7.07×10±7.73×10≈ 2.11×10'±1.43×102- 4.55×103±8.16×109 1.72×103±4.53×103- 2.78×10"±2.74×102 3.54×10“±1.03×1014 fi2 6.22×10±2.78×103≈ 3.55x100±7.77×10 7.46×10±2.58×103 3 5.49×10±2.46×103≈ 6.57×1010±1.20x10°- 8.79×10±3.04×103 3/4/6 9/0/4 3.5子种群数对算法的影响 数，SparkDECC的种群多样性随子种群数的增加逐 为了分析子种群数对SparkDECC性能的影响， 渐增强，提高了解的收敛性。然后，随子问题数目 分别选取了不同数目的子种群进行对比实验，如1、 增多，子问题之间的交互时间随之增加，从而增加 2、5、10、20等5种不同的子种群。根据2.2节中的 了函数的收敛时间。表4的结果显示，函数的运行 子种群数的计算公式，计算子种群的维度，如问题 时间与子问题数成正比，与2.2节中的时间复杂度 维度为1000，则上述5种不同子种群的维度分别 相吻合。当子问题数增加到20时，13个函数总的 为1000、500、200、100、50。算法的其他参数设置 平均时间是1个子问题的11.5倍。因此，Spark- 保持一致，分别在13个测试函数上独立运行了 DECC应从收敛时间和收敛精度两方面综合考虑选 20次，表3和表4分别记录了5种不同子种群数下 取合适的子种群数。 的平均最优值和平均运行时间。 3.6子种群进化代数对算法的影响 表3和表4的结果分析发现，、、6、厂8、f、 SparkDECC算法在子种群进化若干代后，需要 f2、f:共7个函数的收敛精度随子种群数的增加而 合并成新的全局最优解。因此，为了探索子种群局 逐渐增强。5、4、这3个函数解的精度在种群不 部寻优的代数Gen对SparkDECC算法的影响，本 分解的情况下达到最优，种群维度的分解并没有提 文选取了10、20、50、100、250等5种情况分别进行 高解的精度。，的解在子种群数为5时达到最优， 实验。5种情况的其他参数一致并设置相同的函数 再增加子种群数并不会提高解的精度。65、：的解 评价次数，分别独立运行25次，平均运行时间及结 在子种群数为10时达到最优。因此，对于可分解函 果分别如表5和表6所示

合成完整的种群；SparkDECC-2 算法将所有子种群 中的个体按随机方式组合成完整的种群。为了验 证 3 种不同的 SparkDECC 算法的性能，选择了相同 的参数设置，分别在 13 个函数上独立运行 20 次， 实验结果如表 2 所示。 表 2 的实验结果表明，SparkDECC 算法在 f1、 f2、f4、f5、f10、f11、f12、f13 等 8 个函数的实验结果要优 于其他两种协同方式。其中，SparkDECC-1 算法在 f 3、f 6、f 8、f 9 等 4 个函数优于 SparkDECC 算法， SparkDECC-2 算法中的所有函数都劣于 Spark￾DECC 算法。总之，SparkDECC 算法的其他组合方 式不能有效地提高算法的收敛精度，且增加了种群 个体的排列组合运算，算法的运行时间随之增加。 因此，SparkDECC 算法选择最初的协同方式合并子 种群，维持原种群的结构，能有效提高算法的精度 和时间。 3.5 子种群数对算法的影响 为了分析子种群数对 SparkDECC 性能的影响， 分别选取了不同数目的子种群进行对比实验，如 1、 2、5、10、20 等 5 种不同的子种群。根据 2.2 节中的 子种群数的计算公式，计算子种群的维度，如问题 维度为 1 000，则上述 5 种不同子种群的维度分别 为 1 000、500、200、1 00、50。算法的其他参数设置 保持一致，分别在 13 个测试函数上独立运行了 20 次，表 3 和表 4 分别记录了 5 种不同子种群数下 的平均最优值和平均运行时间。 表 3 和表 4 的结果分析发现，f1、f2、f6、f8、f10、 f12、f13 共 7 个函数的收敛精度随子种群数的增加而 逐渐增强。f3、f4、f9 这 3 个函数解的精度在种群不 分解的情况下达到最优，种群维度的分解并没有提 高解的精度。f7 的解在子种群数为 5 时达到最优， 再增加子种群数并不会提高解的精度。f5、f11 的解 在子种群数为 10 时达到最优。因此，对于可分解函 数，SparkDECC 的种群多样性随子种群数的增加逐 渐增强，提高了解的收敛性。然后，随子问题数目 增多，子问题之间的交互时间随之增加，从而增加 了函数的收敛时间。表 4 的结果显示，函数的运行 时间与子问题数成正比，与 2.2 节中的时间复杂度 相吻合。当子问题数增加到 20 时，13 个函数总的 平均时间是 1 个子问题的 11.5 倍。因此，Spark￾DECC 应从收敛时间和收敛精度两方面综合考虑选 取合适的子种群数。 3.6 子种群进化代数对算法的影响 SparkDECC 算法在子种群进化若干代后，需要 合并成新的全局最优解。因此，为了探索子种群局 部寻优的代数 Gen 对 SparkDECC 算法的影响，本 文选取了 10、20、50、100、250 等 5 种情况分别进行 实验。5 种情况的其他参数一致并设置相同的函数 评价次数，分别独立运行 25 次，平均运行时间及结 果分别如表 5 和表 6 所示。 表 2 SparkDECC 3 种不同协同方式的实验结果 Table 2 Experimental results of SparkDECC on three different cooperative modes F SparkDECC-1 (mean±std) SparkDECC-2 (mean±std) SparkDECC (mean±std) f1 1.39×10–12±3.11×10–13－ 3.06×10+6±4.79×10+4－ 5.85×10–13±1.62×10–13 f2 1.11×10–6±1.86×10–7－ 4.73×10+3±3.65×10+1－ 6.60×10–7±1.00×10–7 f3 4.96×10+7±9.00×10+6+ 8.35×10+7±1.62×10+7 ≈ 5.31×10+7±7.20×10+6 f4 9.77×10+1±2.62×10–1 ≈ 9.95×10+1±1.50×10–1 ≈ 9.76×10+1±2.22×10–1 f5 1.68×10+3±1.63×10+2 ≈ 1.43×10+10±3.70×10+8－ 1.62×10+3±1.62×10+2 f6 5.00×10–2±2.24×10–1+ 3.05×10+6±5.15×10+4－ 1.60×10–1±4.73×10–1 f7 2.27×10+0±1.42×10–1 ≈ 2.35×10+5±4.63×10+3－ 3.62×10+0±1.67×10–1 f8 –7.88×10+4±7.81×10+2+ –1.76×10+4±2.74×10+3－ –6.11×10+4±1.18×10+3 f9 1.00×10+4±7.44×10+1+ 1.76×10+4±1.28×10+2 ≈ 1.10×10+4±3.93×10+1 f10 7.07×10–8±7.73×10–9 ≈ 2.11×10+1±1.43×10–2－ 4.55×10–8±8.16×10–9 f11 1.72×10–3±4.53×10–3－ 2.78×10+4±2.74×10+2－ 3.54×10–14±1.03×10–14 f12 6.22×10–4±2.78×10–3 ≈ 3.55×10+10±7.77×10+8－ 7.46×10–4±2.58×10–3 f13 5.49×10–4±2.46×10–3 ≈ 6.57×10+10±1.20×10+9－ 8.79×10–4±3.04×10–3 –/+/≈ 3/4/6 9/0/4 第 2 期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·249·

·250· 智能系统学报 第13卷 表3 SparkDECC在不同子种群数的实验结果 Table 3 Experimental results of SparkDECC in different number of sub-populations FIM I(mean±std) 2(mean+std) 5(mean+std) 10 (mean+std) 20(mean±std) 3.67×10±4.80x103 2.34×10±8.35×102 2.78×103±1.94×1035.69×10-15±1.36×10131.21×1028±3.14×1029 5 3.18×102±2.05×10 5.63×10±7.90×1003.77x102±1.78×102 6.89×10±8.90×1085.79x10±8.83×105 2.27×107±2.28×10 3.05×107±3.89x106 4.21x106.45×1065.30x107±1.05x107 5.03×10±1.09x10*7 9.43×10"±1.33×100 9.66×10±4.75×10 9.74×10±2.58×101 9.75×10±3.57×10 9.77x10'±2.94×10 61.62x10*7±2.77x1066.65×10±2.33x1053.20×1034.66×1021.64×1041.45×102 1.66×10±1.28×102 6 4.18×10°±4.83×1036.08×10±1.34×103 8.12×10'±8.13×1012.00x10±4.08×10 0.00x10°±0.00×100 5 5.24×102±3.18x×1022.22×10±5.63×100 2.83×10°±1.70×1013.63×10±1.35x104.65×10±1.53x10-01 6-2.87x10±1.54×103-3.43×10±1.17x103一4.64×10±1.19x103-6.15x1041.12×103 -8.27x10±1.06×103 3.83×10°±4.48×1029.20x10*±3.00x10t21.10x10±7.07x×1011.10x10±6.00×101 1.04×10±5.14×10 9.70×10°±4.05×10 4.99x10°±3.84×10 6.37×10±4.80×10 4.60x10±5.22x1091.98×10B±9.93×1015 13.34×10±4.28×101 2.13×10±6.73×100 1.29×102±4.73×102 3.95×10±1.97×1031.97x103±4.66×10 2 2.12×10±7.51×105 1.11×10±5.63×10 7.51x10'±5.03x10' 4.98×10±2.49x1035.50x1029±2.49x102 31.90×107±5.26×106 8.57x10±4.55×105 2.73x10±1.06×10*2 8.79x10'±3.04×1039.7×1028±3.24×1028 表4 SparkDECC在不同子种群数的平均运行时间 表5进化代数对SparkDECC优化时间的影响 Table 4 The average running time of SparkDECC Table 5 Optimization time of SparkDECC with in different number of sub-populations ms generations ms FIM 2 10 20 F/Gen 10 20 50 100 250 万1.70×101.75×102.14×10°2.67×1043.81×10 3.69×1043.50×10°2.85x1042.72×1042.65×10 万1.70x101.88×102.46×1043.33×105.16x10 4.34×104.07×103.48x10°3.34×1043.25×104 52.06×1053.94x1059,39x1051.86x1063.76×106 5 1.91×1061.89x1061.87x1061.85×1061.86×106 61.64x101.76×102.09x102.52×10345×10 万3.44x102.99x10“2.70×102.56×10245×10 51.66×101.79×1042.23×102.87×104.22×10 63.89x103.37x103.03×102.89x102.79x10 61.91×10228×102.71×1043.37×1044.98×10 65.79x1044.89×103.72x103.28×1043.25x10 万1.68x101.78×1042.20×102.84×1044.17×104 万3.91×1043.41×103.01×102.86×102.75×10 64.05×106.51x1041.34×1052.49x105481x105 万2.62x1052.57x1052.52×1052.54x105248×105 6355×105.66×101.13×1052.08×1053.94×105 5222x1052.15x1052.08×1052.04×1052.02×105 f03.60×10°5.58x×101.02×1051.78×1053.36×105 0229x1052.23×1051.84×1051.76×1051.75×105 f13.85x1045.91x101.18×1052.20x105425×105 12.42x105235x1052.19x1052.17x1052.16x105 f24.99x107.91x1041.44×1052.37x105441x105 24.92x1054.76×1053.85×1052.34×105229x105 f36.12x109.91x1041.63×1052.46×1054.41×105 3542x105527x1054.06×1052.42×105234x105 表6的结果显示，f5、6、o等6个函数 Gen的函数优化时间几乎相同。但从表5的结果显 的求解精度随进化代数的增加逐渐提高。和∫ 示，SparkDECC算法的优化时间随参数Gen的增加 两个函数增加局部寻优的代数并不能提高解的精 而逐渐减少。其主要原因是，由2.2节中的算法可 度，函数易陷入局部最优。6、2和：等3个函数 知，SparkDECC算法在评价次数相同的情况下，合 的结果在进化代数为100时达到最优。方和，两 并轮数Cycle的值随进化代数Gen变大而逐渐变 个函数在进化代数为50时达到最优，进化代数的增 小，减少了广播变量执行的次数，因此，函数的优化 加并不能提高解的质量。由2.2节中的时间复杂度 时间会相应减少，但总的优化时间相差无异。 可知，在评价次数相同的情况下，不同进化代数 总之，SparkDECC算法的收敛精度与子问题的

表 6 的结果显示，f1、f2、f7、f8、f9、f10 等 6 个函数 的求解精度随进化代数的增加逐渐提高。f3 和 f4 两个函数增加局部寻优的代数并不能提高解的精 度，函数易陷入局部最优。f6、f12 和 f13 等 3 个函数 的结果在进化代数为 100 时达到最优。f5 和 f11 两 个函数在进化代数为 50 时达到最优，进化代数的增 加并不能提高解的质量。由 2.2 节中的时间复杂度 可知，在评价次数相同的情况下，不同进化代数 Gen 的函数优化时间几乎相同。但从表 5 的结果显 示，SparkDECC 算法的优化时间随参数 Gen 的增加 而逐渐减少。其主要原因是，由 2.2 节中的算法可 知，SparkDECC 算法在评价次数相同的情况下，合 并轮数 Cycle 的值随进化代数 Gen 变大而逐渐变 小，减少了广播变量执行的次数，因此，函数的优化 时间会相应减少，但总的优化时间相差无异。 总之，SparkDECC 算法的收敛精度与子问题的 表 3 SparkDECC 在不同子种群数的实验结果 Table 3 Experimental results of SparkDECC in different number of sub-populations F/M 1 (mean±std) 2 (mean±std) 5 (mean±std) 10 (mean±std) 20 (mean±std) f1 3.67×10+4±4.80×10+3 2.34×10+3±8.35×10+2 2.78×10–3±1.94×10–3 5.69×10–13±1.36×10–13 1.21×10–28±3.14×10–29 f2 3.18×10+2±2.05×10+1 5.63×10+1±7.90×10+0 3.77×10–2±1.78×10–2 6.89×10–7±8.90×10–8 5.79×10–14±8.83×10–15 f3 2.27×10+7±2.28×10+6 3.05×10+7±3.89×10+6 4.21×10+7±6.45×10+6 5.30×10+7±1.05×10+7 5.03×10+7±1.09×10+7 f4 9.43×10+1±1.33×10+0 9.66×10+1±4.75×10–1 9.74×10+1±2.58×10–1 9.75×10+1±3.57×10–1 9.77×10+1±2.94×10–1 f5 1.62×10+7±2.77×10+6 6.65×10+5±2.33×10+5 3.20×10+3±4.66×10+2 1.64×10+3±1.45×10+2 1.66×10+3±1.28×10+2 f6 4.18×10+4±4.83×10+3 6.08×10+3±1.34×10+3 8.12×10+1±8.13×10+1 2.00×10–1±4.08×10–1 0.00×10+0±0.00×10+0 f7 5.24×10+2±3.18×10+2 2.22×10+1±5.63×10+0 2.83×10+0±1.70×10–1 3.63×10+0±1.35×10–1 4.65×10+0±1.53×10-01 f8 –2.87×10+4±1.54×10+3 –3.43×10+4±1.17×10+3 –4.64×10+4±1.19×10+3 –6.15×10+4±1.12×10+3 –8.27×10+4±1.06×10+3 f9 3.83×10+3±4.48×10+2 9.20×10+3±3.00×10+2 1.10×10+4±7.07×10+1 1.10×10+4±6.00×10+1 1.04×10+4±5.14×10+1 f10 9.70×10+0±4.05×10–1 4.99×10+0±3.84×10–1 6.37×10–1±4.80×10–1 4.60×10–8±5.22×10–9 1.98×10–13±9.93×10–15 f11 3.34×10+2±4.28×10+1 2.13×10+1±6.73×10+0 1.29×10–2±4.73×10–2 3.95×10–4±1.97×10–3 1.97×10–03±4.66×10–3 f12 2.12×10+6±7.51×10+5 1.11×10+5±5.63×10+4 7.51×10+1±5.03×10+1 4.98×10–4±2.49×10–3 5.50×10–29±2.49×10–29 f13 1.90×10+7±5.26×10+6 8.57×10+5±4.55×10+5 2.73×10+2±1.06×10+2 8.79×10–4±3.04×10–3 9.77×10–28±3.24×10–28 表 4 SparkDECC 在不同子种群数的平均运行时间 Table 4 The average running time of SparkDECC in different number of sub-populations ms F/M 1 2 5 10 20 f1 1.70×10+4 1.75×10+4 2.14×10+4 2.67×10+4 3.81×10+4 f2 1.70×10+4 1.88×10+4 2.46×10+4 3.33×10+4 5.16×10+4 f3 2.06×10+5 3.94×10+5 9.39×10+5 1.86×10+6 3.76×10+6 f4 1.64×10+4 1.76×10+4 2.09×10+4 2.52×10+4 3.45×10+4 f5 1.66×10+4 1.79×10+4 2.23×10+4 2.87×10+4 4.22×10+4 f6 1.91×10+4 2.28×10+4 2.71×10+4 3.37×10+4 4.98×10+4 f7 1.68×10+4 1.78×10+4 2.20×10+4 2.84×10+4 4.17×10+4 f8 4.05×10+4 6.51×10+4 1.34×10+5 2.49×10+5 4.81×10+5 f9 3.55×10+4 5.66×10+4 1.13×10+5 2.08×10+5 3.94×10+5 f10 3.60×10+4 5.58×10+4 1.02×10+5 1.78×10+5 3.36×10+5 f11 3.85×10+4 5.91×10+4 1.18×10+5 2.20×10+5 4.25×10+5 f12 4.99×10+4 7.91×10+4 1.44×10+5 2.37×10+5 4.41×10+5 f13 6.12×10+4 9.91×10+4 1.63×10+5 2.46×10+5 4.41×10+5 表 5 进化代数对 SparkDECC 优化时间的影响 Table 5 Optimization time of SparkDECC with generations ms F/Gen 10 20 50 100 250 f1 3.69×10+4 3.50×10+4 2.85×10+4 2.72×10+4 2.65×10+4 f2 4.34×10+4 4.07×10+4 3.48×10+4 3.34×10+4 3.25×10+4 f3 1.91×10+6 1.89×10+6 1.87×10+6 1.85×10+6 1.86×10+6 f4 3.44×10+4 2.99×10+4 2.70×10+4 2.56×10+4 2.45×10+4 f5 3.89×10+4 3.37×10+4 3.03×10+4 2.89×10+4 2.79×10+4 f6 5.79×10+4 4.89×10+4 3.72×10+4 3.28×10+4 3.25×10+4 f7 3.91×10+4 3.41×10+4 3.01×10+4 2.86×10+4 2.75×10+4 f8 2.62×10+5 2.57×10+5 2.52×10+5 2.54×10+5 2.48×10+5 f9 2.22×10+5 2.15×10+5 2.08×10+5 2.04×10+5 2.02×10+5 f10 2.29×10+5 2.23×10+5 1.84×10+5 1.76×10+5 1.75×10+5 f11 2.42×10+5 2.35×10+5 2.19×10+5 2.17×10+5 2.16×10+5 f12 4.92×10+5 4.76×10+5 3.85×10+5 2.34×10+5 2.29×10+5 f13 5.42×10+5 5.27×10+5 4.06×10+5 2.42×10+5 2.34×10+5 ·250· 智 能 系 统 学 报 第 13 卷

第2期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·251· 进化代数和合并轮数关系紧密，增加子问题的进化 加而减少。因此，为了在全局搜索和局部寻优之间 代数提高了子问题的局部寻优能力。子问题的合并 达到平衡，并能在有效时间内提高算法的收敛精 轮数改善了问题多样性。但是，在评价次数相同的 度，我们可以选择合适的进化代数，合理分配计算 情况下，子问题的合并轮数随子种群进化代数的增 资源。 表6进化代数对SparkDECC优化性能的影响 Table 6 Performance affection of SparkDECC with generations F/Gen l0(mean±std) 20(mean+std) 50(mean+std) 100(mean±std) 250(mean+std) 1.51×10±1.60×10 1.14×10±1.80×10 7.21×10±2.67×105 5.79×10±1.52×10B 1.73×1016±4.28×1017 五 3.15×10±1.99×10 2.68×10±2.26×101 2.21×10±3.11×103 6.62×10±8.59×108 4.63×10±7.16×1010 5 3.62×10”±3.33×106 4.15x107±7.19x106 4.88×10±7.61×106 5.06×10±1.13×107 5.60x10*±1.68×10*7 A 9.72×10±2.55×109.72×10±3.41×1019.75×10±3.13×109.75×10±3.14×10 9.77×10±3.44×10 5 5.01×10±9.54×1073.39×10°±9.52×107 1.08×10±6.90x1011.70×10±2.96×102 2.47×10±2.15x102 6 1.51×10±1.76×101.13×10±2.24×102.39×10±3.29×1002.40x10±8.31×10 1.52×10±2.49×100 1.21x10±2.57x103828×10±2.78×1038.79×10±3.26×1013.64×10±1.48×10 1.67×10±8.74×102 友 -4.64×10±1.28×103-5.09×10°±9.98×102-5.68×10°±9.84×102-6.08×10±1.11×103-6.62×10°±6.21×102 6 1.38×10±7.15×101.32×10°±6.11×1011.21×10±5.44×1011.10×10±7.38×101 9.94x10±6.59×10t1 fio 2.01×10±1.92×1021.95×104.83×1025.70×10±1.03×10 4.63×108±7.33x109 2.10×109±4.34×1010 加 1.36×10±1.44×102 1.01x10*±1.88×1024.83x105±1.55×1063.94×10±1.97×103 1.08×103±3.11×103 1.05×1010±2.76×10*86.77x10”2.08x1081.35×10±2.7x1079.57×10"±7.66x101.24x10±3.48×10 2.09×10±3.83x101.37x1010±5.74×107.38×10±1.79x1068.79×10±3.04×103 2.08×10±7.75×10 3.7 SparkDECC算法的可扩展性分析 5000D,问题规模NP=100,算法独立运行10次。 为了验证SparkDECC算法的可扩展性，本文将 OXDE、CoDE和jDE3种算法在5000维的实 文献25]中的13个测试函数扩展到5000维进行实 验参数与SparkDECC的参数一致，实验结果如 验。子问题的维度S=100,F=0.5,CR=0.9,FES= 表7。 表7 SparkDECC、OXDE、CoDE、jDE算法在5OO0维的平均值、标准差和Vilcoxon秩和检验结果 Table 7 Comparison of SparkDECC,OXDE,CoDE,jDE algorithms for solving the results in 5 000 dimension OXDE (mean+std) CoDE(mean±std jDE(mean±std) SparkDECC(mean±std 5.69×10±4.69×103 4.34×10±1.04×103 4.49×10±1.77×10“ 3.56×102±3.90x1013 五 Inf+NaN Inf+NaN- InftNaN 3.67×10±2.04×10 万 1.05×107±1.33×10+ 6.88×10±9.94×10+ 1.43×106±3.02×10+ 2.51×109±6.30x10+8 2.83×10±1.82×100≈ 3.25×10±1.99×100≈ 5.98×10t±9.43×10≈ 9.93×10±9.33×102 5 5.80x10±9.98×10°- 1.86x10±6.81×10 2.52×10±1.06×108 9.87×10±3.29x102 6 1.92×10±1.52×104 2.64×10±2.86×103- 4.67×10±1.40x105- 1.00×10±6.67×10 5 7.10x10±1.76×102- 7.11x10±1.16×10≈ 2.65×10±1.12×104- 2.16×10'±3.59×10 -2.03×10±4.91×105 -1.26×10±8.25×104_ -2.09×10±4.17×102_ -2.73×10±1.48×103 6 6.68×10±3.36×102+ 2.79×10±1.97×102+ 3.34×10±1.09×10+ 5.67×10±1.31×10*2 fio 9.13×10°±2.84×10- 7.28×10±2.39x10- 1.29×10±2.06×10 6.82×10±3.46×109 加 4.62×102±7.75×101- 3.78×10±6.80×100- 5.45×10±1.07×102- 5.81×10“±5.96×1015 f2 4.55×10±1.63×103_ 1.90x10±3.67×10 1.16×10±4.62×108 6.22×10±1.97x10 f 4.56×10±8.23×105- 4.24×10±7.11×102 2.72×10”±9.69×108 4.40×103±1.39x102 10/2/1 9/2/2 10/2/1

进化代数和合并轮数关系紧密，增加子问题的进化 代数提高了子问题的局部寻优能力。子问题的合并 轮数改善了问题多样性。但是，在评价次数相同的 情况下，子问题的合并轮数随子种群进化代数的增 加而减少。因此，为了在全局搜索和局部寻优之间 达到平衡，并能在有效时间内提高算法的收敛精 度，我们可以选择合适的进化代数，合理分配计算 资源。 3.7 SparkDECC 算法的可扩展性分析 为了验证 SparkDECC 算法的可扩展性，本文将 文献[25]中的 13 个测试函数扩展到 5 000 维进行实 验。子问题的维度 S=100，F=0.5，CR=0.9，FES= 5 000 D，问题规模 NP=100，算法独立运行 10 次。 OXDE、CoDE 和 jDE 3 种算法在 5 000 维的实 验参数与 SparkDECC 的参数一致，实验结果如 表 7。 表 6 进化代数对 SparkDECC 优化性能的影响 Table 6 Performance affection of SparkDECC with generations F/Gen 10 (mean±std) 20 (mean±std) 50 (mean±std) 100 (mean±std) 250 (mean±std) f1 1.51×10+6±1.60×10+4 1.14×10+6±1.80×10+4 7.21×10–5±2.67×10–5 5.79×10–13±1.52×10–13 1.73×10–16±4.28×10–17 f2 3.15×10+3±1.99×10+1 2.68×10+3±2.26×10+1 2.21×10–2±3.11×10–3 6.62×10–7±8.59×10–8 4.63×10–9±7.16×10–10 f3 3.62×10+7±3.33×10+6 4.15×10+7±7.19×10+6 4.88×10+7±7.61×10+6 5.06×10+7±1.13×10+7 5.60×10+7±1.68×10+7 f4 9.72×10+1±2.55×10–1 9.72×10+1±3.41×10–1 9.75×10+1±3.13×10–1 9.75×10+1±3.14×10–1 9.77×10+1±3.44×10–1 f5 5.01×10+9±9.54×10+7 3.39×10+9±9.52×10+7 1.08×10+3±6.90×10+1 1.70×10+3±2.96×10+2 2.47×10+3±2.15×10+2 f6 1.51×10+6±1.76×10+4 1.13×10+6±2.24×10+4 2.39×10+1±3.29×10+0 2.40×10–1±8.31×10–1 1.52×10+0±2.49×10+0 f7 1.21×10+5±2.57×10+3 8.28×10+4±2.78×10+3 8.79×10+0±3.26×10–1 3.64×10+0±1.48×10–1 1.67×10+0±8.74×10–2 f8 –4.64×10+4±1.28×10+3 –5.09×10+4±9.98×10+2 –5.68×10+4±9.84×10+2 –6.08×10+4±1.11×10+3 –6.62×10+4±6.21×10+2 f9 1.38×10+4±7.15×10+1 1.32×10+4±6.11×10+1 1.21×10+4±5.44×10+1 1.10×10+4±7.38×10+1 9.94×10+3±6.59×10+1 f10 2.01×10+1±1.92×10–2 1.95×10+1±4.83×10–2 5.70×10–4±1.03×10–4 4.63×10–8±7.33×10–9 2.10×10–9±4.34×10–10 f11 1.36×10+4±1.44×10+2 1.01×10+4±1.88×10+2 4.83×10–6±1.55×10–6 3.94×10–4±1.97×10–3 1.08×10–3±3.11×10–3 f12 1.05×10+10±2.76×10+8 6.77×10+9±2.08×10+8 1.35×10+8±2.77×10+7 9.57×10–11±7.66×10–11 1.24×10–3±3.48×10–3 f13 2.09×10+10±3.83×10+8 1.37×10+10±5.74×10+8 7.38×10+6±1.79×10+6 8.79×10–4±3.04×10–3 2.08×10–1±7.75×10–1 表 7 SparkDECC、OXDE、CoDE、jDE 算法在 5 000 维的平均值、标准差和 Wilcoxon 秩和检验结果 Table 7 Comparison of SparkDECC, OXDE, CoDE, jDE algorithms for solving the results in 5 000 dimension F OXDE (mean±std) CoDE (mean±std) jDE (mean±std) SparkDECC (mean±std) f1 5.69×10+4±4.69×10+3－ 4.34×10+3±1.04×10+3－ 4.49×10+4±1.77×10+4－ 3.56×10–12±3.90×10–13 f2 Inf±NaN－ Inf±NaN－ Inf±NaN－ 3.67×10–6±2.04×10–7 f3 1.05×10+7±1.33×10+6+ 6.88×10+5±9.94×10+4+ 1.43×10+6±3.02×10+5+ 2.51×10+9±6.30×10+8 f4 2.83×10+1±1.82×10+0 ≈ 3.25×10+1±1.99×10+0 ≈ 5.98×10+1±9.43×10+0 ≈ 9.93×10+1±9.33×10–2 f5 5.80×10+6±9.98×10+5－ 1.86×10+5±6.81×10+4－ 2.52×10+8±1.06×10+8－ 9.87×10+3±3.29×10+2 f6 1.92×10+5±1.52×10+4－ 2.64×10+4±2.86×10+3－ 4.67×10+5±1.40×10+5－ 1.00×10+0±6.67×10–1 f7 7.10×10+2±1.76×10+2－ 7.11×10+1±1.16×10+1 ≈ 2.65×10+4±1.12×10+4－ 2.16×10+1±3.59×10–1 f8 –2.03×10+6±4.91×10+3－ –1.26×10+6±8.25×10+4－ –2.09×10+6±4.17×10+2－ –2.73×10+5±1.48×10+3 f9 6.68×10+3±3.36×10+2+ 2.79×10+3±1.97×10+2+ 3.34×10+3±1.09×10+3+ 5.67×10+4±1.31×10+2 f10 9.13×10+0±2.84×10–1－ 7.28×10+0±2.39×10–1－ 1.29×10+1±2.06×10–1－ 6.82×10–8±3.46×10–9 f11 4.62×10+2±7.75×10+1－ 3.78×10+1±6.80×10+0－ 5.45×10+2±1.07×10+2－ 5.81×10–14±5.96×10–15 f12 4.55×10+1±1.63×10+3－ 1.90×10+0±3.67×10–1－ 1.16×10+9±4.62×10+8－ 6.22×10–5±1.97×10–4 f13 4.56×10+5±8.23×10+5－ 4.24×10+3±7.11×10+2－ 2.72×10+9±9.69×10+8－ 4.40×10–3±1.39×10–2 –/+/≈ 10/2/1 9/2/2 10/2/1 第 2 期 谭旭杰，等：云环境下求解大规模优化问题的协同差分进化算法 ·251·

·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 卷