Improvement and parallelism of real-coded genetic algorithm

doi:10.3969/j.issn.1000-1565.2019.01.015

Abstract

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

CLC Number:

TP319

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.

References

[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