解非線性方程組的多目標(biāo)優(yōu)化進(jìn)化算法

劉素紅，劉淳安

寶雞文理學(xué)院 數(shù)學(xué)系，陜西 寶雞 721013

解非線性方程組的多目標(biāo)優(yōu)化進(jìn)化算法

劉素紅，劉淳安

寶雞文理學(xué)院 數(shù)學(xué)系，陜西 寶雞 721013

1 引言

在工程設(shè)計(jì)、計(jì)算機(jī)應(yīng)用、電子信息及自動(dòng)化等領(lǐng)域的許多復(fù)雜問(wèn)題最終可歸結(jié)為求解形如：

近些年來(lái)，借鑒達(dá)爾文“物競(jìng)天擇”理論誕生的進(jìn)化計(jì)算是一種隨機(jī)搜索算法[9]，其與傳統(tǒng)的優(yōu)化方法不同，該算法在優(yōu)化過(guò)程中不需要計(jì)算問(wèn)題的目標(biāo)或代價(jià)函數(shù)的梯度，而是通過(guò)問(wèn)題的適應(yīng)度函數(shù)，對(duì)搜索到的可行解進(jìn)行信息交換，最終獲得問(wèn)題的全局最優(yōu)解。因此，它已被廣泛地應(yīng)用于眾多優(yōu)化領(lǐng)域。

事實(shí)上，目前我國(guó)許多學(xué)者提出了求解非線性方程組的智能進(jìn)化算法，比如文獻(xiàn)[10]將粒子群優(yōu)化算法和擬牛頓法相結(jié)合給出了求解非線性方程組的混合粒子群算法；文獻(xiàn)[11]給出了求解方程組的差分進(jìn)化算法；文獻(xiàn)[12]成功地將改進(jìn)的遺傳算法用于求解非線性方程組；文獻(xiàn)[13]提出了一種基于Memetic算法的非線性方程組求解算法。本文基于非線性方程組求解的機(jī)理及多目標(biāo)優(yōu)化的思想，將復(fù)雜非線性方程組轉(zhuǎn)化成了多目標(biāo)優(yōu)化問(wèn)題，進(jìn)而設(shè)計(jì)了求解的進(jìn)化算法，最后通過(guò)計(jì)算機(jī)仿真對(duì)算法的有效性進(jìn)行了驗(yàn)證。

2 非線性方程組的轉(zhuǎn)化

一般地，多目標(biāo)優(yōu)化問(wèn)題可用下面數(shù)學(xué)式子描述：

其中，x∈(x1，x2，…，xn)T∈?n，x所在的空間Ω稱為問(wèn)題的多目標(biāo)問(wèn)題的決策空間，fi(x)(i=1，2，…，m)稱為其子目標(biāo)函數(shù)，f(x)的像集所在的空間稱為問(wèn)題的目標(biāo)空間，gi(x)(i=1，2，…，p)為約束條件。

定義1[9]一個(gè)向量u=(u1，u2，…，un)T稱為非劣于（dominates）另一個(gè)向量v=(v1，v2，…，vn)T，當(dāng)且僅當(dāng)對(duì)于?i∈{1，2，…，n}，ui≤vi，且至少存在一個(gè)指標(biāo)i∈{1，2，…，n}，使得ui＜vi，記做：u?v。一個(gè)解x∈?n稱為多目標(biāo)優(yōu)化問(wèn)題式（2）的非劣解或Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在點(diǎn)y∈?n使得f(y)?f(x)。

定義2[9]多目標(biāo)優(yōu)化問(wèn)題的所有Pareto最優(yōu)解構(gòu)成其在決策空間?n上的Pareto最優(yōu)解集，所有Pareto最優(yōu)解通過(guò)目標(biāo)函數(shù)f(x)映射在目標(biāo)空間?m中的像構(gòu)成其Pareto前沿面。

定義3設(shè)第t代生成的種群pοp(t)由N個(gè)個(gè)體x1，x2，…，xn構(gòu)成，則稱pοp(t)中非劣于個(gè)體xi的所有個(gè)體的個(gè)數(shù)為xi的序值。

在上述多目標(biāo)優(yōu)化問(wèn)題的框架下，對(duì)于非線性方程組（1），將每個(gè)非線性方程中的函數(shù)取其絕對(duì)值后看做多目標(biāo)優(yōu)化的一個(gè)子目標(biāo)函數(shù)，則可將式（1）轉(zhuǎn)化為下列等價(jià)的簡(jiǎn)單約束多目標(biāo)優(yōu)化問(wèn)題：

定理1若解x*∈?n是非線性方程組（1）的解，則x*一定是問(wèn)題式（3）的Pareto最優(yōu)解；反之，若存在問(wèn)題式（3）的一個(gè)Pareto最優(yōu)解x*，且，則x*是方程組（1）的解。

證明充分性顯然。下證必要性：

若x*不是問(wèn)題式（3）的Pareto最優(yōu)解，則存在解使得，，且至少存在一個(gè)指標(biāo)i∈{1，2，…，n}，有又由于x*∈?n是非線性方程組（1）的解，則f(x*)=0，更有|fi(x*)|=0(i=1，2，…，n)，因此，對(duì)于上述存在的指標(biāo)i，有不等式成立，矛盾，因此，x*是問(wèn)題式（3）的Pareto最優(yōu)解。

3 多目標(biāo)優(yōu)化進(jìn)化算法

3.1 子空間Levy分布變異算子

為了使算法搜索范圍更加廣泛，產(chǎn)生的進(jìn)化種群更具多樣性，下面給出一種子空間Levy分布變異算子：

步驟1以變異概率從規(guī)模為N的第k代種群pοp(k)中隨機(jī)選取μ個(gè)父代個(gè)體xi(i=1，2，…，μ)。

步驟3對(duì)x*進(jìn)行Levy變異，產(chǎn)生其變異后代Θ，即

3.2 多目標(biāo)優(yōu)化算法流程

步驟2以雜交概率pc對(duì)pοp(t)中的個(gè)體進(jìn)行正交設(shè)計(jì)雜交[14]，產(chǎn)生雜交后代集Μ(t)。

步驟3（變異）對(duì)Μ(t)中的個(gè)體執(zhí)行子空間Levy分布變異操作，并與Μ(t)中沒(méi)有參與變異的個(gè)體組成變異后代集

步驟4（選擇）對(duì)中個(gè)體進(jìn)行非劣性的比較，用序值為1的所有個(gè)體替換存儲(chǔ)器Φ(t)中的個(gè)體。

4 數(shù)值模擬

4.1 實(shí)驗(yàn)函數(shù)

為了驗(yàn)證本文所給算法的有效性，文中對(duì)3個(gè)較為復(fù)雜的非線性方程組進(jìn)行仿真對(duì)比求解，并將本文算法所得結(jié)果與文獻(xiàn)中已有結(jié)果進(jìn)行了比較。比較結(jié)果見(jiàn)表1、表2，其中G1，G2取自文獻(xiàn)[15]，G3選自文獻(xiàn)[4]，且該函數(shù)沒(méi)有理論精確解。所用3個(gè)非線性方程組如下：

表1 MCEA算法與文獻(xiàn)中算法對(duì)G1和G2求得結(jié)果比較1）

表2 MCEA算法與文獻(xiàn)中算法對(duì)G3所得結(jié)果比較

4.2 結(jié)果分析

記本文算法為MCEA，在實(shí)驗(yàn)中，雜交概率pc=0.8，變異概率pm=0.1，作為對(duì)比，對(duì)上述3個(gè)測(cè)試函數(shù)，采用與文獻(xiàn)算法相同的參數(shù)，同時(shí)將MCEA所得結(jié)果與文獻(xiàn)中已有結(jié)果進(jìn)行了比較。其中，對(duì)于G1，群體規(guī)模N=250，外部存儲(chǔ)器容量為100，進(jìn)化代數(shù)K=150，對(duì)于G2，群體規(guī)模N=300，進(jìn)化代數(shù)K=200，外部存儲(chǔ)器容量均為100。對(duì)于G3，群體規(guī)模N=200，外部存儲(chǔ)器容量為50，進(jìn)化代數(shù)K=150。其中表1給出了算法對(duì)G1-G2的結(jié)果比較，表2給出了算法對(duì)G3的比較結(jié)果。

對(duì)于G3，由于該函數(shù)難以得出其理論上的精確解，只能求出近似解，本文采用所給算法MCEA給出了該函數(shù)的9個(gè)較好的近似解（反映在多目標(biāo)模型中對(duì)應(yīng)于目標(biāo)空間中9個(gè)Pareto最優(yōu)解）。其中表2給出了所得9個(gè)Pareto最優(yōu)解，圖1繪出了9個(gè)Pareto最優(yōu)解在目標(biāo)空間中的分布，圖2給出了9個(gè)Pareto最優(yōu)解對(duì)應(yīng)目標(biāo)函數(shù)值的絕對(duì)值之和的分布。從表2及圖2可以看出，本文算法MCEA所得解中除第4個(gè)和第9個(gè)外，其余解對(duì)應(yīng)目標(biāo)函數(shù)值的絕對(duì)值之和比文獻(xiàn)[4]中的結(jié)果要小，但從圖1可知，本文算法求得G2的Pareto最優(yōu)解比文獻(xiàn)中所得解的質(zhì)量（即所得解位于文獻(xiàn)中所得解的左下方）和分布寬廣性均好，這給決策者在帶有目標(biāo)函數(shù)權(quán)重時(shí)選擇非線性系統(tǒng)G3的最優(yōu)解給出了較大的自由度和良好的選擇理想解的空間。從以上分析可知，本文算法對(duì)非線性方程組的求解具有較強(qiáng)的能力。

5 結(jié)語(yǔ)

如何有效地求解非線性方程組是目前進(jìn)化計(jì)算領(lǐng)域研究的一個(gè)熱點(diǎn)問(wèn)題。文章將求解非線性方程組的問(wèn)題轉(zhuǎn)化為求解一個(gè)多目標(biāo)優(yōu)化問(wèn)題，最后設(shè)計(jì)了求解的進(jìn)化算法。實(shí)驗(yàn)數(shù)據(jù)對(duì)比表明，本文所給算法對(duì)非線性方程組的求解非常有效。

圖1 所得9個(gè)Pareto最優(yōu)解的前沿面

圖2 所得9個(gè)Pareto解對(duì)應(yīng)問(wèn)題目標(biāo)函數(shù)值的絕對(duì)值之和

[1]Nie P Y.A null space method for solving system of equations[J].Appl Math Computation，2004，149（1）：215-226.

[2]Nie P Y.An SQP approach with line search for a system of nonlinear equations[J].Math Comput Model，2006，43（3/4）：368-373.

[3]Grapsa T N，Vrahatis M N.New dimension-reducing method for solving systems of nonlinear equations[J].Int Jour Comput Math，1995，55（3/4）：235-244.

[4]Grosan C，Abraham A.A new approach for solving nonlinear equationssystems[J].IEEE Transactionson Systems，Man，and Cybernetics-Part A：Systems and Humans，2008，38（3）：698-714.

[5]Denis J E.On Newton’s method and nonlinear simultaneous replacements[J].SIAM J Numer Anal，1967，4：103-108.

[6]Grapsa T N，Vrahatis M N，Denis J E，et al.A trust-region algorithm for least-squaressolutionsof nonlinear systems of equalities and inequalities[J].SIAM J Opt，1999，9（2）：291-315.

[7]Broyden C G.A class of methods for solving nonlinear simultaneous equations[J].Math Comput，1965，19（92）：577-593.

[8]Denis J E，Wolkowicz H.Least change secant methods，sizing，and shifting[J].SIAM J Numer Anal，1993，30：1291-1314.

[9]Deb K.A fast and elitist multiobjective genetic algorithm：NSGA-II[J].IEEE Transactions on Evolutionary Computation，2002，6（2）：182-187.

[10]張安玲，劉雪英.求解非線性方程組的擬牛頓-粒子群混合算法[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（33）：41-42.

[11]封全喜，劉三陽(yáng)，唐國(guó)強(qiáng)，等.求解方程組的正交差分進(jìn)化算法[J].計(jì)算機(jī)科學(xué)，2012，39（5）：187-189.

[12]燕樂(lè)緯，陳樹輝.基于改進(jìn)遺傳算法的非線性方程組求解[J].中山大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，50（1）：9-13.

[13]屈愛(ài)平.一種基于Memetic算法的非線性方程組求解算法[J].山東理工大學(xué)學(xué)報(bào)，2010，24（4）：42-48.

[14]Leung Yiu-Wing，Wang Yuping.An orthogonal genetic algorithm with quantization for global numerical optimization[J]. IEEE Trans on Evolutionary Computation，2001，5（1）：41-53.

[15]Effati S，Nazemi A R.A new method for solving a system of the nonlinear equations[J].Appl Math Comput，2005，168（2）：877-894.

LIU Suhong,LIU Chun’an

Department of Mathematics,Baoji University of Arts and Sciences,Baoji,Shaanxi 721013,China

How to effectively solve complex nonlinear system of equations is a novel research problem in evolution field.Nonlinear system of equations is transformed into a multi-objective optimization problem and a new multi-objective optimization evolutionary algorithm is proposed.In order to enhance the search ability of the proposed algorithm and avoid the algorithm falls into the local optimum,the self-adaptive evolution operator and the uniform crossover operator are used.The computer simulations demonstrate the effectiveness of the proposed algorithm to solve nonlinear system of equations.

nonlinear system of equations;evolutionary computation;multi-objective optimization;optimal solutions

如何有效地求解復(fù)雜非線性方程組是進(jìn)化計(jì)算領(lǐng)域一個(gè)新的研究問(wèn)題。將非線性方程組等價(jià)地轉(zhuǎn)化成多目標(biāo)優(yōu)化問(wèn)題，同時(shí)設(shè)計(jì)了求解的多目標(biāo)優(yōu)化進(jìn)化算法。為了提高算法的搜索能力及避免算法陷入局部最優(yōu)，采用了自適應(yīng)Levy變異進(jìn)化算子和均勻雜交算子。計(jì)算機(jī)仿真表明該算法對(duì)非線性方程組的求解是有效的。

非線性方程組；進(jìn)化計(jì)算；多目標(biāo)優(yōu)化；最優(yōu)解

A

TP301.6；O224

10.3778/j.issn.1002-8331.1303-0042

LIU Suhong,LIU Chun’an.Multi-objective evolutionary algorithm for solving nonlinear system of equations.Computer Engineering and Applications,2013,49（18）：48-51.

陜西省教育廳科研計(jì)劃項(xiàng)目（No.11JK0506，No.12JK1003）；寶雞文理學(xué)院校級(jí)重點(diǎn)科研計(jì)劃項(xiàng)目（No.ZK12044，No.ZK12092）。

劉素紅（1970—），女，講師，主要研究方向?yàn)樽顑?yōu)化理論及其應(yīng)用；劉淳安（1972—），男，博士，教授，主要研究方向?yàn)槎嗄繕?biāo)優(yōu)化、進(jìn)化算法與人工智能。E-mail：bjwlxylsh@126.com

2013-03-04

2013-04-22

1002-8331（2013）18-0048-04

CNKI出版日期：2013-05-21 http://www.cnki.net/kcms/detail/11.2127.TP.20130521.1027.009.html

◎網(wǎng)絡(luò)、通信、安全◎