改進的細菌覓食算法在航空裝備維修任務調度優化中的應用

崔 嘉，楊 林，胡衛民

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

1 概述

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

2 對原始BFO算法改進

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

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

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

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

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

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

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

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

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

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

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

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

2.3 改進的快速細菌群游優化算法設計

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

2.4 非線性模型的優化問題分析

2.4.1 典型非線性模型

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

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

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

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

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

2.4.2 仿真結果分析

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

1)迭代次數測試。

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

表1 迭代次數結果比較

2)收斂性測試。

設置最大迭代次數為100，每種算法運行100次，計算平均最優解，結果如表2所示。

表2 平均最優解比較

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

3 BFO算法在任務調度優化中的應用

3.1 任務調度問題描述

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

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

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

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

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

使用改進后的細菌覓食優化算法求解該類調度優化問題的一般過程應為：①對問題進行編碼；②執行解碼策略；③設計評價函數，產生初始解群體；④利用群體感應機制，進行全局尋優。

3.2 問題的編碼

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

表3 3×3 車間調度問題工藝約束

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

3.3 解碼策略

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

優化方法：判斷當前操作是否可插入已存在的空閑段中，如果可進行插入，則會在很大程度上縮小可行調度所消耗的時間，從而求得最優或準最優調度方案。

3.4 BFO個體搜索策略應用

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

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

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

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

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

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

3.5 改進的群體感應搜索策略

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

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

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

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

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

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

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

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

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

4 算法實現

圖7為使用改進的細菌覓食算法作為任務優化調度算法庫的處理流程。

圖7 任務優化調度算法庫的處理流程

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

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

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

作業路線如表5所示，圖8為對應的甘特圖。

表5 作業路線

圖8 調度結果甘特圖

5 結束語

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

[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].數據采集與處理,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]王書鋒,鄒益仁.車間作業調度技術問題簡明綜述[J].系統工程理論與實踐,2003,23(1)∶49-50.

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

[11]梁艷春.群智能優化算法理論與應用[M].北京∶科學出版社,2009∶157-162.

[12]張娜.細菌覓食優化算法求解車間調度問題的研究[D].長春∶吉林大學,2007.