分布式进化算法的性能测试与分析

doi:10.11772/j.issn.1001-9081.2014.11.3086

计算机应用 ›› 2014, Vol. 34 ›› Issue (11): 3086-3090.DOI: 10.11772/j.issn.1001-9081.2014.11.3086

• 2014年全国开放式分布与并行计算学术年会(DPCS 2014)论文 • 上一篇下一篇

分布式进化算法的性能测试与分析

陈炳亮¹,张宇辉²,嵇智源³

1. .华南农业大学理学院, 广州 510642;
2. 中山大学计算机科学系, 广州 510006;
3. 科技部高技术研究发展中心, 北京 100044

收稿日期:2014-07-28 修回日期:2014-08-05 发布日期:2014-12-01 出版日期:2014-11-01
通讯作者: 张宇辉
作者简介:陈炳亮(1992-), 男, 广东广州人, 主要研究方向: 计算智能、纠错编码;张宇辉(1990-), 男, 广东兴宁人, 博士研究生, CCF会员, 主要研究方向: 计算智能;嵇智源(1956-), 男,北京人, 高级工程师, 主要研究方向:分布式系统、云计算。
基金资助:
国家自然科学基金资助项目

Performance tests and analysis of distributed evolutionary algorithms

CHEN Bingliang¹,ZHANG Yuhui²,JI Zhiyuan³

1. College of Sciences, South China Agricultural University, Guangzhou Guangdong 510642, China;
2. Department of Computer Science, Sun Yat-sen University, Guangzhou Guangdong 510006, China;
3. High-Tech Research Development Center, Ministry of Science and Technology, Beijing 100044, China

Received:2014-07-28 Revised:2014-08-05 Online:2014-12-01 Published:2014-11-01
Contact: ZHANG Yuhui

摘要/Abstract

摘要：

针对分布式进化算法设计过程中由于缺乏对性能影响因素的分析而导致算法无法达到预期加速比的问题,提出一种全面的性能分析方法。根据分布式进化算法的组成结构,将影响分布式进化算法性能的因素分为进化操作开销、适应值计算开销和通信开销三个部分。首先研究进化算法在不同个体编码维数下进化操作开销的特性;其次,在进化操作开销相对固定的情况下,通过使用操作系统的延时函数控制适应值计算开销,通过改变个体编码维数控制通信开销;最后,应用控制变量方法,逐一测试各因素对算法加速比的影响。实验结果展现了三种因素的相互制约关系,给出了分布式进化算法获得更好加速比的条件。

Abstract:

Due to the lack of performance analysis while designing a distributed Evolutionary Algorithm (dEA), the designed algorithm cannot reach the expected speedup. To solve this problem, a comprehensive performance analysis method was proposed. According to the components of dEAs, factors that influence the performance of dEAs can be divided into three parts, namely, evolutionary cost, fitness evaluation cost and communication cost. Firstly, the feature of evolutionary cost under different individual encoding lengths was studied. Then when the evolutionary cost was kept unchanged, the fitness evaluation cost was controlled by using the delay function of the operating system and the communication cost was controlled by changing the length of individual encoding. Finally, the effect of each factor was tested through control variable method. The experimental results reveal the constraint relation among the three factors and point out the necessary conditions for speeding up dEAs.

中图分类号:

TP301.6

陈炳亮张宇辉嵇智源. 分布式进化算法的性能测试与分析[J]. 计算机应用, 2014, 34(11): 3086-3090.

CHEN Bingliang ZHANG Yuhui JI Zhiyuan. Performance tests and analysis of distributed evolutionary algorithms[J]. Journal of Computer Applications, 2014, 34(11): 3086-3090.

参考文献

[1]TANG T, WEI L, XIE X, et al.Study on distributed parallel computing on hybrid genetic algorithm[J]. Computer Engineering and Applications,2011,47(9):207-209.(唐天兵,韦凌云,谢祥宏,等.分布式并行计算环境下混合遗传算法的研究[J].计算机工程与应用, 2011,47(9):207-209.)
[2]MIAO Q, KONG Z, WANG Y. Function optimization based on distributed immune evolutionary algorithm[J]. Systems Engineering and Electronics,2012,34(2):413-417.(苗启广,孔哲鹏,王艳红. 基于分布式免疫进化算法的函数优化[J].系统工程与电子技术, 2012,34(2):413-417.)
[3]LASSIG J, SUDHOLT D. The benefit of migration in parallel evolutionary algorithms[C]// GECCO 2010: Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation. New York: ACM Press, 2010: 1105-1112.
[4]LI C, WANG J, YAN X, et al.Subpopulation diversity based accepting immigrant in distributed evolutionary algorithms[C]// ICPADS 2013: Proceedings of the 2013 International Conference on Parallel and Distributed Systems. Piscataway: IEEE Press, 2013:422-423.
[5]LASSIG J, SUDHOLT D. Adaptive population models for offspring populations and parallel evolutionary algorithms[EB/OL]. [2013-10-10]. http://www.icsi.berkeley.edu/pubs/algorithms/adaptivepopulationmodels11.pdf.
[6]WHITLEY D. A genetic algorithm tutorial[J]. Statistics and Computing, 1994, 4(2): 65-85.
[7]BRATTON D, KENNEDY J. Defining a standard for particle swarm optimization[C]// SIS 2007: Proceedings of the 2007 Swarm Intelligence Symposium. Piscataway: IEEE Press,2007: 120-127.
[8]ALBA E, TOMASSINI M. Parallelism and evolutionary algorithms[J]. IEEE Transactions on Evolutionary Computation, 2002, 6 (5):443-462.
[9]VITELA J E, CASTANOS O, A real-coded niching memtic algorithm for continuous multimodal function optimization[C]// CEC 2008: Proceedings of the 2008 IEEE Congress on Evolutionary Computation. Piscataway: IEEE Press,2008: 2170-2177.
[10]ZHAN Z, ZHANG J, LI Y, et al.Adaptive particle swarm optimization [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009,39(6):1362-1381.
[11]YAO X, LIU Y, LIN G. Evolutionary programming made faster[J]. IEEE Transactions on Evolutionary Computation, 1999,3(2):82-102.
[12]ZHANG J, CHUNG H, LO W, et al.Implementation of a decoupled optimization technique for design of switching regulators using genetic algorithm[J]. IEEE Transactions on Power Electronics,2001,16(6):752-763.
[13]DUBREUIL M, GAGNE C, PARIZEAU M. Analysis of a master-slave architecture for distributed evolutionary computations[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics,2006,36(1):229-235.

[1]	侯阳张琼赵紫煊朱正宇张晓博. 基于YOLOv5s的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[6]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[7]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[8]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[9]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[10]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[12]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	张倩婷胡丽莹陈黎飞. 时间序列的鲁棒形态表征方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	胡林波倪志伟程家乐刘文涛朱旭辉. 基于融合社区检测的复杂协作众包任务分配方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

分布式进化算法的性能测试与分析

Performance tests and analysis of distributed evolutionary algorithms

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics