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

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

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

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

◎理論研究、研發(fā)設計◎

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

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

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

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

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

局部優(yōu)化；交叉；非線性方程

1 引言

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

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

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

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

2 問題的描述

設非線性方程：

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

在[a，b]中的極小點，當H(x)最小值為0時，所對應的x即為方程（3）的精確解，H(x)最小值越小方程的近似程度越好。

3 細菌覓食算法描述

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

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

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

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

4 混合算法求解非線性方程的設計

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

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

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

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

步驟3隨機生成初始化細菌群體。

步驟4計算細菌適應度值并進行評價。這里適應度函數(shù)取為：

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

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

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

表1 本文算法與參考文獻[5]對例1～例3的比較

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

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

（2）復制操作：對于經(jīng)過趨化性操作的細菌群體，并且對每個細菌的適應度值的累加和進行排序，淘汰掉適應度值較差的一半細菌再從剩下的一半細菌分裂出同樣的細菌，遺傳母細菌的位置和特性。

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

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

5 數(shù)值仿真實驗

為了測試本文算法的性能，選取參考文獻[5-8]的非線性方程。

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

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

6 結(jié)束語

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

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

[2]李慶揚，王能超，易大義.數(shù)值分析[M].北京：清華大學出版社，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].計算機工程與應用，2006，42（7）：56-58.

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

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

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

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

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

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

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

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

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

[15]燕樂緯，陳樹輝.基于改進遺傳算法的非線性方程組求解[J].中山大學學報：理學版，2011，50（1）：620-622.

[16]王志剛.基于差異演化算法的非線性方程組求解[J].計算機工程與應用，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.

國家自然科學基金（No.61165015）；廣西自然科學基金（No.0832082）；廣西自然科學基金重點項目（No.2012GXNSFDA053028）；貴州省教育廳科研項目（黔教科2010093）。

郭德龍（1976—），男，副教授，主要研究方向為智能優(yōu)化算法；鄭添?。?976—），男，講師，主要研究方向為計算機網(wǎng)絡；周永權(quán)（1962—），男，博士，教授，主要研究方向為神經(jīng)網(wǎ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