实数编码遗传算法的改进及并行化实现

doi:10.3969/j.issn.1000-1565.2019.01.015

河北大学学报(自然科学版) ›› 2019, Vol. 39 ›› Issue (1): 86-92.DOI: 10.3969/j.issn.1000-1565.2019.01.015

实数编码遗传算法的改进及并行化实现

刘振鹏^1,2,王雪峰¹,薛雷¹,张彬²,张寿华¹

收稿日期:2018-09-06 出版日期:2019-01-25 发布日期:2019-01-25
通讯作者: 张寿华(1980—),男,河北广宗人,河北大学副教授,主要从事网络安全与隐私保护、高性能计算等方向研究.E-mail:zhangshouhua@hbu.edu.cn
作者简介:刘振鹏(1966—),男,河北安国人,河北大学教授,博士,主要从事云计算与信息安全、并行处理与高性能计算方向研究. E-mail:lzp@hbu.edu.cn
基金资助:
河北省创新能力提升计划项目(179676278D;17455309D);教育部“云数融合”科教创新基金资助项目(2017A20004)

Improvement and parallelism of real-coded genetic algorithm

LIU Zhenpeng^1,2, WANG Xuefeng¹, XUE Lei¹, ZHANG Bin², ZHANG Shouhua¹

1. School of Cyberspace Security and Computer, Hebei University, Baoding 071002, China; 2. Information Technology Center, Hebei University, Baoding 071002, China

Received:2018-09-06 Online:2019-01-25 Published:2019-01-25

摘要/Abstract

摘要： 针对实数编码的遗传算法容易掉入局部极值、收敛速度慢等缺点,提出一种改进的实数编码的遗传算法,并对其进行了基于GPU的并行化实现.通过4个典型的遗传算法性能测试函数进行测试,结果表明,改进后的算法可以有效地跳出局部极值点,并能加快算法的收敛速度;在求解复杂的高维函数时,并行化后的改进算法可以显著减少算法的运行时间.

关键词: 遗传算法, 实数编码, 算法改进, GPU并行

Abstract: Aiming at the shortcoming of the real-coded genetic algorithm, which is easy to fall into local extremum and slow convergence speed, an improved real-coded genetic algorithm is proposed and implemented by GPU-based parallelization. Through four typical genetic algorithm performance test functions, the results show that the improved algorithm can not only effectively jump out of the local extremum, but also accelerate the convergence speed of the algorithm; When solving complex high-dimensional functions, the improved parallel algorithm can significantly reduce the running time of the algorithm.

Key words: genetic algorithm, real-coded, algorithm improvement, GPU parallel

中图分类号:

TP319

刘振鹏,王雪峰,薛雷,张彬,张寿华. 实数编码遗传算法的改进及并行化实现[J]. 河北大学学报(自然科学版), 2019, 39(1): 86-92.

LIU Zhenpeng, WANG Xuefeng, XUE Lei, ZHANG Bin, ZHANG Shouhua. Improvement and parallelism of real-coded genetic algorithm[J]. Journal of Hebei University (Natural Science Edition), 2019, 39(1): 86-92.

参考文献

[1] HOLLAND J H. Adaptation in natural and artificial systems[M]. Ann Arbor: University of Michigan Press, 1975.
[2] DE J KENNETH A. An analysis of the behavior of a class genetic adaptive systems[D]. Ann Arbor: University of Michigan, 1975.
[3] GOLDBERG D E. Genetic algorithms in search, optimization and machine learning[M]. New York: Addison-Wesley Publishing Company, INC, 1989.
[4] GONCHAROV E N, LEONOV V V. Genetic algorithm for the resource-constrained project scheduling problem[J]. Automation & Remote Control, 2017, 78(6):1101-1114. DOI:10.1134/S0005117917060108
[5] ZHANG R, TAO J. A nonlinear fuzzy neural network modeling approach using an improved genetic algorithm[J]. IEEE Transactions on Industrial Electronics, 2018, 65(7): 5882-5892. DOI:10.1109/TIE.2017.2777415
[6] WODECKI J, MICHALAK A, ZIMROZ R, et al. Optimal filter design with progressive genetic algorithm for local damage detection in rolling bearings[J]. Mechanical Systems and Signal Processing, 2018, 102:102-116. DOI:10.1016/j.ymssp.2017.09.008
[7] KHUAT T T, LE M H. A genetic algorithm with multi-parent crossover using quaternion representation for numerical function optimization[J]. Applied Intelligence, 2017, 46(4): 810-826. DOI:10.1007/s10489-016-0867-y
[8] RANA S, SRIVASTAVA S R. Solving travelling salesman problem using improved genetic algorithm[J]. Indian Journal of Science & Technology, 2017, 10(30):1-6. DOI:10.17485/ijst/2017/v10i30/115512
[9] ELSAYED S M, SARKER R A, ESSAM D L. A new genetic algorithm for solving optimization problems[J]. Engineering Applications of Artificial Intelligence, 2014, 27(C):57-69. DOI:10.1016/j.engappai.2013.09.013
[10] ALI M Z, AWARD N H, SUGANTHAN P N, et al. An improved class of real-coded genetic algorithms for numerical optimization[J]. Neurocomputing, 2017, 275:155-166. DOI:10.1016/j.neucom.2017.05.054
[11] MÜHLENBEIN H, SCHLIERKAMP-VOOSEN D. Predictive models for the breeder genetic algorithm I. Continuous parameter optimization[J]. Evolutionary Computation, 1993,1(1):25-49. DOI:10.1162/evco.1993.1.1.25
[12] CHUANG Y C, CHEN C T, HWANG C. A real-coded genetic algorithm with a direction-based crossover operator[J]. Information Sciences, 2015, 305:320-348. DOI:10.1016/j.ins.2015.01.026
[13] TANG P H, TSENG M H. Adaptive directed mutation for real-coded genetic algorithms[J]. Applied Soft Computing Journal, 2013, 13(1):600-614. DOI:10.1016/j.asoc.2012.08.035
[14] KANG S, KIM S S, WON J, et al. GPU-based parallel genetic approach to large-scale travelling salesman problem[J]. Journal of Supercomputing, 2016, 72(11):1-16. DOI:10.1007/s11227-016-1748-1
[15] TSOULOS I G, TZALLAS A, TSALIKAKIS D. PDoublePop: An implementation of parallel genetic algorithm for function optimization [J]. Computer Physics Communications, 2016, 209:183-189. DOI:10.1016/j.cpc.2016.09.006
[16] ZHANG G M, ZHU A X, HUANG Q Y. A GPU-accelerated adaptive kernel density estimation approach for efficient point pattern analysis on spatial big data[J]. International Journal of Geographical Information Science, 2017, 31(10): 2068-2097. DOI:10.1080/13658816.2017.1324975
[17] GONG T, FAN T T, GUO J Z, et al. GPU-based parallel optimization of immune convolutional neural network and embedded system[J]. Engineering Applications of Artificial Intelligence, 2017, 62: 384-395. DOI:10.1016/j.engappai.2016.08.019
[18] LI J, WANG W C. Fast and robust GPU-based point-in-polyhedron determination[J]. Computer-Aided Design, 2017,87:20-28. DOI:10.1016/j.cad.2017.02.001

实数编码遗传算法的改进及并行化实现

Improvement and parallelism of real-coded genetic algorithm

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

本文评价

[1]	张强,杨云杰,赵妙,霍利民,唐巍. 递归搜索与遗传算法融合的终端优化配置方法[J]. 河北大学学报(自然科学版), 2020, 40(1): 87-94.
[2]	陈爱霞,张春琴. 基于极速学习的Choquet模糊积分分类器[J]. 河北大学学报(自然科学版), 2019, 39(4): 337-341.
[3]	孙汉文,夏祥华. 径向基函数神经网络用于毛细管电泳同时检测水中苯二酚、苯酚和对硝基苯酚[J]. 河北大学学报(自然科学版), 2013, 33(3): 252-257.
[4]	杨晨,宗晓萍. 基于蜜蜂进化型遗传算法的电力系统无功优化[J]. 河北大学学报(自然科学版), 2013, 33(2): 198-203.
[5]	陈丽,苏海锋,张晋国. 基于改进共享小生境遗传算法的配电网无功规划[J]. 河北大学学报(自然科学版), 2011, 31(3): 314-318.
[6]	崔耀中,魏光辉,范丽思. 基于遗传算法的混响室桨叶夹角优化数值分析[J]. 河北大学学报(自然科学版), 2010, 30(5): 449-453.
[7]	崔春艳,尤扬,李彩霞,席砺莼. 遗传算法及其在钢轨断面检测系统中的应用[J]. 河北大学学报(自然科学版), 2002, 22(4): 381-384.