張曉明
（長春建筑學院 基礎教學部，吉林 長春 130607）
摘要： 針對傳統的數值算法求解非線性方程組時對方程組要求高和初始值敏感等缺點，提出了一種自適應細菌覓食算法。該算法改變了傳統算法的固定趨化步長，進行自適應調整，加快算法的收斂速度，具有更好的全局搜索能力，改變了固定遷移概率，避免了在進化后期精英解丟失的問題。將自適應細菌覓食算法應用到求解非線性方程組中，結果表明，與其他算法相比，該算法能夠有效避免陷入局部最優，能更好地尋求最優解。
關鍵詞：細菌覓食算法；非線性方程組；自適應
0引言
傳統的求解非線性方程組的方法主要有牛頓法、迭代法等，但這些方法對初始點的選取要求很精確，且要求方程組連續、可導等。近年來隨著智能算法的興起，其在求解非線性方程組問題上得到了很好的應用。2002年，PASSINO K M根據生物體大腸桿菌的覓食行為，提出了細菌覓食算法［12］(Bacterial Foraging Algorithm, BFA)。本文利用BFA很強的全局搜索能力和并行計算能力對非線性方程組進行求解，仿真實驗表明了算法的有效性。
1問題描述
設非線性方程組形式如下：
f1(x1,x2,…,xn)=A1
f2(x1,x2,…,xn)=A2
…
fn(x1,x2,…,xn)=An （1）
非線勝方程組由n個方程組成，有n個未知變量，其中fi(x1,x2,…,xn)=Ai(i=1,2,…,n)為非線性方程，BFA對非線性方程組求解時，取目標函數的方式如下：
易證，當目標函數值等于零時的解為最優解。
2細菌覓食算法
細菌覓食算法是隨機搜索的群智能優化算法，其模擬細菌覓食行為的數學模型在優化計算時，主要由4個步驟完成：趨向、聚集、復制、遷移。
2.1趨向性操作
大腸桿菌主要是依據自身鞭毛的旋轉方向進行覓食。相應的數學模型解釋為通過計算出的適應度值進行比較，決定細菌是繼續前進還是尋找隨機方向移動，當嘗試次數達到最大限制數時選擇下一個細菌進行趨向性的操作。
在BFA模型中，細菌的趨向性操作的數學表達式為：
其中，θi(j,k,l)表示細菌i在第j次趨向第k次復制第l次遷移操作之后所在的位置，C(i)為趨向步長長度，Δ(i)Δ(i)TΔ(i)為移動的一個隨機前進方向。
2.2聚集性操作
聚集操作體現為引力和斥力，引力表示細菌會快速地聚集在一起圍繞最優食物覓食。斥力表示細菌獨立尋找食物的特性。公式為：
其中，dattractant是引力深度，wattractant是引力寬度，hrepellent是斥力高度，wrepellent是斥力寬度，θim為細菌i的第 m個分量。通常取dattractant=hrepellent，趨向性操作的適應度值表示為：
J(i,j+1,k,l)=J(i,j,k,l)+Jcc(θi(j+1,k,l),
P(j+1,k,l))（5）
即通過此引力和斥力操作影響適應度值的大小。
2.3復制性操作
在BFA模型中， Jihealth是細菌i的能量函數，其大小決定細菌覓食能力的強弱。將細菌覓食后的能量函數值進行大小排序，淘汰掉S2個能量值較小的細菌，將剩余的S2個細菌進行復制操作，新生成的復制細菌體與原細菌具有完全相同的覓食能力。
2.4遷移性操作
當局部區域的溫度升高或者食物被消耗掉，必然導致細菌被迫遷移到新的區域去尋找食物，即為遷移操作。細菌按照一定的概率進行遷移，新種群的隨機特性可能具有不同的覓食能力，這種隨機特性能使群體跳出局部極值而更好地尋找全局最優解。
3自適應細菌覓食算法（ABFA）
3.1自適應趨向步長
在BFA進行趨向操作時，固定的步長對算法尋優有很大的影響，太大易忽略局部最優點，太小易陷入局部最優且用時較長。李珺等人［3］提出自適應調節步長，利用群體內細菌的最大最小距離構建步長調整方式，考慮因素缺少。綜合算法各個參數進行耦合，提出自適應變步長的調整方式如下：
其中，V代表靈敏度；Ji為第i個細菌能量值；Jmax為最大能量值；Xmax與Xmin為變量的邊界值；t為當前迭代次數；Tmax為最大迭代次數；s為大于 1 的整數，本文s取值范圍［4］ 為［1,30］。V按照β非線性遞減，迭代開始時離最優解較遠，步長較大，當逐漸靠近最優解時，步長取值較小。該方法能較好地平衡全局搜索能力和局部搜索能力，提高了算法的有效性。
3.2自適應驅散概率
在傳統BFA算法遷移操作中,細菌遷移概率是固定的，固定的遷移概率會引起優秀的細菌群體發生遷移，即丟失精英解，因此遷移操作導致解的退化，故在此提出自適應遷移概率。
其中：Ji為第i個細菌能量值，Jmax為最大、能量值，Javg為平均能量值，pmax、pmin為最大、最小變異概率。遷移概率按照能量值進行調整，形成良好的解空間狀態。
4求解非線性方程組的流程
使細菌覓食算法的主要步驟如下。
（1）初始化參數：種群大小S、空間維數P、趨向性的次數Nc、趨向性最大步數Ns、復制操作次數Nre、遷移操作次數Ned、遷移概率Ped，細菌i的信息用D維向量表示。
（2）形成初始解的細菌群，按照式（5）計算細菌適應度，適應度函數中步長更新按照式（6）進行，存儲最優值Jbest。
（3）趨向性循環操作。按照ABFA進行步長的參數調整，并計算相應適應度值。
（4）復制循環操作。按照趨向性操作后計算的適應度值進行從小到大排序，淘汰掉S2個適應度值較小即能量值較差的細菌，將剩余的適應度值較大的細菌進行復制，使其保存優越的性能。
（5）遷移循環操作。在經過趨向性和復制操作后，將細菌按照一定的遷移概率（式（7））進行遷移，分配到尋優的空間中。
（6）循環結束條件判斷，輸出結果。
5數值計算及分析
為了驗證ABFA在求解非線性方程組的能力，本文針對參考文獻［5］~［8］中典型的方程組進行求解測試。
例題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。
數值計算環境在MATLAB 2010b操作環境編程運行。設置ABFA的參數：細菌的個數為S=50、Nc=20、Nre=20、Ned=4、Tmax=100、最大和最小變異概率為0.35和0.25，進行50次實驗取平均值,實驗結果見表1。
結果分析：平均適應度值越趨近于理論值0，表明算法性能更好。例1中ABC、PSO都能取得近似解，但計算的精度不夠，ABFA利用其自適應調整參數的特性，跳出局部極值且計算出精確的解。例2中，由于傳統PSO算法搜索的缺點，只能搜索到兩組解，丟失解（-1,2），ABFA能搜索到第三組解，體現出該算法有更好的搜索性能。例3中，ABC［8］、QPSO［9］算法的搜索精度及成功率沒有ABFA具有優勢，且ABFA算法平均適應度值的精度優于其他兩種算法。ABFA在計算時采用的是3層循環操作，使用MATLAB計算唯一的缺是點以犧牲時間為代價，用PSO及ABC計算的時間不超過10 s，而ABFA計算時間平均在20 s左右。該算法具有較好的全局搜索能力和求解的搜索精度且在求解非線性方程組上具有明顯優勢。
6結論
本文提出一種自適應的細菌覓食算法，改變傳統細菌覓食算法在計算時步長和變異概率選取上的固定性，根據適應度值和計算次數進行自適應調整參數，增強了算法的快速收斂性能，提高了算法在求解全局最優解的能力和搜索精度，是一種較好求解非線性方程組的算法。
參考文獻
［1］ PASSINO K M. Biomimicry of bacterial foraging for distributed optimization and control［J］.IEEE Control Systems Magazine,2002,22(3):5267.