崔 嘉，楊 林，胡衛(wèi)民

（1.海軍航空工程學(xué)院控制工程系，山東 煙臺 264001；2.海軍裝備部軍械保障部，北京 100841）

1 概述

細菌覓食優(yōu)化(Bacteria Foraging Optimization，BFO)算法是由Passino 于2002年提出的一種仿生隨機搜索算法，其生物學(xué)基礎(chǔ)是大腸桿菌在覓食過程中體現(xiàn)出來的智能行為。大腸桿菌自身有一個控制系統(tǒng)，該系統(tǒng)指導(dǎo)著其在尋找食物過程中的行為，包括趨化、復(fù)制和遷徙(又稱消除—驅(qū)散)等3個步驟[1-2]，并對每一次狀態(tài)的改變進行效果評價，進而為下一步活動提供信息。在這個系統(tǒng)的控制下，大腸桿菌將逐漸朝食物源的方向靠近。在BFO模型中，搜索過程通過營養(yǎng)分布函數(shù)來判斷搜索算法的優(yōu)劣，優(yōu)化問題的解對應(yīng)搜索空間中的細菌的狀態(tài)，即優(yōu)化函數(shù)的適應(yīng)度值。航空裝備修理定檢工作涉及多個車間、工種和工序，利用優(yōu)化算法對定檢修理工作進行有效的組織、精確高效調(diào)度，可實現(xiàn)各類保障資源的優(yōu)化組合與合理分配，降低保障維修費用。通過對BFO算法進行改進，并在航空裝備定檢維修任務(wù)調(diào)度擬實優(yōu)化系統(tǒng)中進行了應(yīng)用。

2 對原始BFO算法改進

2.1 細菌覓食行為中的群體改進

原始BFO算法搜索解空間時，采用的是個體間感應(yīng)機制，細菌每移動到新的位置，將根據(jù)式(1)計算個體間感應(yīng)值(或稱cell-to-cell 感應(yīng)值)[3]：

式中：Jcc(θi(j,k,l),θ (j,k,l))表示在第j次趨向操作、第k次復(fù)制、第l次遷徙操作時，第i個細菌的個體間感應(yīng)值之和；Jct c(θi,θ)表示第t個細菌和第i個細菌之間的群體感應(yīng)值；dattract和ωattract分別表示吸引因子的數(shù)量和釋放速率；hrepellant和ωrepellant分別表示排斥因子的數(shù)量和釋放速率；S表示細菌種群規(guī)模；p表示細菌搜索環(huán)境的維數(shù)；θmi表示第i個細菌所在位置的第m 維。

根據(jù)式(2)將感應(yīng)值疊加到細菌的適應(yīng)值上，這種基于個體間的感應(yīng)機制，有助于保持種群的多樣性，也增加了細菌群體跳出局部最優(yōu)的可能性。但也有可能使得接近最優(yōu)的細菌遭到驅(qū)散，導(dǎo)致優(yōu)化進程延緩。很多細菌聚集到全局最優(yōu)位置附近，但因為數(shù)量的增多導(dǎo)致該區(qū)域產(chǎn)生的排斥因子濃度升高，反而可能會將位置最好的細菌驅(qū)逐出最優(yōu)區(qū)域，造成精度下降。

借鑒粒子群優(yōu)化(Partical Swarm Optimization，PSO)算法[4-6]中粒子自我總結(jié)并向最優(yōu)粒子學(xué)習(xí)，向群體內(nèi)歷史最優(yōu)點靠攏的群體感應(yīng)機制，對BFO算法進行改進。在每次趨向操作完成后，進行類PSO的個體—群體感應(yīng)操作(或稱 cell-to-swarm 感應(yīng)值)：細菌個體感知周圍環(huán)境，試探搜索菌群中是否存在位置最好的細菌。如有，記憶其位置；否則，記憶自身當(dāng)前位置。下一次趨向操作時，細菌每移動到新的位置，就根據(jù)式(3)向記憶位置靠攏。

式(4)、(5)中：ω為慣性權(quán)重，使細菌保持運動慣性和擴展搜索空間的趨勢，有能力探索新區(qū)域；1C為學(xué)習(xí)因子，或稱加速度常數(shù)；?1是[0,1]區(qū)間內(nèi)均勻分布的偽隨機數(shù)；Vi為個體細菌i的速度。

經(jīng)過改進后，新的群體感應(yīng)機制允許細菌個體利用同伴的經(jīng)驗來指導(dǎo)自己的游動路線，這種信念吸引機制加快了在解空間中的全局搜索速度，同時也有助于細菌個體跳出局部最優(yōu)，以及避免了細菌從全局最優(yōu)區(qū)域逃逸的可能。

2.2 細菌趨向操作的可變步長改進

原始BFO算法中，細菌前移的計算方法如式(6)[8]：

細菌在生命周期中，可能產(chǎn)生基因突變，優(yōu)良的細菌可以具備較強的行動能力，其遷徙時進行的趨向行為可以幅度更大，這樣更有利于提高細菌的覓食速度。為了進一步加快搜索速度，提高優(yōu)化前期的全局搜索能力和優(yōu)化后期的局部搜索能力，可對BFO算法進行進一步改進，將趨向操作時的步長設(shè)置為動態(tài)調(diào)整值，而非固定值[7]，如式(7)：

式中：C (k,l)表示細菌第k次復(fù)制、第l次遷徙時的趨向操作步長；Lred表示初始趨向步長；n表示控制步長下降梯度的參數(shù)。

在優(yōu)化前期，即k+l較小時，C (k,l) 增大，提高了個體解空間移動能力，避免在局部范圍過多地消耗搜索時間。在優(yōu)化后期，k+l 逐漸增大，C (k,l)減小，使得個體在接近全局最優(yōu)點附近時的局部搜索能力增強，保證算法最終趨近全局最優(yōu)點。映射到細菌覓食行為中，相當(dāng)于加快了細菌的覓食能力和速度，從細菌群體角度看，是保留了優(yōu)秀細菌的基因，增強了細菌群的遷徙能力。

2.3 改進的快速細菌群游優(yōu)化算法設(shè)計

改進后的算法流程圖如圖1。

2.4 非線性模型的優(yōu)化問題分析

2.4.1 典型非線性模型

選取Shaffer函數(shù)作為典型非線性模型進行仿真，其描述為：

式中：x1,x2∈[?2,2]。選取z 作為適應(yīng)度函數(shù)，種群規(guī)模S=40，趨向次數(shù)Nc=100，最大前趨步數(shù)Ns=4，復(fù)制代數(shù)Nre=4，遷徙次數(shù)Ned=2，遷徙概率 Ped=0.25。仿真結(jié)果如圖2～4所示：

圖2 能量濃度地形圖(山谷=食物，山峰=有害物質(zhì))

圖3 細菌遷徙數(shù)為1時1～4代的運動軌跡

圖4 細菌遷徙數(shù)為2時1～4代的運動軌跡

2.4.2 仿真結(jié)果分析

由仿真結(jié)果可知，第1代細菌隨機散布在待優(yōu)化區(qū)域，進行趨向行為和群體聚集行為，細菌經(jīng)過篩選后繁殖進入第2代，并重復(fù)第1代的行為不斷朝向食物聚集，到第4代時，細菌已在小范圍區(qū)域聚集。遷徙數(shù)為2時，細菌在前4代的基礎(chǔ)上，先按遷徙概率執(zhí)行遷徙操作，再繼續(xù)搜索行為，到第2代時已基本聚集到最優(yōu)區(qū)域，后2代時這一區(qū)域不斷收斂，直至第4代已收斂到很小的區(qū)域，由此可見該算法的有效性。在遷徙數(shù)為2時，細菌已很好地收斂到最優(yōu)區(qū)域，可知該算法簡單且收斂速度快。

1)迭代次數(shù)測試。

以精度為0.000 01時所需要的迭代次數(shù)作為比較，結(jié)果如表1所示。

表1 迭代次數(shù)結(jié)果比較

2)收斂性測試。

設(shè)置最大迭代次數(shù)為100，每種算法運行100次，計算平均最優(yōu)解，結(jié)果如表2所示。

表2 平均最優(yōu)解比較

由以上數(shù)據(jù)分析可知，菌群優(yōu)化算法用于該模型的優(yōu)化問題的求解十分有效，對其進行的改進可明顯增強尋優(yōu)能力，有效避免陷入局部最優(yōu)。

3 BFO算法在任務(wù)調(diào)度優(yōu)化中的應(yīng)用

3.1 任務(wù)調(diào)度問題描述

一般地，對于有n個工件(對應(yīng)我航空兵修理廠則為飛機上的待修部件等)，m個機器(對應(yīng)我航空兵修理廠則為車間里的維修保障裝設(shè)備)的車間，在可行調(diào)度中確定每個工序的開始時間 sij和工序加工時間 tij，使總完工時間 fmax最小，即構(gòu)成了維修作業(yè)調(diào)度問題。即：

如果存在一個確定的工件排列陣MJ?，使得整個維修任務(wù)時間函數(shù)滿足式(8)，且與機器順序陣MG相容，則稱MJ?為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解[9]。

在裝備維修保障系統(tǒng)中，作戰(zhàn)部隊、陣地及裝備都有相對確定的維修保養(yǎng)機構(gòu)(如維修分隊(所)，它們的位置相對固定)，一個維修分隊可以保障若干部隊裝備的維修。進行飛機定檢維修的場所一般情況下是在維修小組所在的地點，通常為修理廠機棚或停機坪。因此，保障資源與故障裝備、維修小組的距離問題可以不予考慮。

利用式(9)描述的細菌覓食算法算子來表示某工件在某種機器加工的排列下加工所用的時間[10]：

式中：J (i,j,k,l)=J (i,j,k,l)+Jcc(θi(j,k,l))表示一個關(guān)于細菌覓食算子的工件排序序列，采用細菌覓食算法對該排列進行搜索，然后求得MJ?，這就是基于群體的細菌覓食算法在車間調(diào)度系統(tǒng)中的應(yīng)用。

使用改進后的細菌覓食優(yōu)化算法求解該類調(diào)度優(yōu)化問題的一般過程應(yīng)為：①對問題進行編碼；②執(zhí)行解碼策略；③設(shè)計評價函數(shù)，產(chǎn)生初始解群體；④利用群體感應(yīng)機制，進行全局尋優(yōu)。

3.2 問題的編碼

采用基于操作的編碼策略，將每個可行解用n×m個代表操作的編號組成，構(gòu)成符合工藝約束條件的所有操作的一個排列，編碼序列中的數(shù)字表示待修部件的編號。待修部件i的第j次出現(xiàn)，表示待修部件i的第j個操作或第j 道工序(i=1,2,???,n;j=1,2,???,m)。由于在編碼時就考慮到了工藝約束，因此在對編碼進行置換變換時，可以得到可行解。表3給出了典型的3×3調(diào)度問題的工藝約束，圖5給出了一個編碼示例[11]。

表3 3×3 車間調(diào)度問題工藝約束

在表3給出的工藝約束下，設(shè)一個可行解[3 1 1 2 1 3 2 2 3]，圖5所示編碼對應(yīng)的工序序列為圖6。

3.3 解碼策略

對于生成的可行解，如果要應(yīng)用于調(diào)度問題實際，則需要將其轉(zhuǎn)換成對應(yīng)的可行活動調(diào)度，這個過程稱為解碼。一個可行解可以解碼出多種調(diào)度，即一個操作序列對應(yīng)多個調(diào)度方案，通過對解碼過程進行優(yōu)化，則可以從操作序列中得到更優(yōu)的調(diào)度方案[12]。

優(yōu)化方法：判斷當(dāng)前操作是否可插入已存在的空閑段中，如果可進行插入，則會在很大程度上縮小可行調(diào)度所消耗的時間，從而求得最優(yōu)或準(zhǔn)最優(yōu)調(diào)度方案。

3.4 BFO個體搜索策略應(yīng)用

細菌個體在覓食過程中，依據(jù)自身的信息來決定其搜索方向的操作(基于個體的搜索策略)具體步驟為：

1)確定細菌群體中將要進行自身搜索的個體細菌I。

2)在當(dāng)前個體代表的可行解的編碼序列上隨機選定兩個位置，稱這兩個位置之間的編碼序列區(qū)間為穩(wěn)定區(qū)。穩(wěn)定區(qū)中的各個操作順序(即編碼)在本次搜索過程中保持不變，相當(dāng)于此次搜索時隨機選定的方向不變。

3)該個體所標(biāo)識的調(diào)度序列被分為3段，除中間的穩(wěn)定區(qū)外，其兩側(cè)的操作序列區(qū)間被稱為置換區(qū)間A和置換區(qū)間B。在這兩個置換區(qū)間上分別進行序列重新隨機排列，即分別對區(qū)間A和區(qū)間B 進行置換操作。經(jīng)過置換后，相當(dāng)于個體細菌按照事先選定的方向前進了一步。由于采用了基于操作的編碼方式，因此隨機置換操作后得到的編碼序列依然是可行解。

4)對個體細菌的當(dāng)前位置進行適應(yīng)度評價。如果新位置更優(yōu)，則認(rèn)為這一次的前進改變是正確的，用新位置上的個體替換掉原個體，相當(dāng)于原個體進行了一次位移。反之，個體回到原來位置，即取消本次的前進操作。

5)當(dāng)前個體細菌停頓。此時其面臨兩種選擇，一是重新選定一個隨機方向，在此進行基于個體的搜索，二是個體馬上停止搜索，調(diào)度系統(tǒng)跳至下一個進行搜索操作的個體細菌，本輪算法結(jié)束。

3.5 改進的群體感應(yīng)搜索策略

基于群體感應(yīng)機制所進行的改進搜索策略，具體步驟為：

1)確定細菌群體中目前位置最優(yōu)的個體 Ic_best，存儲其位置和適應(yīng)度值。

2)確定細菌群體中將要進行搜索的個體細菌I。

3)在最優(yōu)個體 Ic_best的序列中，隨機選定一個編號 Jrand(即工件號)。將來產(chǎn)生的新個體需要保證該編號的開始加工順序與在最優(yōu)個體上的位置相同。

4)遍歷最優(yōu)個體 Ic_best，確定該編號 Jrand在最優(yōu)個體中的位置J

P。5)開始對個體細菌I 進行調(diào)整。遍歷當(dāng)前個體I，找到序列中編號 Jrand的起始位置(即第Jrand號工件在當(dāng)前序列中進行第1 道加工工序時的位置)，將其與位置J

P的編號進行置換。6)對個體細菌的當(dāng)前位置進行基于個體的評價。

7)對個體細菌的當(dāng)前位置進行基于群體的評價。與細菌群體中目前位置最優(yōu)的個體 Ic_best相比，如果當(dāng)前個體I的新位置更優(yōu)，則認(rèn)為這一次的前進改變是使得當(dāng)前個體移動到了群體最優(yōu)的位置，于是最優(yōu)個體細菌更新為當(dāng)前個體細菌的位置，群最優(yōu)適應(yīng)度值也相應(yīng)進行更新。反之，不做任何操作。

8)當(dāng)前個體細菌停頓。此時其面臨兩種選擇，一是重新選定一個隨機方向，在此進行基于個體的搜索，二是個體馬上停止搜索，調(diào)度系統(tǒng)跳至下一個進行搜索操作的個體細菌，本輪算法結(jié)束。

4 算法實現(xiàn)

圖7為使用改進的細菌覓食算法作為任務(wù)優(yōu)化調(diào)度算法庫的處理流程。

圖7 任務(wù)優(yōu)化調(diào)度算法庫的處理流程

利用該算法庫，對實際問題進行驗證。工序信息如表4所示。

表4 某型飛機400 h 定檢工作部分工序

對算法進行了50次運算，均收斂在f (Tj?)=17，尋優(yōu)結(jié)束后，得到的最優(yōu)工序序列為

作業(yè)路線如表5所示，圖8為對應(yīng)的甘特圖。

表5 作業(yè)路線

圖8 調(diào)度結(jié)果甘特圖

5 結(jié)束語

對細菌覓食優(yōu)化算法進行了改進，并將其應(yīng)用于航空裝備定檢修理的任務(wù)優(yōu)化調(diào)度系統(tǒng)中，該系統(tǒng)可建立較為完整的飛機定檢維修任務(wù)模型，能夠有效求解維修任務(wù)的動態(tài)調(diào)度問題，并實現(xiàn)對維修保障資源的優(yōu)化組合與合理分配。

[1]MISHRA S.A hybrid least square-fuzzy bacteria foraging strategy for harmonic estimation[J].IEEE Trans.on Evolutionary Computation,2005,9(1)∶61-73.

[2]PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[R].IEEE Control System Magazine,2002,22(3)∶52-67.

[3]DATTA T,MISRA I S.Improved adaptive bacteria foraging algorithm in optimization of antenna array for faster convergence[J].Progress in Electromagnetic Research C,2008,1(1)∶143-157.

[4]KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.NewYork,1995∶1942-1948.

[5]EBERHART R C,KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the 6th international symposium on micro machine and human science.Nagoya,Japan,1995∶39-43.

[6]SHI Y H,EBERHART R C.A modified particle swarm optimizer[C]//IEEE International Conference on Evolutionary Computation.Anchorage,Alaska,USA,1998∶69-73.

[7]儲穎,糜華,紀(jì)震,等.基于粒子群優(yōu)化的快速細菌群游算法[J].數(shù)據(jù)采集與處理,2010,25(4)∶442-448.

[8]DAS S,BISWAS A,DASGUPTA S,et al.Bacterial foraging optimization algorithm∶theoretical foundations,analysis,and applications[J].Foundations of Comput Inte.,2009,3∶23-55.

[9]王書鋒,鄒益仁.車間作業(yè)調(diào)度技術(shù)問題簡明綜述[J].系統(tǒng)工程理論與實踐,2003,23(1)∶49-50.

[10]王文耀,涂海寧,夏芳臣,等.基于細菌覓食算法車間調(diào)度系統(tǒng)的研究[J].現(xiàn)代制造技術(shù)與裝備,2009(2)∶7-8.

[11]梁艷春.群智能優(yōu)化算法理論與應(yīng)用[M].北京∶科學(xué)出版社,2009∶157-162.

[12]張娜.細菌覓食優(yōu)化算法求解車間調(diào)度問題的研究[D].長春∶吉林大學(xué),2007.