第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. 进行了改进和创新并取得了一些成果。比如BrestDOI: 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