郭德龍，鄭添健，周永權(quán)

1.黔南民族師范學(xué)院數(shù)學(xué)系，貴州都勻 558000

2.廣西民族大學(xué)信息與工程學(xué)院，南寧 530006

◎理論研究、研發(fā)設(shè)計(jì)◎

混合快速細(xì)菌覓食算法求解非線性方程

郭德龍1，鄭添健1，周永權(quán)2

1.黔南民族師范學(xué)院數(shù)學(xué)系，貴州都勻 558000

2.廣西民族大學(xué)信息與工程學(xué)院，南寧 530006

對(duì)于非線性方程組的求解，傳統(tǒng)方法有很多，如牛頓法、梯度下降法等，但這些算法存在要求方程組連續(xù)可微、初值的選取是否合適等缺點(diǎn)，根據(jù)以上缺點(diǎn)將求解的問(wèn)題轉(zhuǎn)化為優(yōu)化的問(wèn)題，提出了新的交叉優(yōu)化算法，充分利用細(xì)菌覓食算法局部搜索能力和粒子群算法的全局搜索能力，充分發(fā)揮了這兩個(gè)算法各自優(yōu)點(diǎn)。數(shù)值實(shí)驗(yàn)表明，新的算法可以彌補(bǔ)粒子群算法局部搜索能力弱和細(xì)菌覓食算法的全局搜索能力的不足，是求解非線性方程的有效方法。

局部?jī)?yōu)化；交叉；非線性方程

1 引言

經(jīng)常遇到求解非線性方程組的問(wèn)題在科學(xué)計(jì)算和實(shí)際工程領(lǐng)域。求方程的數(shù)值解是一個(gè)非常重要的研究?jī)?nèi)容之一，尤其是對(duì)于求解非線性方程的數(shù)值解。傳統(tǒng)的算法有牛頓法、梯度下降法等[1-2]。但是這些算法的收斂速度以及解的精度是受初始值選取是否恰當(dāng)影響的，同時(shí)如何去選擇這個(gè)合適的初始點(diǎn)也是非常難?，F(xiàn)代的智能優(yōu)化算法如遺傳算法、進(jìn)化策略等雖在求解精度有了提高，但是也存在一個(gè)缺點(diǎn)那就是容易陷入局部最解?；谝陨线@些問(wèn)題，研究和探索性能更好的算法是必要的。2002年，K M Passino基于大腸桿菌吞噬食物在人體腸道內(nèi)一種行為，給出了一種新的群智能優(yōu)化算法，細(xì)菌覓食算法[3]（Bacterial Foraging Algorithm，BFA）。并且此算法具有很強(qiáng)的全局搜索能力同時(shí)還具有群智能優(yōu)化算法并行搜索能力?，F(xiàn)在已成為計(jì)算智能領(lǐng)域研究的新的熱點(diǎn)。模仿人體腸道內(nèi)的大腸桿菌覓食是細(xì)菌覓食算法的主要行為，在搜索優(yōu)化過(guò)程中搜索空間中的細(xì)菌的狀態(tài)對(duì)應(yīng)優(yōu)化問(wèn)題的解。

粒子群算法[4-5]是由Kennedy和Eberhart于1995年提出的一種基于群智能的隨機(jī)優(yōu)化算法。此算法模仿基點(diǎn)是群居的生物如鳥(niǎo)、魚(yú)、螞蟻等通過(guò)群聚來(lái)進(jìn)行覓食和逃避被捕殺。在這類群體的動(dòng)物整個(gè)群體中信息是共享的，而且每個(gè)個(gè)體的行為是建立在群體行為基礎(chǔ)之上的，同時(shí)個(gè)體之間也存在著信息的交換與協(xié)作。在PSO算法中，粒子群在一個(gè)高維的空間中搜索是粒子通過(guò)個(gè)體和群體的飛行經(jīng)歷來(lái)不斷調(diào)整自己的位置，同時(shí)每個(gè)粒子所處的位置都被看成解空間的一個(gè)。記做全局極值(xgbest)，第i個(gè)粒子所經(jīng)歷過(guò)的最好位置被記做個(gè)體極值(xpbest)。粒子根據(jù)下面的公式來(lái)更新自己的速度和位置：

其中r1，r2為[0，1]之間的隨機(jī)數(shù)，c1，c2為非學(xué)習(xí)因子，w為非負(fù)慣性權(quán)重。

本文根據(jù)細(xì)菌覓食算法和粒子群算法的優(yōu)點(diǎn)，給出了求解非線性方程的新算法。BFA模擬細(xì)菌群體行為，包括趨化、復(fù)制、驅(qū)散3個(gè)步驟。核心操作是趨化操作，一般包括翻轉(zhuǎn)和前進(jìn)兩個(gè)過(guò)程，但由于BFA采取的是任意方向的翻轉(zhuǎn)，收斂速度比較慢。而PSO中利用了個(gè)體極值和整體極值來(lái)更新位置的收斂速度快些。因此用PSO中的粒子移動(dòng)的方式代替細(xì)菌的趨化操作步驟，即在細(xì)菌趨化中采用上面的公式（1），（2）進(jìn)行細(xì)菌位置的更新。

2 問(wèn)題的描述

設(shè)非線性方程：

的全部實(shí)根包含在(c，d)中，x*為方程（3）的任一固定實(shí)根，在[a，b]內(nèi)只包含方程（3）的一個(gè)實(shí)根x*，[a，b]?[c，d]由優(yōu)化理論易證方程（3）在[a，b]中的根x*等價(jià)于函數(shù)：

在[a，b]中的極小點(diǎn)，當(dāng)H(x)最小值為0時(shí)，所對(duì)應(yīng)的x即為方程（3）的精確解，H(x)最小值越小方程的近似程度越好。

3 細(xì)菌覓食算法描述

BFA算法包括趨化（chemotaxis）、復(fù)制（reproduction）和驅(qū)散（elimination-dispersal）3個(gè)步驟。

（1）趨化是指細(xì)菌聚集到營(yíng)養(yǎng)豐富的區(qū)域。在這過(guò)程中運(yùn)動(dòng)方式包括前進(jìn)和翻轉(zhuǎn)。翻轉(zhuǎn)是指細(xì)菌向任何方向移動(dòng)單位步長(zhǎng)。前進(jìn)是指細(xì)菌完成一次翻轉(zhuǎn)后它的適應(yīng)度值得到改善，它將繼續(xù)沿同一方向移動(dòng)若干次直到適應(yīng)度值不再改變，或達(dá)到預(yù)定的移動(dòng)臨界值。

（2）細(xì)菌進(jìn)行繁殖。為簡(jiǎn)化計(jì)算法，可以規(guī)定復(fù)制繁殖的過(guò)程中細(xì)菌總數(shù)保持不變。以趨化過(guò)程中的每個(gè)細(xì)菌適應(yīng)度值相加和為標(biāo)準(zhǔn)。較好的半數(shù)細(xì)菌分裂成兩個(gè)子細(xì)菌，較差的半數(shù)細(xì)菌死亡。在這過(guò)程中遵循自然界“優(yōu)勝劣汰，適者生存原則”。同時(shí)子細(xì)菌將繼續(xù)繼承生物特性，具有和母細(xì)胞相同的位置及步長(zhǎng)。

（3）驅(qū)散過(guò)程指細(xì)菌在完成一定次數(shù)的復(fù)制后，將以一定概率被驅(qū)散到搜索空間中任意位置，也是加強(qiáng)算法全局尋優(yōu)能力。對(duì)于復(fù)雜問(wèn)題由復(fù)制和趨化無(wú)法避免陷入局部極小現(xiàn)象發(fā)生，但同時(shí)保留趨化過(guò)程可確保細(xì)菌局部搜索能力，復(fù)制過(guò)程能加快細(xì)菌的搜索速度。

4 混合算法求解非線性方程的設(shè)計(jì)

BFA算法中的核心是趨化操作為了更新細(xì)菌的位置，本文算法應(yīng)用PSO中的粒子移動(dòng)來(lái)更新細(xì)菌位置，而這充分利用了粒子群算法全局搜索能力強(qiáng)優(yōu)點(diǎn)。充分發(fā)揮PSO算法全局搜索能力強(qiáng)，收斂速度快的優(yōu)點(diǎn)，利用該算法的個(gè)體極值和全局極值來(lái)更新粒子位置。

混合算法的主要步驟如下：

步驟1給出細(xì)菌種群規(guī)模，遷移次數(shù)、復(fù)制次數(shù)、趨化次數(shù)和遷移概率進(jìn)行參數(shù)設(shè)置。

步驟2首先設(shè)定每一個(gè)細(xì)菌的局部極值的初始值和全局極值的初始值，同時(shí)給出粒子群算法的參數(shù)。

步驟3隨機(jī)生成初始化細(xì)菌群體。

步驟4計(jì)算細(xì)菌適應(yīng)度值并進(jìn)行評(píng)價(jià)。這里適應(yīng)度函數(shù)取為：

步驟5執(zhí)行細(xì)菌的三層循環(huán)操作

（1）內(nèi)層循環(huán)（趨化性操作）按以下公式（8）進(jìn)行細(xì)菌更新。包括更新個(gè)體最優(yōu)和全局最優(yōu)，并用公式（7）更新各細(xì)菌的速度。

其中w為非負(fù)慣性權(quán)重，c1，c2為非學(xué)習(xí)因子，r1，r2為[0，1]之間的隨機(jī)數(shù)。

表1 本文算法與參考文獻(xiàn)[5]對(duì)例1～例3的比較

表2 例4的數(shù)值結(jié)果

表3 本文算法與參考文獻(xiàn)[8]對(duì)例5的比較結(jié)果

（2）復(fù)制操作：對(duì)于經(jīng)過(guò)趨化性操作的細(xì)菌群體，并且對(duì)每個(gè)細(xì)菌的適應(yīng)度值的累加和進(jìn)行排序，淘汰掉適應(yīng)度值較差的一半細(xì)菌再?gòu)氖Ｏ碌囊话爰?xì)菌分裂出同樣的細(xì)菌，遺傳母細(xì)菌的位置和特性。

（3）遷移操作：通過(guò)上面的循環(huán)操作之后細(xì)菌可能走向局部極值。因此對(duì)于每一個(gè)細(xì)菌按照一定的遷移概率進(jìn)行遷移，為了保證算法的收斂，設(shè)定一定的遷移細(xì)菌數(shù)目（憑經(jīng)驗(yàn)值）。

步驟6輸出群體最優(yōu)解。

5 數(shù)值仿真實(shí)驗(yàn)

為了測(cè)試本文算法的性能，選取參考文獻(xiàn)[5-8]的非線性方程。

數(shù)值實(shí)驗(yàn)在Matlab2010a中完成，為了保證該混合算法的可比性，各相關(guān)算法取相同的參數(shù)，細(xì)菌種群規(guī)模S=50，遷移次數(shù)Ned=2，復(fù)制次數(shù)Nre=10，趨化次數(shù)Nc=10和遷移概率p=0.25，采用慣性權(quán)重ω=0.7的線性遞減策略，學(xué)習(xí)因子c1=c2=1.494，粒子數(shù)為50，r1，r2是[0，1]之間的隨機(jī)數(shù)。

從表1～3比較結(jié)果可以看到本文所提出的混合算法收斂速度較快、求解的精度比較高，并且還能求出非線性方程的全部解。

6 結(jié)束語(yǔ)

本文提出了一種混合快速細(xì)菌覓食算法，充分將細(xì)菌覓食算法和粒子群算法（PSO）收斂性優(yōu)點(diǎn)結(jié)合起來(lái)，應(yīng)用在求解非線性方程數(shù)值解中。從數(shù)值計(jì)算結(jié)果可以看到本文設(shè)計(jì)該算法不僅有良好的穩(wěn)定性而且有很高運(yùn)算速度和精度，是一種可行而有效的優(yōu)化算法，從而也為該算法在其他方面應(yīng)用提供了一種新途徑。

[1]李慶揚(yáng)，莫孜中，祁力群.非線性方程組的數(shù)值方法[M].北京：科學(xué)技術(shù)出版社，1987.

[2]李慶揚(yáng)，王能超，易大義.數(shù)值分析[M].北京：清華大學(xué)出版社，2008.

[3]Passino K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine，2002，22（3）：52-67.

[4]Kennedy J，Eberhart R.Particle swarm optimization[C]// Proceedings of the 4th IEEE International Conference onNeural Networks.Piscataway：IEEEServiceCenter，1995：1942-1948.

[5]張建科.求解非線性方程及方程組的粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，42（7）：56-58.

[6]臧明磊，楊十俊.用遺傳算法解一元非線性方程[J].濟(jì)寧師專學(xué)報(bào)，1998，19（6）：1-2.

[7]高飛，奄恒慶.一類求解方程根的改進(jìn)粒子群優(yōu)化算法[J].武漢大學(xué)學(xué)報(bào)：理學(xué)版，2006，52（3）：296-300.

[8]張姣玲.求解非線性方程及方程組的人工蜂群算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（22）：45-47.

[9]王曉鋒，張鐵.一類求解非線性方程最優(yōu)的8階收斂迭代法[J].吉林大學(xué)學(xué)報(bào)：理學(xué)版，2013，51（4）：568-572.

[10]游煦.一類非線性方程近似解的改進(jìn)Newton法[J].北京石油化工學(xué)院學(xué)報(bào)，2013，21（3）：62-66.

[11]倪健，馬昌鳳.解非線性方程的一種新的全局快速算法[J].合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，34（4）：620-622.

[12]張海蒂，曹德欣.求解非線性方程重根的區(qū)間牛頓法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（31）：40-42.

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

[14]李超燕，賴紅輝，周建良.基于極大熵和聲搜索算法的非線性方程組求解[J].計(jì)算機(jī)工程，2011，37（20）：189-193.

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

[16]王志剛.基于差異演化算法的非線性方程組求解[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（6）：54-55.

GUO Delong1,ZHENG Tianjian1,ZHOU Yongquan2

1.Department of Maths,Qiannan Normal University for Nationalities,Duyun,Guizhou 558000,China
2.College of Information and Engineering,Guangxi University for Nationalities,Nanning 530006,China

Traditional methods for solving nonlinear equations,such as Newton’s method,gradient descent method and so on,but they are required continuous differentiable,initial value selection.Aiming at above faults,the solution of the problem is transformed to an optimization problem.A new crossover foraging algorithm which is made full use of the ability of local search and particle swarm algorithm bacterial search ability,giving full play to the advantages of the two algorithms is proposed.Numerical experiments result shows that the new algorithm can make up for the lack of local search ability of particle swarm optimization algorithm and bacterial foraging algorithm global searching ability.This algorithm is an effective method for solving nonlinear equations.

local optimization;crossover;nonlinear equations

A

TP18

10.3778/j.issn.1002-8331.1401-0345

GUO Delong,ZHENG Tianjian,ZHOU Yongquan.Hybrid fast bacterial foraging algorithm for solving nolinear equation.Computer Engineering and Applications,2014,50（21）：32-34.

國(guó)家自然科學(xué)基金（No.61165015）；廣西自然科學(xué)基金（No.0832082）；廣西自然科學(xué)基金重點(diǎn)項(xiàng)目（No.2012GXNSFDA053028）；貴州省教育廳科研項(xiàng)目（黔教科2010093）。

郭德龍（1976—），男，副教授，主要研究方向?yàn)橹悄軆?yōu)化算法；鄭添?。?976—），男，講師，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)；周永權(quán)（1962—），男，博士，教授，主要研究方向?yàn)樯窠?jīng)網(wǎng)絡(luò)，計(jì)算智能及應(yīng)用。E-mail：guodelong19760319@126.com

2014-01-21

2014-03-20

1002-8331（2014）21-0032-03

CNKI出版日期：2014-05-29，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0345.html