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