基于混合遺傳算法求非線性二階兩點(diǎn)邊值問題的數(shù)值解*

王 芳

(忻州師范學(xué)院 數(shù)學(xué)系，山西 忻州 034000)

基于混合遺傳算法求非線性二階兩點(diǎn)邊值問題的數(shù)值解*

王 芳

(忻州師范學(xué)院 數(shù)學(xué)系，山西 忻州 034000)

針對非線性二階兩點(diǎn)邊值問題，構(gòu)造了一種基于實(shí)數(shù)編碼的混合遺傳算法，將遺傳算法和Levenberg-Marquardt算法進(jìn)行了組合；由于前者全局優(yōu)化能力強(qiáng)，后者有較強(qiáng)的局部優(yōu)化能力，故改進(jìn)后的算法不僅具有全局優(yōu)化能力，計(jì)算的精度不會(huì)受到初始取值的影響，并且計(jì)算時(shí)間少，可以有效提高算法的收斂速度；最后，通過改進(jìn)后的算法計(jì)算非線性二階兩點(diǎn)邊值問題解析解和精確解的對比分析表明，該算法對非線性二階兩點(diǎn)邊值問題計(jì)算有較大的優(yōu)勢，是一種有效的求數(shù)值解方法。

實(shí)數(shù)編碼混合遺傳算法；二階邊值問題；數(shù)值解

在微分方程中，非線性二階兩點(diǎn)邊值問題是其研究領(lǐng)域重要和活躍的一個(gè)分支。許多學(xué)者研究了非線性微分方程邊值問題正解的存在性[1-4]，大多數(shù)文獻(xiàn)都僅證明了解的存在性，由于邊值問題的解析解的求解難度較大，對于如何求解并未提及?，F(xiàn)階段，求二階兩點(diǎn)邊值問題數(shù)值解的方法有：有限差分法、打靶法和遺傳算法[5]等。其中有限差分法一般僅適用于線性問題；打靶法主要思路是恰當(dāng)選擇和調(diào)整初值的條件，對一系列初值問題進(jìn)行求解，使其接近給定的邊界條件。因此，如何采用一種計(jì)算精度不受初始取值影響的全局尋優(yōu)算法對于求非線性二階兩點(diǎn)邊值問題是十分必要的。由此，本文構(gòu)造了一種具有全局優(yōu)化能力的混合遺傳算法，并利用算例檢驗(yàn)了模型和算法的有效性和穩(wěn)健性，為非線性二階兩點(diǎn)邊值問題數(shù)值解提供了新思路。

1 問題描述

二階兩點(diǎn)邊值問題表示為

(1)

將上述二階兩點(diǎn)邊值問題轉(zhuǎn)換為求最優(yōu)解的問題，分兩步進(jìn)行。

(2)

(3)

則方程(1)的離散格式為

(4)

定義內(nèi)部節(jié)點(diǎn)的殘差為

(5)

全體節(jié)點(diǎn)的殘差為

(6)

記y(xi)為二階兩點(diǎn)邊值問題的數(shù)值解，當(dāng)殘差R的值越小時(shí)，方程(1)的y(xi)就越好。因此，求二階邊值問題的數(shù)值解問題就轉(zhuǎn)換為求下面的優(yōu)化問題：

(7)

其中，f為優(yōu)化準(zhǔn)則函數(shù)；X為目標(biāo)函數(shù)的N維向量。

2 實(shí)數(shù)編碼混合遺傳算法設(shè)計(jì)

遺傳算法(Genetic Algorithm，GA)[6-13]是一種優(yōu)化算法，具有全局優(yōu)化能力，其搜索最優(yōu)解的原理是模仿自然界的選擇與遺傳機(jī)理。由于遺傳算法具有較差的局部搜索能力以及在進(jìn)化后期其搜索效率也比較低，基于此，將該算法做了改進(jìn)，即引入Levenberg-Marquardt優(yōu)化算法作為遺傳算法的一個(gè)算子，遺傳算法的收斂速率是通過Levenberg-Marquardt優(yōu)化算法具有較強(qiáng)的局部優(yōu)化能力來提高，組合之后，達(dá)到兩種算法所具有的全局優(yōu)化性能和高效局部優(yōu)化能力，以下為主要步驟。

2.1 編碼方案

x(i,j)=xmin(i)+y(i,j)(xmax(i)-

(8)

其中，xmax(i)，xmin(i)為參數(shù)x(i)的上下限，i為節(jié)點(diǎn)的值，j為群體中個(gè)體的序號(hào)。

2.2 初始化

均勻隨機(jī)數(shù)生成的個(gè)數(shù)是NPOP組，其定義在[0,1]區(qū)間。每個(gè)組有N個(gè){u(i,j)}，將各u(i,j)作為初始群體的父代個(gè)體值y(i,j)，把y(i,j)代入式(8)得x(i,j)，再通過式(7)得到相應(yīng)的目標(biāo)函數(shù)值f(j)。把{f(j)}(j=1,2,3,…,N)排序，對應(yīng)的個(gè)體{y(i,j)}也跟著排序。這時(shí)，確定出最好的個(gè)體{y(i,j)}。

2.3 適應(yīng)值的獲取

個(gè)體{y(i,j)}的適應(yīng)度值記作f(j)值。將f(j)值轉(zhuǎn)化為F(j)，F(xiàn)(j)表示父代個(gè)體的適應(yīng)度函數(shù)值。定義如下：

(9)

2.4 構(gòu)造選擇算子

采用比例選擇方式，進(jìn)行選擇操作產(chǎn)生第1代子個(gè)體{y1(i,j)}。

2.5 構(gòu)造交叉算子

雙親是隨機(jī)選擇父代個(gè)體y(i,j1)和y(i,j2)， 此時(shí)，進(jìn)行隨機(jī)線性組合，一個(gè)子代個(gè)體y2(i,j)產(chǎn)生:

(10)

其中，u1，u2，u3是[0,1]區(qū)間上的隨機(jī)數(shù)。通過這樣的雜交操作，共產(chǎn)生NPOP個(gè)子代個(gè)體。

2.6 構(gòu)造變異算子

采用文獻(xiàn)[9-12]的方法，NPOP個(gè)隨機(jī)數(shù)以pm(j)的概率來代替?zhèn)€體y(i,j)，從而得到第3代個(gè)體y3(i,j)， 即

(11)

其中，u(i)(i=1,2,3,…,p)、um均為[0,1]區(qū)間上隨機(jī)數(shù)。

2.7 構(gòu)造Levenberg-Marquardt算子

由上面的構(gòu)造可以得到3NPOP個(gè)子代個(gè)體，對父代群體中的每一個(gè)個(gè)體以概率ps(j)進(jìn)行局部收斂因子Levenberg-Marquardt算子操作，即對父代個(gè)體y(i,j)，隨機(jī)生成[0,1]中的隨機(jī)數(shù)pl，若pl(j)

反之，若pl(j)≥ps(j)，以y(i,j)為參數(shù)的初始取值，直接采用Levenberg-Marquardt算法[9-12]進(jìn)行優(yōu)化計(jì)算得到y(tǒng)*(i,j)(i=1,2,3,…,N)，并計(jì)算個(gè)體y*(i,j)適應(yīng)度函數(shù)值F*(j)，若F*(j)>F(j)則y4(i,j)=y*(i,j)，反之y4(i,j)=y(i,j)。

2.8 終止準(zhǔn)則

以{y4(i,j)}看作新一代父代群體，算法重新對父代群體依前面的步驟進(jìn)行循環(huán)演化。若最好的個(gè)體的目標(biāo)函數(shù)值小于設(shè)定值或算法運(yùn)行達(dá)到預(yù)定循環(huán)次數(shù)時(shí)，則進(jìn)化結(jié)束。保存當(dāng)前群體中最好的個(gè)體或者其最好個(gè)體的平均值為結(jié)果。

3 實(shí)例分析

用文中構(gòu)造的算法求解非線性二階兩點(diǎn)邊值問題:

(12)

表1 數(shù)值解、精確解以及誤差

4 結(jié) 論

由表1中的數(shù)值結(jié)果可知，本文構(gòu)造的新的混合遺傳算法對非線性二階兩點(diǎn)邊值問題進(jìn)行優(yōu)化求解是可行的。從計(jì)算結(jié)果看，該算法充分發(fā)揮了遺傳算法的全局優(yōu)化能力和Levenberg-Marquardt算法的局部優(yōu)化能力，因此，可廣泛應(yīng)用于各類非線性二階邊值問題，是一種較理想的計(jì)算方法。

[1] LIAN W C,WONG F H,YEH C C.On the Existence of Positive Solutions of Nonlinear Second Order Differential Equations[J].Journal of AMS,1996,124(6):1117-1126

[2] ERBE L H,H U S,WANG H.Multiple Positive Solutions of Some Boundary Value Problems[J].Journal of Mathe-matical Analysis & Applications,1994,184:640-648

[3] LIU Z,LI F.Multiple Positive Solutions of Nonlinear Two- point Boundary Value Problem[J].Journal of Mathematical Analysis & Applications,1996,203(5):610- 625

[4] LEES M.Diserete Methods for Two-point Boundary Value Problems,Numerical Solutions of Partial Differential Equations[J].New York:Academic Press,1966

[5] BASKAR S,SUBBARAJ P,RAO M V C.Hybrid Real Coded Genetic Algorithm Solution to Economic Dispatch Problem[J].Computers and Electrical Engineering,2003,29(3):407-419

[6] GOLDBERGD E.Genetic Algorithms in Search,Optimi-zation and Machine Learning[M].New York:Addison-Wesley,1989

[7] BACK T.Evolution Strategies:an Alternative Evolutionary Algorithm[C]∥Artificial Evolution:European Conference Selected Papers,Berlin,1995:1-20

[8] MARQUARDT D W.An Algorithm for the Solution of Certain Nonlinear Inequalities[J].Journal of Applied Math,1963(11):431-441

[9] 王芳,楊虎山.實(shí)數(shù)編碼混合遺傳算法在參數(shù)估計(jì)中的應(yīng)用[J].高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào),2013,35(4):375-383

WANG F,YANG H S.Application of Parameter Estimation Based on Real Coded Hybrid Genetic Algorithm[J].Numerical Mathematics a Journal of Chinese Universities,2013,35(4):375-383

[10] 郭向紅,孫西歡,馬娟娟.基于混合遺傳算法估計(jì)van Genuchten方程參數(shù)[J].水科學(xué)進(jìn)展,2009(5):677-681

GUO X H,SUN X H,MA J J.Parametric Estimation of the Van Genuchten’s Equation Based on Hybrid Genetic Algorithm[J].Advances in Water Science,2009(5):677-681

[11] 金菊良,楊曉華,丁晶.基于實(shí)數(shù)編碼的加速遺傳算法[J].四川大學(xué)學(xué)報(bào),2000(4):20-24

JIN J L,YANG X H,DING J.Real Coding Based Acceleration Genetic Algorithm[J].Journal of Sichuan University (Engineering Science Edition),2000(4):20-24

[12] 王芳,楊虎山.基于LM算法和遺傳算法求解非線性方程組[J].忻州師范學(xué)院學(xué)報(bào)(自然科學(xué)版),2016(5)：19-21

WANG F,YANG H S.Based on the LM Algorithm and Genetic Algorithm for Solving Non-linear Equations[J].Xinzhou Teachers University (Natural Science Edition),2016(5)：19-21

[13] 王芳.一種混合遺傳算法的收斂性分析[J].九江學(xué)院學(xué)報(bào)(自然科學(xué)版),2016(3):84-85

WANG F.Convergence Analysis of a Hybrid Genetic Algorithm[J].Journal of Jiujiang University (Natural Science Edition),2016(3):84-85

責(zé)任編輯：羅姍姍

Numerical Solution to Nonlinear Second-order Two-point Boundary Value Problem Based on Hybrid Genetic Algorithm

WANG Fang

(Department of Mathematics,Xinzhou Normal College, Shanxi Xinzhou 034000, China)

According to nonlinear second-order two-point boundary problem, a hybrid genetic algorithm based on real coding is constructed by the combination of the genetic algorithm with Levenberg-Marquardt algorithm. Because the former has the advantages of global optimization ability while the latter has strong local optimization ability, therefore, the improved algorithm not only has global optimization ability but also the calculation accuracy can not be affected by initial values, can use less computing time, and can effectively improve the convergence speed of the algorithm. Finally, the comparison between analytical solution and exact solution to nonlinear second-order two-point boundary value problems by using the improved algorithm indicates that the improved algorithm has big advantages of nonlinear second-order two-point boundary value problems computation and is an effective method for numerical solution.

real coded hybrid genetic algorithm; second-order boundary value problem; numerical solution

10.16055/j.issn.1672-058X.2017.0003.002

2016-12-10；

2017-01-15. * 基金項(xiàng)目：忻州師范學(xué)院青年基金(QN201316).

王芳(1978-)，女，河南焦作人，講師，碩士，從事應(yīng)用數(shù)學(xué)研究.

O241.8

A

1672-058X(2017)03-0007-04