晏曉輝， 朱云龍， 張智聰， 呂賜興， 李 帥， 蟻文潔

(1.東莞理工學(xué)院 機(jī)械工程學(xué)院，廣東 東莞 523808； 2.東莞理工學(xué)院 電子工程與智能化學(xué)院，廣東 東莞 523808； 3.深圳大學(xué) 管理學(xué)院,廣東 深圳 518060)

0 引言

群體智能(swarm intelligence, SI)算法是近年來(lái)智能計(jì)算和優(yōu)化領(lǐng)域的熱門(mén)方向.自20世紀(jì)90年代起，學(xué)者們從蟻群覓食、鳥(niǎo)類(lèi)飛行、蜂群分工合作、螢火蟲(chóng)發(fā)光吸引、魚(yú)群結(jié)伴游弋等行為中受到啟發(fā)，先后提出多種群體智能算法[1-5]，并在許多數(shù)值優(yōu)化和工程優(yōu)化問(wèn)題上進(jìn)行了測(cè)試應(yīng)用.對(duì)于傳統(tǒng)運(yùn)籌學(xué)方法難以求解的大規(guī)模組合優(yōu)化問(wèn)題，群體智能算法能在較短時(shí)間內(nèi)求得較好的滿意解，展現(xiàn)出極大的優(yōu)越性.

菌群優(yōu)化是基于細(xì)菌群體的優(yōu)化行為而提出的一類(lèi)新型群體智能方法.早在20世紀(jì)中期，生物學(xué)家就通過(guò)顯微鏡觀察到細(xì)菌的移動(dòng)并非隨意，而是具有一定的規(guī)律.1960年，Alder深入研究了大腸桿菌的分子機(jī)制，提出了細(xì)菌的趨化性機(jī)理.1974年，Bremermann在文獻(xiàn)中指出了細(xì)菌趨化行為用于優(yōu)化的可能性[6].1990年Bremermann根據(jù)細(xì)菌內(nèi)部的反應(yīng)機(jī)制以及細(xì)菌與環(huán)境的相互作用機(jī)制提出了細(xì)菌趨化優(yōu)化模型，并將其用于神經(jīng)網(wǎng)絡(luò)訓(xùn)練[7].隨后，許多學(xué)者對(duì)細(xì)菌行為用于優(yōu)化展開(kāi)了研究，其中比較成功的細(xì)菌優(yōu)化算法有細(xì)菌趨化算法(bacterial chemotaxis algorithm, BC)[8]、細(xì)菌覓食算法(bacterial foraging optimization, BFO)[9]和近年來(lái)提出的磁性細(xì)菌算法(magnetotactic bacteria optimization algorithm, MBOA)[10]，而基于這些算法的改進(jìn)和應(yīng)用研究也一直未曾間斷.

以最有代表性的BFO算法為例，2000—2017年，在Web of Science數(shù)據(jù)庫(kù)以“bacterial foraging optimization”為關(guān)鍵詞可搜索到學(xué)術(shù)文獻(xiàn)781篇(數(shù)據(jù)截至2017年9月28日)，每年的文獻(xiàn)數(shù)量如圖1所示.由圖1可以看出，相關(guān)研究熱度一直穩(wěn)步攀升.從文獻(xiàn)的國(guó)度來(lái)看，主要集中在中國(guó)、印度、美國(guó)、英國(guó)和伊朗，如圖2所示.

圖1 歷年BFO算法相關(guān)文獻(xiàn)數(shù)量Fig.1 Quantityof literatures relevant to BFO algorithm in past few years

圖2 細(xì)菌覓食算法相關(guān)研究國(guó)家分布Fig.2 National distributingsituation of literatures relevant to BFO algorithm

與粒子群算法等成熟群體智能算法相比，基于菌群的優(yōu)化研究還處在初步階段.基本BFO算法的優(yōu)化能力也與標(biāo)準(zhǔn)PSO算法有一定差距.然而，與鳥(niǎo)群、魚(yú)群等其他生物群體相比，細(xì)菌個(gè)體結(jié)構(gòu)和行為簡(jiǎn)單，但群體種類(lèi)及特性多變，不同菌群之間的相互關(guān)系多樣且復(fù)雜，符合智能涌現(xiàn)的非線性、多樣性要求.在多層次群體建模上可能更具優(yōu)勢(shì).此外，菌群快節(jié)奏的生命演化周期也適合優(yōu)化模擬，值得進(jìn)一步深入研究.目前，國(guó)內(nèi)外關(guān)于菌群優(yōu)化的綜述文章較少，武林娟、高金鳳的兩篇綜述文章[11-12]均從算法理論、算法改進(jìn)、算法混合、算法應(yīng)用4個(gè)方面進(jìn)行了綜述，但分析較少，缺乏系統(tǒng)性.李娜等對(duì)細(xì)菌覓食算法的進(jìn)展進(jìn)行了回顧，但應(yīng)用部分的綜述較為簡(jiǎn)單，改進(jìn)建議也僅從改進(jìn)算法現(xiàn)有的3個(gè)操作著手[13].外文文獻(xiàn)也僅有幾篇關(guān)于BFO算法的綜述：其中1篇為Hernandez等在2013年CEC會(huì)議上的論文，集中討論BFO算法在約束數(shù)值優(yōu)化上的應(yīng)用[14]；另外2篇為牛奔等在2010年ICIC國(guó)際會(huì)議上的論文[15-16]，分別對(duì)BFO算法從背景、發(fā)展、應(yīng)用和挑戰(zhàn)4方面進(jìn)行了綜述.從圖1可以看出，近年來(lái)關(guān)于菌群優(yōu)化的研究也有大幅增長(zhǎng)，因此，筆者擬對(duì)近幾年的菌群優(yōu)化研究?jī)?nèi)容和發(fā)展方向進(jìn)行系統(tǒng)的梳理，以期為本領(lǐng)域的學(xué)者提供一個(gè)更為清晰的思路.

基于781篇文獻(xiàn)的標(biāo)題，筆者對(duì)其進(jìn)行了詞頻分析，去掉介詞以及“bacteria”“foraging”“optimization”“algorithm”等與BFO直接相關(guān)的單詞，再用高詞頻詞匯與“bacterial foraging optimization”做主題組合查詢，文獻(xiàn)數(shù)量排序如圖3所示.

圖3 相關(guān)文獻(xiàn)高頻關(guān)鍵詞Fig.3 High frequency key words in relevantliteratures

從關(guān)鍵詞組合的主題文獻(xiàn)數(shù)量來(lái)看，文獻(xiàn)的研究點(diǎn)主要集中在算法改進(jìn)和應(yīng)用上.而諸如“power”“parameter”“hybrid”“adaptive”“dynamic”“image”“structure”“PID”“economic”“multi objective”“operator”等關(guān)鍵詞也表明了算法改進(jìn)和應(yīng)用的主要方向和場(chǎng)景.下文將從基本菌群優(yōu)化方法、菌群優(yōu)化方法改進(jìn)研究和菌群優(yōu)化方法應(yīng)用研究3個(gè)方面展開(kāi)綜述，進(jìn)而探討菌群優(yōu)化方法的發(fā)展方向.

1 基本菌群優(yōu)化方法

1.1 BC

細(xì)菌趨化算法BC的早期研究是基于Berg、Brown和Dahlquist提出的細(xì)菌趨藥性微觀模型.在此基礎(chǔ)上，S. D. Müller等人結(jié)合最新研究，提出了BC算法[8].實(shí)際上，BC算法并非基于細(xì)菌群體，而是基于對(duì)細(xì)菌單個(gè)個(gè)體運(yùn)動(dòng)覓食行為的模擬.細(xì)菌不斷地感受它周?chē)沫h(huán)境變化并利用它過(guò)去的經(jīng)驗(yàn)和當(dāng)前狀態(tài)來(lái)調(diào)節(jié)下一步行動(dòng)策略，從而尋找最優(yōu)點(diǎn).在BC算法中，細(xì)菌對(duì)引誘劑的反應(yīng)運(yùn)動(dòng)遵守如下的假設(shè)：①細(xì)菌的運(yùn)動(dòng)軌跡是由一系列連續(xù)的直線組成，并且由運(yùn)動(dòng)方向和移動(dòng)距離兩個(gè)參數(shù)決定；②細(xì)菌在進(jìn)行下一步運(yùn)動(dòng)要改變運(yùn)動(dòng)方向時(shí)，向左轉(zhuǎn)和向右轉(zhuǎn)的概率相同；③細(xì)菌在各段相鄰軌跡間的夾角由概率分布來(lái)決定.

BC算法在迭代過(guò)程中，細(xì)菌僅利用它上一步或上幾步的位置信息來(lái)確定下一步的移動(dòng)，其實(shí)質(zhì)是一種近似梯度的隨機(jī)搜索方法.

1.2 BFO

2002年，模擬細(xì)菌群體的覓食和繁殖行為，Passino提出了細(xì)菌覓食優(yōu)化算法BFO[9].算法從初始化一組隨機(jī)解開(kāi)始，將細(xì)菌的位置表示為問(wèn)題的潛在解，通過(guò)模擬菌群的趨化(chemotaxis)、繁殖(reproduction)和遷徙(elimination-dispersal)行為來(lái)改變細(xì)菌的位置，從而進(jìn)行優(yōu)化.

原始BFO算法的結(jié)構(gòu)為3層循環(huán)嵌套結(jié)構(gòu).主要參數(shù)包括：遷移次數(shù)Ned、繁殖次數(shù)Nre、趨化次數(shù)Nc，分別控制遷徙、繁殖和趨化的次數(shù).此外，還有種群規(guī)模S、遷移概率Ped、最大前進(jìn)次數(shù)Ns等.

趨化操作是BFO算法的核心層.在趨化環(huán)節(jié)，細(xì)菌個(gè)體按照如下公式來(lái)更新其位置，

θi(j+1,k,l)=θi(j,k,l)+C(i)φ(j)；

(1)

(2)

式中：θi(j,k,l)代表第i個(gè)細(xì)菌個(gè)體在第l次遷徙、第k次繁殖、第j次趨化中的位置；C(i)代表細(xì)菌個(gè)體i的趨化步長(zhǎng)；φ(j)為第j次趨化中隨機(jī)生成的趨化方向，為一單位向量，如公式(2).當(dāng)細(xì)菌通過(guò)上述公式，位置得到改善時(shí)(如函數(shù)適應(yīng)度變優(yōu))，細(xì)菌個(gè)體可以按照上述公式繼續(xù)前進(jìn)一步，直到位置變差或達(dá)到最大前進(jìn)次數(shù)Ns.趨化操作可以實(shí)現(xiàn)細(xì)菌向更為有利的生存環(huán)境移動(dòng)，獲得較優(yōu)的位置.

每進(jìn)行Nc次趨化操作，就進(jìn)行一次繁殖操作.根據(jù)在這一輪趨化中的適應(yīng)度總和來(lái)進(jìn)行排序，適應(yīng)度總和較高的一半個(gè)體被認(rèn)為是獲得了充足的營(yíng)養(yǎng)，在原位置進(jìn)行分裂復(fù)制；另一半個(gè)體執(zhí)行消亡操作，從種群中移除.繁殖操作通過(guò)優(yōu)勝劣汰，來(lái)加快收斂.

每進(jìn)行Nre次繁殖操作，就進(jìn)行一次遷徙操作.所有細(xì)菌個(gè)體以概率Ped進(jìn)行遷徙，被移到解空間中一隨機(jī)位置.遷移操作可以在一定程度上避免算法陷入局部最優(yōu)，以免早熟.

Ned次遷徙操作完成后，算法結(jié)束，輸出最優(yōu)解.

此外，BFO算法還模擬了細(xì)菌的群聚行為.菌群覓食過(guò)程中，每個(gè)細(xì)菌個(gè)體除按照自己的方式搜索食物外，還會(huì)收到其他個(gè)體發(fā)出的引力信號(hào)，若是吸引力信號(hào)，則個(gè)體會(huì)游向種群中心；若是排斥力信號(hào)，則保持個(gè)體與個(gè)體之間的安全距離.細(xì)菌間聚集作用的數(shù)學(xué)表達(dá)式如公式(3)所示，

(3)

1.3 MBOA

磁性細(xì)菌優(yōu)化算法(magnetotactic bacteria optimization algorithm, MBOA)是哈爾濱工業(yè)大學(xué)莫宏偉等根據(jù)細(xì)菌的趨磁性提出的一種優(yōu)化方法[10].磁性細(xì)菌是對(duì)地球磁場(chǎng)和外部磁場(chǎng)敏感，可以沿著磁力線方向和氧氣濃度梯度方向運(yùn)動(dòng)的一類(lèi)特殊細(xì)菌的總稱.該趨磁現(xiàn)象最早由生物學(xué)家Blakemore于1975年發(fā)現(xiàn)[17].經(jīng)研究，這類(lèi)細(xì)菌具有趨磁性的原因是其體內(nèi)存在磁小體.磁小體的主要成分為磁鐵礦(Fe3O4等)，呈細(xì)小顆粒狀被包裹在蛋白膜中.該類(lèi)細(xì)菌通常包含多個(gè)磁小體組成的磁小體鏈，因而整個(gè)細(xì)菌類(lèi)似于生物磁針，能感應(yīng)磁力線并通過(guò)鞭毛擺動(dòng)沿其方向運(yùn)動(dòng).此外，磁小體鏈還能起到利于細(xì)菌能量收集、調(diào)劑胞內(nèi)氧化還原數(shù)值大小等作用.關(guān)于磁性細(xì)菌的研究在文獻(xiàn)[18]中有詳細(xì)論述，在此不作過(guò)多介紹.2013年，莫宏偉教授根據(jù)磁性細(xì)菌的特征提出了MBOA算法.在MBOA中，將每個(gè)具有磁小體的細(xì)菌看作解空間中的一個(gè)解.其求解過(guò)程為磁小體調(diào)整適應(yīng)磁場(chǎng)的過(guò)程，而最終具有最小凈磁能的磁小體即為所求的最優(yōu)解.算法首先初始化，在求解空間內(nèi)隨機(jī)生成一系列磁小體個(gè)體；其后，根據(jù)細(xì)胞間的相互作用計(jì)算磁小體力矩；接著，對(duì)磁小體實(shí)施拓展操作以獲得新的力矩；然后，對(duì)磁小體的力矩進(jìn)行調(diào)整替換，重復(fù)上述計(jì)算、拓展和調(diào)整過(guò)程直到算法滿足結(jié)束條件.

在原始MBOA的基礎(chǔ)上，莫宏偉團(tuán)隊(duì)及其他學(xué)者對(duì)MBOA進(jìn)行了一系列研究，提出了基于最優(yōu)個(gè)體指導(dǎo)的MBOA算法[19]、基于力矩遷移的MBOA算法[20]、趨磁性細(xì)菌多目標(biāo)算法[21]等，并將這些算法應(yīng)用于多峰優(yōu)化、約束優(yōu)化等數(shù)值優(yōu)化問(wèn)題以及移動(dòng)機(jī)器人路徑規(guī)劃等工程問(wèn)題[22-23].

2 菌群優(yōu)化方法改進(jìn)研究

結(jié)合上述菌群優(yōu)化的關(guān)鍵詞分析和其相關(guān)性，筆者將從參數(shù)與結(jié)構(gòu)改進(jìn)、多算法混合改進(jìn)、算子改進(jìn)和多目標(biāo)優(yōu)化改造等4個(gè)典型方面展開(kāi)菌群優(yōu)化方法改進(jìn)研究綜述.需要說(shuō)明的是，同一篇文獻(xiàn)也可能綜合用到下面的多種改進(jìn)方法.

2.1 參數(shù)與結(jié)構(gòu)改進(jìn)

參數(shù)改進(jìn)是群體智能算法改進(jìn)的常見(jiàn)方式[24].與粒子群算法、遺傳算法等經(jīng)典算法相比，原始BFO算法有Ned、Nre、Nc、Ped、Ns、C(i)等主要參數(shù)，聚集操作中還有4個(gè)參數(shù)，參數(shù)個(gè)數(shù)較多，不便于控制.

BFO算法參數(shù)較多的原因之一是采用了3層循環(huán)嵌套結(jié)構(gòu).如果Ned、Nre、Nc等參數(shù)設(shè)置不當(dāng)，可能在不合適的時(shí)間進(jìn)行繁殖、消亡與遷徙等操作，從而影響算法的收斂性.在一些改進(jìn)的菌群優(yōu)化算法中，去掉了趨化-繁殖-遷徙3層嵌套，將繁殖和遷徙作為趨化的并行步驟來(lái)進(jìn)行[25].基于該算法結(jié)構(gòu)的改進(jìn)算法可以去掉Ned、Nre、Nc等參數(shù).

BFO算法中另外一個(gè)重點(diǎn)參數(shù)改進(jìn)為趨化步長(zhǎng)C(i).現(xiàn)有的群體智能算法都是通過(guò)種群的進(jìn)化迭代來(lái)實(shí)現(xiàn)最優(yōu)解的改進(jìn).進(jìn)化迭代在算法執(zhí)行的過(guò)程中表現(xiàn)為種群中各個(gè)體在解空間中的位置更新.不同算法基于所模擬的不同生物行為，其具體更新公式各不相同.其中，主要包括兩大類(lèi)：基于相對(duì)位置的更新和基于絕對(duì)位置的更新，表1為幾種典型群體智能算法的更新公式.

表1 典型算法位置更新公式比較Tab.1 Comparison of position updating equation to several classic algorithms

由表1可以看出，GA、PSO、ABC等算法都采用的是基于相對(duì)位置的更新，通過(guò)個(gè)體之間的組合或差異來(lái)產(chǎn)生新的個(gè)體.原始的BFO和FA算法中采用了基于絕對(duì)位置的更新.BFO算法中，細(xì)菌個(gè)體在確定游動(dòng)角度后，沿該角度以步長(zhǎng)C(i)向前游動(dòng).FA算法中，隨機(jī)項(xiàng)α(rand-0.5)是以一個(gè)常數(shù)α乘以一個(gè)(-0.5，0.5)的隨機(jī)數(shù)[26].在基于相對(duì)位置的更新中，種群中的個(gè)體的前期差異大，算法趨向于全局搜索，后期差異小，算法趨向于局部開(kāi)發(fā)，能動(dòng)態(tài)地平衡算法的多樣性和收斂性.在基于絕對(duì)位置的更新中，個(gè)體更新中使用指定的步長(zhǎng).該類(lèi)方法在局部搜索上有一定的優(yōu)勢(shì)，但若步長(zhǎng)設(shè)置不當(dāng)，在前期可能搜索的范圍不夠，后期難以收斂,文獻(xiàn)[27]的研究證實(shí)了這一點(diǎn).為彌補(bǔ)上述菌群優(yōu)化中基于絕對(duì)位置更新帶來(lái)的缺點(diǎn)，很多學(xué)者對(duì)趨化步長(zhǎng)C(i)進(jìn)行了改進(jìn).其中，大部分學(xué)者采用了基于動(dòng)態(tài)下降或自適應(yīng)的步長(zhǎng).

作者在前期的研究中，拋棄了趨化-繁殖-遷徙3層嵌套，改為對(duì)細(xì)菌的生命周期進(jìn)行建模，根據(jù)細(xì)菌個(gè)體在優(yōu)化過(guò)程中的營(yíng)養(yǎng)獲取和流失動(dòng)態(tài)地進(jìn)行分裂、死亡和遷徙，并在趨化步長(zhǎng)線性下降的基礎(chǔ)上根據(jù)營(yíng)養(yǎng)值動(dòng)態(tài)地改變其步長(zhǎng)，取得了較好的效果[27].牛奔等提出了(structure-redesign-based bacterial foraging optimization, SRBFO)算法，將原始的BFO算法中3層嵌套改為單層循環(huán)，并重新設(shè)計(jì)了繁殖、消亡和遷徙操作，進(jìn)一步簡(jiǎn)化算法的結(jié)構(gòu)，在投資組合優(yōu)化的實(shí)驗(yàn)中證明了該算法優(yōu)于PSO算法[28].Tan等提出了一種自適應(yīng)結(jié)構(gòu)重構(gòu)的細(xì)菌覓食算法(adaptive structure-redesigned-based bacterial foraging optimization, ASRBFO)，在ASRBFO中，采用自適應(yīng)的趨化步長(zhǎng)，用個(gè)體的當(dāng)前位置、歷史最優(yōu)位置、所有細(xì)菌的平均位置等信息來(lái)計(jì)算細(xì)菌的趨化步長(zhǎng).通過(guò)該方法，算法收斂速度和精度優(yōu)于其他對(duì)比算法[29].在對(duì)BFO改進(jìn)的研究中，大多數(shù)文獻(xiàn)都有涉及對(duì)趨化步長(zhǎng)的改進(jìn).

2.2 多算法混合改進(jìn)

與其他優(yōu)秀算法的思想或算子結(jié)合也是算法改進(jìn)的一大途徑.自菌群算法提出以來(lái)，許多學(xué)者在這方面展開(kāi)了研究.

Manikandan等針對(duì)不同蛋白質(zhì)序列分析中多目標(biāo)多序列對(duì)比帶來(lái)的計(jì)算量大的問(wèn)題，將BFO算法和GA算法結(jié)合，提出一種BFO-GA算法來(lái)實(shí)現(xiàn)高效比對(duì).實(shí)驗(yàn)結(jié)果表明，該算法優(yōu)于多種傳統(tǒng)的序列對(duì)比算法以及ABC、PSO等經(jīng)典智能算法[30].Chen等結(jié)合BFO算法和PSO算法提出一種BFPSO算法，用于神經(jīng)模糊分類(lèi)器的參數(shù)優(yōu)化[31].該算法在局部搜索中采用BFO的趨化操作，在全局搜索中采用PSO的搜索方法，取得了較好的效果.Emre等將BFO算法中的趨化操作與差分進(jìn)化算法(differential evolution, DE)結(jié)合，提出一種趨化差分優(yōu)化算法，在CEC2014測(cè)試集上的測(cè)試結(jié)果表明，該算法優(yōu)于原始的BFO算法[32].杜鵬楨等提出一種混合蜂群算法的自適應(yīng)細(xì)菌覓食算法.在該算法中，借鑒人工蜂群算法的雇傭蜂行為，設(shè)計(jì)出一種雇傭蜂趨化算子.此外，在原趨化的基礎(chǔ)上提出自適應(yīng)步長(zhǎng)趨化算子.算法根據(jù)種群的多樣性在兩種趨化算子中進(jìn)行自適應(yīng)切換[33].Manjith將BFO算法和改進(jìn)的布谷鳥(niǎo)搜索算法(cuckoo search, CS)結(jié)合，用于解決認(rèn)知無(wú)線電的頻道估計(jì)誤差最小化問(wèn)題.測(cè)試結(jié)果表明，該算法得到的導(dǎo)頻序列優(yōu)于其他算法[34].Wu等提出一種BF-PSO-FSVCM模型，將BFO和PSO算法結(jié)合，用于優(yōu)化模糊支持向量機(jī)的未知參數(shù)，從而提高分類(lèi)器的精度，更好地鑒別肌電圖信號(hào)的疲勞狀態(tài)[35].

在算法混合的研究中，與遺傳算法和粒子群算法的混合居多.其他一些新興智能算法也有涉及.在算法混合中經(jīng)常利用BFO算法的框架或趨化算子.趨化算子“改進(jìn)則繼續(xù)試探一次”的思想可以較好地調(diào)整計(jì)算資源的分配，在潛在的最優(yōu)解附近加強(qiáng)局部搜索.

2.3 算子改進(jìn)

BFO算法的核心是趨化操作[36].因此算子改進(jìn)最多的是趨化算子的改進(jìn).在2.1節(jié)中已經(jīng)提到一些關(guān)于趨化步長(zhǎng)的改進(jìn).此外，還有一些研究是針對(duì)趨化算子中的翻轉(zhuǎn)方向或新個(gè)體生成公式的改進(jìn).

Yang等提出了一種BFOCC算法.該算法采用了新的趨化算子：每個(gè)細(xì)菌隨機(jī)選擇一個(gè)標(biāo)準(zhǔn)基向量作為趨化方向來(lái)游動(dòng)或翻轉(zhuǎn)，從而減少各維度之間的相互干擾.另外，該算法還引入了一個(gè)新設(shè)計(jì)的共軛算子來(lái)加強(qiáng)細(xì)菌之前的信息交換，提高算法的收斂性[37].Meng等在BFO的趨化操作中引入了變異因子，在每次迭代中，細(xì)菌個(gè)體以一定概率被選擇并進(jìn)行變異.經(jīng)測(cè)試，采用小波變異的方法效果最為理想.該改進(jìn)的算法被用于陣列綜合問(wèn)題[38].Hernandez等提出了一種改進(jìn)的菌群優(yōu)化算法用于四桿機(jī)構(gòu)的綜合優(yōu)化.該改進(jìn)的菌群優(yōu)化算法在趨化操作中引入了兩種游動(dòng)算子.其中，一種傾向于全局搜索，另一種則加強(qiáng)在細(xì)菌個(gè)體附近的鄰域搜索.通過(guò)這兩種游動(dòng)因子，細(xì)菌在搜索過(guò)程中能找到更好的解[39].Zhao等在趨化操作中引入混沌搜索算子來(lái)增強(qiáng)細(xì)菌個(gè)體的活躍水平，拓展其搜索空間，用以解決置換流水線調(diào)度優(yōu)化問(wèn)題[40].

除趨化算子外，也有一些學(xué)者對(duì)細(xì)菌覓食算法的繁殖、遷徙等其他算子進(jìn)行改進(jìn).

Svrakov對(duì)BFO算法的繁殖算子進(jìn)行了分析，將繁殖算子與進(jìn)化算法的選擇進(jìn)行了類(lèi)比.分析表明，一個(gè)穩(wěn)定的繁殖活動(dòng)有助于細(xì)菌的快速收斂[41].Mai等對(duì)BFO算法中的消亡-遷徙操作進(jìn)行了改進(jìn)，引入了一個(gè)自適應(yīng)的遷徙概率，根據(jù)細(xì)菌個(gè)體的適應(yīng)度來(lái)確定其是否遷徙.算法還在趨化移動(dòng)后加入了一個(gè)PSO算法的學(xué)習(xí)算子.實(shí)驗(yàn)表明改進(jìn)后的算法具有更好的收斂速度和收斂精度[42].Liu等針對(duì)BFO算法中遷徙操作隨機(jī)性太強(qiáng)這一缺點(diǎn)，引入了信息素來(lái)控制細(xì)菌的遷徙.此外，在繁殖算子中加入了柯西變異來(lái)增強(qiáng)算法的全局搜索能力.測(cè)試結(jié)果表明，該算法能提高收斂速度，并避免陷入局部最優(yōu)[43].

2.4 多目標(biāo)優(yōu)化改造

經(jīng)典群體智能算法提出之初大多用于單目標(biāo)優(yōu)化問(wèn)題.對(duì)其進(jìn)行改造使之能適用于多目標(biāo)優(yōu)化問(wèn)題也是算法改進(jìn)的一大方向.

Tan等人提出一種基于全面學(xué)習(xí)策略的多目標(biāo)細(xì)菌覓食算法，用于電力系統(tǒng)分配的多目標(biāo)優(yōu)化.算法通過(guò)非支配排序和擁擠距離來(lái)保持非支配解集的多樣性.此外，算法還采用了全面學(xué)習(xí)策略來(lái)增強(qiáng)BFO的搜索能力，并在繁殖操作中采用了基于健康值排序的方法來(lái)提高菌群的質(zhì)量[44].Zhou等建立了抽水蓄能水電站的導(dǎo)葉關(guān)閉計(jì)劃優(yōu)化模型.該模型綜合考慮單位轉(zhuǎn)速的上升速度,每個(gè)液壓?jiǎn)卧囟ü?jié)點(diǎn)的壓力以及各種復(fù)雜的液壓和機(jī)械約束等多個(gè)優(yōu)化目標(biāo)，采用了一種增強(qiáng)的細(xì)菌覓食優(yōu)化-重力搜索算法來(lái)對(duì)其進(jìn)行求解.該算法采用了種群重建、自適應(yīng)的選擇趨化算子及局部搜索策略，并使用外部存檔來(lái)保存精英解集，較好地解決了優(yōu)化問(wèn)題[45].

多序列對(duì)比問(wèn)題(multiple sequence alignment, MSA)是計(jì)算生物學(xué)和生物信息學(xué)中經(jīng)常遇到的一類(lèi)多目標(biāo)優(yōu)化問(wèn)題.Rani等提出多目標(biāo)細(xì)菌覓食算法(multi-objective bacterial foraging optimization, MO-BFO)對(duì)其進(jìn)行求解.測(cè)試結(jié)果表明，該多目標(biāo)細(xì)菌覓食算法優(yōu)于其他對(duì)比算法[46].牛奔等人提出一種多目標(biāo)菌群優(yōu)化算法，該方法綜合采用健康值排序和帕累托支配機(jī)制來(lái)實(shí)現(xiàn)多目標(biāo)優(yōu)化.此外，通過(guò)一定概率保留邊界非可行解來(lái)保持種群的多樣性.算法通過(guò)多樣性和總逼近距離來(lái)評(píng)估非支配前沿的優(yōu)劣，結(jié)果表明了該算法的有效性[47].在另一種多目標(biāo)菌群優(yōu)化算法中，牛奔等還將鄰域搜索引入到多目標(biāo)細(xì)菌優(yōu)化算法中，采用基于環(huán)形拓?fù)浜托切瓮負(fù)涞膬煞N鄰域搜索來(lái)提高非支配前沿的精度和多樣性[48].Yi等采用多目標(biāo)細(xì)菌覓食算法來(lái)解決最大化電流效率、最小化能量損耗和全氟化碳生成量的電解鋁生產(chǎn)優(yōu)化問(wèn)題.作者首先建立了一個(gè)面向任務(wù)的優(yōu)化框架，并采用并行細(xì)胞熵方法來(lái)評(píng)估非支配解集的進(jìn)化狀態(tài).該多目標(biāo)優(yōu)化方法采用基于非支配存檔進(jìn)化法和自適應(yīng)覓食方法來(lái)平衡優(yōu)化過(guò)程中非支配前沿的分布性和收斂性[49].Kaur提出了一種精英多目標(biāo)細(xì)菌優(yōu)化算法，該算法采用精英保持策略來(lái)求解多標(biāo)準(zhǔn)網(wǎng)格調(diào)度問(wèn)題.實(shí)驗(yàn)測(cè)試表明，算法優(yōu)于多目標(biāo)PSO算法和NSGA-Ⅱ等經(jīng)典多目標(biāo)優(yōu)化算法[50].

總的來(lái)說(shuō)，基于菌群的多目標(biāo)優(yōu)化方法在多目標(biāo)的處理上大多都借鑒了PESA-Ⅱ和NSGA-Ⅱ等經(jīng)典第二代多目標(biāo)優(yōu)化算法，例如精英外部存檔、用于擁擠距離的適應(yīng)度分配等，并在占優(yōu)機(jī)制、進(jìn)化策略等方面進(jìn)行了改進(jìn)補(bǔ)強(qiáng).

3 菌群優(yōu)化方法應(yīng)用研究

除數(shù)值優(yōu)化外，基于菌群的優(yōu)化方法還被應(yīng)用于許多工程優(yōu)化問(wèn)題中.排名第一的關(guān)鍵詞“power”即為其在電力系統(tǒng)中的應(yīng)用，“application”的詞頻也排名第四.其他關(guān)鍵詞“dynamic”“image”“PID”等高頻詞也展示了它在動(dòng)態(tài)優(yōu)化、圖像處理、PID控制優(yōu)化等工程領(lǐng)域中的應(yīng)用.

除“power”外，關(guān)鍵詞“dynamic”“economic”“PID”很大一部分指向的應(yīng)用領(lǐng)域也為電力系統(tǒng)的動(dòng)態(tài)經(jīng)濟(jì)調(diào)度(dynamic economic dispatch, DED)和PID穩(wěn)定性控制等優(yōu)化問(wèn)題.電力系統(tǒng)優(yōu)化是智能算法應(yīng)用的一個(gè)熱門(mén)方向[51]，前文提到的文獻(xiàn)[44-45]也均為電力系統(tǒng)中的應(yīng)用.

此外，Azizipanah綜合考慮電力系統(tǒng)的最優(yōu)動(dòng)態(tài)優(yōu)化問(wèn)題中存儲(chǔ)約束、禁止區(qū)域、閥點(diǎn)效應(yīng)等約束，建立了一個(gè)非線性、非凸、不平滑、多模態(tài)、變量相關(guān)、不可微的模型，采用細(xì)菌覓食算法-簡(jiǎn)化群優(yōu)化混合方法來(lái)對(duì)該問(wèn)題進(jìn)行求解[52].Krishan等提出一種混合的細(xì)菌覓食-差分算法，用于電力系統(tǒng)穩(wěn)定器的設(shè)計(jì)優(yōu)化.算法在較寬范圍的系統(tǒng)條件和操作下進(jìn)行了測(cè)試，以確保其魯棒性.特征分析及不同干擾下的時(shí)域響應(yīng)證明了它的有效性[53].Tripathy等將一種改進(jìn)的BFO算法用于存在多電力系統(tǒng)穩(wěn)定器和多可控串了聯(lián)補(bǔ)充電容器的多機(jī)電力系統(tǒng)Hopf分叉失穩(wěn)的參數(shù)控制優(yōu)化[54].Nasiruddin等將細(xì)菌覓食算法用于兩個(gè)地區(qū)整合的多源發(fā)電站的自動(dòng)發(fā)電機(jī)組控制[55].

除電力系統(tǒng)外，還有一些學(xué)者將菌群優(yōu)化算法用于動(dòng)態(tài)環(huán)境下機(jī)器人路徑規(guī)劃[56-57]、機(jī)器人沿墻導(dǎo)航控制[58]、車(chē)輛路徑規(guī)劃[59]、制造單元?jiǎng)討B(tài)調(diào)度問(wèn)題[60]、動(dòng)態(tài)投資組合優(yōu)化[61-62]、信息動(dòng)態(tài)路由優(yōu)化[63]等動(dòng)態(tài)優(yōu)化問(wèn)題.

在圖像處理領(lǐng)域，BFO算法在圖像分類(lèi)、邊緣處理、圖像配準(zhǔn)、圖像壓縮等技術(shù)問(wèn)題上也有廣泛的應(yīng)用.

文獻(xiàn)[64]在徑向基函數(shù)神經(jīng)網(wǎng)絡(luò)中整合了BFO算法，用于圖像分類(lèi)優(yōu)化，在對(duì)參數(shù)進(jìn)行系列調(diào)試后，該算法能有效且穩(wěn)健地解決圖像分類(lèi)問(wèn)題.Tang等利用改進(jìn)的BFO算法解決圖像處理中多級(jí)閾值處理問(wèn)題.在該算法中，趨化環(huán)節(jié)借鑒了PSO的算子來(lái)增強(qiáng)尋優(yōu)能力，在繁殖環(huán)節(jié)中采用了精英保存策略.通過(guò)最大化Tsallis閾值函數(shù)得到優(yōu)化解[65].Pan等人針對(duì)傳統(tǒng)邊緣處理算法依賴初值且可能產(chǎn)生不連續(xù)邊緣的問(wèn)題，提出了一種基于BFO的邊緣檢測(cè)算法用于細(xì)胞圖像的處理[66].Verma等采用BFO算法和最小核值相似區(qū)法構(gòu)建一種模糊系統(tǒng)用于圖像邊緣檢測(cè).其中，用BFO算法來(lái)優(yōu)化模糊隸屬函數(shù)和增強(qiáng)模糊算子的參數(shù)[67].Bermejo等將細(xì)菌覓食算法用于基于灰度的醫(yī)學(xué)圖像配準(zhǔn)(image registration, IR)問(wèn)題[68]，并對(duì)細(xì)菌覓食算法在圖像配準(zhǔn)的應(yīng)用進(jìn)行了深入研究，通過(guò)大量對(duì)比發(fā)現(xiàn)，細(xì)菌覓食算法在該問(wèn)題上優(yōu)于其他對(duì)比算法[69].Sanyal等將一種變種群的細(xì)菌覓食算法用于基于模糊矢量量化的圖像壓縮問(wèn)題.該算法能夠有效減少訓(xùn)練和重構(gòu)之間的平均失真問(wèn)題,采用變化的種群比原始BFO的固定種群更為有效[70].

在PID控制方面，如前文所述，BFO在電力系統(tǒng)的穩(wěn)定性控制、負(fù)載頻率控制、自動(dòng)電壓調(diào)節(jié)器穩(wěn)壓控制等問(wèn)題中有很多應(yīng)用.除此之外，菌群優(yōu)化方法也被應(yīng)用到很多其他控制問(wèn)題中.

Abdelkarim提出一種混合的細(xì)菌覓食-粒子群優(yōu)化算法，并將其用于耦合精餾過(guò)程中的解耦和控制參數(shù)優(yōu)化.時(shí)域結(jié)果分析表明，相對(duì)于傳統(tǒng)PID控制方法有顯著的改進(jìn)[71].Arya等采用細(xì)菌覓食算法對(duì)多區(qū)域互連傳統(tǒng)/重構(gòu)電力系統(tǒng)模糊控制器的增益進(jìn)行了優(yōu)化[72].Li為了改善可變風(fēng)量空調(diào)系統(tǒng)的變風(fēng)量性能，提出了一種基于細(xì)菌覓食算法的PID控制策略.首先建立一個(gè)非線性的PID控制模型并分析其參數(shù)，然后用BFO算法對(duì)參數(shù)進(jìn)行調(diào)整優(yōu)化[73].陳東寧等結(jié)合粒子群和細(xì)菌覓食算法，提出一種混合算法.采用粒子群的位置更新公式來(lái)指導(dǎo)菌群的趨化方向，并將其用于材料試驗(yàn)機(jī)電液位置伺服系統(tǒng)的PID控制器參數(shù)尋優(yōu)，取得了較好的效果[74].

此外，隨著近幾年機(jī)器學(xué)習(xí)和大數(shù)據(jù)技術(shù)的興起，菌群優(yōu)化在這些方面的應(yīng)用也大幅增加.以“bacterial foraging optimization”和“machine learning”作主題組合查詢一共有文獻(xiàn)30篇，全部為2007年之后的，其中2014—2017年20篇，占比66.6%.

Kora等采用混合的BFO和PSO算法，進(jìn)行心電圖信號(hào)的特征選擇，將特征值作為L(zhǎng)evenberg-Marquard神經(jīng)網(wǎng)絡(luò)分類(lèi)器的輸入，從而診察束支傳導(dǎo)阻滯，以進(jìn)行心臟疾病的診斷[75].Wang等人提出了一種離散的細(xì)菌覓食算法用于微陣列基因表達(dá)癌癥數(shù)據(jù)分類(lèi)中的特征選擇.針對(duì)基因表達(dá)癌癥數(shù)據(jù)因高維難以分類(lèi)的問(wèn)題，通過(guò)離散細(xì)菌優(yōu)化算法選擇合適的特征以進(jìn)行數(shù)據(jù)降維[76].Panda等提出一種自適應(yīng)交叉細(xì)菌覓食算法，采用自適應(yīng)的趨化來(lái)提高尋優(yōu)效率，并引入交叉因子來(lái)加強(qiáng)鄰域搜索.該算法被用于人臉識(shí)別，以進(jìn)行數(shù)據(jù)降維，從而獲得人臉識(shí)別分析數(shù)據(jù)中的最優(yōu)主成分[77].Wu等提出一種基于細(xì)菌覓食算法的混合高斯支持向量分類(lèi)機(jī)，用于肌電圖信號(hào)的疲勞分類(lèi).在這一過(guò)程中，用細(xì)菌覓食算法來(lái)進(jìn)行高斯支持向量機(jī)的參數(shù)優(yōu)化[78].

綜上，隨著細(xì)菌優(yōu)化算法的不斷改進(jìn)，其在工程問(wèn)題上的應(yīng)用也越來(lái)越多.

4 菌群優(yōu)化方法發(fā)展方向展望

從上述菌群優(yōu)化的算法改進(jìn)和應(yīng)用來(lái)看，在過(guò)去十幾年中，基于菌群優(yōu)化的研究有了長(zhǎng)足的進(jìn)步.參數(shù)改善、多算法混合、算子改善等將依然是算法改進(jìn)研究的重要方向.然而，現(xiàn)有研究也還有一些內(nèi)容有所欠缺，值得我們繼續(xù)深入研究.

細(xì)菌及菌群行為特征提取的多樣化.從菌群優(yōu)化研究來(lái)看，目前研究主要還是以BFO算法作為基礎(chǔ)展開(kāi)，其核心模擬的是大腸桿菌的趨化行為.除該趨化性和莫宏偉教授MBOA算法的趨磁性外，少有對(duì)細(xì)菌其他特性的模仿.而自然界中的細(xì)菌種類(lèi)繁多，行為特性也各不相同，如何繼續(xù)提取一些其他細(xì)菌或菌群的典型特征，如細(xì)菌的誘導(dǎo)劑分泌、pH值改造，菌群的拮抗、合作現(xiàn)象等以用于優(yōu)化，是細(xì)菌優(yōu)化方法改進(jìn)的一個(gè)突破方向.

多種群多層次建模.現(xiàn)有的菌群優(yōu)化方法大多是單一種群，采用相對(duì)統(tǒng)一的進(jìn)化規(guī)則和信息交互規(guī)則.從自組織的角度看，不利于智能的涌現(xiàn).利用上述菌群間協(xié)作、競(jìng)爭(zhēng)、拮抗等生物現(xiàn)象建立多層次的拓?fù)浣Y(jié)構(gòu)及信息交互，并在不同菌群內(nèi)部采用不同的進(jìn)化規(guī)則，從而保持一定的多樣性、非線性和種群進(jìn)化動(dòng)力，可能能夠更好地促進(jìn)智能的涌現(xiàn)，以達(dá)到優(yōu)化的目的.目前，一些學(xué)者已經(jīng)展開(kāi)了多種群粒子群算法的研究[79-80].而多菌群的優(yōu)化研究較少，尚在起步階段，值得進(jìn)一步深入研究.

基于相對(duì)位置的更新.在2.1節(jié)中已經(jīng)對(duì)比了基于相對(duì)位置更新和絕對(duì)位置更新的區(qū)別，也指明了基于絕對(duì)位置更新存在的不足.原始BFO算法采用基于絕對(duì)位置更新的趨化操作，雖然很形象地模擬了細(xì)菌趨化覓食的生物現(xiàn)象，但不利于算法的收斂.在2.1節(jié)的算法改進(jìn)中，有部分文獻(xiàn)借鑒了PSO、DE等算法的算子用個(gè)體的相對(duì)位置來(lái)確定趨化方向，并在趨化步長(zhǎng)上采用了一些自適應(yīng)的方法，但均為通過(guò)對(duì)趨化步長(zhǎng)的控制來(lái)平衡全局開(kāi)發(fā)和局部搜索，其本質(zhì)仍是絕對(duì)位置更新.合理改進(jìn)趨化操作，使之直接采用基于相對(duì)位置的更新方式，可能會(huì)使菌群優(yōu)化方法的尋優(yōu)能力得到新的飛躍.

應(yīng)用范圍的進(jìn)一步擴(kuò)展.從應(yīng)用領(lǐng)域的統(tǒng)計(jì)情況來(lái)看，目前菌群優(yōu)化方法在電力系統(tǒng)的優(yōu)化控制上應(yīng)用占比非常高，在一些新興領(lǐng)域也有一些運(yùn)用，但還不夠發(fā)散.隨著算法的優(yōu)化能力進(jìn)一步加強(qiáng)，可以預(yù)見(jiàn)的是，菌群優(yōu)化算法的應(yīng)用范圍也會(huì)越來(lái)越廣.

5 結(jié)論

對(duì)菌群優(yōu)化方法進(jìn)行了介紹，結(jié)合近幾年的相關(guān)文獻(xiàn)，從參數(shù)與結(jié)構(gòu)改進(jìn)、多算法混合改進(jìn)、算子改進(jìn)和多目標(biāo)優(yōu)化改造4個(gè)方面對(duì)算法改進(jìn)進(jìn)行了系統(tǒng)論述，并介紹了其在電力系統(tǒng)、動(dòng)態(tài)優(yōu)化、圖像處理、PID控制和機(jī)器學(xué)習(xí)等工程領(lǐng)域的應(yīng)用情況.結(jié)合現(xiàn)有研究的趨勢(shì)和存在的不足，對(duì)未來(lái)發(fā)展方向提出了展望.