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

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