何俊红，赵天绪

(宝鸡文理学院 数学系,陕西 宝鸡 721013)



·数理科学·

解非线性方程组的拟牛顿混合遗传算法

何俊红，赵天绪

(宝鸡文理学院 数学系,陕西 宝鸡 721013)

利用熵函数将非线性方程组转化为一个极小值优化问题。结合拟牛顿法和遗传算法的优缺点,提出了一种求解非线性方程组的拟牛顿混合遗传优化算法。该方法不仅有效发挥了遗传算法在进化初期的群搜索能力,而且利用了拟牛顿法的局部精搜索性能,克服了遗传算法在后期易陷入局部收敛的缺陷,提高了算法整体寻优效率。计算机仿真表明，该算法对非线性方程组的求解具有较好的稳定性和较高的收敛精度。

非线性方程组;拟牛顿法;遗传算法;熵函数

对计算机工程、网络优化、航空航天交通流管理等领域的许多优化问题的解决可归结为求解复杂非线性方程组。非线性方程组的解法长期以来是数值计算领域一个重要的研究内容，已经引起众多学者的研究兴趣,且在求解的理论和方法上已经得到了许多有效求解方法[1-4]。从现有的文献可知,这些方法大体可分为两类,一是纯粹的经典优化算法,例如牛顿法、Newton流线法、区间牛顿法等；二是现代发展起来的一些智能进化计算法。对于经典优化算法而言，最典型的方法是牛顿法。牛顿法是一种线性逐步迭代计算方法，突出优点在于收敛速度较快，但有个明显缺点,即每次迭代需知道函数导数值及迭代初始值的信息,而且初值选取的是否恰当会直接影响算法的收敛。近年来,由许多学者提出的求解非线性方程组的智能优化算法,有效避免了传统优化算法在求解非线性方程组需求解目标函数的导数等解析性质,进而直接设计适应度函数进行群搜索。如文献[5]利用差分思想设计了求解方程组的有效解法;文献[6]利用模拟退火算法对非线性方程组进行了求解;文献[7]结合遗传进化设计了求解非线性方程组的有效方法；文献[8]提出了一种求解非线性方程组的人工蜂群算法,这些方法在求解非线性方程组上取得了较好的效果。然而，智能进化计算法在进化初期具有较强的全局搜索能力,但在后期容易陷入局部最优,导致算法终止或只找到问题的局部最优解。针对这些缺陷,本文将非线性方程组转化为一个极小值问题的极限形式,然后充分利用拟牛顿法的局部精搜索能力和遗传算法的全局搜索性能,设计了求解非线性方程组的一种拟牛顿混合遗传算法。最后通过3个经典实例对算法的性能进行了比较测试。结果表明，所给出算法对非线性方程组的求解是有效的。

1 相关概念及模型转化

考虑下列的非线性方程组

(1)

这里x=(x1,x2,…，xn)T是n维实向量,x∈[L,U],fi(x)(i=1,2,…,n)是n个实非线性函数,且

[L,U]={x=(x1,x2,…，xn)T|li≤xi≤ui,i=1,2,…,n}

是问题解的搜索空间,li,ui分别是x的第i个分量xi的上下界。

若设‖·‖α表示向量值空间上的α-范数,当α→∞时,非线性方程组(1)可转化为下列的极大极小优化问题

(2)

证 明 因为

2 算法设计

2.1 子空间高斯变异算子

在遗传算法中,变异算子起着重要的角色,其能有效的增加种群的多样性,促使种群向最优解逼近,设在第t代,设个体x0(t)被选择参加变异,则变异的方法为

Δx～N(0,δ2),

ε为给定正常数,fmin为到目前为止种群找到的最优值。

2.2 保优策略

最好的个体不一定出现在最后一代,所以在进化开始时把最好的个体保留下来,如果在新种群中又发现更好的个体,则用它代替前面保留的个体。

2.3 拟牛顿法[10]

大家知道,Newton法[9]的突出优点是收敛速度快,可是,利用牛顿法需要计算目标函数的二阶导数,且目标函数的Hessen矩阵可能非正定。而拟牛顿法正克服了Newton法需求目标函数的二阶导数及Hessen矩阵求逆的缺点,其主要通过迭代中所得到解的梯度信息来构造近似矩阵列{Hk},从而用以近似牛顿法中的Hessen矩阵,然后沿方向dk=-Hkgk作一维搜索。其基本步骤为

步骤1 给出初始点x(1)∈[L,U]及允许误差ε>0。

步骤2 计算‖gk‖=‖Ω(x(k),α)‖,若‖gk‖≤ε,停;否则,计算dk=-Hkgk。

步骤3 从x(k)出发,沿方向dk进行一维线性精搜索求出步长λk,使其满足

且令x(k+1)=x(k)+λkdk。

步骤4 矫正Hk产生Hk+1,使得拟牛顿条件成立,令k=k+1,转步骤2。

3 拟牛顿混合遗传算法流程

对给定的非线性方程组,定义算法的适应度函数Ω(x,α),设定种群规模pop,杂交概率pc,变异概率pm,最优解的精度及遗传算子中的参数值。

步骤1 随机在搜索空间[L,U]产生初始种群pop(0),令t=0。

步骤2 对[L,U]中的个体以概率pc进行算术杂交产生杂交后代种群popc(t)。

步骤3 对popc(t)中的个体执行子空间高斯变异操作,变异后代与popc(t)中没有参与变异个体共同组成新的变异后代种群popm(t)。

步骤4 对popm(t)中的每个个体执行拟牛顿精搜索,所得个体组成新搜索后代种群popn(t)。

步骤6 当终止条件满足时,输出方程组的最优解或满足精度要求的次优解,否则,令t=t+1,转步骤2。

4 数值模拟

为了有效验证本文算法性能,记文中算法为NGEA,另从文献选取3个具有代表性的非线性方程组,将其结果与本文算法所得结果进行数值比较,其比较结果如表1，2所示,其中G1,G3取自文献[3]。G2选自文献[11],3个非线性方程组具体形式为

其中,x=(x1,x2,x3),xi∈[-1.732,1.732](i=1～3),且理论解为x*=(1,1,1)T。

其中,x=(x1,x2),x1,x2∈[-2,2],且理论解x*=(0.290 9,0)T。

在计算仿真实验中,群体规模pop=450,变异算子中随机生成子空间个体数μ=200,杂交概率pc=0.80,变异概率pm=0.15,算法精度δ=10-12。对于上述每个方程,算法独立运行30次,每次最大迭代次数为150,并将所求得解的平均值与文献中的已有结果加以比较,其结果如表1，2所示。

从表1可以看出,算法NGEA所得方程G1的结果相比文献[11]所得解的精度高,且每次运行中均能找到满足精度要求的最优解,而且迭代的次数相比其他比较算法而言较少,即寻优成功率较高。相对于文献[3],本文算法在找到问题的解的成功率与比较算法相同(其均为100%)。而所得解的3个分量的平均值均好于文献中的结果,且每次运行中,本文算法最大迭代次数相比而言偏低。

表2的结果表明,文中算法NGEA对第2个测试函数G2所得结果比粒子群算法和文献[3]中算法所得解的精度偏高,但每次搜索成功率相同(粒子群算法对G2的成功率没有记录)。对于第3个非线性方程G3,文中算法在所得最优解的各个分量上比粒子群算法及文献[3]中的结果偏好。且独立运行时,其每次迭代到最大次数不超过15次时算法基本终止,即这时已经找到问题的最优解或满足精度要求的次优解,而粒子群算法和文献[3]算法没有给出详细记录,另外本文算法与比较的两种算法对G2，G3均能在每次运行中找到满足精度的最优解。

因此,从上述实验仿真分析可以看出,本文所给算法对非线性方程组的求解具有良好的能力,其能利用较短的迭代次数获得方程的最优解或满足一定精度要求的次优解。

表1 文献[11]、文献[3]算法与NGEA对G1求得结果Tab.1 The results for the algorithms of reference [3],[11]and NGEA on G1

表2 粒子群算法、文献[3]算法及文中算法NGEA对G2,G3求得结果Tab.2 The results for the algorithms of particle swarm, reference [3]and NGEA on G2,G3

5 结 语

在计算机工程、最优设计等领域的许多问题可归结为求解非线性方程组。因此,如何高效求解非线性方程组是目前智能计算领域一个研究热点问题。本文提出了一种解非线性方程组的拟牛顿混合遗传算法,该方法利用熵函数法将问题转化成了一个极小值化问题,并对转化后的优化问题设计了求解的方法。最后的计算机仿真表明,所给方法对非线性方程组的求解非常有效。

[1] 付振岳,王顺芳,丁海燕.并发遗传煺火算法求解复杂非线性方程[J].云南大学学报(自然科学版),2012,34 (1):15-19.

[2] ABDOLLAHI M, LSAZADEH A, ABDOLLAHI D. Imperialist competitive algorithm for solving systems of nonlinear equations [J]. Computers and Mathematics with Applications, 2013,65：1894-1908.

[3] GROSAN C, ABRAHAM A. A new approach for solving nonlinear equations systems [J]. IEEE Transaction on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2008, 38(3), 698-714.

[4] DENIS J E. On Newton′s method and nonlinear simultaneous replacements [J]. SIAM J Numer Anal, 1967(4):103-108.

[5] 封全喜,刘三阳,唐国强,等.求解方程组的正交差分进化算法[J].计算机科学, 2012,39(5):187-189.

[6] 许小勇,张海芳,钟太勇.求解非线性方程及方程组的模拟退火算法[J]. 航空计算技术, 2007, 37(1): 44-46.

[7] KARRA C L, WECKB B L,FREEMAN M. Solutions to systems of nonlinear equations via a genetic algorithm[J].Engineering Applications of Artificial Intelligence, 1998，11：369-375.

[8] 张姣玲.求解非线性方程及方程组的人工蜂群算法[J].计算机工程与应用, 2012, 48(22)：45-47.

[9] 李兴斯. 解非线性规划的凝聚函数法[J]. 中国科学(A辑),1991,21(12): 1283-1288.

[10] 马昌风. 最优化方法及其Matlab程序设计[M]. 北京：科学出版社,2010.

[11] 张安玲,刘雪英.求解非线性方程组的拟牛顿-粒子群混合算法[J].计算机工程与应用, 2008, 44(33)：41-43.

(编 辑亢小玉)

Quasi-Newton hybrid genetic algorithm for solving nonlinear system of equations

HE Jun-hong, ZHAO Tian-xu

(Department of Mathematics, Baoji University of Arts and Sciences, Baoji 721013， China)

First, the nonlinear system of equations was transformed into a minimum optimal problem by using an entropy function. And combining the Quasi-Newton method with the genetic algorithm, a Quasi-Newton hybrid genetic algorithm for solving the nonlinear system of equations is proposed. The proposed algorithm can not only utilize the swarm search ability of genetic algorithm in the initial evolution stage, but also take advantage of the local search property of the Quasi-Newton, and these have made the proposed algorithm overcome the local convergence of genetic algorithm in the later evolution stage and improved the overall search ability of the proposed algorithm. The computer simulations demonstrate the proposed algorithm has good stability and convergence precision in solving the nonlinear system of equations.

nonlinear system of equations; Quasi-Newton method; genetic algorithm; entropy function

2014-03-16

国家自然科学基金资助项目(11371291)；陕西省教育厅科研计划基金资助项目(11JK0506)；宝鸡文理学院校级重点科研计划基金资助项目(ZK12044)

何俊红， 女，陕西宝鸡人，从事最优化、智能计算与系统模拟研究。

赵天绪，男，陕西宝鸡人，宝鸡文理学院教授，博士，从事最优化理论研究。

O224; TP301.6

：ADOI：10.16152/j.cnki.xdxbzr.2015-03-002