基于GBFA求解復微分方程①

張志敏

(陽光學院基礎教研部，福建福州350015)

基于GBFA求解復微分方程①

張志敏

(陽光學院基礎教研部，福建福州350015)

為了提高傳統(tǒng)方法在求解二階以及高階復微分方程之時搜索能力差、后期收斂速度較慢以及難以得到的缺陷，基于傳統(tǒng)的免疫算法(generate and test)和BFA(Bacterial Foraging Algorithm，細菌覓食算法)的相關概念，融合半解析解的相關思想，構建一種新的算法GBFA(Generate Bacterial Foraging Algorithm)，并基于此方法進行求解實驗，結果表明該方法具有極高的收斂速度，可以得到二階以及高階復微分方程解析表達式.

細菌覓食算法，全局搜索，半解析法，解析表達式

0 引言

復微分方程是數學、工程實踐中廣泛存在的棘手問題.類型多樣化是傳統(tǒng)數值計算方法的一大特征，具體包括弦截法、單形調優(yōu)法、對分法及復形調優(yōu)法等[1,2].然而方程特點對上述數值計算方式造成了較大的干擾，在初值不同的情況下會使計算結果產生顯著的差異，因此傳統(tǒng)數值法不具有良好的通用性，且精確程度不高.所以廣大研究學者結合經驗，針對實際問題對計算法進行選取，但也存在主觀性較強的問題，所以不能在工程中普遍運用數值計算法.

二十世紀九十年代，K.M.Passino等提出了Bacterial Foraging Algorithm[3]，該算法在求解復微分方程之時，可以很好地探尋解復微分方程的根.Bacterial Foraging Algorithm作為實用性較強的數學工具，擁有較強的通用性，且迭代格式簡便，能夠普遍用于解決、處理(非)連續(xù)性問題，方便進行學習和應用[4,5].然而，Bacterial Foraging Algorithm需要運用較長的時間進行后期收斂，效果不夠理想，無法達到小范圍的收斂效果[6,7].李闖利用解析解的思想對于BFA進行了部分優(yōu)化，提高了BFA的收斂精度和尋優(yōu)速度，可以得到方程的解析表達式，但是李闖針對的是特定問題，沒有系統(tǒng)探討B(tài)FA，更沒有涉及BFA的搜索能力[8]；Tang W J[9]將繁殖算子的思想融合進入BFA，提高了BFA的尋優(yōu)能力，但是卻犧牲了精度和尋優(yōu)的速度.

現有的針對BFA的研究成果往往針對BFA的尋優(yōu)能力和搜索能力進行優(yōu)化，無法兼顧尋優(yōu)速度和收斂精度.本研究結合BFA算法的復制、趨向性及遷移這三個關鍵操作過程，融合免疫算法(generate and test)的相關思想，研究出全新的BFA優(yōu)化算法，即GBFA算法(Generate Bacterial Foraging Algorithm).在該算法中，首先能夠對趨向性操作過程下的步長進行非固定轉變，步長要根據運算而變化，并針對趨向性操作步長構建動態(tài)更新機制；其次，要對復制操作過程借助免疫算法進行更換，篩選細菌群落，將低適應度細菌更換成高適應度細菌，或對高適應度細菌進行復制；然后，高適應度個體在遷移操作過程被驅散率是零，剩余個體被驅散率是Ped.并利用C++開發(fā)計算程序，與傳統(tǒng)的計算方法相比較，驗證Generate Bacterial Foraging Algorithm的對于求解復微分方程的適應性.

1 問題描述

有一復微分方程

f(h(x))=0.

(1)

可以將式(1)轉化為

g(h(x))=f(h(x))2.

(2)

區(qū)間范圍下，公式(2)的最小值點為公式(1)的解，若g(x)的極小值是零，則相應函數h(x)就是式(1)的根的解析表達式.

2 算法簡介

2.1GBFA算法的基本思想

BFA中第i次的步長為

(3)

其中，BFA虛擬的細菌群落內細菌游動次數的最大值是Ns，細菌游動的初始步長是Led，初始步長均各次移動步長要大.運算初期的i值相對不大，而第i次步長Ci較大，能夠使搜索速度大大提升，改善了運算效率.在運算不斷推進的過程中，i值會不斷變大，第i次步長Ci出現不斷減小趨勢，這樣就能夠使后期運算過程中收斂精度提升.

借助構建的趨向性操作步長動態(tài)更新機制，可以累計加和群落內全部細菌的適應度，按照由大到小的次序建立細菌序列.復制前部分細菌序列的m(%)，復制次數為n，刪除序列內的其它細菌，則m、n能夠表示成

(4)

結合上述公式，原細菌群落即為群落細菌的m，這樣能夠使群落的覓食能力得到顯著增強.細菌菌落的變異及繁殖過程為：(1)以高適應度為標準，對細菌群落內的細菌進行挑選，挑選出的細菌標成克隆群體A；(2)繁殖克隆群體A，使其形成群體B.

(5)

其中，細菌群落的總數量表示成S，四舍五入函數表示成Round；運算所得的克隆群體數目為A(i)；第i次運算表示成i，克隆系數是a.通過下述方式來標準化處理適應度F，能夠使運算更加簡便化.

(6)

公式中最大值函數是max.

(3)變異處理細菌群體B，生產群體C：

B(i)=B(i)+βrandomn(C)，

(7)

其中，隨機函數表示成random，變異概率是β，運算所得的克隆群體數量是B(i).詳細運算方式如

β=e-F(n-i+1).

(8)

參考上述公式能夠得知：細菌個體適應度如果較高，則變異概率越大，二者成正比關系.交叉法的公式為

H=B(x1)-B(x2)+B(x3)-B(x4).

(9)

式(9)中，克隆群體內細菌的四大類型為x1、x2、x3和x4.在細菌群體內融入克隆群體，可以構建出新細菌群體

D=B+C.

(10)

(4)在細菌群體D中復制前m(%)的細菌群落，復制次數為n，剔除其它細菌.

基于BFA算法下，將遷移概率設置為Ped，若遷移概率Ped大于隨機數，則需要遷移細菌，從而有效擺脫陷入局部最優(yōu)解的狀況.然而該方式也存在缺陷，由于全部細菌均存在遷移概率，因此適應度不同的細菌均存在被遷移的可能性.在GBFA算法中的遷移操作過程，適應度最高細菌個體被驅散概率是零，剩余個體被驅散率是Ped，由此能夠加快搜索的速度，減小耗時.

參考上述理論，得出GBFA算法的流程，詳見圖1.

圖1 GBFA算法的流程示意圖

2.2 GBFA算法的斂散性

在BFA算法的斂散性方面，DASGUPTA開展了深入的分析[11,12]，然而并未研究BFA算法下細菌群落中的個體間也會彼此影響，未對影響關系進行模擬.本文中的GBFA算法基于原算法的概念，融入了免疫算法，因此還應對GBFA算法的斂散性進行驗證.

結合李濤的分析成果[13]：抗體種群為A0，抗體空間幾何表示成I*，經運算的最優(yōu)解數目是v(A(k))，最優(yōu)解個數是B*

(11)

化簡得到

(12)

因此1是GBFA算法收斂到最優(yōu)解集的概率.若算法迭代數量符合特定標準，算法就會收斂.

將免疫算法融合到GBFA算法中，針對細菌抗體種群A0則有

(13)

其中，k=1,2…,第k次操作時，細菌i的位置為Ai(k)，Ai(k-1)經過變異和克隆后能夠得到Ai(k).通常采用下述方式進行簡便表示

P0(k)=P{v(A(k))=0}=P{A(k)∩B*}，

(14)

則有

P0(k+1)=P{v(A(k+1))=0|v(A(k))≠0}P{v(A(k))≠0}，

+P{v(A(k+1))=0|v(A(k))=0}P{v(A(k))=0}，

(15)

因為

P{v(A(k+1))=0|v(A(k))≠0}=0，

(16)

則有

P0(k+1)=P{v(A(k|+1))=0|v(A(k))=0}P{v(A(k))=0}，

(17)

又因為

(18)

P{v(A(k+1))≥1|v(A(k))=0}≥?0，

(19)

所以

P{v(A(k+1))=0|v(A(k))=0}=1-P{v(A(k+1))≠1|v(A(k))=0}≤1-0，

(20)

故而

0≤P0(k+1)≤…≤(1-)k+1P0(0)，

(21)

因為

(22)

0≤P0(0)≤1，

(23)

所以

(24)

所以

(25)

綜上所述，GBFA以概率1收斂.

3 半解析解的思想

根據李闖[8]使用的半解析法的思想，將計算機計算解釋為計算機代數系統(tǒng).在計算機代數系統(tǒng)之中，每一個數值項以及變量都以字符的形式儲存，可以以字符串為基本運算單位.但其收斂與否應受到GBFA算法的影響.

4 計算仿真

利用上述思想，編制GenerateBacterialForagingAlgorithm的C++程序GOS，利用GOS進行計算.

4.1 二階及高階復微分方程

算例1 求解y″-6iy′=-i{6(1-3 ix)x+2 (19 i +6x) cosh[(6- ix)x]+4 (3 i +x)2 sinh[(6- ix)x]}.利用GOS，得到

y=-ix3+sin(x2+6ix).

(26)

算例2 求解y(5)+ iy′= 720 i -(16 807+7 i) e7x+720x-30x4+6 ix5,利用GOS，得到

y=x6-e7x+6ixs.

(27)

算例3 求解

+9ix(20(9x6-2)sin(x3)+3(9x6-80)x3cos(x3))540e(3x2+i)x2

+60ex3+ix(3x2+i)3x+ex(3x2+i)5+60ex3+ix(3x2+i)2

-3i(18x3sin(x3)+(9x6-2)cos(x3))+18ex3+ix(3x2+i)x

利用GOS，得到

(28)

通過算例1、算例2和算例3可知，GenerateBacterialForagingAlgorithm可以很好的求解出二階微分方程和高階微分方程的解析表達式，說明GenerateBacterialForagingAlgorithm對于該類問題給予極好的適用性.

4.2 計算時間

算例4 利用三種方法分別計算算例3

利用文獻7中FAC算法、SPSO算法進行計算，同GenerateBacterialForagingAlgorithm對局部根進行搜索耗時開展對照研究，具體如表1所示.

表1 本研究法、FAC法及SPSO法的對比結果

結合上表得知：GenerateBacterialForagingAlgorithm的耗時最大為55ms，FAC法、SPSO法耗時最大分別為398ms、452ms.GenerateBacterialForagingAlgorithm耗時僅為FAC法、SPSO法的13.8%、12.2%；GenerateBacterialForagingAlgorithm的平均耗時最大為29ms，FAC法、SPSO法耗時最大分別為224ms、275.6ms.GenerateBacterialForagingAlgorithm的平均耗時僅為FAC法、SPSO法的12.9%、10.5%；GenerateBacterialForagingAlgorithm和FAC法的運算成功率都是百分之百，而SPSO法的運算成功率為47%-75%，這就表示GenerateBacterialForagingAlgorithm是一種計算成功率高，耗時極短的計算方法.

5 結論

基于BFA算法的復制、趨向性及遷移三大操作環(huán)節(jié)，融合免疫算法(generateandtest)的相關思想，研究出全新的BFA優(yōu)化算法GBFA算法，該算法的優(yōu)點可總結如：(1)融合了半解析解思想，基于計算機代數系統(tǒng)的GBFA可以求解出二次微分方程以及高階微分方程的解的表達式；(2)相對于現有的計算方法，GBFA的計算耗時較短，但收斂效果遠遠高于其他兩種常用的傳統(tǒng)復微分方程求解方法.

[1]BianchiniM,FanelliS,GoriM.OptimalAlgorithmsforWell-ConditionedNonlinearSystemsofEquations[J].IEEETransactionsonComputers, 2001, 50(7):689-698.

[2] 陳子儀,康立山,胡欣.遺傳算法在方程求根中的應用[J].武漢大學學報：理學版,1998，44(5):577-580.

[3]LiuY,PassinoKM.BiomimicryofSocialForagingBacteriaforDistributedOptimization:Models,Principles,andEmergentBehaviors[J].JournalofOptimizationTheory&Applications, 2002, 115(3):603-628.

[4]EberhartR,KennedyJ.Anewoptimizerusingparticleswarmtheory[C].//MicroMachineandHumanScience1995.ProceedingsoftheSixthInternationalSymposiumonIEEE, 1995.

[5] 劉華鎣.粒子群優(yōu)化算法的改進研究及在石油工程中的應用[D].大慶：東北石油大學,2012.

[6] 田明俊,周晶.巖土工程參數反演的一種新方法[J].巖石力學與工程學報,2005,24(9):1 492-1 496.

[7]JingKE,QianJX,QiaoYZ.AModifiedParticleSwarmOptimizationAlgorithm[J].JournalofCircuits&Systems, 2003, 26(2):151-155.

[8] 王俊奇, 李闖, 董曄.Bishop法的半解析解及其廣義數學模型[J]. 水利與建筑工程學報, 2015(6):123-128.

[9]TangWJ,LiMS,HeS,etal.OptimalPowerFlowWithDynamicLoadsUsingBacterialForagingAlgorithm[C].//PowerSystemTechnology2006.InternationalConferenceon.IEEE, 2006.

Solving Complex Differential Equations Based GBFA

ZHANG Zhi-min

(Basic Teaching and Research Department, Sunshine College，Fuzhou 350015，China)

In order to enhance the traditional methods in solving when searching for second order and higher-order complex differential equations of the poor, the latter is difficult to obtain and slow convergence defects, based on traditional immune algorithm (generate and test) and BFA (Bacterial Foraging Algorithm, bacterial foraging algorithm) related concepts, integration of related thought semi-analytical solution to construct a new algorithm GBFA (Generate bacterial foraging algorithm), and solved by experiments based on this method, the results show that this method has a very high rate of convergence, you can be second order and higher-order complex differential equations analytical expressions.

bacterial foraging algorithm，global search，semi-analytical method，analytical expressions

2016-12-10

福建省自然科學基金項目(2012J01256)資助

張志敏，E-mail：crystal_100@sohu.com

O241.3

A

1672-6634(2017)01-0033-05