并行化遗传算法研究综述
|
摘要
说明遗传算法的基本思想和特点。根据近五年国内遗传算法的研究现状,分析遗传算法当前发展的潜力与不足。对遗传算法未来的发展和研究热点进行了推理,指出遗传算法的主要发展方向是并行化,研究热点将集中在早熟机理和参数设置等方面,并且遗传算法未来会跟其他的技术进一步结合。从遗传算法的主要环节入手,分析遗传算法的并行化策略和4种常见的并行化模型,并分析不同模型使用的硬件环境和模型的优缺点。对并行化遗传算法的评价模型进行讨论,说明了常见的评价模型和改进之处。
The basic idea and characteristics of genetic algorithm were described in this paper. According to the research status of genetic algorithm in China in recent five years,we analyzed the potential and deficiency of genetic algorithm,and reasoned the future development and research hotspot of genetic algorithm. It was pointed out that the main development direction of genetic algorithm was parallelization,and the research hotspot focused on the mechanism of precocity and parameter setting. The genetic algorithm would be further combined with other technologies in the future. Starting from the key steps of genetic algorithm,we analyzed the parallel strategies and four common parallel models,and analyzed the hardware environment and advantages and disadvantages of different models. The evaluation model of parallel genetic algorithm was discussed,and the common evaluation model and improvement were explained.
The basic idea and characteristics of genetic algorithm were described in this paper. According to the research status of genetic algorithm in China in recent five years,we analyzed the potential and deficiency of genetic algorithm,and reasoned the future development and research hotspot of genetic algorithm. It was pointed out that the main development direction of genetic algorithm was parallelization,and the research hotspot focused on the mechanism of precocity and parameter setting. The genetic algorithm would be further combined with other technologies in the future. Starting from the key steps of genetic algorithm,we analyzed the parallel strategies and four common parallel models,and analyzed the hardware environment and advantages and disadvantages of different models. The evaluation model of parallel genetic algorithm was discussed,and the common evaluation model and improvement were explained.
引文
[1]Komusiewicz C,Bulteau L,Hüffner F,et al.Multivariate algorithmics for NP-hard string problems[J].Bulletin of Eatcs,2014,114(114).
[2]Wicker J,Fenner K,Kramer S.A hybrid machine learning and knowledge based approach to limit combinatorial explosion in biodegradation prediction[M]//Computational Sustainability.Springer International Publishing,2016.
[3]林静怡.优化问题神经网络方法研究及实证分析[D].厦门:厦门大学,2007.
[4]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.
[5]李菊娥,冯晓慧.一种提高解大规模线性规划数值解精度的算法[J].西安电子科技大学学报(自然科学版),1999,26(6):780-784.
[6]Melkonian V.An integer programming model for the kenken problem[J].American Journal of Operations Research,2016,6(3):213-225.
[7]Chebil K,Khemakhem M.A dynamic programming algorithm for the knapsack problem with setup[J].Computers&Operations Research,2015,64(C):40-50.
[8]吴金荣.求解课程表问题的分支定界算法[J].运筹与管理,2002,11(1):17-22.
[9]Ross G T,Soland R M.A branch and bound algorithm for the generalized assignment problem[J].Mathematical Programming,1975,8(1):91-103.
[10]Metropolis N,Rosenbluth A W,Rosenbluth M N,et al.E-quation of state calculations by fast computing machines[J].The Journal of Chemical Physics,1953,21(6):1087-1092.
[11]Holland J H.Erratum:genetic algorithms and the optimal allocation of trials[J].Siam Journal on Computing,2006,2(2):88-105.
[12]Glover F.Future paths for integer programming and links to artificial intelligence[J].Computers&Operations Research,1986,13(5):533-549.
[13]Glover F.Tabu search-Part I[J].Orsa J on Computing,1989,1(1):89-98.
[14]Glover F,Marti R.Tabu search[J].General Information,1989,106(2):221-225.
[15]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//European Conference on Artificial Life.The MIT Press,1992.
[16]Hopfield J J.Neural networks and physical systems with emergent collective computational abilities[J].Proceedings of the National Academy of Sciences of the United States of A-merica,1982,79(8):2554-2558.
[17]Jungnickel D.The greedy algorithm[M]//Graphs,Networks and Algorithms.Springer Berlin Heidelberg,1999:135-161.
[18]Kumar M,Husian M,Upreti N,et al.Genetic algorithm:Review and application[J].Computer,2010,2(2):451-454.
[19]宗德才,王康康.一种混合局部搜索算法的遗传算法求解旅行商问题[J].计算机应用与软件,2015,32(3):266-270,305.
[20]王银年.遗传算法的研究与应用[D].无锡:江南大学,2009.
[21]Zeigler B P,Kim J.Asynchronous genetic algorithms on parallel computers[C]//Proceedings of the 5th International Conference on Genetic Algorithms.Morgan Kaufmann Publishers Inc.1993.
[22]刘晓平,安竹林,郑利平.基于MPI的主从式并行遗传算法框架[J].系统仿真学报,2004,16(9):1938-1940.
[23]侯燕,刘辛.基于主从架构和GA的模糊关联规则挖掘算法[J].控制工程,2017,24(2):276-282.
[24]张步忠,程玉胜,王一宾.求解N皇后问题的片上多核并行混合遗传算法[J].计算机工程,2015,41(7):199-203.
[25]李志坚,吴晓军,任哲坡,等.基于分布式粗粒度并行计算的遗传规划算法研究[J].计算机应用研究,2015,32(1):48-50.
[26]李建明,迟忠先,万单领.一种基于GPU加速细粒度并行遗传算法的实现方法[J].控制与决策,2008,23(6):697-700.
[27]张文金,许爱军.基于云计算的混合并行遗传算法求解最短路径[J].电子技术应用,2015,41(3):123-125,129.
[28]田旻,刘人境.分层混合遗传算法求解柔性作业车间调度问题[J].工业工程与管理,2017,22(5):32-39.
[29]高家全,何桂霞.并行遗传算法研究综述[J].浙江工业大学学报,2007,35(1):56-59.
[30]Gustafson J L.Reevaluating amdahl's law[J].Communications of the Acm,1988,31(5):532-533.
[31]Han Y F,Esbensen H,Song J,et al.Performance improvement of a genetic algorithm for floorplanning with parallel computing technology[C]//IEEE International Symposium on Circuits and Systems.IEEE,1997:1544-1547.
[32]Kuonen P,Kobler D.Parallel island-based genetic algorithm for radio network design[J].Journal of Parallel&Distributed Computing,1997,47(1):86-90.
[33]孙如祥,黄春,邓国斌.高维多峰优化的遗传算法设计[J].科技通报,2017,33(8):197-201,229.
[34]李和壁.遗传算法(GA)在旅行商问题(TSP)中的应用[J].科技创新与应用,2015(10):48-49.
[35]Wang J,Ersoy O K,He M,et al.Multi-offspring genetic algorithm and its application to the traveling salesman problem[J].Applied Soft Computing,2016,43(C):415-423.
[36]Lv H.A novel Quantum Genetic Algorithm in TSP[J].Applied Mechanics&Materials,2014,519/520:759-763.
[37]陈守家,付霞,周欣.基于遗传禁忌算法结合解决排课问题[J].计算机应用,2007,27(7):1806-1808.
[38]李素粉,朱云龙.流水车间作业提前/拖期调度问题研究[[J].计算机集成制造系统,2006,12(8):1235-1240.
[39]饶运清,严治雄,张超勇,等.一种混合遗传算法在车间作业调度中的应用研究[J].机械科学与技术,2006,25(5):584-587.
[40]虞蕾,赵红,赵宗涛.一种基于遗传算法的航迹优化方法[J].西北大学学报(自然科学版),2006,36(2):205-208.
[41]李辉,韩红,韩崇昭,等.基于遗传算法的模糊逻辑控制器优化设计[J].西安交通大学学报,2002,36(4):385-389.
[42]王科俊,徐晶,王磊,等.基于可拓遗传算法的机器人路径规划[J].哈尔滨工业大学学报,2006,38(7):1135-1138.
[43]林磊,王晓龙,刘家锋.基于遗传算法的手写体汉字识别系统优化方法的研究[J].计算机研究与发展,2001,38(6):658-661.
[44]赵应丁,刘金刚.基于遗传算法的指纹图像二值化算法研究[J].计算机工程,2006,32(7):169-171.
[45]王建锋,吴庆标.分层遗传算法实现图像边缘检测[J].计算机工程与应用,2006,42(14):95-96.
[46]王静莲,刘弘,李少辉.基于决策树的遗传算法在数据挖掘领域的应用[J].计算机工程与应用,2005,41(28):153-155.
[47]张细政,邢立宁,伍栖.基于遗传算法的数据挖掘方法及应用[J].哈尔滨工程大学学报,2006,24(S1):384-388.(下转第页)
[48]Choenni S.Design and implementation of a genetic-based algorithm for data mining[C]//VLDB 2000,Proceedings of,International Conference on Very Large Data Bases,September 10-14,2000,Cairo,Egypt.DBLP,2000:33-42.
[49]He Y,Hui C W.A binary coding genetic algorithm for multi-purpose process scheduling:A case study[J].Chemical Engineering Science,2010,65(16):4816-4828.
[50]Yang X,Yang Z,Yin X,et al.Chaos gray-coded genetic algorithm and its application for pollution source identifications in convection-diffusion equation[J].Communications in Nonlinear Science&Numerical Simulation,2008,13(8):1676-1688.
[51]陈辉,张家树,张超.实数编码混沌量子遗传算法[J].控制与决策,2005,20(11):1300-1303.
[52]郑朝晖,张焱,裘聿皇.一种基于复数编码的遗传算法[J].控制理论与应用,2003,20(1):97-100.
[53]梁旭,王佳,黄明.解决大规模生产调度问题的一种新编码方法[J].计算机集成制造系统,2008,14(10):1974-1977.
[54]Tang K Z,Sun T K,Yang J Y.An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems[J].Computers&Chemical Engineering,2011,35(4):615-621.
[55]乔家庆,付平,孟升卫.基于个体差异的遗传选择算子设计[J].电子学报,2006,34(S1):2414-2416.
[56]陈皓,崔杜武,严太山,等.基于竞争指数的模拟退火排序选择算子[J].电子学报,2009,37(3):586-591.
[57]Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics&Computation,2007,188(1):895-911.
[58]Tutkun N.Optimization of multimodal continuous functions using a new crossover for the real-coded genetic algorithms[J].Expert Systems with Applications,2009,36(4):8172-8177.
[59]Wang L,Tang D B.An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem[J].Expert Systems with Applications,2011,38(6):7243-7250.
[60]Deep K,Thakur M.A new mutation operator for real coded genetic algorithms[J].Applied Mathematics&Computation,2007,193(1):211-230.
[61]巩敦卫,郝国生,严玉若.交互式遗传算法基于用户认知不确定性的定向变异[J].控制与决策,2010,25(1):74-78.
[62]Albayrak M,Allahverdi N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert Systems with Applications,2011,38(3):1313-1320.
[63]Liu L,Chen X.Reconfiguration of distribution networks based on fuzzy genetic algorithms[J].Proceedings of the Csee,2000,20(2):66-69.
[64]戴朝华,朱云芳,陈维荣.云自适应遗传算法[J].控制理论与应用,2007,24(4):646-650.
[65]Ponnambalam S G,Jawahar N,Kumar B.Estimation of optimum genetic control parameters for job shop scheduling[J].International Journal of Advanced Manufacturing Technology,2002,19(3):224-234.
[66]陈世哲,刘国栋,浦欣,等.基于优势遗传的自适应遗传算法[J].哈尔滨工业大学学报,2007,39(7):1021-1024.
[67]陈峰,武小悦.基于定向变异算子的求解GA欺骗问题研究[J].系统工程与电子技术,2009,31(1):204-207.
[68]Rudolph G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks,1994,5(1):96.
[69]于志刚,宋申民,段广仁.遗传算法的机理与收敛性研究[J].控制与决策,2005,20(9):971-980.
[70]李敏强,寇纪淞.遗传算法的模式欺骗性分析[J].中国科学:技术科学,2002,32(1):95-102.
[71]何军,康立山.遗传算法求解完全欺骗性问题的平均计算时间[J].计算机学报,1999,22(9):999-1003.
[2]Wicker J,Fenner K,Kramer S.A hybrid machine learning and knowledge based approach to limit combinatorial explosion in biodegradation prediction[M]//Computational Sustainability.Springer International Publishing,2016.
[3]林静怡.优化问题神经网络方法研究及实证分析[D].厦门:厦门大学,2007.
[4]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1328-1333.
[5]李菊娥,冯晓慧.一种提高解大规模线性规划数值解精度的算法[J].西安电子科技大学学报(自然科学版),1999,26(6):780-784.
[6]Melkonian V.An integer programming model for the kenken problem[J].American Journal of Operations Research,2016,6(3):213-225.
[7]Chebil K,Khemakhem M.A dynamic programming algorithm for the knapsack problem with setup[J].Computers&Operations Research,2015,64(C):40-50.
[8]吴金荣.求解课程表问题的分支定界算法[J].运筹与管理,2002,11(1):17-22.
[9]Ross G T,Soland R M.A branch and bound algorithm for the generalized assignment problem[J].Mathematical Programming,1975,8(1):91-103.
[10]Metropolis N,Rosenbluth A W,Rosenbluth M N,et al.E-quation of state calculations by fast computing machines[J].The Journal of Chemical Physics,1953,21(6):1087-1092.
[11]Holland J H.Erratum:genetic algorithms and the optimal allocation of trials[J].Siam Journal on Computing,2006,2(2):88-105.
[12]Glover F.Future paths for integer programming and links to artificial intelligence[J].Computers&Operations Research,1986,13(5):533-549.
[13]Glover F.Tabu search-Part I[J].Orsa J on Computing,1989,1(1):89-98.
[14]Glover F,Marti R.Tabu search[J].General Information,1989,106(2):221-225.
[15]Colorni A,Dorigo M,Maniezzo V.Distributed optimization by ant colonies[C]//European Conference on Artificial Life.The MIT Press,1992.
[16]Hopfield J J.Neural networks and physical systems with emergent collective computational abilities[J].Proceedings of the National Academy of Sciences of the United States of A-merica,1982,79(8):2554-2558.
[17]Jungnickel D.The greedy algorithm[M]//Graphs,Networks and Algorithms.Springer Berlin Heidelberg,1999:135-161.
[18]Kumar M,Husian M,Upreti N,et al.Genetic algorithm:Review and application[J].Computer,2010,2(2):451-454.
[19]宗德才,王康康.一种混合局部搜索算法的遗传算法求解旅行商问题[J].计算机应用与软件,2015,32(3):266-270,305.
[20]王银年.遗传算法的研究与应用[D].无锡:江南大学,2009.
[21]Zeigler B P,Kim J.Asynchronous genetic algorithms on parallel computers[C]//Proceedings of the 5th International Conference on Genetic Algorithms.Morgan Kaufmann Publishers Inc.1993.
[22]刘晓平,安竹林,郑利平.基于MPI的主从式并行遗传算法框架[J].系统仿真学报,2004,16(9):1938-1940.
[23]侯燕,刘辛.基于主从架构和GA的模糊关联规则挖掘算法[J].控制工程,2017,24(2):276-282.
[24]张步忠,程玉胜,王一宾.求解N皇后问题的片上多核并行混合遗传算法[J].计算机工程,2015,41(7):199-203.
[25]李志坚,吴晓军,任哲坡,等.基于分布式粗粒度并行计算的遗传规划算法研究[J].计算机应用研究,2015,32(1):48-50.
[26]李建明,迟忠先,万单领.一种基于GPU加速细粒度并行遗传算法的实现方法[J].控制与决策,2008,23(6):697-700.
[27]张文金,许爱军.基于云计算的混合并行遗传算法求解最短路径[J].电子技术应用,2015,41(3):123-125,129.
[28]田旻,刘人境.分层混合遗传算法求解柔性作业车间调度问题[J].工业工程与管理,2017,22(5):32-39.
[29]高家全,何桂霞.并行遗传算法研究综述[J].浙江工业大学学报,2007,35(1):56-59.
[30]Gustafson J L.Reevaluating amdahl's law[J].Communications of the Acm,1988,31(5):532-533.
[31]Han Y F,Esbensen H,Song J,et al.Performance improvement of a genetic algorithm for floorplanning with parallel computing technology[C]//IEEE International Symposium on Circuits and Systems.IEEE,1997:1544-1547.
[32]Kuonen P,Kobler D.Parallel island-based genetic algorithm for radio network design[J].Journal of Parallel&Distributed Computing,1997,47(1):86-90.
[33]孙如祥,黄春,邓国斌.高维多峰优化的遗传算法设计[J].科技通报,2017,33(8):197-201,229.
[34]李和壁.遗传算法(GA)在旅行商问题(TSP)中的应用[J].科技创新与应用,2015(10):48-49.
[35]Wang J,Ersoy O K,He M,et al.Multi-offspring genetic algorithm and its application to the traveling salesman problem[J].Applied Soft Computing,2016,43(C):415-423.
[36]Lv H.A novel Quantum Genetic Algorithm in TSP[J].Applied Mechanics&Materials,2014,519/520:759-763.
[37]陈守家,付霞,周欣.基于遗传禁忌算法结合解决排课问题[J].计算机应用,2007,27(7):1806-1808.
[38]李素粉,朱云龙.流水车间作业提前/拖期调度问题研究[[J].计算机集成制造系统,2006,12(8):1235-1240.
[39]饶运清,严治雄,张超勇,等.一种混合遗传算法在车间作业调度中的应用研究[J].机械科学与技术,2006,25(5):584-587.
[40]虞蕾,赵红,赵宗涛.一种基于遗传算法的航迹优化方法[J].西北大学学报(自然科学版),2006,36(2):205-208.
[41]李辉,韩红,韩崇昭,等.基于遗传算法的模糊逻辑控制器优化设计[J].西安交通大学学报,2002,36(4):385-389.
[42]王科俊,徐晶,王磊,等.基于可拓遗传算法的机器人路径规划[J].哈尔滨工业大学学报,2006,38(7):1135-1138.
[43]林磊,王晓龙,刘家锋.基于遗传算法的手写体汉字识别系统优化方法的研究[J].计算机研究与发展,2001,38(6):658-661.
[44]赵应丁,刘金刚.基于遗传算法的指纹图像二值化算法研究[J].计算机工程,2006,32(7):169-171.
[45]王建锋,吴庆标.分层遗传算法实现图像边缘检测[J].计算机工程与应用,2006,42(14):95-96.
[46]王静莲,刘弘,李少辉.基于决策树的遗传算法在数据挖掘领域的应用[J].计算机工程与应用,2005,41(28):153-155.
[47]张细政,邢立宁,伍栖.基于遗传算法的数据挖掘方法及应用[J].哈尔滨工程大学学报,2006,24(S1):384-388.(下转第页)
[48]Choenni S.Design and implementation of a genetic-based algorithm for data mining[C]//VLDB 2000,Proceedings of,International Conference on Very Large Data Bases,September 10-14,2000,Cairo,Egypt.DBLP,2000:33-42.
[49]He Y,Hui C W.A binary coding genetic algorithm for multi-purpose process scheduling:A case study[J].Chemical Engineering Science,2010,65(16):4816-4828.
[50]Yang X,Yang Z,Yin X,et al.Chaos gray-coded genetic algorithm and its application for pollution source identifications in convection-diffusion equation[J].Communications in Nonlinear Science&Numerical Simulation,2008,13(8):1676-1688.
[51]陈辉,张家树,张超.实数编码混沌量子遗传算法[J].控制与决策,2005,20(11):1300-1303.
[52]郑朝晖,张焱,裘聿皇.一种基于复数编码的遗传算法[J].控制理论与应用,2003,20(1):97-100.
[53]梁旭,王佳,黄明.解决大规模生产调度问题的一种新编码方法[J].计算机集成制造系统,2008,14(10):1974-1977.
[54]Tang K Z,Sun T K,Yang J Y.An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems[J].Computers&Chemical Engineering,2011,35(4):615-621.
[55]乔家庆,付平,孟升卫.基于个体差异的遗传选择算子设计[J].电子学报,2006,34(S1):2414-2416.
[56]陈皓,崔杜武,严太山,等.基于竞争指数的模拟退火排序选择算子[J].电子学报,2009,37(3):586-591.
[57]Deep K,Thakur M.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics&Computation,2007,188(1):895-911.
[58]Tutkun N.Optimization of multimodal continuous functions using a new crossover for the real-coded genetic algorithms[J].Expert Systems with Applications,2009,36(4):8172-8177.
[59]Wang L,Tang D B.An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem[J].Expert Systems with Applications,2011,38(6):7243-7250.
[60]Deep K,Thakur M.A new mutation operator for real coded genetic algorithms[J].Applied Mathematics&Computation,2007,193(1):211-230.
[61]巩敦卫,郝国生,严玉若.交互式遗传算法基于用户认知不确定性的定向变异[J].控制与决策,2010,25(1):74-78.
[62]Albayrak M,Allahverdi N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert Systems with Applications,2011,38(3):1313-1320.
[63]Liu L,Chen X.Reconfiguration of distribution networks based on fuzzy genetic algorithms[J].Proceedings of the Csee,2000,20(2):66-69.
[64]戴朝华,朱云芳,陈维荣.云自适应遗传算法[J].控制理论与应用,2007,24(4):646-650.
[65]Ponnambalam S G,Jawahar N,Kumar B.Estimation of optimum genetic control parameters for job shop scheduling[J].International Journal of Advanced Manufacturing Technology,2002,19(3):224-234.
[66]陈世哲,刘国栋,浦欣,等.基于优势遗传的自适应遗传算法[J].哈尔滨工业大学学报,2007,39(7):1021-1024.
[67]陈峰,武小悦.基于定向变异算子的求解GA欺骗问题研究[J].系统工程与电子技术,2009,31(1):204-207.
[68]Rudolph G.Convergence analysis of canonical genetic algorithms[J].IEEE Transactions on Neural Networks,1994,5(1):96.
[69]于志刚,宋申民,段广仁.遗传算法的机理与收敛性研究[J].控制与决策,2005,20(9):971-980.
[70]李敏强,寇纪淞.遗传算法的模式欺骗性分析[J].中国科学:技术科学,2002,32(1):95-102.
[71]何军,康立山.遗传算法求解完全欺骗性问题的平均计算时间[J].计算机学报,1999,22(9):999-1003.