改進(jìn)人工蜂群算法求解非線性方程組

汪繼文，楊 丹，邱劍鋒，王心靈

非線性方程組的求解是一種基本而又重要的問題，很多實(shí)際問題如工程技術(shù)、經(jīng)濟(jì)學(xué)、信息安全以及動(dòng)力學(xué)等最后都可歸結(jié)為求解非線性方程組，因此研究非線性方程組的求解方法具有重要意義.傳統(tǒng)的數(shù)值方法如牛頓法，需要設(shè)置初始值，而且對初始值的設(shè)置很敏感.牛頓法還需用到目標(biāo)函數(shù)的導(dǎo)數(shù)信息，對于有些函數(shù)在某些特殊的點(diǎn)導(dǎo)數(shù)不存在或者很難求解的時(shí)候，牛頓法就受到限制.

2005年，D.Karaboga第一次比較系統(tǒng)地提出一種人工蜂群(artificial bee colony，簡稱ABC)算法［1］，并將其應(yīng)用到函數(shù)數(shù)值優(yōu)化的問題上.該算法主要基于蜜蜂群的特定智能行為來進(jìn)行優(yōu)化搜索，由于它簡單、控制參數(shù)少、魯棒性強(qiáng)，且不依賴于初始條件的設(shè)置和目標(biāo)函數(shù)的導(dǎo)數(shù)信息，故而吸引了大量學(xué)者對其進(jìn)行研究和改進(jìn)［2－8］.而非線性方程組可以轉(zhuǎn)化成函數(shù)優(yōu)化問題，這樣人工蜂群算法就可以被用來求解非線性方程組.

1 非線性方程組

設(shè)非線性方程組由n個(gè)方程組成，有n個(gè)未知變量，形式如下

其中:fi(x1，x2，…，xn)=Ai(i=1，2，…，n)為非線性方程，X=(x1，x2，…，xn)T為方程組的一個(gè)未知數(shù)向量，Ai(i=1，2，…，n)是常數(shù)項(xiàng).

特別地，當(dāng)n=1時(shí)，上述非線性方程組就是一個(gè)非線性方程.將非線性方程(組)轉(zhuǎn)換成ABC能解決的目標(biāo)函數(shù)的方式如下

易證 fi(x1，x2，…，xn)=Ai(i=1，2，…，n)的解即使公式(2)達(dá)到最小值的解.

2 標(biāo)準(zhǔn)人工蜂群算法簡述

標(biāo)準(zhǔn)的ABC算法主要是模擬蜜蜂采蜜的過程，3種蜜蜂根據(jù)各自分工進(jìn)行采蜜活動(dòng)，期間通過對蜜源信息的交流與共享最終達(dá)到找到最好的蜜源(最優(yōu)解)的目的.這3種蜜蜂分別是雇傭蜂、觀察蜂以及偵察蜂.3種蜜蜂通過彼此間的交流、協(xié)作和轉(zhuǎn)化來實(shí)現(xiàn)解的優(yōu)化.首先，雇傭蜂在其所依附的蜜源鄰域內(nèi)進(jìn)行局部搜索，一旦發(fā)現(xiàn)比當(dāng)前好的蜜源，就更新蜜源的位置.其次，觀察蜂根據(jù)雇傭蜂所提供蜜源的信息，按照某種選擇策略(論文用輪盤賭策略)依附到特定的蜜源，轉(zhuǎn)化成雇傭蜂，然后進(jìn)行和雇傭蜂相同的搜索方式更新其蜜源的位置.在此過程中，優(yōu)質(zhì)的蜜源就會吸引較多的觀察蜂.最后，如果一個(gè)蜜源在多次迭代中都未被更新，則該蜜源將被拋棄，依附于該蜜源的雇傭蜂成為偵察蜂，繼續(xù)隨機(jī)在整個(gè)解空間內(nèi)尋找一個(gè)新的可行解作為蜜源位置，開始新的搜索.這里的偵察蜂的行為相當(dāng)于全局搜索.

蜂群的這種智能行為可以總結(jié)為如下:

1)在初始階段，蜂群開始在整個(gè)空間內(nèi)隨機(jī)搜索，尋找蜜源.

2)找到一個(gè)蜜源后，這個(gè)蜜蜂便成為雇傭蜂，開始采蜜，并將該蜜源的信息(含蜜量的多少，距離蜂巢距離等信息)帶回到蜂巢.此后，它可以選擇繼續(xù)回到它發(fā)現(xiàn)的那個(gè)蜜源，或者通過跳搖擺舞的方式來與巢穴周圍的觀察蜂分享蜜源信息.當(dāng)所依附的蜜源已經(jīng)開采殆盡，它就成為一只偵察蜂，隨機(jī)搜索下一個(gè)新的蜜源.

3)在蜂巢周圍的觀察蜂根據(jù)雇傭蜂所攜帶的蜜源信息，根據(jù)蜜源含蜜量的多少，按概率選擇一個(gè)蜜源進(jìn)行進(jìn)一步開采.然后重復(fù)第2步，直到滿足結(jié)束條件.

將上述蜜蜂尋找最優(yōu)蜜源的過程所表現(xiàn)出來的智能行為加以抽象，即Karaboga提出的人工蜂群算法［1］.

3 改進(jìn)的人工蜂群算法

3.1 初始化

含有蜜源位置的蜂巢環(huán)境被視為搜索空間，算法在搜索空間內(nèi)隨機(jī)地產(chǎn)生蜜源位置來作為問題的可行解.初始化的蜜源的各分量在其取值范圍內(nèi)隨機(jī)產(chǎn)生

其中:i=1，…，SN，j=1，…，D.SN是蜜源的個(gè)數(shù)，D是問題的維數(shù).

在初始化后，最初的蜜源位置將經(jīng)過ABC算法反復(fù)迭代進(jìn)行改進(jìn).算法的終止條件是運(yùn)行次數(shù)達(dá)到最大循環(huán)次數(shù)(maximum cycle number，簡稱MCN).

3.2 雇傭蜂階段

因?yàn)橐粋€(gè)雇傭蜂唯一對應(yīng)一個(gè)蜜源，所以蜜源的個(gè)數(shù)就等于雇傭蜂的個(gè)數(shù).雇傭蜂找到當(dāng)前蜜源的一個(gè)鄰近蜜源，評估它的蜜量，然后根據(jù)記憶(已存儲的信息)決定要不要對當(dāng)前的蜜源作修正.在標(biāo)準(zhǔn)ABC算法中，鄰近的蜜源被定義為其中:j是一個(gè)［1，D］之間的隨機(jī)整數(shù);k，i∈ {1，2，…，SN}，且 k≠ i;φij是一個(gè)［－1，1］之間的隨機(jī)實(shí)數(shù).

如果由此公式產(chǎn)生的分量值超過了此分量的上下界，那么將它的值就設(shè)為邊界值.如xi＞xmaxi，那么xi=;如xi＜，那么xi=.

通過對標(biāo)準(zhǔn)ABC算法的研究，發(fā)現(xiàn)雇傭蜂的搜索方式(4)只是在第i個(gè)蜜源附近隨機(jī)選取一個(gè)蜜源k，而沒有利用現(xiàn)有的任何信息，這樣隨機(jī)到一個(gè)好的蜜源和不好的蜜源的概率是相等的，這很有可能導(dǎo)致算法的局部搜索能力較弱.因此改進(jìn)的算法借鑒差分進(jìn)化算法［9］中的改進(jìn)，將個(gè)體當(dāng)前最優(yōu)值引入到雇傭蜂的搜索方式中去，來提高算法的局部搜索能力.在改進(jìn)算法中，將個(gè)體當(dāng)前最優(yōu)值記為xbest，xbest表示每只蜜蜂記住的自己到目前為止發(fā)現(xiàn)的最好位置.另外，還引入一個(gè)隨機(jī)擾動(dòng)項(xiàng)，以防止算法陷入局部最優(yōu).這樣雇傭蜂的搜索方式(4)被改進(jìn)為

其中:φa和φb是［－1，1］之間的隨機(jī)數(shù)，vij是代替xij的新蜜源位置.

如果由此產(chǎn)生的分量值越界，和標(biāo)準(zhǔn)ABC的處理方法相同.等式(5)的第一部分表示蜜蜂的當(dāng)前所在的位置;第二部分表示該蜜蜂的歷史最好位置對當(dāng)前位置的影響，它指引當(dāng)前的搜索方向向歷史最優(yōu)靠攏，代表局部搜索能力;第三部分是一個(gè)隨機(jī)向量，由兩個(gè)隨機(jī)位置的差值所得，是對前面兩部分的值產(chǎn)生的擾動(dòng)，防止搜索陷入局部最優(yōu)，代表全局搜索能力.

在產(chǎn)生了vi之后，計(jì)算它的適應(yīng)度值.在標(biāo)準(zhǔn)ABC算法中用來計(jì)算適應(yīng)度值fiti的公式如下

其中:fi是目標(biāo)函數(shù)在vi這點(diǎn)所取得的函數(shù)值.

在改進(jìn)的人工蜂群算法中，直接用函數(shù)的值F(X)(即式(2)的值)來代替上述復(fù)雜的適應(yīng)度值計(jì)算方式，這樣可以減少算法的運(yùn)算時(shí)間，也更加容易理解.在xi和vi之間采取貪心算法，適應(yīng)度高的被選為下次迭代的初始值.如果此處xi被適應(yīng)度高的vi所代替，那么視為被改進(jìn)了一次.

3.3 觀察蜂階段

當(dāng)所有雇傭蜂完成搜索之后，它們將自己所依附的蜜源信息(蜜量和位置)共享給觀察蜂.觀察蜂分析所有雇傭蜂傳遞的信息，按照概率選擇策略選擇一個(gè)蜜源進(jìn)行依附，此概率pi與該蜜源的蜜量有關(guān)系，計(jì)算方式如下上式中fiti即式(6)中的適應(yīng)度值.標(biāo)準(zhǔn)ABC和改進(jìn)的ABC算法都使用的是輪盤賭策略.對于每個(gè)蜜源都產(chǎn)生一個(gè)［0，1］之間的隨機(jī)數(shù)，如果此蜜源在式(7)中計(jì)算的概率值pi大于其對應(yīng)的隨機(jī)數(shù)，那么觀察蜂就依附到此蜜源，對它進(jìn)行改進(jìn)，觀察蜂也就成了雇傭蜂，其過程與雇傭蜂改進(jìn)蜜源原理相同.

3.4 偵察蜂階段

在一次迭代結(jié)束時(shí)，所有的雇傭蜂和觀察蜂都完成了它們的搜索，這時(shí)算法將檢查是否有枯竭的蜜源需要被拋棄.ABC算法中有個(gè)參數(shù)“l(fā)imit”，如果一個(gè)蜜源被改進(jìn)的次數(shù)超過了這個(gè)預(yù)設(shè)的“l(fā)imit”值，就認(rèn)為這個(gè)蜜源已經(jīng)枯竭而要被拋棄，被拋棄的蜜源將被偵察蜂隨機(jī)找到的新蜜源所代替，具體由公式(3)實(shí)現(xiàn).在ABC算法中，假設(shè)每次迭代有且僅有一個(gè)蜜源被拋棄.也僅有一只雇傭蜂可以轉(zhuǎn)化成偵察蜂.如果有多個(gè)蜜源被改進(jìn)的次數(shù)都超過了“l(fā)imit”值，那么拋棄其中被改進(jìn)次數(shù)最多的蜜源.

綜上，改進(jìn)人工蜂群算法的流程如圖1所示.

圖1 改進(jìn)ABC算法流程圖Fig.1 Flow chart of the improved ABC algorithm

4 實(shí)驗(yàn)及討論

4.1 基本函數(shù)測試

為了測試改進(jìn)算法的性能，先將其應(yīng)用到一組基本函數(shù)中去，選用的基本函數(shù)來自文獻(xiàn)［7］，如表1所示.這組函數(shù)包含2種類型，一類是單峰函數(shù)sphere和rosenbrock，另一組是多峰函數(shù)griewank，weierstrass以及schwefel.將改進(jìn)算法與PSO(particle swarm optimization)算法、標(biāo)準(zhǔn)ABC算法、文獻(xiàn)［7］中的IABC算法作比較.

表1 基本函數(shù)列表Tab.1 Basic function list

實(shí)驗(yàn)參數(shù)設(shè)置如下:種群大小設(shè)為10，最大循環(huán)次數(shù)設(shè)為3 000，運(yùn)行次數(shù)為30次，limit設(shè)為200，然后函數(shù)的維數(shù)D都定為10.這樣得到的實(shí)驗(yàn)結(jié)果見表2，其中IABC是取文獻(xiàn)［7］中最好結(jié)果.Mean指30次單獨(dú)運(yùn)行結(jié)果的平均值，Std表示標(biāo)準(zhǔn)差.

表2 基本函數(shù)測試結(jié)果Tab.2 Test results of the basic functions

對于作比較的各智能算法，將結(jié)果最接近函數(shù)最優(yōu)值的加粗表示.由表2可知，ABC/current－tobest算法對于5個(gè)基本函數(shù)計(jì)算的結(jié)果都優(yōu)于其他3種智能算法，尤其對于第4和第5個(gè)函數(shù)，改進(jìn)算法更是達(dá)到了最優(yōu)值，且前3個(gè)函數(shù)的精度也都有不同程度的提高.由此可見，引入了個(gè)體當(dāng)前最優(yōu)值和隨機(jī)向量的改進(jìn)算法，在加速單峰函數(shù)收斂速度、避免多峰函數(shù)陷入局部最優(yōu)方面起到了作用.

4.2 具體應(yīng)用求解

有了上面對于基本函數(shù)的測試結(jié)果，期待改進(jìn)算法解決實(shí)際問題的能力.接下來的第2部分實(shí)驗(yàn)，將其應(yīng)用到解非線性方程組中去.參考一些用群智能算法及別的改進(jìn)人工蜂群算法解非線性方程組的文獻(xiàn)［10－13］，將文獻(xiàn)［12］中的6個(gè)例子和文獻(xiàn)［13］中的3個(gè)例子作為實(shí)驗(yàn)用例，具體如下:

例1 f(x)=x3－2x－5=0，x∈［－4，4］.

例2 f(x)=x exp(x)－ 1=0，x∈［0，4］.

例3 f(x)=x3－3x2－6x+8=0，x∈［0，2］.

其中:－ 1 ≤ x1，x2，x3≤1 ，理論解為 x*=(0，0，0).

其中:－ 2≤ x1，x2≤2，理論解為 x*=(0.290 9，0).

其中:－ 1.732 ≤ x1，x2，x3≤1.732 ，理論解為 x*=(1，1，1).

其中:－ 100≤ x1，x2≤100，理論解為x*=(10，1)和x*=(－7.5，1).

其中:－ 5≤ x1，x2，…，x6≤5，理論解為 x*=(－1，1，－1，1，－1，1).

其中:－2≤x1≤5，－1≤x2≤4，－1≤x3≤2，理論解為x*=(4，3，1).

文獻(xiàn)［12］表明標(biāo)準(zhǔn)ABC算法比其他群智能優(yōu)化算法在解非線性方程組問題上有明顯優(yōu)勢，而第1部分實(shí)驗(yàn)也表明ABC/current－to－best算法比其他改進(jìn)的ABC算法在解決基本函數(shù)的問題上要優(yōu)越.所以在這第2部分實(shí)驗(yàn)中，前6例將ABC/current－to－best算法與標(biāo)準(zhǔn)ABC算法做比較，后3例與標(biāo)準(zhǔn)ABC以及文獻(xiàn)［13］中改進(jìn)的ABC算法(記為MABC)比較.

為了和文獻(xiàn)［12］中的標(biāo)準(zhǔn)ABC結(jié)果作比較，所以將實(shí)驗(yàn)設(shè)置與它相同.例1至例3的實(shí)驗(yàn)設(shè)置如下:種群大小設(shè)為30，limit為30，相應(yīng)的最大的循環(huán)次數(shù)即iter_MAX為100，每個(gè)方程算法隨機(jī)運(yùn)行30次求其平均值.例4至例6的設(shè)置如下:種群大小設(shè)為50，limit=30，相應(yīng)的最大的循環(huán)次數(shù)為2 000，每個(gè)方程組算法隨機(jī)運(yùn)行50次求其平均值.為了和文獻(xiàn)［13］中的MABC作比較，將最后3例的實(shí)驗(yàn)設(shè)置與它相同:種群大小為50，limit=100，最大循環(huán)次數(shù)為2 500次，各運(yùn)行30次求其平均值.這樣得到前6例的實(shí)驗(yàn)結(jié)果如表3所示.最后3例的實(shí)驗(yàn)結(jié)果如表4所示.

表4 3種算法的結(jié)果對比Tab.4 Inter-comparisonoftheresultsfromthreeofthealgorithms

文獻(xiàn)［12］中前3例并沒有給出x的精確解，但知道目標(biāo)函數(shù)的理論值是0，故在這里添加了一列F(X)(運(yùn)行30次的目標(biāo)函數(shù))的平均值來衡量哪個(gè)算法得到的解更精確.從表3可以看出這3例改進(jìn)算法比標(biāo)準(zhǔn)ABC算法得到的解要更精確.其中例2和例3目標(biāo)函數(shù)的平均值為0，可知用ABC/current－to－best算法得出的x的平均值是準(zhǔn)確解.

文獻(xiàn)［12］中后3例的x和F(X)的理論值都是知道的，所以將F(X)的平均值與理論值比較，便能看出哪個(gè)算法的精確度較高.從表3可以看出，例4用ABC/current－to－best算法求出的是準(zhǔn)確解.例5用 ABC/current－to－best得到的解和標(biāo)準(zhǔn)的 ABC算法在一個(gè)數(shù)量級上，兩者持平.例6用ABC/current－to－best得到的解比標(biāo)準(zhǔn)ABC算法的精度要高.由此可知，對于非線性方程組的求解，論文的改進(jìn)算法相對標(biāo)準(zhǔn)ABC算法有明顯優(yōu)勢.

文獻(xiàn)［13］中的3例情況稍為復(fù)雜，故單獨(dú)列表4說明.對于例7，方程組的解有兩組，分別是(10，1)和(－7.5，1)，論文的改進(jìn)算法運(yùn)行30次過程中，有13次收斂到第一個(gè)解，目標(biāo)函數(shù)的平均值在10－31，有17次收斂到第2個(gè)解，目標(biāo)函數(shù)的平均值為0，即是理論值.這樣的結(jié)果比ABC和文獻(xiàn)［13］中的改進(jìn)算法MABC要好很多.對于例8，論文的改進(jìn)算法在3種算法中也是最好的.對于例9，論文改進(jìn)算法略遜于MABC，但比標(biāo)準(zhǔn)ABC的結(jié)果要好.由此可見，論文的改進(jìn)算法相對于其他ABC改進(jìn)算法在解非線性方程組的問題上，也是絕大部分占優(yōu)勢.

5 結(jié)束語

基于差分進(jìn)化搜索策略，提出了一種用于求解非線性方程組的改進(jìn)人工蜂群算法.它保持了標(biāo)準(zhǔn)ABC算法的特點(diǎn)，將個(gè)體當(dāng)前最優(yōu)值和隨機(jī)向量引入ABC算法的雇傭蜂階段，一方面提高了算法的局部搜索能力，加快收斂速度;另一方面通過隨機(jī)向量的引入，防止多峰問題陷入局部最優(yōu).從兩部分的實(shí)驗(yàn)結(jié)果可以看出，論文提出的算法計(jì)算更簡單、精度更高、收斂速度更快，是對標(biāo)準(zhǔn)ABC算法性能改進(jìn)的一次有益嘗試.

［1］ Karaboga D.An idea based on honey bee swarm for numerical optimization［R］.Turkey:Erciyes University，2005:1－10.

［2］ Kashan M H，Nahavandi N，Kashan A H.DisABC:A new artificial bee colony algorithm for binary optimization［J］.Applied Soft Computing，2012，12(1):342 －352.

［3］ Akbari R，Hedayatzadeh R，Ziarati K，et al.A multi－ objective artificial bee colony algorithm［J］.Swarm and Evolutionary Computation，2012(2):39 －52.

［4］ Zhu G，Kwong S.Gbest-guided artificial bee colony algorithm for numerical function optimization［J］.Applied Mathematics and Computation，2010，217(7):3166 －3173.

［5］ Banharnsakun A，Achalakul T，Sirinaovakul B.The best－so－far selection in artificial bee colony algorithm［J］.Applied Soft Computing，2011，11(2):2888 －2901.

［6］ Gao W，Liu S.Improved artificial bee colony algorithm for global optimization［J］.Information Processing Letters，2011，111(17):871 －882.

［7］ Akay B，Karaboga D.A modified artificial bee colony algorithm for real－ parameter optimization［J］.Information Sciences，2012，192:120 －142.

［8］ Gao W，Liu S，Huang L.A global best artificial bee colony algorithm for global optimization［J］.Journal of Computational and Applied Mathematics，2012，236(11):2741 －2753.

［9］ Storn R，Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces［J］.Journal of global optimization，2010，23:689 －694.

［10］ 張建科，王曉智，劉三陽，等.求解非線性方程及方程組的粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，42(7):56－58.

［11］ 歐陽艾嘉，劉利斌，樂光學(xué)，等.求解非線性方程組的混合粒子群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(9):33－36.

［12］ 張姣玲.求解非線性方程及方程組的人工蜂群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48(22):45－47.

［13］ 劉佳，周真真，夏少芳，等.基于人工蜂群算法的非線性方程組求解研究［J］.自動(dòng)化儀表，2013，34(2):19－22.