改進型細菌覓食算法求解FJSP問題?

王新剛 衣鵬飛

1 引言

車間作業(yè)調度問題（Job-shop Scheduling Problem，JSP）一般可以描述為優(yōu)化作業(yè)的加工順序，然后使生產(chǎn)資源得到優(yōu)化配置的過程，是典型的NP-hard問題［1］。柔性作業(yè)車間調度問題（Flexible Job-shop Scheduling Problem，F(xiàn)JSP）是JSP 的擴展，其除了考慮待加工工序外，還允許一個工序可以在有能力加工的多臺機器中選擇，提高了資源柔性，減少了資源約束，擴大了解的范圍，F(xiàn)JSP成為比JSP更加復雜的組合優(yōu)化問題［2］。由于柔性作業(yè)車間更加符合實際的生產(chǎn)環(huán)境，因此研究FJSP具有重要的理論意義和實際價值。

在FJSP作業(yè)中，求解過程中要經(jīng)過大規(guī)模的可行性檢驗以保證解的可行性，直接影響算法的效率和應用性能，近年來，國內外很多學者利用多種智能優(yōu)化算法對FJSP進行優(yōu)化求解。G.Moslehi將改進的粒子群優(yōu)化算法用于求解具有柔性特征的多目標作業(yè)車間調度問題。G Waligora等將模擬退火算法用于求解多目標的調度問題中，取得了不錯的效果［3］。趙琴研究了排隊論在車間調度中的應用，并給出了詳細的理論依據(jù)和分析［4］。劉紅軍等提出了一種新型的優(yōu)化遺傳算法，該算法將模擬退火策略和禁忌搜索的思想融入到遺傳算法中提出了模擬退火交叉機制和禁忌搜索變異機制，適合于求解車間調度問題［5］。

BFO算法是由Passino提出的模擬大腸桿菌覓食行為的新的進化計算技術［6］。本文提出一種改進的BFO算法，重點對趨化操作的運動步長以及翻轉方向進行了改進，設計了自適應步長在三種情況下的變化值，并加強全局最優(yōu)位置與個體最優(yōu)位置在翻轉方向上的引導，避免算法早熟現(xiàn)象的發(fā)生。將IBFO算法運用到解決FJSP問題中進行仿真試驗。通過與標準細菌覓食算法和改進遺傳算法（Improved Genetic Algorithm，IGA）在柔性車間調度應用中的計算結果進行對比分析，驗證了算法的進步性。

2 FJSP問題描述

FJSP問題是一種特殊的作業(yè)車間調度問題，相對于傳統(tǒng)車間調度問題，待加工工件的每一道工序都在可選擇的一臺或多臺機器上加工，不再有機器約束的局限。

假設加工車間內有 J=(J1,J2,…Ji,Jn)個工件和M=(M1,M2,…Mi,Mn)臺機器，每個工件有多道工序，其中Oij表示Ji工件對應的第j道工序。根據(jù)機器的占有情況，F(xiàn)JSP的調度方法有兩種，分別為完全柔性作業(yè)車間調度和路徑柔性作業(yè)車間調度。若各工件的每道工序選擇只能選擇機器集中的部分機器進行加工，則稱之為部分路徑柔性車間調度；若各工件的每道工序通過所有機器完成加工，則稱之為完全路徑柔性車間調度。兩種調度情況分別如表1、表2所示，其中數(shù)字表示工序Oij在機器Mi上的加工時間，“—”表示工序Oij不能在機器Mi上加工。以工件J1為例，該工件的加工工序為（O11，O12，O13），在完全柔性調度中，J1的三個工序均可以在4臺機器上加工，其中第一個工序的加工時間分別為：1，3，4，6；而在部分柔性調度中，該工序只能在M1和M2兩臺機器上加工，加工時間為3，6。所有機器可以加工任意工件的所有工序并不符合實際操作，相對而言，部分柔性調度方式更適合實際的加工系統(tǒng)。

表1 完全柔性調度

表2 部分柔性調度

3 FJSP問題的優(yōu)化模型

將總任務的最大完成時間作為優(yōu)化目標，設定目標函數(shù)如下：

Cmax為調度任務的最大完成時間，Cij為工序Oij的完工時間。以下為優(yōu)化目標的約束條件：

式（3）限定兩個工件不能同時在同臺機器上加工。其中，pijk為工序Oij在機器k上加工所需要的時間，Xijk為工序分配機器的決策變量。

Yhgij為決定工序先后順序的決策變量。

式（4）限定一道工序只能在一臺機器上完成。式（5）、（6）限定決策變量的取值范圍。

4 BFO算法簡介

BFO算法是從生物的覓食行為中抽象出來的算法，首先確定初始解群體，通過適應度函數(shù)判斷個體和群體位置的優(yōu)劣，迭代運算直到達到收斂條件，算法停止。將細菌的覓食過程描述為趨向性、復制和遷移3個操作過程［7］。

趨化操作過程指細菌在解空間域內按照一定的規(guī)則進行搜索，并依據(jù)適應度進行尋找和調整行進方向的過程。趨化行為包括翻轉和游動兩個過程。翻轉指細菌在原地隨機選擇一個前進方向的行為；游動指細菌沿著翻轉方向或者上一次的運動方向前進，直到當前適應值低于前一步適應值，或者達到游動步數(shù)閾值。通過多次翻轉和游動，細菌向目標解方向游動，最終尋找到最優(yōu)解。趨化操作主要是在局部搜索最優(yōu)解的過程，是算法的核心操作，決定著整個算法的尋優(yōu)精度［8］。

設菌群規(guī)模是 S，用 D 維向量 Pi=（Pi1，Pi2，…，PiD）表示第i個細菌的信息，細菌i每一步趨化操作后的位置更新公式為

其中：表示細菌i在第j次趨化操作第k次復制操作第l次遷徙操作后的位置，即細菌i在搜索空間中的一個候選解。C（i）為細菌i游動的單位步長；Δ(i)為［-1，1］的為細菌i翻轉后選擇的一個隨機角度矢量，φ()j為Δ(i)的標準化函數(shù)。

復制操作：當細菌完成設定的趨向性次數(shù)，后，細菌將進行分裂，這個操作主要模擬了細菌個體優(yōu)勝劣汰的繁殖過程。設細菌種群大小為N，F(xiàn)i（j，k，l）為個體i的適應度值，先對整個種群的適應度進行降序排列，適應度值較大的前N/2個個體保留下來，并進行無差異性分裂為二，后面的適應度較低的2/N個個體被淘汰掉，這樣一次復制操作完成后，保證了細菌種群大小不變［9］。

遷移操作：為了提高算法的全局搜索能力，當一個問題的解空間存在多個極值點時，由于細菌的群聚性，算法容易陷入局部極值。這個過程是用新的個體來代替原有的個體，不同于復制操作，遷移操作是按照一定的概率p而發(fā)生的，當某個細菌符合遷移的條件時，該細菌將被隨機分配到解空間中去［10］。

5 趨化操作的改進

5.1 細菌趨化步長的改進

傳統(tǒng)算法中采用固定趨化步長，而BFO算法是一個動態(tài)尋優(yōu)過程，每進行一次趨向操作，細菌的活性就會有一定比例的下降。步長越大越有可能會錯過最優(yōu)解，步長過小反而會過早陷入局部最優(yōu)。隨著趨化次數(shù)的增加，步長應該做出合適的調整，才能保持算法的搜索效率［11］。

將細菌趨化步長進行自適應改進：細菌i所在區(qū)域的擁擠度，由搜索區(qū)間內的個體數(shù)量和搜索區(qū)間長度決定，crowd=n/len；Δtj=cs(i)(j-1,k,l)-cs(i)(j,k,l)表示細菌i第j次趨化，第k次復制，第l次遷移的適應值與第j-1次趨化，第k次復制，第l次遷移的適應值之間的差值，步長共分三次變化，搜索前期處于全局尋優(yōu)階段，周圍細菌數(shù)量稀少時，說明在一定范圍內營養(yǎng)不夠充分，將趨化補償設置為較大值，有利于全局尋優(yōu)，當尋找到擁擠度大的范圍，則進入局部尋優(yōu)狀態(tài)，將步長設小，以免錯過最優(yōu)解。

當擁擠程度過大并且個體適應值的增長率逐漸變小時，將步長慢慢調大，以免陷入局部尋優(yōu)。計算方法如下：

其中，Ni表示當前已經(jīng)執(zhí)行的趨化次數(shù)，N表示趨化總次數(shù)，cmax表示最大趨化步長，cmin分別表示最小趨化步長，?為預設定閾值。

5.2 翻轉方向的改進

在趨化過程中，記錄個體的最優(yōu)位置即個體趨化過程中適應值最高的位置，以及種群最優(yōu)位置，即適應度最高的個體所在的位置。一般認為種群最優(yōu)個體周圍的環(huán)境營養(yǎng)更豐富，在標準細菌算法的翻轉操作中，細菌的翻轉方向過于隨機，無法體現(xiàn)細菌群體在實際環(huán)境中的相互影響，因此本文提出通過兩個因子來引導細菌個體的翻轉方向：個體最優(yōu)位置Pibest和種群最優(yōu)位置Pgbest，細菌i向種群最優(yōu)個體學習到的翻轉方向為

細菌i自身經(jīng)過的最優(yōu)位置對其引導的翻轉方向為

結合兩個方向因子的引導，細菌i在第j次趨化操作后的翻轉方向為

Pi表示細菌當前所在位置，Prand表示隨機方向向量，r1+r2+r3=1。

6 仿真試驗

6.1 算法性能分析

為了驗證改進BFOA算法的有效性，本文對FJSP的標準算例Kacem的5個標準問題和Benchmark的5個經(jīng)典問題進行了試驗，并與標準BFOA算法和改進遺傳算法（IGA）的試驗結果進行了對比。本文的仿真實驗環(huán)境：硬件，Intel（R）Core（TM）i5-34700 3.20GHz雙核CPU，4.00GB內存；軟件，操作系統(tǒng)為Windows 7，編程平臺為Matlab。

本文通過多次試驗取得的最優(yōu)參數(shù)值為：細菌規(guī)模S=100，趨化次數(shù)NC=150，復制次數(shù)Nre=10和遷移／驅散次數(shù)Ned=16，趨化步長初始值設為0.15；遺傳算法參數(shù)設置為：交叉概率0.9，變異概率0.1。算法對每一個算例均獨立運行10次，計算結果見表3，cmax為多次實驗得到的最優(yōu)值，Ave（c）為平均值。

表3 算例實驗結果

從表中可以看出，使用本文算法得到的最優(yōu)解，除了算例MK05外，其余算例所得到的目標函數(shù)值均優(yōu)于或等于另外兩種算法，對于MK05這種大規(guī)模調度問題，雖然未找到最優(yōu)解，但是平均解的值小于前兩種算法，對于大規(guī)摸調度問題Kacem4和Kacem5，算法同樣取的了比較理想的效果。因此，本文算法求解性能優(yōu)于其他兩種算法，雖然對于大柜摸調度問題上表現(xiàn)有些不穩(wěn)定，但正確率還是比其他算法高一些。

6.2 實例驗證

采用表中第一個Benchmark算例MK01進行驗證，機器數(shù)為6臺，工件數(shù)為10臺，分別使用三種算法求解，對于該算例，在迭代次數(shù)200內，改進算法和IGA算法都能搜索到最優(yōu)解38，而對與標準BFOA算法搜索到的解為41，圖1為三種算法的收斂曲線，從圖中可以看出，雖然前兩種算法都能得到最優(yōu)解，但IGA算法的收斂速度明顯比改進算法的速度慢，改進算法在迭代30次后就找到了最優(yōu)解，而IGA算法在迭代70次后才得到最優(yōu)解，因此本文算法可以快速尋到最優(yōu)解。圖2為本文算法的甘特圖，用來表示在收斂過程中算法所得到的調度方案，Y軸為機器編號，X軸為執(zhí)行時間，小矩形中的數(shù)字表示“工件號-工序號”。

圖2 MK01調度甘特圖

7 結語

BFO算法是一種新興的優(yōu)化算法，然而原始的算法由于缺乏靈活性使得收斂速度慢、尋優(yōu)準確率不高。本文通過深入分析細菌覓食的特性，閱讀了大量相關文獻，結合多方面研究，對細菌覓食算法進行了改進，并將其應用到FJSP中尋找最優(yōu)解的問題上。與傳統(tǒng)算法相比，本文方法尋優(yōu)能力更加準確。與改進遺傳算法相比，改進的方法減少了迭代次數(shù)，大大縮短了求解時間。但是鑒于BFO算法的程序運行略慢，參數(shù)眾多，目前研究重點主要放在單目標優(yōu)化上，對于求解組合優(yōu)化問題上需要加強研究。

［1］崔靜靜，孫延明，車蘭秀，等.改進細菌覓食算法求解車間調度問題［J］.計算機應用與研究，2011，28（9）：3324-3326.

CUIJingjing，SUNYanming，CHELanxiu，et al.The modified bacterial foraging algorithm shop scheduling problem［J］.Computer Application Research，2011，28（9）：3324-3326.

［2］金花，寧濤，劉芳.改進細菌覓食算法求解多目標FJSP問題［J］.化工自動化及儀表，2015，42（6）：665-668.

JINHua，NINGTao，LIUFang，et al.The modified bacterial foraging algorithm to solve multi-objective FJSP problem［J］.Chemical Industry Automation and Instrumentation，2015，42（6）：665-668.

［3］G.Waligora.Simulated Annealing and Tabu Search for Discrete-Continuous Project Scheduling with discounted Cash Flows［J］.RAIRO-Operations Research，2014，38（6）：21-25.

［4］趙琴.排隊論在在車間調度中的應用［D］.蘭州：蘭州理工大學，2013.

ZHAO Qin.Queuing theory in the application in the shop scheduling［D］.Lanzhou：Lanzhou University of Technology，2013.

［5］劉紅軍，趙帥.一種基于混合遺傳算法的車間生產(chǎn)調度的研究［J］.制造業(yè)自動化，2011，33（6）：33-35.

LIU Hongjun，ZHAO Shuai.A hybrid genetic algorithm based on the research of workshop production scheduling［J］.Manufacturing Automation，2011，33（6）：33-35.

［6］G.Moslehi，M.Mahnam.A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search［J］.International Journal of Production Economics，2011，39（8）：14-22.

［7］楊大煉，李學軍，蔣玲莉，等.一種細菌覓食算法的改進與應用［J］.計算機工程與應用，2012，48（13）：31-35；

YANGDalian，LIXuejun，JIANGLingli，et al.A bacterial foraging algorithm improvement and application［J］.Computer Engineering and Application，2012，48（13）：31-35.

［8］Shiv P，Deo PV.A Hybrid GABFO Scheduling for Optimal Makespan in Computational Grid［J］.International Journal of Applied Evolutionary Computation，2014，5（3）：57-83.

［9］張利平.作業(yè)車間預反應式動態(tài)調度理論與方法研究［D］.武漢：華中科技大學，2013.

ZHANF Liping.Job-shop pre reactive dynamic scheduling theory and method research［D］.Wuhan：Huazhong University of Science and Technology，2013.

［10］姜建國，周佳薇，鄭迎春，等.一種雙菌群細菌覓食優(yōu)化算法［J］.深圳大學學報，2014，31（1）：43-51.

JIANG Jianguo，ZHOU Jiawei，DENG Yingchun，et al.A double bacteria bacterial foraging optimization algorithm［J］.Journal of Shenzhen University，2014，31（1）：43-51.

［11］HMIDA A B，HAOUARI M，HUGUET M J，et al.Discrepancy search for the flexible job shop scheduling problem［J］.Computers and Operations Research，2010，37（12）：2192-2201.