求解非线性问题的混合遗传算法研究
|
摘要
本文针对非线性数值的问题,结合经典优化算法和遗传算法,构造新的混合遗传算法,数值模拟试验表明,该算法具有很高的精确性和较好的收敛性,是求解非线性数值问题的一种有效算法。
在第一章中,概述了遗传算法的基本理论,论述了混合遗传算法的研究现状。
在第二章中,分析和论述了非线性方程组的基本解法,主要介绍了牛顿型算法、信赖域方法和遗传算法在求解非线性方程组中应用。
在第三章中,提出了一种求解非线性互补问题(NCP)的混合遗传算法,首先将NCP转化为等价的最优问题,然后利用浮点遗传算法快速求出NCP等价优化问题的接近精确解的较优解,将其作为牛顿型算法的初始迭代值,利用牛顿算法的局部寻优能力强的特点,快速迭代至满足精度要求的数值解。该算法保证了全局收敛性,克服了传统算法的缺点,数值试验结果验证了这种混合遗传算法的有效性。
在第四章中,提出将非线性不等式组求解问题转化为等价的求解无约束极小化问题的全局最优解,基于浮点遗传算法全局群体搜索能力强和起始搜索速度快的特点,用浮点遗传算法快速求出无约束极小化问题的接近精确解的较优解,作为(拟)牛顿算法的初始迭代值,然后转入牛顿型迭代求得满足精度要求的近似解。这种算法充分利用了牛顿型方法收敛速度快的优点,又解决了牛顿型方法初始值选取的困难,数值试验结果验证了该混合遗传算法的有效性。
For solve the nonlinear numerical problems, the traditional optimization and genetic algorithm will be combined for proposing a new hybrid genetic algorithm. Numerical experiments show that this algorithm has highly precision and reliable convergent resulting.
In Chapter 1, we review the basic theory of genetic algorithm, introduce the research state and advances of hybrid genetic algorithm.
In Chapter 2, we analyze some basic methods for solving the nonlinear equations. And introduce three methods for solving the nonlinear equations.
In Chapter 3, we propose a hybrid genetic algorithm for solving nonlinear complement-tarity problems (denoted by NCP). At first, we transform NCP into the equivalent optimization problems.Then taking advantage of excellence of the floating genetic algorithms, we gain the superior results which close to precise solutions quickly, and then taking the results as the initial values of Newton or quasi-Newton iterations, which has strong ability in locally converging to precise solution, we obtain satisfactory approximation solution. The hybrid genetic algorithm absorbs fully the merits of the floating genetic algorithm and the Newton-type'methods.Some numerical results show that this method is effective.
In Chapter 4, we discuss a method that transform the problems of solving nonlinear equations into an unconstrained optimization problem.Then taking advantage of excellence of the floating genetice algorithms,we obtain the superior results which close to precise solution quickly,and then taking the results as the initial values of Newton or quasi-Newton interations.This algorithm absorbs fully the merits of the Newton methods and overcome the limitations of initial values. The numerical results show the effectiveness of the algorithm.
在第一章中,概述了遗传算法的基本理论,论述了混合遗传算法的研究现状。
在第二章中,分析和论述了非线性方程组的基本解法,主要介绍了牛顿型算法、信赖域方法和遗传算法在求解非线性方程组中应用。
在第三章中,提出了一种求解非线性互补问题(NCP)的混合遗传算法,首先将NCP转化为等价的最优问题,然后利用浮点遗传算法快速求出NCP等价优化问题的接近精确解的较优解,将其作为牛顿型算法的初始迭代值,利用牛顿算法的局部寻优能力强的特点,快速迭代至满足精度要求的数值解。该算法保证了全局收敛性,克服了传统算法的缺点,数值试验结果验证了这种混合遗传算法的有效性。
在第四章中,提出将非线性不等式组求解问题转化为等价的求解无约束极小化问题的全局最优解,基于浮点遗传算法全局群体搜索能力强和起始搜索速度快的特点,用浮点遗传算法快速求出无约束极小化问题的接近精确解的较优解,作为(拟)牛顿算法的初始迭代值,然后转入牛顿型迭代求得满足精度要求的近似解。这种算法充分利用了牛顿型方法收敛速度快的优点,又解决了牛顿型方法初始值选取的困难,数值试验结果验证了该混合遗传算法的有效性。
For solve the nonlinear numerical problems, the traditional optimization and genetic algorithm will be combined for proposing a new hybrid genetic algorithm. Numerical experiments show that this algorithm has highly precision and reliable convergent resulting.
In Chapter 1, we review the basic theory of genetic algorithm, introduce the research state and advances of hybrid genetic algorithm.
In Chapter 2, we analyze some basic methods for solving the nonlinear equations. And introduce three methods for solving the nonlinear equations.
In Chapter 3, we propose a hybrid genetic algorithm for solving nonlinear complement-tarity problems (denoted by NCP). At first, we transform NCP into the equivalent optimization problems.Then taking advantage of excellence of the floating genetic algorithms, we gain the superior results which close to precise solutions quickly, and then taking the results as the initial values of Newton or quasi-Newton iterations, which has strong ability in locally converging to precise solution, we obtain satisfactory approximation solution. The hybrid genetic algorithm absorbs fully the merits of the floating genetic algorithm and the Newton-type'methods.Some numerical results show that this method is effective.
In Chapter 4, we discuss a method that transform the problems of solving nonlinear equations into an unconstrained optimization problem.Then taking advantage of excellence of the floating genetice algorithms,we obtain the superior results which close to precise solution quickly,and then taking the results as the initial values of Newton or quasi-Newton interations.This algorithm absorbs fully the merits of the Newton methods and overcome the limitations of initial values. The numerical results show the effectiveness of the algorithm.
引文
[1]周明,孙树栋.遗传算法原理及应用[M].北京：国防工业出版社,1999.
[2]李敏强,寇纪松,林丹,等.遗传算法的基本理论与应用[M].北京：科学出版社,2002.3.
[3]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002.1.
[4]葛继科,邱玉辉,吴春明,等,遗传算法研究综述[J],计算机应用研究,2008,25(10)：2911-2916.
[5]黄翼卓,王湛,马人乐.一种新的求解约束多目标优化问题的遗传算法[J],计算机工程与应用,2006,42(23)：47-51.
[6]文绍纯,罗飞,付连续.遗传算法在人工神经网络中的应用综述[J],计算机技术与自动化,2001,20(2)：1-5.
[7]路文江,汤富领,刘树群,等.用神经网络-遗传算法优化镍基喷涂材料[J],甘肃工业大学学报,1998,24(1)：11-15.
[8]刘江梅,李可意.基于BP神经网络和遗传算法优化莪术超临界萃取工艺[J],中国药学杂志,2006,41(5)：371-374.
[9]贾兆江,倪志伟.改进型遗传算法及其在数据挖掘中的应用[J],计算机应用,2002,22(9)：31-33.
[10]王静莲,刘弘,李少辉.基于决策树的遗传算法在数据挖掘领域的应用[J],计算机工程与应用,2005,41(28)：153-155.
[11]张细致,邢立宁,伍栖.基于遗传算法的数据挖掘方法及其应用[J],计算机应用,2006,27(7)：384-388.
[12]赵应丁,刘金刚,基于遗传算法的指纹图像二值化算法研究[J],计算机工程,2006,32(7)：169-171.
[13]王建锋,吴庆标.分层遗传算法实现图像边缘检测[J],计算机工程与应用,2006,42(14)：95-96,151.
[14]邓勃,刘嘉.遗传算法在分析化学中的应用[J],分析科学学报,1997,13(2)：160-168.
[15]李进文,陈朝辉,曾平.基于遗传算法的药物动力学参数估计[J],树理医药学杂志,2006,19(5)：529-530.
[16]蔡煜东.分析化学中非线性多元函数拟合的的遗传算法[J],分析化学,1995,23(7)：790-792.
[17]陈开,李通化,卢佩章.遗传算法在色谱图解析中的应用[J],分析化学,2003,31(2)：58-162.
[18]仇丽霞,刘桂芬,何大卫,肖林.遗传算法在正交试验设计最优条件选择中的应用[J],现在预防医学,2004,31(4)：493-495.
[19]杨尚达,李世平.遗传算法研究[J],网络与信息研究,2008,27(9)：60-62.
[20]靖稳峰,魏红,段惠娣,遗传算法及其发展现状[J],西安工业学院学报,2000,20(3)：230-235.
[21]杨商达,李世平.遗传算法研究[J],网络与信息技术,2008,27(9)：60-62.
[22]马玉明,贺爱珍,李爱民.遗传算法的理论研究综述[J],山东轻工业学院学报,2004,18(3)：77-80.
[23]恽为民,席裕庚.遗传算法的运行机理分析[J],控制理论与应用,1996,13(3)：289-297.
[24]戴晓辉,李敏强,寇纪松.遗传算法理论研究综述[J],控制与决策,2000,15(3)：263-273.
[25]郑立平,牛熠.遗传算法综述[J],东莞理工学院学报[J],2005,12(3)48-52.
[26]王丽薇,洪勇,洪家荣.遗传算法的收敛性研究[J],计算机学报,1996,19(10)：794-797.
[27]李书全,寇纪松,李敏强.遗传算法的随机泛函分析[J],系统工程学报,1998,13(1)
[28]张讲社,徐本,梁怡.整体群体遗传算法及其收敛充要条件[J],中国科学[E辑],1997,27(2)：154-164.
[29]屠昂燕,陈建成.遗传算法的收敛性研究[J],河北第二师范学院学报,2008,25(2)：49-51.
[30]李献业,钟绍春.基于遗传算法的多代理规划方法[J],东北师范大学学报(自然科学版),2000,32(1)：1-5.
[31]闫洁,曹秉刚,史维祥.一种快速收敛的遗传算法及其应用[J],西安交通大学学报,2001,(1).
[32]刘杰,王媛.一种高效混合遗传算法[J],河海大学学报,2002,30(2)：49-53.
[33]李宏,焦永昌,张莉,王宇平.一种求解全局优化问题的新混合遗传算法[J]控制理论与应用,2007,24(03)：128-136.
[34]杨莉.混合遗传算法设计方法的探讨[J],湖北师范学院学报(自然科学版),2000,20(3)：70-73.
[35]刘铁男,段玉波,雷顺.一种混合遗传算法及收敛性分析[J],自动化技术与应用,2003,22(10)：4-6.
[36]谢巍,方康玲.一种求解不可微非线性函数的全局解的混合遗传算法[J],控制理论与应用,2000,17(2)：180-183.
[37]陈凯,马景义,温慧博.一种改进的集成混合遗传算法[J],统计与决策,2008,17：41-43.
[38]吴国辉,代冀阳,吴印华,朱国民.一种新的求解非线性方程组的混合遗传算法[J],南昌航空工业学院学报(自然科学版),2007,21(1)：5-9.
[39]杜娟,刘志刚.一种新的求解非线性方程组的混合量子遗传算法[J],微计算机应用,2008,29(7)：1-5.
[40]张宏生,吴拓.遗传算法在非线性方程组求解中的应用[J],肇庆学院学报,2002,23(2)：16-19,27.
[41]刘灿文,刘捷.基于求解非线性方程组的并行遗传算法的设计[J],华东师范大学学报(自然科学版),2004,1：29-34.
[42]曾毅.改进的遗传算法在求解非线性方程组的应用[J],华东交通大学学报,2004,21(4)：39-41.
[43]曾毅.浮点遗传算法在非线性方程组求解中的应用[J],华东交通大学学报,2005,22(1)：152-155.
[44]Harker,P.T.,Pang,J.S., Finite-dimensional variational inequality and nonlinear complementarity problems:A survey of theory, algorithms and applications [J], Mathematical Programming 48:161-220(1990).
[45]Ferris,M. C., Pang, J. S., Engineering and economic applications of complementarity problems [J], SIAM Review 39:669-713(1997).
[46]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M],上海科学技术出版社,2006.
[47]何郁波,梁茜,田亚娟,马昌凤.非线性互补问题的内点法[J],桂林电子工业学院学报,2006,26(3)：207-211.
[48]陈国庆,陈余泉.非线性互补问题的熵函数法[J],内蒙古大学学报,2000,31(5)：447-451.
[49]范江华.求解非线性互补问题的单纯同伦算法[J],工程数学学报,2006,23(4)：619-624.
[50]马昌凤.求解非线性互补问题的光滑信赖域算法[J],工程数学学报,2006,23(1)：20-28.
[51]田亚娟,马昌凤,何郁波.求解非线性互补问题的一个无导数下降算法[J],桂林电子工业学院学报,2006,26(1)：68-71.
[52]Kanzow C, Pieper H. Jacobian smoothing methods for nonlinear complementarity problems [J]. SIAM Journal on Optimization,1999,(9):342-373.
[53]Qi,H.,A regularized smoothing Newton method for box constrained variational inequality problems with PO-functions [J], SIAM Journal on Optimization,10(1):315-330(2000).
[54]Chen.B.,and Marker,P.T.,Smoothing approximations to nonlinear complementarity problems [J],SIAM Journal on Optimization,7(1):403-420(1997)
[55]Qi, L, Sun,D.,and Zhou,G.,A new look at smoothing Newton methods for nonlinear complem-entarity problems and box constrained variational inequality problems [J], Mathematical Programming,87(1): 1-35(2000).
[56]Kanzow C., Some, noniterior continuation methods for linear complementarity problem [J]. SIAM J. Matrix Anal. Appl.,1996,17:851-868.
[57]Jiang H.Y. and Qi L., A new nonsmooth equastions approach to nonlinear complementarity problems,SIAM J.Control Optim.,35(1997):178-193.
[58]J.W.Daniel,Newton method of nonlinear inequelities[J],Numer.Math.21 (1973) 381-387.
[59]D.Q.Mayne,E.Polak,A.J.Heunis,Solving nonlinear inequalities in a finite number of iterations [J],Optim.Theory Appl.33(1981)207-221.
[60]Changfeng Ma.A globally convergment Levenberg-Marquardt method for the least 12-norm solution of nonlinear inequalities[J], Applied Mathematics and Computation,206(2008):133-144.
[2]李敏强,寇纪松,林丹,等.遗传算法的基本理论与应用[M].北京：科学出版社,2002.3.
[3]王小平,曹立明.遗传算法理论、应用与软件实现[M].西安：西安交通大学出版社,2002.1.
[4]葛继科,邱玉辉,吴春明,等,遗传算法研究综述[J],计算机应用研究,2008,25(10)：2911-2916.
[5]黄翼卓,王湛,马人乐.一种新的求解约束多目标优化问题的遗传算法[J],计算机工程与应用,2006,42(23)：47-51.
[6]文绍纯,罗飞,付连续.遗传算法在人工神经网络中的应用综述[J],计算机技术与自动化,2001,20(2)：1-5.
[7]路文江,汤富领,刘树群,等.用神经网络-遗传算法优化镍基喷涂材料[J],甘肃工业大学学报,1998,24(1)：11-15.
[8]刘江梅,李可意.基于BP神经网络和遗传算法优化莪术超临界萃取工艺[J],中国药学杂志,2006,41(5)：371-374.
[9]贾兆江,倪志伟.改进型遗传算法及其在数据挖掘中的应用[J],计算机应用,2002,22(9)：31-33.
[10]王静莲,刘弘,李少辉.基于决策树的遗传算法在数据挖掘领域的应用[J],计算机工程与应用,2005,41(28)：153-155.
[11]张细致,邢立宁,伍栖.基于遗传算法的数据挖掘方法及其应用[J],计算机应用,2006,27(7)：384-388.
[12]赵应丁,刘金刚,基于遗传算法的指纹图像二值化算法研究[J],计算机工程,2006,32(7)：169-171.
[13]王建锋,吴庆标.分层遗传算法实现图像边缘检测[J],计算机工程与应用,2006,42(14)：95-96,151.
[14]邓勃,刘嘉.遗传算法在分析化学中的应用[J],分析科学学报,1997,13(2)：160-168.
[15]李进文,陈朝辉,曾平.基于遗传算法的药物动力学参数估计[J],树理医药学杂志,2006,19(5)：529-530.
[16]蔡煜东.分析化学中非线性多元函数拟合的的遗传算法[J],分析化学,1995,23(7)：790-792.
[17]陈开,李通化,卢佩章.遗传算法在色谱图解析中的应用[J],分析化学,2003,31(2)：58-162.
[18]仇丽霞,刘桂芬,何大卫,肖林.遗传算法在正交试验设计最优条件选择中的应用[J],现在预防医学,2004,31(4)：493-495.
[19]杨尚达,李世平.遗传算法研究[J],网络与信息研究,2008,27(9)：60-62.
[20]靖稳峰,魏红,段惠娣,遗传算法及其发展现状[J],西安工业学院学报,2000,20(3)：230-235.
[21]杨商达,李世平.遗传算法研究[J],网络与信息技术,2008,27(9)：60-62.
[22]马玉明,贺爱珍,李爱民.遗传算法的理论研究综述[J],山东轻工业学院学报,2004,18(3)：77-80.
[23]恽为民,席裕庚.遗传算法的运行机理分析[J],控制理论与应用,1996,13(3)：289-297.
[24]戴晓辉,李敏强,寇纪松.遗传算法理论研究综述[J],控制与决策,2000,15(3)：263-273.
[25]郑立平,牛熠.遗传算法综述[J],东莞理工学院学报[J],2005,12(3)48-52.
[26]王丽薇,洪勇,洪家荣.遗传算法的收敛性研究[J],计算机学报,1996,19(10)：794-797.
[27]李书全,寇纪松,李敏强.遗传算法的随机泛函分析[J],系统工程学报,1998,13(1)
[28]张讲社,徐本,梁怡.整体群体遗传算法及其收敛充要条件[J],中国科学[E辑],1997,27(2)：154-164.
[29]屠昂燕,陈建成.遗传算法的收敛性研究[J],河北第二师范学院学报,2008,25(2)：49-51.
[30]李献业,钟绍春.基于遗传算法的多代理规划方法[J],东北师范大学学报(自然科学版),2000,32(1)：1-5.
[31]闫洁,曹秉刚,史维祥.一种快速收敛的遗传算法及其应用[J],西安交通大学学报,2001,(1).
[32]刘杰,王媛.一种高效混合遗传算法[J],河海大学学报,2002,30(2)：49-53.
[33]李宏,焦永昌,张莉,王宇平.一种求解全局优化问题的新混合遗传算法[J]控制理论与应用,2007,24(03)：128-136.
[34]杨莉.混合遗传算法设计方法的探讨[J],湖北师范学院学报(自然科学版),2000,20(3)：70-73.
[35]刘铁男,段玉波,雷顺.一种混合遗传算法及收敛性分析[J],自动化技术与应用,2003,22(10)：4-6.
[36]谢巍,方康玲.一种求解不可微非线性函数的全局解的混合遗传算法[J],控制理论与应用,2000,17(2)：180-183.
[37]陈凯,马景义,温慧博.一种改进的集成混合遗传算法[J],统计与决策,2008,17：41-43.
[38]吴国辉,代冀阳,吴印华,朱国民.一种新的求解非线性方程组的混合遗传算法[J],南昌航空工业学院学报(自然科学版),2007,21(1)：5-9.
[39]杜娟,刘志刚.一种新的求解非线性方程组的混合量子遗传算法[J],微计算机应用,2008,29(7)：1-5.
[40]张宏生,吴拓.遗传算法在非线性方程组求解中的应用[J],肇庆学院学报,2002,23(2)：16-19,27.
[41]刘灿文,刘捷.基于求解非线性方程组的并行遗传算法的设计[J],华东师范大学学报(自然科学版),2004,1：29-34.
[42]曾毅.改进的遗传算法在求解非线性方程组的应用[J],华东交通大学学报,2004,21(4)：39-41.
[43]曾毅.浮点遗传算法在非线性方程组求解中的应用[J],华东交通大学学报,2005,22(1)：152-155.
[44]Harker,P.T.,Pang,J.S., Finite-dimensional variational inequality and nonlinear complementarity problems:A survey of theory, algorithms and applications [J], Mathematical Programming 48:161-220(1990).
[45]Ferris,M. C., Pang, J. S., Engineering and economic applications of complementarity problems [J], SIAM Review 39:669-713(1997).
[46]韩继业,修乃华,戚厚铎.非线性互补理论与算法[M],上海科学技术出版社,2006.
[47]何郁波,梁茜,田亚娟,马昌凤.非线性互补问题的内点法[J],桂林电子工业学院学报,2006,26(3)：207-211.
[48]陈国庆,陈余泉.非线性互补问题的熵函数法[J],内蒙古大学学报,2000,31(5)：447-451.
[49]范江华.求解非线性互补问题的单纯同伦算法[J],工程数学学报,2006,23(4)：619-624.
[50]马昌凤.求解非线性互补问题的光滑信赖域算法[J],工程数学学报,2006,23(1)：20-28.
[51]田亚娟,马昌凤,何郁波.求解非线性互补问题的一个无导数下降算法[J],桂林电子工业学院学报,2006,26(1)：68-71.
[52]Kanzow C, Pieper H. Jacobian smoothing methods for nonlinear complementarity problems [J]. SIAM Journal on Optimization,1999,(9):342-373.
[53]Qi,H.,A regularized smoothing Newton method for box constrained variational inequality problems with PO-functions [J], SIAM Journal on Optimization,10(1):315-330(2000).
[54]Chen.B.,and Marker,P.T.,Smoothing approximations to nonlinear complementarity problems [J],SIAM Journal on Optimization,7(1):403-420(1997)
[55]Qi, L, Sun,D.,and Zhou,G.,A new look at smoothing Newton methods for nonlinear complem-entarity problems and box constrained variational inequality problems [J], Mathematical Programming,87(1): 1-35(2000).
[56]Kanzow C., Some, noniterior continuation methods for linear complementarity problem [J]. SIAM J. Matrix Anal. Appl.,1996,17:851-868.
[57]Jiang H.Y. and Qi L., A new nonsmooth equastions approach to nonlinear complementarity problems,SIAM J.Control Optim.,35(1997):178-193.
[58]J.W.Daniel,Newton method of nonlinear inequelities[J],Numer.Math.21 (1973) 381-387.
[59]D.Q.Mayne,E.Polak,A.J.Heunis,Solving nonlinear inequalities in a finite number of iterations [J],Optim.Theory Appl.33(1981)207-221.
[60]Changfeng Ma.A globally convergment Levenberg-Marquardt method for the least 12-norm solution of nonlinear inequalities[J], Applied Mathematics and Computation,206(2008):133-144.