張志敏

(陽(yáng)光學(xué)院基礎(chǔ)教研部，福建福州350015)

基于GBFA求解復(fù)微分方程①

張志敏

(陽(yáng)光學(xué)院基礎(chǔ)教研部，福建福州350015)

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

細(xì)菌覓食算法，全局搜索，半解析法，解析表達(dá)式

0 引言

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

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

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

1 問(wèn)題描述

有一復(fù)微分方程

f(h(x))=0.

(1)

可以將式(1)轉(zhuǎn)化為

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

(2)

區(qū)間范圍下，公式(2)的最小值點(diǎn)為公式(1)的解，若g(x)的極小值是零，則相應(yīng)函數(shù)h(x)就是式(1)的根的解析表達(dá)式.

2 算法簡(jiǎn)介

2.1GBFA算法的基本思想

BFA中第i次的步長(zhǎng)為

(3)

其中，BFA虛擬的細(xì)菌群落內(nèi)細(xì)菌游動(dòng)次數(shù)的最大值是Ns，細(xì)菌游動(dòng)的初始步長(zhǎng)是Led，初始步長(zhǎng)均各次移動(dòng)步長(zhǎng)要大.運(yùn)算初期的i值相對(duì)不大，而第i次步長(zhǎng)Ci較大，能夠使搜索速度大大提升，改善了運(yùn)算效率.在運(yùn)算不斷推進(jìn)的過(guò)程中，i值會(huì)不斷變大，第i次步長(zhǎng)Ci出現(xiàn)不斷減小趨勢(shì)，這樣就能夠使后期運(yùn)算過(guò)程中收斂精度提升.

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

(4)

結(jié)合上述公式，原細(xì)菌群落即為群落細(xì)菌的m，這樣能夠使群落的覓食能力得到顯著增強(qiáng).細(xì)菌菌落的變異及繁殖過(guò)程為：(1)以高適應(yīng)度為標(biāo)準(zhǔn)，對(duì)細(xì)菌群落內(nèi)的細(xì)菌進(jìn)行挑選，挑選出的細(xì)菌標(biāo)成克隆群體A；(2)繁殖克隆群體A，使其形成群體B.

(5)

其中，細(xì)菌群落的總數(shù)量表示成S，四舍五入函數(shù)表示成Round；運(yùn)算所得的克隆群體數(shù)目為A(i)；第i次運(yùn)算表示成i，克隆系數(shù)是a.通過(guò)下述方式來(lái)標(biāo)準(zhǔn)化處理適應(yīng)度F，能夠使運(yùn)算更加簡(jiǎn)便化.

(6)

公式中最大值函數(shù)是max.

(3)變異處理細(xì)菌群體B，生產(chǎn)群體C：

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

(7)

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

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

(8)

參考上述公式能夠得知：細(xì)菌個(gè)體適應(yīng)度如果較高，則變異概率越大，二者成正比關(guān)系.交叉法的公式為

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

(9)

式(9)中，克隆群體內(nèi)細(xì)菌的四大類(lèi)型為x1、x2、x3和x4.在細(xì)菌群體內(nèi)融入克隆群體，可以構(gòu)建出新細(xì)菌群體

D=B+C.

(10)

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

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

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

圖1 GBFA算法的流程示意圖

2.2 GBFA算法的斂散性

在BFA算法的斂散性方面，DASGUPTA開(kāi)展了深入的分析[11,12]，然而并未研究BFA算法下細(xì)菌群落中的個(gè)體間也會(huì)彼此影響，未對(duì)影響關(guān)系進(jìn)行模擬.本文中的GBFA算法基于原算法的概念，融入了免疫算法，因此還應(yīng)對(duì)GBFA算法的斂散性進(jìn)行驗(yàn)證.

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

(11)

化簡(jiǎn)得到

(12)

因此1是GBFA算法收斂到最優(yōu)解集的概率.若算法迭代數(shù)量符合特定標(biāo)準(zhǔn)，算法就會(huì)收斂.

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

(13)

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

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)

因?yàn)?/p>

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)

又因?yàn)?/p>

(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)

因?yàn)?/p>

(22)

0≤P0(0)≤1，

(23)

所以

(24)

所以

(25)

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

3 半解析解的思想

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

4 計(jì)算仿真

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

4.1 二階及高階復(fù)微分方程

算例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)

通過(guò)算例1、算例2和算例3可知，GenerateBacterialForagingAlgorithm可以很好的求解出二階微分方程和高階微分方程的解析表達(dá)式，說(shuō)明GenerateBacterialForagingAlgorithm對(duì)于該類(lèi)問(wèn)題給予極好的適用性.

4.2 計(jì)算時(shí)間

算例4 利用三種方法分別計(jì)算算例3

利用文獻(xiàn)7中FAC算法、SPSO算法進(jìn)行計(jì)算，同GenerateBacterialForagingAlgorithm對(duì)局部根進(jìn)行搜索耗時(shí)開(kāi)展對(duì)照研究，具體如表1所示.

表1 本研究法、FAC法及SPSO法的對(duì)比結(jié)果

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

5 結(jié)論

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

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

[2] 陳子儀,康立山,胡欣.遺傳算法在方程求根中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)：理學(xué)版,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)化算法的改進(jìn)研究及在石油工程中的應(yīng)用[D].大慶：東北石油大學(xué),2012.

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

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

[8] 王俊奇, 李闖, 董曄.Bishop法的半解析解及其廣義數(shù)學(xué)模型[J]. 水利與建筑工程學(xué)報(bào), 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，F(xiàn)uzhou 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

福建省自然科學(xué)基金項(xiàng)目(2012J01256)資助

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

O241.3

A

1672-6634(2017)01-0033-05