求解非线性方程组的混合遗传算法

第22卷第1期2005年2月　计算力学学报　

Chinese Journal of Computational Mechanics

V ol. 22, N o . 1F ebr uary 2005

文章编号:1007-4708(2005) 01-0109-06

求解非线性方程组的混合遗传算法

罗亚中, 　袁端才, 　唐国金*

(国防科技大学航天与材料工程学院, 湖南长沙410073)

摘　要:非线性方程组的求解是数值计算领域中最困难的问题, 大多数的数值求解算法例如牛顿法的收敛性和性能特征在很大程度上依赖于初始点。但是对于很多非线性方程组, 选择好的初始点是一件非常困难的事情。本文结合遗传算法和经典算法的优点, 提出了一种用于求解非线性方程组的混合遗传算法。该混合算法充分发挥了遗传算法的群体搜索和全局收敛性, 有效地克服了经典算法的初始点敏感问题; 同时在遗传算法中引入经典算法(P ow ell 法、拟牛顿迭代法) 作局部搜索, 克服了遗传算法收敛速度慢和精度差的缺点。选择了几个典型非线性方程组, 从收敛可靠性、计算成本和适用性等指标分析对比了不同算法。计算结果表明所设计的混合遗传算法有着可靠的收敛性和较高的收敛速度和精度, 是求解非线性方程组的一种成功算法。关键词:非线性方程组; 混合遗传算法; 优化和迭代; 嵌套混合; 拟牛顿迭代法中图分类号:T P18　　　文献标识码:A

1　引　言

非线性方程组求解是实际工程领域的一个重要问题, 在数值天气预报、石油地质勘探、计算生物化学、控制领域和轨道设计等方面均有较强的应用背景。长期以来, 人们在理论和数值计算方面对非线性方程组作了大量的研究, 但是非线性方程求解仍然是困扰人们的一个难题, 特别是对于高非线性度的实际工程问题, 始终缺乏高效可靠的算法。牛顿迭代法及其改进形式是目前应用最广泛的非线性方程组求解算法, 但是此类算法的收敛性在很大程度上依赖于初始点的选择, 不合适的初始点很容易导致算法收敛失败, 然而选择一个好的初始点往往是一件非常困难的事情。从实际应用角度出发, 有必要探索高效可靠的算法。

近年来具有全局收敛性的遗传算法是优化设计领域的研究热点。遗传算法是模仿自然选择和遗传机制的一种智能优化算法, 隐含并行性和群体全局搜索特性是它的两个显著特征, 具有较强的鲁棒性, 对于一些大型、复杂非线性系统求解具有独特的优越性能。本文尝试从优化和迭代相结合的角度求解非线性方程组, 从遗传算法的特点和经典算法特点出发, 设计了一种用于求解非线性方程组的高效可靠的混合算法, 算法继承了遗传算法的群体全

收稿日期:2003-04-14; 修改稿收到日期:2003-10-10. 基金项目:“863”课题(2002AA 001006) . :() , 男, 博士;

(.

[1]

局搜索能力, 具有全局收敛性; 同时在遗传算法中引入经典算法(Po well 法、牛顿法及其改进形式) 作为一个元算子则有效地提高了算法的局部搜索能力, 使得算法具有较高的收敛速度和求解精度。

2　问题描述

实函数非线性方程组的一般形式(假定有n 个变量X =[x 1, x 2, …, x n ]和n 个方程, 且有解) 为

f 1(x 1, x 2, …, x n ) =0f 2(x 1, x 2, …, x n ) =0　　　　

f n (x 1, x 2, …, x n ) =0

求解此方程组等价于求解下面一个极值优化问题:

find:　X =[x 1, x 2, …, x n ], X ∈5

n

(1)

(2)

2

i

min:　f (X ) =

∑f

i =1

(X )

式(2) 中5为方程组解的区间, 当f (X ) 最小值为0时, 所对应的X 即为方程组的解。

针对式(1) 和式(2) 出发求解非线性方程组的方法可以分为以下两种。

2. 1　牛顿法及其改进方法

从式(1) 的等式条件出发构造迭代格式是求解方程组的基本方法, 而牛顿法就是其中应用最广泛最基本的方法[1]。

牛顿法在实际的应用中存在着需要大量计算

・110・

计算力学学报

　第22卷　

了许多牛顿法的改进方法, 如修正牛顿法、带参数的牛顿法等, 拟牛顿法是其中有代表性的一种方法, 其核心思想是用通过计算函数值代替导数计算。本文在实现求解非线性方程组的混合算法时对这两种算法均进行了调试, 考虑到拟牛顿法在实际的应用更为广泛一些, 算例分析以拟牛顿法为准。

用牛顿法及其改进形式求解非线性方程组, 其收敛速度是相当快的, 在适当的条件下, 该方法具有二阶收敛速度。但牛顿法对迭代的初值要求很苛刻, 如果初始迭代点不在牛顿法的收敛域内, 该方法失效, 同时该方法对于一些性态较差的非线性方程组收敛效果很差, 这是牛顿法在实际应用中的较突出的问题。

2. 2　直接数值优化算法

把非线性方程组求解问题化为形如式(2) 所示的优化问题后, 常用的非线性优化数值算法如最速下降法, 单纯型法和Pow ell 法等均可以用到非线性方程组的求解中, 但由于这些算法也有初始点敏感、局部收敛等局限性, 相对于牛顿迭代法并没有明显的优势, 因此实际应用它们求解非线性方程组的例子并不多, 文献[3]提出了一种求解非线性方程组的组合算法, 该算法利用了求目标函数极值的最速下降法作初始点预估, 拟牛顿法精确求解, 取得了较好的效果。文献[4]则把非线性方程组转化为二次规划问题, 为非线性方程组求解提供了一种新思路。

在优化领域, 近年来的全局优化算法如遗传算法、模拟退火算法、神经网络算法和混沌算法等已经被证明具有良好的全局收敛性和较强的鲁棒性, 广泛地适应于各个领域, 这其中又以遗传算法的应用最为广泛和成功。将遗传算法应用于方程求解领域, 人们也做出了一定的研究:文献[5, 6]将遗传算法应用到方程求根中, 取得了一定的效果; 文献[7]将进化策略应用到线性方程组求解算法SOR 的最佳松弛因子确定中, 文献[8]利用遗传算法设计了串行混合策略求解非线性方程组。

但是, 诚如文献[2, 5, 6]所述, 遗传算法在任何领域的成功应用都需要一个过程, 应用于方程组的求解也不例外, 一方面需要遗传算法提高自身性能(如优化控制参数、改进各种算子等) , 另一方面则需要在遗传算法引入应用领域的知识型启发算本文结合遗传算法和经典算法的优点, 从优化和迭代相结合角度求解非线性方程组, 设计了一类混合遗传算法用于非线性方程组的求解中, 取得了良好的应用效果。

3　遗传算法设计

3. 1　编码方式

本文采用的编码方式是实数编码, 与二进制编码相比, 实数编码具有如下明显优点:¹在遗传算法中可方便地表示范围较大的数, 便于在较大空间进行搜索, 同时也改善了遗传算法的计算复杂性, 提高了运算效率; º求解精度高, 便于与经典优化方法混合使用。鉴于实数编码的上述优越性和非线性方程组求解的实际要求, 在本文所设计的混合遗传算法中采用实数编码方式, 这样使得算法对于任何方程组求解都具有通用性。3. 2　适应度计算

遗传算法在运行时, 是依靠适应度函数值的大小来区分每个个体的优劣, 并判定是否进入下一代的进化。适应度函数的选择直接影响着算法的性能, 几种常用的适应度函数方法及其分析参见文献[2]。本文在算子设计时以联赛竞争算子为选择算子, 该算子可以直接通过比较个体的目标函数值完成操作, 因此本文的遗传算法的适应度函数直接选择为优化目标函数, 即由式(2) 确定。3. 3　遗传算子

遗传算子设计包括交叉算子、变异算子和选择算子的设计。

(1) 交叉算子

算术交叉算子是实数编码遗传算法中应用最广泛的一种算子, 该算子描述如下:

假设在两个体X 1和X 2之间进行算术交叉, 则交叉运算后所产生出的两个新个体为

X 1=aX 1+(1-a ) X 2X

*

2*

=(1-a ) X +aX

1

(3)

2

其中a 是在[0, 1]区间内的参数, 它可以是一个常数, 也可以是由进化所决定的变量, 本文选择为[0, 1]区间上的随机数。

(2) 变异算子

传统的实数编码遗传算法的收敛速度慢、容易产生早熟现象, 在很大程度上是由于变异操作在进化过程中对局部极值点的干扰效果不明显。因此构

　第1期

罗亚中, 等:求解非线性方程组的混合遗传算法

・111・

的关键。本文设计了一种新的随机方向变异算子, 称之为确定性随机方向变异, 算子描述如下:

设被选中变异的个体的染色体为X k , 随机产生一个扰动方向p k , 整个变异操作的过程是以X k 为起点, 沿方向p k 寻求最优点作为新的染色体, 即完成如下一维搜索运算:

min

变异后个体的新染色体X k 为

X ′k =X k +K 0p k

(3) 选择算子设计

传统的标准选择算子一方面要求适应度函数大于零, 给适应度函数的选择带了一定的困难; 另一方面基于适应值的排序选择算子是造成算法早熟、收敛速度慢的主要原因。为避免上述问题, 本文采用了既具有较高确定性和一定随机性的联赛竞争法为选择算子, 联赛规模取为3。由于遗传算法中有许多随机因素的影响, 当前群体的最好个体可能会被破坏, 影响算法的运行效率和收敛性, 因此采用了最优保存策略, 即当前群体中最优个体不参与交叉运算和变异运算, 而是用它来替代本代群体中经过交叉、变异操作后所产生的最差个体。

[2]

′

化的代数, 常数p 0∈(0, 1]类似于遗传算法中的交叉概率和变异概率, 反映了局部强搜索算子对每个个体的最大可能作用程度, p 0大则混合算子对遗传算法搜索空间的局部开采愈充分, 但是相应的计算成本愈大, 本文选择了p 0=0. 10。a 为控制算子概率变化的参数, 本文选择了a =1, 设计p n 为关于t 的递增函数的出发点是:在进化的初期, 为保持个体的多样性, 针对个体的局部寻优操作的可能性要小; 在进化的后期, 有理由相信个体已接近全局最优解, 此时对个体以较高的概率进行局部寻优将有助于其加速收敛至全局最优解。

本文分别从式(1) 和式(2) 出发, 设计了拟牛顿迭代混合算子和Po w ell 混合算子, 并进行了分析比较。拟牛顿混合算子的构造方法是:以被选中个体的染色体为初始点进行拟牛顿迭代操作, 若算法收敛则以收敛点作为个体新的染色体, 若不收敛则不改变个体的染色体。Po w ell 混合算子的构造方法是:以个体的染色体为初始点进行Pow ell 寻优计算, 以优化结果作为个体新的染色体。4. 2　算法描述

Beg in

确定设计变量上下限, 随机产生父代群体, 设定算法基本参数。While

评价群体:计算各个个体的基本属性(计算目标函数、确定最好最差个体等) ;

依据交叉概率p c 对群体进行算术交叉操作; 依据变异概率p m 对群体进行确定性随机方向变异操作;

依据自适应混合算子概率p n 对群体进行经典算法局部搜索;

依据最优保留策略的联赛竞争算子选择新的群体;

until 迭代终止条件End

对于非线性方程组的求解, 迭代中终止条件有两个:一个是进化到最大代数, 另外一个是误差

-6E =max ûf i (x ) û

(4)

本文以黄金分割方法搜索得到最优步长K 0, 则

(5)

4　混合遗传算法

在实现遗传算法与经典算法混合通常有两种思路:其一, 将经典算法的优化过程作为遗传算法的一个遗传算子, 加快进化过程的收敛速度; 其二, 在应用遗传算法进行优化设计的基础上, 采用经典算法进行二次优化, 获得结果作为最优的设计结果。本文的研究侧重于将经典算法作为遗传算法的一个镶嵌型混合算子。

4. 1　镶嵌型混合算子-拟牛顿法和Powell 法

混合算子的设计思路是:对于完成交叉和变异操作的当前群体, 以一定概率选择其中的个体采用经典算法进行局部寻优, 以优化的结果作为个体的新染色体, 然后对改善后的群体进行评估与选择, 经典算法是作为遗传算法的一个强局部搜索算子参与整个进化过程。本文针对混合算子设计了一个自适应概率p n , p n 随着进化的增加而变大, 最后趋近于一个常数p 0:

p n (t ) =p 0e

-a (1-t /T )

[2]

5　算例及分析

为验证本文算法的有效性, 选择了大量的非线性方程组进行了算例测试, 为了方便对比分析, 下3(6)

・112・

计

[9]

2

算力学学报

表1　收敛可靠性对比

　第22卷　

　　问题1

x 2x 4x 6

f 1(x ) =x 1++0. 75

4f 2(x ) =x 2+0. 405e

1+x x

12

Tab. 1　Co ntrast of conv er gence reliability

Powell 法拟牛顿法

问题1问题2

52%64%38%

30%042%

混合遗传算法

Po well 混合算子

100%100%100%

100%100%100%

遗传

拟牛顿法混合算子算法

000

-1. 405

(7)

问题3

46

f 3(x ) =x 3-2+1. 5f 4(x ) =x 4-0. 605e f 5(x ) =x 5-21-x

3

-0. 395

Pow ell 的求解可靠性明显高于拟牛顿迭代法, 因此把非线性优化算法引入到非线性方程组求解中是有一定的优越性。遗传算法在所有的试验中均没有得到精确解, 作者的数值试验表明采用本文改进的遗传算法可以获得非线性方程组的近似解, 但是精度很难满足; 因此单独的遗传算法在求解类似非线性方程组这种高精度要求的问题中, 并没有优势。

º混合遗传算法对三个问题的求解可靠性均达到了100%, 明显高于单独的拟牛顿法、Pow ell

(8)

法和遗传算法, 这说明了在遗传算法中引入经典算法作为混合算子是提高遗传算法效率, 并有效地解决问题的一个较好方法。

»作者的数值试验表明, 对于性态特别差的非线性方程组, Pow ell 混合遗传算法的性能高于拟牛顿法混合遗传算法。对于一般性的问题, 两者的收敛可靠性相当, 但是后者的效率和求解精度是

3

x 2x 6

+1. 52

f 6(x ) =x 6-x 1x 5

文献[9]给出的解为(-1, 1, -1, 1, -1, 1) 。

　　问题2

该非线性方程组的维数为10, 其中

f 1(x ) =(3-5x 1) x 1+1-2x 2

f i (x ) =(3-5x i ) x i +1-x i -1-2x i +1

(i =2, …, 9)

f 10(x ) =(3-5x 10) x 10+1-x 9

该方程组为一个稀疏非线性方程组, 牛顿系列迭代法的求解效果很差。文献[9]并未给出该方程组的解, 作者的数值试验表明该方程组有不少于10组解。

问题3　求解薄壁矩形梁截面几何尺寸[4]A =bh -(b -2t ) (h -2t ) I y =bh /12-(b -2t ) (h -2t ) /12I n =2(h -t ) (b -t ) t /(h +b -2t ) 其中b 为矩形梁截面的宽度, h 为高度, t 为厚度。当A =165, I y =9369, I n =6835时, 文献[4]给出的解为x 0=(h *=22. 8949, b *=12. 5655, t *=2. 7898) T , 实际上不考虑物理意义约束, 该方程组有多解。

5. 1　算法收敛可靠性分析对比

本文在进行算法测试时, 问题1和2的所有变量区间选择为[-5, 5], 问题3的选择为[0, 50]。遗传算法的群体规模取为80, 进化总代数取为80, p c =0. 92, p m =0. 05。本文选择了Pow ell 法、拟牛顿法、遗传算法、Pow ell 算子混合遗传算法和拟牛顿法算子混合遗传算法对每个问题各随机作了100次实验。表1给出5种不同的算法在求解三个问题的100次试验中的成功概率。(认为E =m ax ûf i (x ) û

结果分析:

-6*

2

2

3[9]

T

(9) 明显地优于前者的。在实际应用中, 可以根据非线性方程组的性态选择不同的混合算子, 当然两种算子也可以同时交替使用。5. 2　计算成本分析

衡量非线性方程组求解算法的首要指标是算法收敛的可靠性, 同时计算成本也是一个需要考虑的指标, 本节对比分析了拟牛顿法和拟牛顿混合遗传算法的计算成本。由于拟牛顿法对问题2收敛概率为0, 拟顿法相对于混合算法已经没有可比较的前提。因此只是选择问题1和3作为分析计算成本的测试问题。表2给出了30次试验每种算法找到有效解的平均采样次数(拟牛顿法是在变量区间上随机选择初始点, 若不收敛则改变初始点, 采样次数累加) 。

表2　计算成本的对比

T ab. 2　Contrast of co mputatio nal costs

拟牛顿法

问题1368. 4拟牛顿混合遗传算法

403. 5

　第1期

罗亚中, 等:求解非线性方程组的混合遗传算法

・113・

　　从上面的数据看出, 对于问题1和3这类拟牛顿应用效果较好的非线性方程组, 本文设计的混合算法的计算成本同拟牛顿法基本相当, 混合算法具有较高的收敛速度。5. 3　其它几个问题的讨论

事实上, 上述三个算例均是有多个解, 本文的混合算法在进行数值求解时, 除了获得前面已提及的各个方程组的解外, 还获得了方程组的其它解。问题1的另一组解为(-1. 043201, -0. 550936, 0. 431936, 1. 759659, -2. 104875, 2. 195808) T , 问题2则有(0. 915551, -0. 222256, -0. 414654, -0. 440697, -0. 439254, 0. 420892, -0. 354588, -0. 135767, 0. 427562, 0. 752203) 等不少于10组解, 问题3还有x

T

*

*1

T

分发挥遗传算法的全局收敛性和群体搜索能力及经典算法的强局部收敛速度和精度高的特点, 其整体性能明显优于单一算法。数值计算表明, 混合算法具有很高的收敛可靠性以及较高的收敛速度和精度, 对于实际非线性方程组求解问题具有良好的适应性, 其设计策略对于解决实际问题有较好的借鉴意义。

参考文献(References ) :

[1]　黄象鼎, 曾钟钢, 马亚南. 非线性数值分析[M ]. 武

汉:武汉大学出版社, 2000. (HU A N G X iang -ding , Z ENG Zho ng -g ang , M A Ya' -nan . N onlinear N ume -r ical A naly sis [M ].

Wuhan :

Wuhan U niver sity

P r ess , 2000. (in Chinese ) )

[2]　周　明, 孙树栋. 遗传算法原理及应用[M ].北京:

国防工业出版社, 1999. (ZHO U M ing , SU N Shu-do ng.

Pr incip le of

Genetic A lgor ithms and its

A p p lication [M ]. Beijing :D efence Industry P ress, 1999. (in Chinese) )

[3]　杨　超, 洪冠新. 求解非线性方程组的一种建议方法

[J].飞行力学, 1997, 15(2) :573-576. (YA N G Cha o, HO N G Guan-x in. A reco mmendable metho d to solv e no nlinear alg ebraic [J ].F light Dy anmics , 1997, 15(2) :573-576. (in Chinese ) )

[4]　隋允康, 兆文忠. 非线性方程组的二次规划解法和应

用[J ]. 计算力学学报, 2002, 19(2) :245-246. (SU I Y un -kang , ZHA O W en -zhong . A quadrat ic pr o gr a -m ming met hod for so lving the NSE and its applica-t ion[J].Chinese J our nal of Comp utational M echa -nics , 2002, 19(2) :245-246. (in Chinese) )

[5]　胡小兵, 吴树范, 江　驹. 一种基于遗传算法的求解代

数方程组数值解的新方法[J ].控制理论与应用, 2002, 19(4) :573-576. (HU Xiao-bing , W U Shu-fan, JIA N G Ju. N ew method based on genetic algo rithms f or r eso lv ing alg ebraic equatio ns[J]. Contr ol T heor y 576. (in Chinese ) ) and Ap p lication , 2002, 19(4) :573-[6]　陈子仪, 康立山, 胡　欣. 遗传算法在方程求根中的应

用[J ].武汉大学学报(自然科学版) , 1998, 44(5) :577-580. (CHEN Z i -y i , K A NG L i -sha n , HU Xin . A pplicat ion

o f

g enetic

algo rithms

fo r

so lv ing

equatio ns [J ]. J . W uhan U niv . (N atur al Science E dition ) , 1998, 44(5) :577-580. (in Chinese) ) [7]　HE Jun, X U Ji-yo u, YA O X in. Solving Equatio ns

by Hybr id Ev olutio nar y Computation T echniques [J ].I E EE T r ans on Ev olutionary Comp utation , 4=(23. 271482, 8. 943089,

*

**

*

*

12. 912774) , x 3=-x 1, x 2=(35. 756376, -2. 363740, 3. 015078) T , x 4=-x 2和x 5=-x 0等五组解, 只是不满足物理意义约束。获得非线性方程组所有解一直是非线性方程组算法研究领域中的一个较难解决的问题, 本文设计的混合算法由于采用了遗传算法的群体搜索, 在求解非线性方程组全部解方面具有天然的优势。混合遗传算法能以较高的概率获得非线性方程组的多解甚至是全部解, 当然要使得算法能以100%的概率找到所有解, 需要尝试引入遗传算法中多模态函数的优化机制, 相关的研究正在进行。

对于问题3这种有实际应用背景的非线性方程组求解问题, 单独的拟牛顿法是无法保证一定能获得有物理意义的解(对于薄壁矩形梁截面通常要求h >b >t >0) 。但是本文的基于优化和迭代相结合的混合策略则可以保证获得有实际意义的解。针对问题4引入三个不等式约束:h -b >0, b -t >0, t >0, 用罚函数处理三个等式约束和三个不等式约束, 采用本文提出的混合遗传算法可以保证100%地获得x 0。实际工程中的非线性方程组求解问题往往对迭代变量有约束, 单独的等式迭代无法保证能获得有意义的解, 本文的混合策略则可以很好地解决这一问题。

*

*

6　结　论

本文针对传统非线性方程组求解算法的初始点敏感问题, 综合考虑遗传算法和经典算法的优缺点, 设计了一类混合遗传算法用来求解非线性方程

・114・

计算力学学报

　第22卷　

[8]　Kar r C L , W eck , Bar ry , Fr eeman L M . Solut ions to

system s o f nonlinear

equatio ns

via

a

genetic

algo r ithm [J ]. Engineer ing A p p lications of A rtif icial I ntelligence , 1998, 11(3) :369-375.

[9]　So nia K rzyw o rzcka . Ex tension of the La nczos and

CG S methods to systems o f nonlinear equations [J ].J our nal of Comp utational and Ap p lied M athematics , 1996, 69(1) :181-190.

Hybrid Genetic Algorithm for solving systems of nonlinear equations

LUO Ya-zho ng , 　YU AN Duan-cai, 　T ANG Guo -jin

*

(Scho ol of Aer ospace and M at eria l Engineer ing , N ational U niv. of Defense T echnolog y, Chang sha 410073, China )

Abstract :Solving systems of nonlinear equations is perhaps the m ost difficult problem in all of numerical co mputatio n. For most numerical methods such as New ton's metho d for solving sy stems of no nlinear equations, their co nv erg ence and perfo rmance character istics can be hig hly sensitive to the initial guess of the so lution supplied to the methods . How ever , it is very difficult to select a g ood initial guess for most systems of nonlinear equations. Aiming at these pro blems, a Hy br id Genetic Algo rithm (HGA) w as put forw ard , w hich combined the advantag es of Genetic Alg orithm (GA) and classical alg orithm s. The HGA sufficiently exerted the advantag es of GA such as gr oup search and glo bal conver gence , can efficiently ov ercome the pro blem of hig h sensitivity to initial g uess; and it also had a hig h conver gence rate and solution precisio n just because it used those hig h local-converg ence classical algorithms (Pow ell, Quasi-New ton M ethod ) for local search. Converg ence r eliability , computational cost and applicability of different alg orithms w ere compared by testing sev eral classical equatio ns o f no nlinear equations. T he numerical computations show that hy brid approach for solving systems of no nlinear equations has reliable conv erg ence pro bability , high co nv erg ence r ate and solutio n precisio n , and is a successful appro ach in solving system s of no nlinear equations .

Key words :sy stem s of no nlinear equations; Hybrid Genetic Algorithm (HGA ) ; optimization and

iteration ; nesting hybrid ; quasi -new ton iter ations