一类结合传统优化算法的混合遗传算法
|
摘要
遗传算法(Genetic Algorithm,简称GA)是一种新兴的演化算法。该算法具有设计简单、容易实现和全局优化能力较强等的优点,因而应用广泛。
传统优化算法能够充分利用问题本身所提供的信息与邻域知识,在搜索空间中从一个初始点按照某种确定的原则去寻找下一个迭代点,搜索过程具有针对性,而且收敛速度快、局部寻优能力强。
本文设计出一类结合传统优化算法的混合遗传算法。主要工作概述如下:
首先,由于基本遗传算法随机性较强,使其存在易产生早熟现象、陷入局部极值点、局部寻优能力差、进化后期收敛慢等缺点。本文正是针对这些问题,提出将遗传算法和传统的优化算法相结合,给出一类混合遗传算法;其次,对算法的收敛性进行了理论分析和数值试验,通过在相关的测试函数(Test function)的数值试验结果中表现出了令人满意的优化性能,说明了算法的有效性;最后又将该类混合遗传算法应用到无约束优化问题和约束问题中。
Genetic Algorithm (GA) is a new evolutionary algorithm. The algorithm is simple, easy to implement and has strong global optimization capability, a wider range of applications.
Traditional optimization algorithm can take full advantage of the information of the problems provided by the neighborhood knowledge, in accordance with the certain principles to find the next iteration from an initial point in the search space, the search process is targeted, rapid convergence, and has advantages of strong local Optimization.
In this paper, I design a kind of hybrid genetic algorithm base on traditional optimization algorithm. Major work summarized as follows:
Firstly, because of the strong randomness, standard genetic algorithm easily produce shortcomings,such as premature phenomenon、a local maximum、the poor local optimization and late evolutionary convergence is slow. In light of these problem this paper combine the genetic algorithm and the traditional optimization algorithm,A kind of hybrid genetic algorithms (HGA) based on the traditional optimization is proposed; Secondly, this paper complete the theoretical analysis and numerical experiments for the convergence of the algorithm, Through the relevant test function, the results of numerical experiments demonstrate satisfactory optimal performance and the effectiveness of the algorithm; finally the kind of hybrid genetic algorithm applied to the unconstrained and constrained optimization problem.
传统优化算法能够充分利用问题本身所提供的信息与邻域知识,在搜索空间中从一个初始点按照某种确定的原则去寻找下一个迭代点,搜索过程具有针对性,而且收敛速度快、局部寻优能力强。
本文设计出一类结合传统优化算法的混合遗传算法。主要工作概述如下:
首先,由于基本遗传算法随机性较强,使其存在易产生早熟现象、陷入局部极值点、局部寻优能力差、进化后期收敛慢等缺点。本文正是针对这些问题,提出将遗传算法和传统的优化算法相结合,给出一类混合遗传算法;其次,对算法的收敛性进行了理论分析和数值试验,通过在相关的测试函数(Test function)的数值试验结果中表现出了令人满意的优化性能,说明了算法的有效性;最后又将该类混合遗传算法应用到无约束优化问题和约束问题中。
Genetic Algorithm (GA) is a new evolutionary algorithm. The algorithm is simple, easy to implement and has strong global optimization capability, a wider range of applications.
Traditional optimization algorithm can take full advantage of the information of the problems provided by the neighborhood knowledge, in accordance with the certain principles to find the next iteration from an initial point in the search space, the search process is targeted, rapid convergence, and has advantages of strong local Optimization.
In this paper, I design a kind of hybrid genetic algorithm base on traditional optimization algorithm. Major work summarized as follows:
Firstly, because of the strong randomness, standard genetic algorithm easily produce shortcomings,such as premature phenomenon、a local maximum、the poor local optimization and late evolutionary convergence is slow. In light of these problem this paper combine the genetic algorithm and the traditional optimization algorithm,A kind of hybrid genetic algorithms (HGA) based on the traditional optimization is proposed; Secondly, this paper complete the theoretical analysis and numerical experiments for the convergence of the algorithm, Through the relevant test function, the results of numerical experiments demonstrate satisfactory optimal performance and the effectiveness of the algorithm; finally the kind of hybrid genetic algorithm applied to the unconstrained and constrained optimization problem.
引文
[1]徐宗本等.计算智能中的仿生学:理论与算法.北京:科技出版社,2003
[2]周明等.遗传算法原理及应用.北京:国防工业出版社1999年
[3]Melanie Mitchell.An Introduction to Genetic Algorithms.Cambridge,MA:The MIT Press,1996
[4]Holland J.Adaptation in Natural and Artifical Systems.Ann Arbor,MI:University of Michigan Press,1975
[5]DeJong K.The analysis of the behavior of a class of genetic adaptive system.Michigan:University of Michigan Press,1975
[6]Goldberg D E.Genetic algorithms in search,optimization and machine learning,MA:Addison-Wesley Publishing Company,1989.
[7]Koza J R.Genetic Programming,on the Programming of Computers by Means of Natural Selection.MIT Press,1992.
[8]Koza J R.Genetic Programming Ⅱ.Automatic Discovery of Reusable Programs.MIT Press,1992
[9]席裕庚等.遗传算法综述.控制理论与应用,1996,13(6):697-708
[10]Davis L D.Handbook of Genetic Algorithms.New York:Van Nostrand Reinhold,1991
[11]李敏强等.遗传算法的基本理论与应用.北京:科学出版社,2002
[12]刘勇等.非数值并行算法(第二册)--遗传算法.北京:科学出版社,2003
[13]陈国良等.遗传算法及其应用.北京:人民邮电出版社,1996
[14]De Jong K.Genetic Algorithms are NOT Function Optimizers.In Whitley(ed.)FOGA-2 Foundations of Genetic Algorithms-2.5-17.Morgan Kaufmann Publishers.San Mateo,CA,1992
[15]Syswerda G.Uniform Crossover in Genetic Algorithm In:Proc.Conf.on Genetic Algorithms,Morgan Kaufmann,1989,2-9
[16]唐飞等.十进制整数编码遗传算法的模式定理研究.计算机科学,1999,(6):53-56
[17]Mahfoud S W,Goldberg D E.A Genetic Algorithm for Parallel Simulated Annealing.In:Parallel Solving from Nature 2,North Holland,1992,301-310
[18]简炜等.基于爬山法和遗传算法的联合搜索算法.湖北汽车工业学院学报,2004,18(2):47-48
[19]张晓伟等.求解一类无约束优化的混合遗传算法.西北大学学报(自然科学版),2005,35(2):130-132
[20]David Kincaid & Ward Cheney.Numerical Analysis:Mathematics of Scientific Computing,Third Edition,2002:73-77
[21]金聪等.启发式遗传算法及应用.数值计算与计算机应用,2003,24(1):30-35
[22]黎钧琪等.遗传算法交叉率与变异率关系的研究.武汉理工大学(交通科学与工程版),2003,27(1):97-99
[23]袁亚湘等.最优化理论与方法.北京:科学出版社,1997
[24]张金华等.基于种群差异度的自适应遗传算法.计算机工程与应用,2002,38(9):49-51
[25]张文修等.遗传算法的数学基础.西安:西安交通大学出版社,2000
[26]解伟等.混合遗传算法的收敛性分析.上海大学学报,1998,4(1):1-6
[27]张晓伟等.一类混合遗传算法的收敛性研究.数学的实践与认识,2006,36(12):169-173
[28]刘琼荪等.基于自适应惩罚函数法的混合遗传算法.重庆大学学报(自然科学版),2006,29(6):78-81
[29]Jiafu Tang,etal.A hybrid Genetic Algorithm for a type of nonlinear Programming Problem.computers math.Applic,1998,5:11-21.
[30]Richard Y.K.Fung,etal.Extension of a hybrid genetic algorithm for nonlinear programming problem with equality and inequality constraints.Computers &Operations Research,2002,29:261-274
[31]Michalewich Z,et.Al.A Modified Genetic Algorithm for Optimal Control Programs.Computers Math.Application,1992 23(12):83-94
[32]Grefenstette J J.Incorporating Problem Specific Knowledge into Genetic Algorithms.In:Davis L Ed.Genetic Algorithms and Simulated Annealing,Pitman,1987,42-60
[33]Orvosh D,Davis L.Using a Genetic Algorithm to Optimize Problems with Feasibility Constrains.In:Proc.Of 1st IEEE Conf.on Evolutionary Computation,1994,548-553
[34]Chen H,Flann N S.Paralled Simulated Annealing and Genetic Algorithms:A Space of Hybrid Methods.In:Paralled Problem Solvoing from Nature 3,Springer-Verlag,1994,428-438
[35]徐宗本等.遗传算法基础理论研究的新近发展.数学进展,2000,29(2):97-114
[36]张文修等.遗传算法的概率收敛定理.工程数学学报,2001,18(4):1-11
[37]何琳等.混合算法的收敛性分析及收敛速度估计.系统工程,1999,17(6):64-68
[38]曲中水等.基于遗传算法的收敛性分析方法.哈尔滨理工大学学报,2003,8(1):42-45
[39]戴晓晖等.遗传算法理论研究综述.控制与决策,2000,15(3):263-268
[40]吉根林.遗传算法研究综述.计算机应用与软件,2004,21(2):69-73
[41]闫利军等.基于混合优化算法的遗传算法参数设定研究.系统工程与电子技术,2007,29(10):1753-1756
[2]周明等.遗传算法原理及应用.北京:国防工业出版社1999年
[3]Melanie Mitchell.An Introduction to Genetic Algorithms.Cambridge,MA:The MIT Press,1996
[4]Holland J.Adaptation in Natural and Artifical Systems.Ann Arbor,MI:University of Michigan Press,1975
[5]DeJong K.The analysis of the behavior of a class of genetic adaptive system.Michigan:University of Michigan Press,1975
[6]Goldberg D E.Genetic algorithms in search,optimization and machine learning,MA:Addison-Wesley Publishing Company,1989.
[7]Koza J R.Genetic Programming,on the Programming of Computers by Means of Natural Selection.MIT Press,1992.
[8]Koza J R.Genetic Programming Ⅱ.Automatic Discovery of Reusable Programs.MIT Press,1992
[9]席裕庚等.遗传算法综述.控制理论与应用,1996,13(6):697-708
[10]Davis L D.Handbook of Genetic Algorithms.New York:Van Nostrand Reinhold,1991
[11]李敏强等.遗传算法的基本理论与应用.北京:科学出版社,2002
[12]刘勇等.非数值并行算法(第二册)--遗传算法.北京:科学出版社,2003
[13]陈国良等.遗传算法及其应用.北京:人民邮电出版社,1996
[14]De Jong K.Genetic Algorithms are NOT Function Optimizers.In Whitley(ed.)FOGA-2 Foundations of Genetic Algorithms-2.5-17.Morgan Kaufmann Publishers.San Mateo,CA,1992
[15]Syswerda G.Uniform Crossover in Genetic Algorithm In:Proc.Conf.on Genetic Algorithms,Morgan Kaufmann,1989,2-9
[16]唐飞等.十进制整数编码遗传算法的模式定理研究.计算机科学,1999,(6):53-56
[17]Mahfoud S W,Goldberg D E.A Genetic Algorithm for Parallel Simulated Annealing.In:Parallel Solving from Nature 2,North Holland,1992,301-310
[18]简炜等.基于爬山法和遗传算法的联合搜索算法.湖北汽车工业学院学报,2004,18(2):47-48
[19]张晓伟等.求解一类无约束优化的混合遗传算法.西北大学学报(自然科学版),2005,35(2):130-132
[20]David Kincaid & Ward Cheney.Numerical Analysis:Mathematics of Scientific Computing,Third Edition,2002:73-77
[21]金聪等.启发式遗传算法及应用.数值计算与计算机应用,2003,24(1):30-35
[22]黎钧琪等.遗传算法交叉率与变异率关系的研究.武汉理工大学(交通科学与工程版),2003,27(1):97-99
[23]袁亚湘等.最优化理论与方法.北京:科学出版社,1997
[24]张金华等.基于种群差异度的自适应遗传算法.计算机工程与应用,2002,38(9):49-51
[25]张文修等.遗传算法的数学基础.西安:西安交通大学出版社,2000
[26]解伟等.混合遗传算法的收敛性分析.上海大学学报,1998,4(1):1-6
[27]张晓伟等.一类混合遗传算法的收敛性研究.数学的实践与认识,2006,36(12):169-173
[28]刘琼荪等.基于自适应惩罚函数法的混合遗传算法.重庆大学学报(自然科学版),2006,29(6):78-81
[29]Jiafu Tang,etal.A hybrid Genetic Algorithm for a type of nonlinear Programming Problem.computers math.Applic,1998,5:11-21.
[30]Richard Y.K.Fung,etal.Extension of a hybrid genetic algorithm for nonlinear programming problem with equality and inequality constraints.Computers &Operations Research,2002,29:261-274
[31]Michalewich Z,et.Al.A Modified Genetic Algorithm for Optimal Control Programs.Computers Math.Application,1992 23(12):83-94
[32]Grefenstette J J.Incorporating Problem Specific Knowledge into Genetic Algorithms.In:Davis L Ed.Genetic Algorithms and Simulated Annealing,Pitman,1987,42-60
[33]Orvosh D,Davis L.Using a Genetic Algorithm to Optimize Problems with Feasibility Constrains.In:Proc.Of 1st IEEE Conf.on Evolutionary Computation,1994,548-553
[34]Chen H,Flann N S.Paralled Simulated Annealing and Genetic Algorithms:A Space of Hybrid Methods.In:Paralled Problem Solvoing from Nature 3,Springer-Verlag,1994,428-438
[35]徐宗本等.遗传算法基础理论研究的新近发展.数学进展,2000,29(2):97-114
[36]张文修等.遗传算法的概率收敛定理.工程数学学报,2001,18(4):1-11
[37]何琳等.混合算法的收敛性分析及收敛速度估计.系统工程,1999,17(6):64-68
[38]曲中水等.基于遗传算法的收敛性分析方法.哈尔滨理工大学学报,2003,8(1):42-45
[39]戴晓晖等.遗传算法理论研究综述.控制与决策,2000,15(3):263-268
[40]吉根林.遗传算法研究综述.计算机应用与软件,2004,21(2):69-73
[41]闫利军等.基于混合优化算法的遗传算法参数设定研究.系统工程与电子技术,2007,29(10):1753-1756