張曉明

　　（長春建筑學(xué)院 基礎(chǔ)教學(xué)部，吉林 長春 130607）

　　摘要： 針對傳統(tǒng)的數(shù)值算法求解非線性方程組時(shí)對方程組要求高和初始值敏感等缺點(diǎn)，提出了一種自適應(yīng)細(xì)菌覓食算法。該算法改變了傳統(tǒng)算法的固定趨化步長，進(jìn)行自適應(yīng)調(diào)整，加快算法的收斂速度，具有更好的全局搜索能力，改變了固定遷移概率，避免了在進(jìn)化后期精英解丟失的問題。將自適應(yīng)細(xì)菌覓食算法應(yīng)用到求解非線性方程組中，結(jié)果表明，與其他算法相比，該算法能夠有效避免陷入局部最優(yōu)，能更好地尋求最優(yōu)解。

　　關(guān)鍵詞：細(xì)菌覓食算法；非線性方程組；自適應(yīng)

0引言

　　傳統(tǒng)的求解非線性方程組的方法主要有牛頓法、迭代法等，但這些方法對初始點(diǎn)的選取要求很精確，且要求方程組連續(xù)、可導(dǎo)等。近年來隨著智能算法的興起，其在求解非線性方程組問題上得到了很好的應(yīng)用。2002年，PASSINO K M根據(jù)生物體大腸桿菌的覓食行為，提出了細(xì)菌覓食算法［12］(Bacterial Foraging Algorithm, BFA)。本文利用BFA很強(qiáng)的全局搜索能力和并行計(jì)算能力對非線性方程組進(jìn)行求解，仿真實(shí)驗(yàn)表明了算法的有效性。

　　1問題描述

　　設(shè)非線性方程組形式如下：

　　f1(x1,x2,…,xn)=A1

　　f2(x1,x2,…,xn)=A2

　　…

　　fn(x1,x2,…,xn)=An （1）

　　非線勝方程組由n個(gè)方程組成，有n個(gè)未知變量，其中fi(x1,x2,…,xn)=Ai(i=1,2,…,n)為非線性方程，BFA對非線性方程組求解時(shí)，取目標(biāo)函數(shù)的方式如下：

　　易證，當(dāng)目標(biāo)函數(shù)值等于零時(shí)的解為最優(yōu)解。

2細(xì)菌覓食算法

　　細(xì)菌覓食算法是隨機(jī)搜索的群智能優(yōu)化算法，其模擬細(xì)菌覓食行為的數(shù)學(xué)模型在優(yōu)化計(jì)算時(shí)，主要由4個(gè)步驟完成：趨向、聚集、復(fù)制、遷移。

　　2.1趨向性操作

　　大腸桿菌主要是依據(jù)自身鞭毛的旋轉(zhuǎn)方向進(jìn)行覓食。相應(yīng)的數(shù)學(xué)模型解釋為通過計(jì)算出的適應(yīng)度值進(jìn)行比較，決定細(xì)菌是繼續(xù)前進(jìn)還是尋找隨機(jī)方向移動(dòng)，當(dāng)嘗試次數(shù)達(dá)到最大限制數(shù)時(shí)選擇下一個(gè)細(xì)菌進(jìn)行趨向性的操作。

　　在BFA模型中，細(xì)菌的趨向性操作的數(shù)學(xué)表達(dá)式為：

　　其中，θi(j,k,l)表示細(xì)菌i在第j次趨向第k次復(fù)制第l次遷移操作之后所在的位置，C(i)為趨向步長長度，Δ(i)Δ(i)TΔ(i)為移動(dòng)的一個(gè)隨機(jī)前進(jìn)方向。

　　2.2聚集性操作

　　聚集操作體現(xiàn)為引力和斥力，引力表示細(xì)菌會(huì)快速地聚集在一起圍繞最優(yōu)食物覓食。斥力表示細(xì)菌獨(dú)立尋找食物的特性。公式為：

　　其中，dattractant是引力深度，wattractant是引力寬度，hrepellent是斥力高度，wrepellent是斥力寬度，θim為細(xì)菌i的第 m個(gè)分量。通常取dattractant=hrepellent，趨向性操作的適應(yīng)度值表示為：

　　J(i,j+1,k,l)=J(i,j,k,l)+Jcc(θi(j+1,k,l),

　　P(j+1,k,l))（5）

　　即通過此引力和斥力操作影響適應(yīng)度值的大小。

　　2.3復(fù)制性操作

　　在BFA模型中， Jihealth是細(xì)菌i的能量函數(shù)，其大小決定細(xì)菌覓食能力的強(qiáng)弱。將細(xì)菌覓食后的能量函數(shù)值進(jìn)行大小排序，淘汰掉S2個(gè)能量值較小的細(xì)菌，將剩余的S2個(gè)細(xì)菌進(jìn)行復(fù)制操作，新生成的復(fù)制細(xì)菌體與原細(xì)菌具有完全相同的覓食能力。

　　2.4遷移性操作

　　當(dāng)局部區(qū)域的溫度升高或者食物被消耗掉，必然導(dǎo)致細(xì)菌被迫遷移到新的區(qū)域去尋找食物，即為遷移操作。細(xì)菌按照一定的概率進(jìn)行遷移，新種群的隨機(jī)特性可能具有不同的覓食能力，這種隨機(jī)特性能使群體跳出局部極值而更好地尋找全局最優(yōu)解。

3自適應(yīng)細(xì)菌覓食算法（ABFA）

　　3.1自適應(yīng)趨向步長

　　在BFA進(jìn)行趨向操作時(shí)，固定的步長對算法尋優(yōu)有很大的影響，太大易忽略局部最優(yōu)點(diǎn)，太小易陷入局部最優(yōu)且用時(shí)較長。李珺等人［3］提出自適應(yīng)調(diào)節(jié)步長，利用群體內(nèi)細(xì)菌的最大最小距離構(gòu)建步長調(diào)整方式，考慮因素缺少。綜合算法各個(gè)參數(shù)進(jìn)行耦合，提出自適應(yīng)變步長的調(diào)整方式如下：

　　其中，V代表靈敏度；Ji為第i個(gè)細(xì)菌能量值；Jmax為最大能量值；Xmax與Xmin為變量的邊界值；t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)；s為大于 1 的整數(shù)，本文s取值范圍［4］ 為［1,30］。V按照β非線性遞減，迭代開始時(shí)離最優(yōu)解較遠(yuǎn)，步長較大，當(dāng)逐漸靠近最優(yōu)解時(shí)，步長取值較小。該方法能較好地平衡全局搜索能力和局部搜索能力，提高了算法的有效性。

　　3.2自適應(yīng)驅(qū)散概率

　　在傳統(tǒng)BFA算法遷移操作中,細(xì)菌遷移概率是固定的，固定的遷移概率會(huì)引起優(yōu)秀的細(xì)菌群體發(fā)生遷移，即丟失精英解，因此遷移操作導(dǎo)致解的退化，故在此提出自適應(yīng)遷移概率。

　　其中：Ji為第i個(gè)細(xì)菌能量值，Jmax為最大、能量值，Javg為平均能量值，pmax、pmin為最大、最小變異概率。遷移概率按照能量值進(jìn)行調(diào)整，形成良好的解空間狀態(tài)。

4求解非線性方程組的流程

　　使細(xì)菌覓食算法的主要步驟如下。

　　（1）初始化參數(shù)：種群大小S、空間維數(shù)P、趨向性的次數(shù)Nc、趨向性最大步數(shù)Ns、復(fù)制操作次數(shù)Nre、遷移操作次數(shù)Ned、遷移概率Ped，細(xì)菌i的信息用D維向量表示。

　　（2）形成初始解的細(xì)菌群，按照式（5）計(jì)算細(xì)菌適應(yīng)度，適應(yīng)度函數(shù)中步長更新按照式（6）進(jìn)行，存儲(chǔ)最優(yōu)值Jbest。

　?。?）趨向性循環(huán)操作。按照ABFA進(jìn)行步長的參數(shù)調(diào)整，并計(jì)算相應(yīng)適應(yīng)度值。

　?。?）復(fù)制循環(huán)操作。按照趨向性操作后計(jì)算的適應(yīng)度值進(jìn)行從小到大排序，淘汰掉S2個(gè)適應(yīng)度值較小即能量值較差的細(xì)菌，將剩余的適應(yīng)度值較大的細(xì)菌進(jìn)行復(fù)制，使其保存優(yōu)越的性能。

　?。?）遷移循環(huán)操作。在經(jīng)過趨向性和復(fù)制操作后，將細(xì)菌按照一定的遷移概率（式（7））進(jìn)行遷移，分配到尋優(yōu)的空間中。

　　（6）循環(huán)結(jié)束條件判斷，輸出結(jié)果。

5數(shù)值計(jì)算及分析

　　為了驗(yàn)證ABFA在求解非線性方程組的能力，本文針對參考文獻(xiàn)［5］~［8］中典型的方程組進(jìn)行求解測試。

　　例題1

　　f1(x)=x21+x22+x23－3=0

　　f2(x)=x21+x22+x1x2+x1+x2－5=0

　　f3(x)=x1+x2+x3－3=0

　　其中－1.732≤x1,x2,x3≤1.732，理論解為x*=(1,1,1)T。

　　例題2

　　f1(x)=x21－x2+1=0

　　f2(x)=x1－cos(0.5πx2)=0

　　其中x∈［－2,2］，理論解為x*=(－12,1.5)T，x*=(0,1)T，x*=(－1,2)T。

　　例題3

　　f1(x)=xx21+xx12－5x1x2x3－85=0

　　f2(x)=x31－xx32－xx23－60=0

　　f3(x)=xx31+xx13－x2－2=0

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

　　數(shù)值計(jì)算環(huán)境在MATLAB 2010b操作環(huán)境編程運(yùn)行。設(shè)置ABFA的參數(shù)：細(xì)菌的個(gè)數(shù)為S=50、Nc=20、Nre=20、Ned=4、Tmax=100、最大和最小變異概率為0.35和0.25，進(jìn)行50次實(shí)驗(yàn)取平均值,實(shí)驗(yàn)結(jié)果見表1。

　　   結(jié)果分析：平均適應(yīng)度值越趨近于理論值0，表明算法性能更好。例1中ABC、PSO都能取得近似解，但計(jì)算的精度不夠，ABFA利用其自適應(yīng)調(diào)整參數(shù)的特性，跳出局部極值且計(jì)算出精確的解。例2中，由于傳統(tǒng)PSO算法搜索的缺點(diǎn)，只能搜索到兩組解，丟失解（-1,2），ABFA能搜索到第三組解，體現(xiàn)出該算法有更好的搜索性能。例3中，ABC［8］、QPSO［9］算法的搜索精度及成功率沒有ABFA具有優(yōu)勢，且ABFA算法平均適應(yīng)度值的精度優(yōu)于其他兩種算法。ABFA在計(jì)算時(shí)采用的是3層循環(huán)操作，使用MATLAB計(jì)算唯一的缺是點(diǎn)以犧牲時(shí)間為代價(jià)，用PSO及ABC計(jì)算的時(shí)間不超過10 s，而ABFA計(jì)算時(shí)間平均在20 s左右。該算法具有較好的全局搜索能力和求解的搜索精度且在求解非線性方程組上具有明顯優(yōu)勢。

6結(jié)論

　　本文提出一種自適應(yīng)的細(xì)菌覓食算法，改變傳統(tǒng)細(xì)菌覓食算法在計(jì)算時(shí)步長和變異概率選取上的固定性，根據(jù)適應(yīng)度值和計(jì)算次數(shù)進(jìn)行自適應(yīng)調(diào)整參數(shù)，增強(qiáng)了算法的快速收斂性能，提高了算法在求解全局最優(yōu)解的能力和搜索精度，是一種較好求解非線性方程組的算法。

參考文獻(xiàn)

　?。?］ PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine,2002,22(3):5267.