Performance tests and analysis of distributed evolutionary algorithms

doi:10.11772/j.issn.1001-9081.2014.11.3086

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (11): 3086-3090.DOI: 10.11772/j.issn.1001-9081.2014.11.3086

Previous Articles Next Articles

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

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

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

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

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

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.

摘要：

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

CLC Number:

TP301.6

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

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

References

[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-MRD: an efficient fire and smoke detection algorithm for complex scenarios based on YOLOv5s [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	Qiye ZHANG, Xinrui ZENG. Efficient active-set method for support vector data description problem with Gaussian kernel [J]. Journal of Computer Applications, 2024, 44(12): 3808-3814.
[3]	. Path planning of multi-UAV formation based on improved artificial potential field method [J]. Journal of Computer Applications, 0, (): 0-0.
[4]	. Dual-population dual-stage evolutionary algorithm for complex constrained multi-objective optimization problems [J]. Journal of Computer Applications, 0, (): 0-0.
[5]	Qin LENG, Zhengyuan MAO. Two echelon location-routing optimization considering facility sizing decision [J]. Journal of Computer Applications, 2024, 44(11): 3513-3520.
[6]	Qingyuan PENG, Xiaofeng WANG, Junxia WANG, Yingying HUA, Ao TANG, Fei HE. Review of phase transition in satisfiability problems [J]. Journal of Computer Applications, 2024, 44(11): 3503-3512.
[7]	Renke SUN, Zhiyu HUANGFU, Hu CHEN, Zhongnian LI, Xinzheng XU. Survey of neural architecture search [J]. Journal of Computer Applications, 2024, 44(10): 2983-2994.
[8]	Antai SUN, Ye LIU, Dongmei XU. Dynamic surface asymptotic compensation algorithm for multi-agent systems [J]. Journal of Computer Applications, 2024, 44(10): 3151-3157.
[9]	Chaoying YAN, Ziyi ZHANG, Yingnan QU, Qiuyu LI, Dixiang ZHENG, Lijun SUN. Double auction carbon trading based on consortium blockchain [J]. Journal of Computer Applications, 2024, 44(10): 3240-3245.
[10]	. Dung beetle optimizer algorithm with restricted reverse learning and Cauchy-Gauss variation [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	Guanglei YAO, Juxia XIONG, Guowu YANG. Flower pollination algorithm based on neural network optimization [J]. Journal of Computer Applications, 2024, 44(9): 2829-2837.
[12]	Shanglong LI, Jianhua LIU, Heming JIA. Reptile search algorithm based on multi-hunting coordination strategy [J]. Journal of Computer Applications, 2024, 44(9): 2818-2828.
[13]	Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904.
[14]	. Robust shapeles representation method for time series [J]. Journal of Computer Applications, 0, (): 0-0.
[15]	HU Linbo , NI Zhiwei , CHENG Jiale, LIU Wentao , ZHU Xuhui , . Complex collaborative crowdsourcing task allocation method based on fusion community detection [J]. Journal of Computer Applications, 0, (): 0-0.

Performance tests and analysis of distributed evolutionary algorithms

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics