[1]谭旭杰,邓长寿,吴志健,等.云环境下求解大规模优化问题的协同差分进化算法[J].智能系统学报,2018,13(2):243-253.[doi:10.11992/tis.201706053]
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.[doi:10.11992/tis.201706053]
点击复制
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.[doi:10.11992/tis.201706053]
云环境下求解大规模优化问题的协同差分进化算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
13
期数:
2018年第2期
页码:
243-253
栏目:
学术论文—智能系统
出版日期:
2018-04-15
- Title:
- Cooperative differential evolution in cloud computing for solving large-scale optimization problems
- Keywords:
- differential evolution; large-scale optimization; coevolution; resilient distributed dataset; cloud computing
- 分类号:
- TP301
- 摘要:
- 差分进化是一种求解连续优化问题的高效算法。然而差分进化算法求解大规模优化问题时，随着问题维数的增加，算法的性能下降，且搜索时间呈指数上升。针对此问题，本文提出了一种新的基于Spark的合作协同差分进化算法（SparkDECC）。SparkDECC采用分治策略，首先通过随机分组方法将高维优化问题分解成多个低维子问题，然后利用Spark的弹性分布式数据模型，对每个子问题并行求解，最后利用协同机制得到高维问题的完整解。通过在13个高维测试函数上进行的对比实验和分析，实验结果表明算法加速明显且可扩展性好，验证了SparkDECC的有效性和适用性。
- 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 capability 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.
- 参考文献/References:
-
[1] 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.
[2] 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]. IEEEtransactions on evolutionary computation, 2006, 10(6): 646-657.
[3] WANG Yong, ZHANG Qingfu. Differential evolution with composite trial vector generation strategies and co-ntrol parameters[J]. IEEE transactions on evolutionary computation, 2011, 2(15): 55-66.
[4] FRANS V D B, ENGELBRECHT A P. A cooperative approach to particle swarm optimization[J]. IEEE transactions on evolutionary computation, 2004, 8(3): 225-239.
[5] POTTER M A, De JONG K A. A cooperative coevolutionary approach to function optimization[J]. Lecture notes in computer science, 1994, 866: 249-257.
[6] YANG Z, TANG K, YAO X. Large scale evolutionary o-ptimization using cooperative coevolution[J]. Information sciences, 2008, 178(15): 2985-2999.
[7] 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.
[8] 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.
[9] HU X M, HE F L, CHEN W N, et al. Cooperation coevolution with fast interdependency identification for large scale optimization[J]. Information sciences, 2017, 381: 142-160.
[10] LI X, YAO X. Cooperatively coevolving particle swarms for large scale optimization[J]. IEEE transactions on evolutionary computation, 2012, 16(2): 210-224.
[11] 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 evolutionary computation, 2017, 21(6): 929-942.
[12] MENG X, BRADLEY J, YUVAZ B, et al. Mllib: machine learning in apache spark[J]. Journal of machine research, 2015, 17(34): 1235-1241.
[13] 王诏远, 王宏杰, 邢焕来, 等. 基于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.
[14] 朱继召, 贾岩涛, 徐君, 等. SparkCRF: 一种基于Spark的并行CRFs算法实现[J]. 计算机研究与发展, 2016, 53(8): 1819-1828.
ZHU Jizhao, JIA Yantao, XU Jun, et al. SparkCRF: a parallel implementation of crfs algorithm with spark[J]. Journal of computer research and development, 2016, 53(8): 1819-1828.
[15] 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 Applications. Springer, Berlin, Heidelberg, 2015: 84-93.
[16] TEIJEIRO D, PARDO X C, GONZáLEZ P, et al. Implementing Parallel Differential Evolution on Spark[C]//European Conference on the Applications of Evolutionary Computation. Springer International Publishing, 2016: 75-90.
[17] 王虹旭, 吴斌, 刘旸.基于Spark的并行图数据分析系统[J]. 计算机科学与探索, 2015, 9(9): 1066-1074.
WANG Hongxu, WU Bin, LIU Yang. Parallel graph data analysis based on spark[J]. Journal of frontiers of computer science and technology, 2015, 9(9): 1066-1074.
[18] 刘志强, 顾荣, 袁春风, 等.基于SparkR 的分类算法并行化研究[J]. 计算机科学与探索, 2015, 9(11): 1281-1294.
LIU Zhiqiang, GU Rong, YUAN Chunfeng, et al. Parallelization of classification algorithms based on sparkR[J]. Journal of frontiers of computer science and technology, 2015, 9(11): 1281-1294.
[19] 袁斯昊, 邓长寿, 董小刚, 等.求解大规模优化问题的云差分进化算法[J]. 计算机应用研究, 2016, 33(10): 2949-2953.
YUAN Sihao, DENG Changshou, DONG Xiaogang, et al. Cloud computing based differential evolution algorithm for large-scale optimization problems[J]. Application research of computers, 2016, 33(10): 2949-2953.
[20] 董小刚, 邓长寿, 袁斯昊, 等. MapReduce模型下的分布式差分进化算法[J]. 小型微型计算机系统, 2016, 37(12): 2695-2701.
DONG Xiaogang, DENG Changshou, YUAN Sihao, et al. Distributed differential evolution algorithm based on mapreduce model[J]. Journal of Chinese computer systems, 2016, 37(12): 2695-2701.
[21] 谭旭杰, 邓长寿, 董小刚, 等.SparkDE: 一种基于RDD云计算模型的并行差分进化算法[J]. 计算机科学, 2016, 43(9): 116-119.
TAN Xujie, DENG Changshou, DONG Xiaogang, et al. SparkDE: a parallel version of differential evolutionbased on resilient distributed datasets model in clo-ud computing[J]. Computer Science, 2016, 43(9): 116-119.
[22] ZAHARIA M, CHOWDHURY M, DAS T, et al. Resilient di-stributed datasets: a fault-tolerant abstraction for inm-emory cluster computing[C]//Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association, 2012: 2-2.
[23] DAS S, SUGANTHAN P N. Differential evolution: a su-rvey of the state-of-the-art[J]. IEEE transactions on evolutionary computation, 2011, 15(1): 4-31.
[24] 王贤伟, 戴青云, 姜文超, 等.基于Mapreduce的外观设计专利图像检索方法[J]. 小型微型计算机系统, 2012, 33(3): 626-632.
WANG Xianwei, DAI Qingyun, JIANG Wenchao, et al. Retrieval of design patent images based on mapred-uce model[J]. Journal of Chinese computer systems, 2012, 33(3): 626-632.
[25] YAO X, LIU Y, LIN G. Evolutionary programming ma-de faster[J]. IEEE transactions on evolutionary computation, 2000, 3(2): 82-102.
[26] WANG Y, CAI Z, ZHANG Q. Enhancing the search abil-ity of differential evolution through orthogonal crosso-ver[J]. Information sciences, 2012, 185(1): 153-177.
[27] 范德斌, 邓长寿, 袁斯昊, 等. 基于MapReduce模型的分布式粒子群算法[J]. 山东大学学报: 工学版, 2016, 46(6): 23-30.
FAN Debin, DENG Chanshou, YUAN Sihao, et al. Dis-tributed particle swarm optimization algorithm based on mapreduce[J]. Journal shandong univers-ity: engineering science, 2016, 46(6): 23-30.
[28] TAGAWA K, ISHIMIZU T. Concurrent differential evolut-ion based on MapReduce[J]. International journal of computers, 2010, 4(4): 161-168.
- 相似文献/References:
-
[1]刘三阳,张晓伟.混合差分变异策略[J].智能系统学报,2008,3(6):487.
LIU San-yang,ZHANG Xiao-wei.A hybrid strategy for differential variation[J].CAAI Transactions on Intelligent Systems,2008,3():487.
[2]杨振宇,唐珂.差分进化算法参数控制与适应策略综述[J].智能系统学报,2011,6(5):415.
YANG Zhenyu,TANG Ke.An overview of parameter control and adaptation strategiesin differential evolution algorithm[J].CAAI Transactions on Intelligent Systems,2011,6():415.
[3]毕晓君,刘国安,肖婧.基于自适应差分进化的干线交通信号协调控制[J].智能系统学报,2012,7(5):437.
BI Xiaojun,LIU Guoan,XIAO Jing.Coordination and control of arterial traffic signalsbased on adaptive differential evolution[J].CAAI Transactions on Intelligent Systems,2012,7():437.
[4]杨艳霞.一种基于模拟退火操作的混合差分进化算法[J].智能系统学报,2014,9(1):109.[doi:10.3969/j.issn.1673-4785.201305027]
YANG Yanxia.A hybrid differential evolutionary algorithm based on the simulated annealing operation[J].CAAI Transactions on Intelligent Systems,2014,9():109.[doi:10.3969/j.issn.1673-4785.201305027]
[5]丁青锋,尹晓宇.差分进化算法综述[J].智能系统学报,2017,12(4):431.[doi:10.11992/tis.201605015]
DING Qingfeng,YIN Xiaoyu.Research survey of differential evolution algorithms[J].CAAI Transactions on Intelligent Systems,2017,12():431.[doi:10.11992/tis.201605015]
[6]黎延海,拓守恒.一种求解多模态复杂问题的混合和声差分算法[J].智能系统学报,2018,13(2):281.[doi:10.11992/tis.201612030]
LI Yanhai,TUO Shouheng.Hybrid algorithm based on harmony search and differential evolution for solving multi-modal complex problems[J].CAAI Transactions on Intelligent Systems,2018,13():281.[doi:10.11992/tis.201612030]
[7]林锦,胡家琛,刘莞玲,等.利用MISA多目标优化的置信规则库分类算法[J].智能系统学报,2019,14(5):982.[doi:10.11992/tis.201809022]
LIN Jin,HU Jiachen,LIU Wanling,et al.Belief rule base classification algorithm using MISA multi-objective optimization[J].CAAI Transactions on Intelligent Systems,2019,14():982.[doi:10.11992/tis.201809022]
[8]吴莹莹,丁肇红,刘华平,等.面向环境探测的多智能体自组织目标搜索算法[J].智能系统学报,2020,15(2):289.[doi:10.11992/tis.201908023]
WU Yingying,DING Zhaohong,LIU Huaping,et al.Self-organizing target search algorithm of multi-agent system for envi-ronment detection[J].CAAI Transactions on Intelligent Systems,2020,15():289.[doi:10.11992/tis.201908023]
[9]项前,周亚云,陆枳屹,等.响应动态约束条件的多目标货位优化算法研究[J].智能系统学报,2020,15(5):925.[doi:10.11992/tis.201906041]
XIANG Qian,ZHOU Yayun,LU Zhiyi,et al.Multi-objective location optimization algorithm in response to dynamic constraints[J].CAAI Transactions on Intelligent Systems,2020,15():925.[doi:10.11992/tis.201906041]
[10]黎建宇,詹志辉.面向大规模特征选择的自监督数据驱动粒子群优化算法[J].智能系统学报,2023,18(1):194.[doi:10.11992/tis.202206008]
LI Jianyu,ZHAN Zhihui.A self-supervised data-driven particle swarm optimization approach for large-scale feature selection[J].CAAI Transactions on Intelligent Systems,2023,18():194.[doi:10.11992/tis.202206008]
备注/Memo
收稿日期:2017-06-13。
基金项目:国家自然科学基金项目（61364025，61763019）；武汉大学软件工程国家重点实验室开放基金项目（SKLSE2012-09-39）；九江学院科研项目（2013KJ30，2014KJYB032）；江西省教育厅科技项目（GJJ161076，GJJ161072）.
作者简介:谭旭杰,男,1978年生,讲师,主要研究方向为计算智能、云计算;邓长寿,男,1972年生,教授,博士,主要研究方向为计算智能、云计算、数据挖掘;吴志健,男,1963年生,教授,博士生导师,主要研究方向为智能计算、并行计算和智能信息处理。主持或参与国家自然科学基金、“863”计划等各类科研项目20余项,发表学术论文120余篇。
通讯作者:邓长寿.E-mail:csdeng@jju.edu.cn.
更新日期/Last Update:
1900-01-01