基于非均勻消除-擴(kuò)散概率分布的情緒化細(xì)菌覓食算法

董 海，齊新娜

（1.沈陽大學(xué)應(yīng)用技術(shù)學(xué)院，沈陽 110044；2.沈陽大學(xué)機(jī)械工程學(xué)院，沈陽 110044）

（?通信作者電子郵箱1205344726@qq.com）

0 引言

自20 世紀(jì)40 年代以來，針對工程存在的具有高維度、多峰值、非線性且不可微分等特征的實(shí)際問題，許多仿生優(yōu)化演進(jìn)算法被廣泛用于優(yōu)化多式聯(lián)運(yùn)、單一方式、多變量、多層面、多目標(biāo)工程問題的基準(zhǔn)功能［1］。初始階段應(yīng)用較廣泛的搜索最優(yōu)解的優(yōu)化技術(shù)是Mirjalili［2］提出的遺傳算法（Genetic Algorithm，GA），GA 是通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，該算法被廣泛應(yīng)用于解決許多復(fù)雜的最優(yōu)解和滿意解等現(xiàn)實(shí)問題。Eberhart 等［3］開發(fā)了粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法，該算法擁有更好的收斂性和更精確的優(yōu)化效果，但網(wǎng)絡(luò)權(quán)重編碼的選擇較麻煩，計(jì)算成本高。劉曉陽等［4］提出了蟻群優(yōu)化（Ant Colony Optimization，ACO）算法，該算法是用來在圖中尋找優(yōu)化路徑的幾率型算法，適用于圖上路徑搜索問題。李曉磊等［5］提出魚群優(yōu)化（Fish Swarm Optimization，F(xiàn)SA）多用于精度要求不高的情況，可快速得到一個可行解，具有局限性。繼Müller 等［6］提出的基于單個細(xì)菌運(yùn)動行為的細(xì)菌趨藥性（Bacterial Chemotaxis，BC）算法之后，Passion［7］在2002 年提出細(xì)菌覓食優(yōu)化算法（Bacterial Foraging Optimization Algorithm，BFOA），研究表明：盡管BFOA的搜索性能優(yōu)于GA，但不及GA成熟。

為了提高BFOA 的性能，一些學(xué)者從算法融合和算法參數(shù)上進(jìn)行了研究。在算法融合方面：劉小龍等［1］將分布估計(jì)算法的思想引入BFOA 的繁殖過程，提出了基于高斯分布估計(jì)的細(xì)菌覓食算法；劉小龍等［8］將免疫算法與BFOA 進(jìn)行融合，提出了基于免疫算法的細(xì)菌覓食優(yōu)化算法；王振東等［9］將混沌優(yōu)化算法融入BFOA，提出了混沌優(yōu)化細(xì)菌覓食算法；徐玉韜等［10］將差分進(jìn)化算法中的交叉與變異操作引入BFOA，提出了一種混合型全局優(yōu)化算法。在算法參數(shù)調(diào)整方面：易軍等［11］提出了基于變鄰域趨化操作的BFOA，利用鄰域搜索提高局部最優(yōu)解的精確度；章國勇等［12］提出了一種具有量子行為的細(xì)菌覓食算法，以細(xì)菌群體信息為依據(jù)建立量子化的勢能阱模型；謝平平等［13］提出了基于社會學(xué)習(xí)自適應(yīng)BFOA，將社會學(xué)習(xí)機(jī)制及自適應(yīng)步長策略引入到標(biāo)準(zhǔn)BFOA 中進(jìn)行算法改進(jìn)；蔡昌春等［14］提出了基于神經(jīng)網(wǎng)絡(luò)改進(jìn)的細(xì)菌覓食算法；王新剛等［15］對趨化操作的運(yùn)動步長以及翻轉(zhuǎn)方向進(jìn)行了改進(jìn)，提出了一種改進(jìn)型細(xì)菌覓食算法。

綜上所述，上述研究提出的改進(jìn)型BFOA，其自適應(yīng)趨化步長存在不適用于多模情況等局限性，且忽略了消除-擴(kuò)散過程中概率的非均勻性［16］。針對上述問題，本文將基于情緒智能的突變引入標(biāo)準(zhǔn)的BFOA，并結(jié)合符合非均勻概率分布的消除-擴(kuò)散操作，提出了一種基于非均勻消除-擴(kuò)散概率分布的情緒化細(xì)菌覓食算法，通過仿真及算法對比，驗(yàn)證了算法具有良好的優(yōu)化性能。

1 算法設(shè)計(jì)

標(biāo)準(zhǔn)的細(xì)菌覓食優(yōu)化算法（BFOA）通過趨化、群集、繁殖和消除-擴(kuò)散四個步驟進(jìn)行優(yōu)化。在BFOA 中，通過游動和翻轉(zhuǎn)進(jìn)行優(yōu)化。在游動的過程中，如果細(xì)菌獲取到最佳狀態(tài)，會朝最佳狀態(tài)食物功能評估，并改變其在最大食物方向上的位置。

首先，在任何優(yōu)化技術(shù)中，最優(yōu)解的精度和收斂性都取決于步長。由于BFOA的步長尺寸固定［17］，存在以下缺點(diǎn)：

1）如果步長尺寸較小，可能無法獲取到全局最優(yōu)值；

2）如果步長尺寸較大，有可能在局部極小處捕獲細(xì)菌，雖可快速獲得最優(yōu)解，但最優(yōu)解的精度不高；

3）如果步長固定，細(xì)菌在接近最佳值時振蕩，無法收斂于最佳值。

針對上述步長存在的不確定性，本文利用自適應(yīng)或動態(tài)的步長來修正BFOA，以獲得低計(jì)算成本的最優(yōu)解；與此同時，為了減少計(jì)算時間，提高經(jīng)典BFOA 中最優(yōu)解的精度，本文擬從以下三個方面對BFOA 進(jìn)行改進(jìn)。首先，對其位置進(jìn)行更新，在趨化步驟中提出古斯分布搜索機(jī)制；其次，對其步長大小進(jìn)行改進(jìn)，在初始階段，固定的步長用于局部搜索，當(dāng)生成的數(shù)量增加時，利用自適應(yīng)或動態(tài)步長進(jìn)行全局搜索，并利用情緒智能的突變來實(shí)現(xiàn)自適應(yīng)步長；第三，標(biāo)準(zhǔn)的BFOA在消除-擴(kuò)散過程中，所有細(xì)菌個體都服從恒定的消除-擴(kuò)散概率，這項(xiàng)操作會使即將接近最優(yōu)位置的細(xì)菌替換為遠(yuǎn)離最優(yōu)解的細(xì)菌，從而影響其收斂速度，本文利用線性和非線性概率分布代替?zhèn)鹘y(tǒng)的常數(shù)分布來實(shí)現(xiàn)非均勻分布。具體算法設(shè)計(jì)如下。

1.1 改進(jìn)的趨化操作

傳統(tǒng)的BFOA 由于趨化操作，其搜索性能較差，發(fā)現(xiàn)每一種細(xì)菌都通過隨機(jī)翻滾來調(diào)整自己的游動和翻轉(zhuǎn)方向，使每一種細(xì)菌都能在特定的環(huán)境中生存。在整個生命周期內(nèi)，以隨機(jī)方式在每個維度上游動或翻轉(zhuǎn)，從而使細(xì)菌具有較差的搜索能力，如果整個搜索空間很大，則容易陷入局部最優(yōu)。此外，每個細(xì)菌的運(yùn)動都是孤立的，在趨化操作中缺乏信息交換能力。為了解決細(xì)菌運(yùn)動的基本趨向步驟，本文提出了基于古斯分布的搜索機(jī)制，對趨化性細(xì)菌的運(yùn)動規(guī)律進(jìn)行調(diào)整［17］。假設(shè)細(xì)菌i的位置由θi(j，k，l)表示，其中：j為趨化步驟，k為繁殖步驟，l為消除-擴(kuò)散步驟。C（i）表示每次游動或翻轉(zhuǎn)的趨化步長大小，那么對于每次趨化步驟，細(xì)菌i的運(yùn)動可表示為：

否則：

其中：

式中：N表示游動或翻轉(zhuǎn)的次數(shù)；p表示局部細(xì)菌個體總數(shù)。

1.2 群集操作

接近最優(yōu)路徑的細(xì)菌個體可跟隨其他較低梯度的細(xì)菌個體進(jìn)行覓食，以便更快地收斂。菌群的群集行為使細(xì)菌個體形成群體，并以同心圓為軌跡進(jìn)行運(yùn)動，菌群密度高，則食物梯度高。該群集機(jī)制可建模型，如式（8）表示。

其中：Jcc(θ，P(j，k，l))表示細(xì)菌個體之間的吸引和排斥作用值；θ∈{θ1，θ2，…，θq}表示q維搜索域中的一個點(diǎn)；s表示細(xì)菌的總數(shù)；q表示優(yōu)化變量的個數(shù)；n表示維度內(nèi)某節(jié)點(diǎn)；dattract、wattract分別表示細(xì)菌的引誘因子深度和寬度的度量系數(shù)；hrepelent、wrepelent分別表示細(xì)菌驅(qū)避高度和寬度系數(shù)。

1.3 情緒化突變

基于情緒智能突變使細(xì)菌的位置發(fā)生動態(tài)變化，在基于非均勻消除-擴(kuò)散概率分布的情緒化細(xì)菌覓食算法中，突變發(fā)生在繁殖步驟之前。在突變中，采用自適應(yīng)步長可避免過早收斂，此過程假設(shè)細(xì)菌有心理，每種細(xì)菌都有兩種情緒：快樂和悲傷，每種細(xì)菌都會根據(jù)自己的感受對當(dāng)前的位置作出反應(yīng)，不同的位置被用來刺激下一代的細(xì)菌。利用著名的韋伯-費(fèi)克納定律計(jì)算情緒感知因子。由韋伯-費(fèi)克納定律描述的刺激強(qiáng)度P大小之間的關(guān)系［16］，如式（9）所示：

其中：k為常數(shù)因子；S0為刺激閾值；S為刺激函數(shù)。刺激和感知之間使用對數(shù)關(guān)系。如果一個刺激依據(jù)幾何表達(dá)式變化，并且相應(yīng)的知覺在對數(shù)關(guān)系的數(shù)學(xué)表達(dá)式中改變。細(xì)菌的全局感知rg和歷史感知rh分別通過方程式（10）～（11）來描述：

其中，f(θ(i，j，k，l))表示如果細(xì)菌遠(yuǎn)離全局最佳位置，將對刺激產(chǎn)生強(qiáng)烈的反應(yīng)，這些刺激將與其所經(jīng)歷的歷史相比較。細(xì)菌的快樂和悲傷兩種情緒會動態(tài)地改變細(xì)菌的位置，使其步幅變小或變大，細(xì)菌的情緒表現(xiàn)如方程式（12）～（13）所示。

快樂的細(xì)菌個體為：

悲傷的細(xì)菌個體為：

其中：θglobal表示全局最佳位置；f（θglobal）表示全局最佳位置適應(yīng)度；f（θ（i，j，k，l））表示實(shí)時的適應(yīng)度；v（i，j，k，l）表示細(xì)菌速度；w（k）表示線性減小慣性重量；c表示加速度系數(shù)；rand表示隨機(jī)函數(shù)。

根據(jù)情緒感知因子更新細(xì)菌速度：如果隨機(jī)函數(shù)rand小于情緒感知因子es，依據(jù)式（12）更新細(xì)菌速度；否則，依據(jù)等式（13）更新細(xì)菌速度。

根據(jù)式（14）可推斷出全局最佳位置υ(i，j+1，k，l)，以更新每種細(xì)菌的當(dāng)前位置：

其中，m表示動力因子。

為了防止細(xì)菌在游泳或翻轉(zhuǎn)后離開脫水區(qū)域，使用動量因子。動量因子限制了未定義的搜索空間中的細(xì)菌，因此不必在每一代之后檢查細(xì)菌的位置，從而節(jié)省計(jì)算成本。動量因子的選擇為隨機(jī)值而不是常量值，因?yàn)樗屑?xì)菌每次都會被拉入具有不同限制的搜索空間，從而導(dǎo)致無法逃離全局最優(yōu)值。在整個搜索空間，搜索實(shí)驗(yàn)的初始階段步長非常大，當(dāng)細(xì)菌接近全局最優(yōu)值時，步長會動態(tài)地縮減，因此，自適應(yīng)步長f（θ（i，j，k，l））將更接近f（θglobal）。

1.4 繁殖操作

在基于非均勻消除-擴(kuò)散概率的分布的細(xì)菌覓食算法中，細(xì)菌的繁殖類似于經(jīng)典的BFOA，隨著營養(yǎng)素的不斷吸收，細(xì)菌逐漸生長。在適當(dāng)?shù)臈l件下，每個健康的個體會分裂成兩個子細(xì)菌，但是，對于營養(yǎng)不良的個體這些細(xì)菌會被清除。為了保留細(xì)菌趨化過程中的良好經(jīng)驗(yàn)，加快算法的收斂速度，本文將細(xì)菌適應(yīng)度在歷次趨化過程中的歷史最優(yōu)值作為健康適應(yīng)度函數(shù)Jhealth［13］，再現(xiàn)操作排序如式（15）所示：

其中，Nc為趨向步驟次數(shù)。

1.5 非均勻概率分布的消除-擴(kuò)散操作

為了避免在局部最優(yōu)條件下存儲細(xì)菌的可能性，提高細(xì)菌的搜索能力，一些細(xì)菌被消除，而一些則根據(jù)概率分散在搜索空間中內(nèi)，即在該過程中，具有最佳適應(yīng)度值和最差適應(yīng)度值的細(xì)菌均以相同概率被消除。因此，會將接近最優(yōu)位置的細(xì)菌個體替換為遠(yuǎn)離最優(yōu)位置的細(xì)菌個體，從而影響算法的性能［16］。據(jù)此，本文提出依據(jù)非均勻概率分布消除細(xì)菌，該方法是通過將細(xì)菌重新定位到環(huán)境中的隨機(jī)位置來實(shí)現(xiàn)該過程的。線性消除概率定義為：

根據(jù)式（16）可知，種群內(nèi)的消除-擴(kuò)散概率與種群內(nèi)的細(xì)菌指數(shù)成線性正比，其概率步長增加為s/2，在該情況下，獲得最佳適應(yīng)度的細(xì)菌被消滅的可能性最低，適應(yīng)度最差的個體因被分配了等同的概率而被淘汰。另一種非均勻分布概率可用于定義非線性行為，如式（17）所示。

在該概率分布中，最優(yōu)細(xì)菌個體將具有最低的概率，而最差的細(xì)菌個體將完全被淘汰，在這種情況下概率與細(xì)菌指數(shù)成線性正比。

消除-擴(kuò)散概率（Pe）決定了搜索過程中的探索和開發(fā)的量：Pe值越大，消除作用越強(qiáng)，對細(xì)菌的遷移作用越好，可避免陷入局部極小值，并且探索過程越容易實(shí)現(xiàn)；Pe值越小，越可保證最佳細(xì)菌的發(fā)展，并可加強(qiáng)對局部區(qū)域的研究，然而這種細(xì)菌將有更少的機(jī)會被從局部區(qū)域釋放，可能會造成局部極小值。因此，控制Pe值至關(guān)重要。在研究初期本文采取探索整個搜索空間，相反，在搜索結(jié)束時進(jìn)行開發(fā)（增強(qiáng)），該操作可通過分配小的Pe值來實(shí)現(xiàn)。對于線性分布及非線性分布可推廣為包含消除-擴(kuò)散指數(shù)，分別定義如式（18）、（19）所示：

線性為：

非線性為：

1.6 算法設(shè)計(jì)

本文提出的基于非均勻消除-擴(kuò)散概率的情緒化細(xì)菌覓食算法流程如圖1所示。

圖1 本文算法流程Fig.1 Flowchart of proposed algorithm

2 仿真實(shí)驗(yàn)與結(jié)果分析

2.1 仿真設(shè)計(jì)

表1 給出Rosenbrock、Sphere、Griewank、Schaffer’s、Shekel’s Foxholes、Rastrigin六個基準(zhǔn)函數(shù)，測試本文提出的基于非均勻消除-擴(kuò)散概率分布的情緒化細(xì)菌覓食算法，并驗(yàn)證算法的性能。其中：f1（x）與f2（x）為單峰函數(shù)，解的空間有非常多狹窄的局部極小通道；f3（x）、f4（x）、f5（x）與f6（x）為多峰函數(shù)，算法很容易陷入通向全局最優(yōu)點(diǎn)的局部最優(yōu)上。表2為全局最優(yōu)搜索范圍及初始化范圍的參數(shù)，表中d表示無限大。表3為算法參數(shù)設(shè)置。

表1 模擬基準(zhǔn)函數(shù)Tab.1 Simulated benchmark functions

表2 搜索范圍及初始化范圍Tab.2 Search range and initialization range

2.2 算法對比分析

為測試新算法的性能，本文對具有量子行為的細(xì)菌覓食算法（Bacterial Foraging Algorithm with Quantum Behavior，BFAQB）、差分進(jìn)化改善的細(xì)菌覓食算法（Improved Bacterial Foraging Algorithm Based on Differential Evolution，IBFABDE）、基于高斯分布的細(xì)菌覓食算法（Bacterial Foraging Algorithm Based on Gaussian Distribution，BFABGD）及本文提出的基于非均勻消除-擴(kuò)散概率分布的情緒化細(xì)菌覓食算法（Nonuniform Probability Emotional Bacteria Foraging Algorithm，NPEBFA）在上述六個基準(zhǔn)函數(shù)進(jìn)行測試，實(shí)驗(yàn)對比結(jié)果如表4所示。

表4 中，NPEBFA 的性能優(yōu)于BFAQB 和IBFABDE，但對Rosenbrock 函數(shù)的性能不如BFABGD。與NPEBFA 相比，BFABGD 獲得的Rosenbrock 函數(shù)的平均迭代效率優(yōu)于NPEBFA。

Sphere 函數(shù)的模擬結(jié)果顯示，NPEBFA 和比較算法執(zhí)行于球體函數(shù)上，標(biāo)準(zhǔn)差分析結(jié)果表明，球面函數(shù)擬合度的參數(shù)值彼此接近。

表3 算法參數(shù)設(shè)置Tab.3 Algorithm parameter setting

表4 不同算法函數(shù)仿真結(jié)果對比Tab.3 Comparison of functional simulation results of different algorithms

Griewank 函數(shù)的模擬結(jié)果顯示，該方法可以提高算法的精度和收斂性，通過分析NPEBFA 計(jì)算結(jié)果，證明其能夠以較低的計(jì)算成本獲得精確的最優(yōu)解。

Schaffer’s 函數(shù)的模擬結(jié)果顯示，NPEBFA 以較低的計(jì)算成本提供了較好的優(yōu)化質(zhì)量。

Shekel’s Foxholes函數(shù)的模擬結(jié)果顯示，其全局最小值不是零。對于這種函數(shù)，NPEBFA 技術(shù)在節(jié)省計(jì)算成本方面的性能也很好，同時與其他方法相比，擬合參數(shù)彼此接近。

Rastrigin函數(shù)的模擬結(jié)果顯示，NPEBFA以最小的計(jì)算成本獲得精確的最優(yōu)值。與BFAQB、IBFABDE 和BFABGD 相比，NPEBFA對Rastrigin函數(shù)的代數(shù)要求較少。

對單個最優(yōu)函數(shù)和多個局部最優(yōu)函數(shù)的實(shí)驗(yàn)結(jié)果表明，該算法除針對Rosenbrock 函數(shù)外，在計(jì)算成本較低的情況下，具有較好的優(yōu)化質(zhì)量，且對于求解多模態(tài)函數(shù)等復(fù)雜問題更為有效，優(yōu)化精度高。

不同算法收斂性的比較如圖2 所示，仿真結(jié)果表明本文提出的NPEBFA 在最優(yōu)均值范圍不同的情況下均具有較好的收斂性，即該算法較BFABGD、IBFABDE、BFAQB 更適用于不同的搜索空間范圍，該優(yōu)勢可確保算法優(yōu)化過程中種群的多樣性，并避免范圍內(nèi)待優(yōu)化因子的丟失。

圖2 不同算法收斂性比較Fig.2 Convergence comparison of different algorithms

3 結(jié)語

本文通過賦予細(xì)菌個體情緒感知因子的概念來改變細(xì)菌的趨化步長，并將古斯分布搜索機(jī)制嵌入趨化步驟中，同時在個體消除-擴(kuò)散過程中，利用線性和非線性概率分布代替?zhèn)鹘y(tǒng)的常數(shù)分布來實(shí)現(xiàn)非均勻分布，進(jìn)而提出了一種改進(jìn)的細(xì)菌覓食優(yōu)化算法，算法中的待優(yōu)化變量的搜索空間在開發(fā)能力和探索能力上取得提升。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的NPEBFA 的性能及收斂性優(yōu)于傳統(tǒng)的BFO 算法，并且避免了其他改進(jìn)細(xì)菌覓食算法存在的部分缺陷，適用于解決高維度工程優(yōu)化問題。