改進貓群算法求解置換流水車間調度問題

裴小兵，于秀燕

（天津理工大學 管理學院，天津 300384）

置換流水車間調度問題(permutation flow shop scheduling problem，PFSP)是智能制造的核心問題之一，具有很重要的工程應用價值。研究表明，該問題屬于NP難題[1](non-deterministic polynomial-time hard，NP)。常見的PFSP求解方法可分為：精確算法、啟發(fā)式算法[2]等。啟發(fā)式算法能夠快速求得問題的可行解，但這些算法結構比較復雜，求解最優(yōu)解比較困難。

在有限的資源條件下，對PFSP的優(yōu)化可有效增加企業(yè)收益，相關人士一直致力于研究和開發(fā)高效的優(yōu)化技術，希望能夠快速找到PFSP的最優(yōu)解。受貓日常行為啟發(fā)，Chu[3]在2006年提出了貓群算法(cat swarm optimization，CSO)。貓群算法將貓的行為分為搜尋模式和跟蹤模式，這兩種模式通過結合律MR(mixture ratio)進行交互轉換。搜尋模式下，通過對個體進行擾動從而使得每個個體向局部最優(yōu)個體靠近；跟蹤模式下，貓通過一定速度來跟蹤目標，從而使得個體向全局最優(yōu)靠近。近年來，貓群算法被應用于很多領域，并取得較好效果。在識別領域，Ganapati[4]將該算法運用到無線脈沖響應(IIR)系統(tǒng)識別；Pradhan[5]將貓群算法應用于圖像識別；Guo等[6]基于以上研究基礎，運用貓群算法對光伏系統(tǒng)進行優(yōu)化。在數學研究領域，Pappula等[7]將貓群算法用于函數優(yōu)化問題，但收斂速度較慢；為提高貓群算法的全局搜索速度，Tsai等[8]提出了貓群算法并行結構，同時驗證了在種群規(guī)模較小及總迭代次數較少的情況下，該并行結構能有效提高收斂速度。在多目標生產調度方面，Pradhan[5]運用貓群算法求解多目標優(yōu)化問題；劉瓊等[9]將該算法運用到混流裝配線排序問題。

盡管貓群算法在以上領域取得了一些研究成果，但在單目標置換流水車間調度領域的研究較少。Bouzidi等[10]針對置換流水車間調度問題利用標準的貓群算法來求解；此外，Bouzidi等[11]還將貓群算法與遺傳算法中的相關解碼操作結合起來對置換流水車間進行求解；馬邦雄等[12]運用貓群算法對置換流水車間調度問題進行求解并與其他算法進行比較。針對置換流水車間調度問題，盡管上述研究都取得較好效果，但求解過程中該算法收斂速度較慢，同時，當問題規(guī)模變大時容易出現“維數災難”。為加快尋優(yōu)速度，同時避免“維數災難”，本研究提出一種基于分布估計算法的改進貓群算法(EDA-CSO)用于解決PFSP。

目前，分布估計算法(estimation of distribution algorithms，EDA)已應用于智能學習、函數優(yōu)化、圖像識別、多目標規(guī)劃[13]等多個領域。EDA算法利用概率矩陣模型描述解序列在空間的分布，利用統(tǒng)計學知識分析概率模型，同時，利用概率矩陣產生子群體。為得到更好的解，TZENG等[14]將蟻群算法與EDA算法相結合，用于求解PFSP；Chang等[15]將EDA算法與遺傳算法相結合來解決旅行商問題(traveling salesman problem，TSP)；同時，Chang等[16]將區(qū)塊模型與分布估計算法(block-based estimation distribution algorithm，BBEDA)相結合來求解PFSP問題；鑒于EDA良好的收斂速度，本研究將CSO算法與EDA相結合，得到高適應度的人工解，同時利用3種變異算子對解序列重組以提高解序列的質量和多樣性，并通過仿真實例驗證EDA-CSO算法的有效性及良好的魯棒性。

1 置換流水車間調度問題數學模型

PFSP是許多生產調度問題的簡化模型，該問題主要研究了n個工件在m臺機器上加工，并且每個工件有m道加工工序，目標是求使某項生產指標達到最優(yōu)的方案。相關約束條件如下：1)所有工件按照相同順序，即 1，2，···，m 在機器上加工；2)某一時刻，任一機器只能加工一個工件；3)某一時刻，任一工件只能在一臺機器上進行加工；4)任何工件在加工過程中不能中斷；5)所有工件在初始時刻都可以加工。

若PFSP以最大完工時間為目標，則該問題可以用n、m、prmu、這幾個符號來表示，其中，n代表總工件數，m代表總機器數，prmu代表所有工件在所有機器上的加工順序相同，代表最大完工時間。

2 改進的貓群算法

基于以上優(yōu)化目標及約束條件，改進的貓群算法求解PFSP的流程如下：

1) 初始化種群；

2) 計算貓的適應度值；

3) 改進的貓群算法通過利用混合比率將貓群分為搜尋模式和跟蹤模式的2個子群，對不同子群采取不同的方法處理；

4) 在搜尋模式下，利用概率模型更新記錄可行解信息并更新可行解；

5) 先后運用區(qū)塊挖掘及區(qū)塊競爭來得到適應度較高的人工解；

6) 為提高人工解的質量和多樣性，運用搜尋算子對人工解進行重組；

7) 在跟蹤模式中利用基于二元競賽法的速度-位移模型對貓的速度、位置更新，直至達到全局最優(yōu)；

8) 算法終止條件判斷。

基于區(qū)塊的貓群算法求解PFSP的具體流程如圖1所示。

圖 1 EDA-CSO流程圖Fig. 1 The flow chart of EDA-CSO

2.1 復雜度分析

一般而言，時間復雜度能夠度量算法的運行時間及算法的優(yōu)劣。假設種群規(guī)模為N，貓?zhí)幱谒褜つＪ较碌母怕蕿镸R，迭代次數為T，根據改進貓群算法的步驟進行時間復雜度分析。

步驟1) 中種群初始化需要N次操作，所以步驟1)的時間復雜度為O(N)；

步驟2) 中用以計算適應度的時間復雜度為O(N)；

步驟3) 中用以選擇貓行為方式的時間復雜度為O(N)；

步驟4)～6) 中執(zhí)行搜尋模式的貓，每次迭代更新概率矩陣1次，挖掘區(qū)塊n次，區(qū)塊競爭1次，組合人造解1次，解序列重組1次，故搜尋模式下的時間復雜度為O(MRN+MR2N2+MRN+MRN+MRN)；

步驟7) 中執(zhí)行跟蹤模式的貓，每次迭代速度更新1次，位置更新1次，解序列更新1次，故跟蹤模式下的時間復雜度為O((1-MR)(N+N+N))；

步驟8) 中終止條件判斷需要1次操作，故此步驟的時間復雜度為O(1)。

由以上可知，該算法的時間復雜度為O(T(MR+5)N+TMRN2)，故時間復雜度主要與與初始種群規(guī)模、混合比率及迭代次數有關。

2.2 初始化種群

傳統(tǒng)的貓群算法通過輪盤賭的方式生成初始種群，由于初始種群個體適應度較低，在一定程度上制約了算法的收斂速度。本研究利用貪婪準則[16]尋及輪盤賭相結合的方式優(yōu)化初始化種群，以達到加快收斂速度的同時，增加初始解的多樣性。在利用貪婪準則初始化種群時，隨機選取第一個工件，并將其加入到里，然后在其他未加工的工件中搜索，尋找下一個工件，其在所有未加工工件中加工時間最短，將其加至里，并將其作為當前加工工件，繼續(xù)搜索并增加下一個加工工件，直至所有工件都加入加工順序集。運用貪婪準則產生的是初始解序列，因而，需要將初始解序列轉變?yōu)橐欢▍^(qū)間內的位置矢量。具體如式(1)：

初始位置及速度產生方式為

2.3 基于混合比率的貓行為模式選擇

傳統(tǒng)的貓群算法不能根據算法的迭代次數合理分配局部搜索和全局搜索的比重，若在算法迭代前期采用較大的混合比率的跟蹤貓，可以增加算法的全局搜索能力，但在算法迭代后期搜尋貓所占比率較大，可以提高解精度和收斂性。因此，本研究采用文獻[9]中的一種貓行為混合比率選擇法，具體如圖2所示。

圖 2 混合比率分配Fig. 2 The allocation of mixed ratio

該線性混合比率的計算公式為

2.4 搜尋模式

2.4.1 構建概率模型

本研究采用位置矩陣和相依矩陣來記載不同的加工信息，位置矩陣用來表示工件和所處加工位置之間的關系，相依矩陣用來表示任意兩個工件之間的加工前后順序。

對初始解的適應度函數值從小到大排序，選

具體位置、相依矩陣更新方式如圖3、圖4所示。

圖 3 位置矩陣更新方式Fig. 3 Updating method of position matrix

圖 4 相依矩陣更新方式Fig. 4 Updating method of dependency matrix

2.4.2 組合區(qū)塊

組合區(qū)塊能夠降低種群迭代復雜度，降低解的維度，加快收斂速度。以單個機器10個工件的排序為例，如圖5所示，未組合區(qū)塊之前母體中的工件{工件1，工件2，，工件10}為單獨的基因，此時可產生10！種排列組合，而組合區(qū)塊后排列組合變?yōu)?！種，在很大程度上降低了解的維度。為找出含有高競爭優(yōu)勢的區(qū)塊，本研究從區(qū)塊挖掘與區(qū)塊競爭兩個步驟來組合區(qū)塊。

圖 5 種群迭代復雜度比較Fig. 5 The comparison of iterative complexity of population

1) 區(qū)塊挖掘

根據位置矩陣和相依矩陣模型提供的相關信息，進行相應的區(qū)塊挖掘。以隨機的方式選擇區(qū)塊的起始位置，產生一個符合最小長度的空白區(qū)塊，設區(qū)塊的最小長度為3。

在空白區(qū)塊中放入最適合的工件，為計算方便，將各工件在位置矩陣與相依矩陣中的累計結果轉化為概率，同時，將兩矩陣的概率整合成一個合并概率(combination probability，CP)，利用輪盤賭對合并概率進行挑選，其中，起始位置按照依據位置矩陣的概率，以輪盤賭進行選擇。選出第1個工件后，以合并概率對第2個、第3個工件等進行選擇。經一系列研究發(fā)現，在進化前期前后關系相比位置關系更能影響解序列的適應度高低[17]，相反，在進化中后期位置關系比工件前后關系更重要，因而在進化的不同階段，令位置矩陣的權重隨著世代數由0.3增加到0.7，反之，相依矩陣由0.7遞減到0.3。合并概率的計算如式(9)所示，其中，代表工件編碼、表示緊前工件號碼、j表示工件所在的位置、表?示工件總數、表示工件的合并概率、與分別表示當前位置矩陣與相依矩陣的合并權重值、為位置矩陣中工件i處于位置j上的概率、為相依矩陣中工件j緊前于工件i的概率。

計算出所有工件的合并概率，并運用輪盤賭選擇出區(qū)塊的第2個工件及第3個工件等，具體如圖6所示。

圖 6 以合并概率挖掘區(qū)塊Fig. 6 Mining blocks by combining probability

隨著區(qū)塊長度的增長，總概率逐漸降低，即錯誤的概率越大。例如，一個由5個工件{工件1，工件2，工件3，工件4，工件5}組成的區(qū)塊，其概率分別為 0.5、0.8、0.6、0.4、0.3，此區(qū)塊的總概率0.5×0.8×0.6×0.4×0.3=0.028 8，若該區(qū)塊由 3 個工件{工件1，工件2，工件3}組成，則總概率為0.5×0.8×0.6=0.24，由此可見，錯誤概率隨著區(qū)塊長度的增長而變大。為保證區(qū)塊的質量不會隨著區(qū)塊長度的增加而降低，設計一個閾值用以篩選上述挖掘的區(qū)塊，閾值隨著迭代次數的增加由0.24增到0.8。將符合閾值的區(qū)塊暫存在區(qū)塊庫中，區(qū)塊庫中保留著本次迭代中全部符合閾值的區(qū)塊。

2) 區(qū)塊競爭

區(qū)塊挖掘完成后，利用區(qū)塊競爭選擇競爭力較大的區(qū)塊，每迭代一次，其產生的區(qū)塊與區(qū)塊庫中的區(qū)塊進行比較，最終選擇其中競爭優(yōu)勢較大的區(qū)塊，更新區(qū)塊庫。區(qū)塊進行競爭時，如果幾個區(qū)塊之間工件重復或者區(qū)塊之間包含的位置出現重復，利用平均概率對這幾個區(qū)塊比較，淘汰概率較小的區(qū)塊。

平均概率的計算方法：區(qū)塊的第一個工件位置矩陣概率加上其余工件的合并概率之和除以區(qū)塊總長度，即可求出該區(qū)塊的平均概率。平均概率的計算如式(10)所示：

圖 7 區(qū)塊競爭Fig. 7 The competition of blocks

2.4.3 組合人工解

為提高解序列的質量，在完成區(qū)塊挖掘后，利用區(qū)塊庫中保留的區(qū)塊組合人工解，具體步驟如下：

1) 從人工解的第一個位置開始挖掘，挖掘方法與上述區(qū)塊挖掘相同，第一個位置利用位置矩陣中概率以輪盤賭的方式選擇工件；

2) 其余N-1個位置以輪盤賭的形式對合并概率進行選擇；

3) 每選出一個工件，將該工件與所有其他區(qū)塊的起始位置進行比較，若與其他區(qū)塊的位置及工件都相同，則將此區(qū)塊直接復制到人工解中，然后從下個位置繼續(xù)進行選擇和比較，直至人工解組合完成。

具體的操作方式如圖8所示。

圖 8 人工解組合過程Fig. 8 The combination process of artificial solution

2.4.4 解序列重組

為了增加該算法尋找最優(yōu)解的概率，本研究對每只貓即解序列進行相應的重組操作。首先每只貓在記憶池中將自身位置復制H份，對記憶池中的貓即解序列進行相應的重組操作，使得所有貓能夠到達新位置，計算記憶池中所有貓的適應度，然后將適應度最高的貓代替當前貓，以完成貓的位置更新。在記憶池進行變異操作時，為避免局部最優(yōu)及增加解序列的多樣性，本研究將解序列隨機切成N個片段，選取最短的兩個片段，利用遺傳算法中的插入搜尋算子操作，對解序列重組，使得兩個最短片段形成一個基因片段。若重組之后的片段不再是最短片段，則對解序列中的最長片段及該片段按照合并概率重組，若區(qū)塊庫含有以被選擇的工件開頭的區(qū)塊，則直接插入，具體如圖9和圖10所示。

圖 9 插入搜尋算子Fig. 9 Insert search operator

圖 10 利用概率重組解序列Fig. 10 Using probability recombination solution sequence

2.5 跟蹤模式

貓的跟蹤模式是為了使個體靠近全局最優(yōu)解，在該模式下，貓與群體最優(yōu)位置進行比較來更新個體速度與位置[18]。跟蹤模式可以根據以下兩步進行。

1) 速度的更新。

任意時刻，每個貓都有一個速度，第i只貓的當前速度可表示為，所有貓的速度按照式(11)進行更新：

式中：Vi(n+1)表示更新后第i只貓的速度；w為慣性權重，w的大小由式(12)決定；t表示迭代信息；tmax表示最大迭代次數；c代表加速度常數；rand服從[0，1]均勻分布。

2) 位置更新。

每只貓的位置更新由式（13）決定：

3) 如果第i只貓分的新位置超出搜索空間，則將速度乘以-1，從反方向繼續(xù)搜索。

4) 利用二元競賽法更新解序列，即將母體種群與子群的適應度兩兩對比并將適應度最高的子群代替母體種群，進行下一次搜索。

3 仿真測試

3.1 參數設置

為了驗證基于區(qū)塊的貓群算法的性能，本研究測試數據采用Carlier[19]中的Car類基準例題集進行測試，應用該算法求解這些案例，并與其他文獻中的算法進行比較。本研究程序利用Visual Studio2015中的C++，在操作系統(tǒng)為Windows8，處理器的主頻為2.71 G的Intel(R)Core(TM)i5-6400處理器8 G內存的電腦上進行仿真測試。參數設計：仿真測試次數為20，初始種群的數量為100，最大的迭代次數為100。本研究將各個算法的最優(yōu)相對誤差(BRE)、平均相對誤差(ARE)及最差相對誤差(WRE)進行比較。其中，C*表示已知算例的最優(yōu)解，表示所求解的最優(yōu)值，表示所求解的平均值，表示所求解的最差值。

3.2 實驗測試與比較

針對Carlier例題，本研究將基于分布估計算法的改進貓群算法(EDA-CSO)與貓群算法(CSO)[12]、標準粒子群算法(PSO)[12]、蝙蝠算法(BA)[12]進行比較。具體比較結果如表1所示。

由表1和圖11、圖12可知，盡管這4種算法在Carlier案例中均能求出問題的最優(yōu)解(BRE為0)，然而EDA-CSO的ARE均優(yōu)于其他算法。表明了本算法的整體求解性能優(yōu)于其他算法。此外，EDA-CSO顯然比CSO、PSO、BA的ARE和WRE更小，這是因為通過調整貓的混合比率，迭代前期采用較大的混合比率的跟蹤貓，增加了算法的全局搜索能力，在算法迭代后期增加搜尋貓所占比率較大，增加了局部搜索能力，減少了求解誤差，提高了精度和收斂性，因此EDA-CSO算法明顯優(yōu)于文中其他算法。

表 1 EDA-CSO、CSO、PSO和BA的測試結果對比Table 1 Comparison of test results for EDA-CSO、 CSO、PSO and BA

圖 11 平均相對誤差比較Fig. 11 Comparison of average relative error

圖 12 最差相對誤差比較Fig. 12 Comparison of the worst relative error

為進一步驗證算法的有效性，針對Reeves[20]例題，將基于貓群算法的改進估計分布算法(EDA-CSO)與貓群算法(CSO)[10]、基于區(qū)塊的分布估計算法(BBEDA)[17]、基于粒子群算法的分布估計算法(PSO-EDA)[21]各迭代20 000次并進行比較。具體結果如表2所示。其中，Cmin表示所求解的最優(yōu)值，s；G表示算法的運行時間，s。

表 2 Reeves案例測試結果比較Table 2 Performance comparison on Reeves's instances

由表2可知，由于增加算子，盡管本算法在求解Rec01、Rec05、Rec07時，處理時間上慢于CSO算法，但BRE均優(yōu)于CSO、BBEDA及PSOEDA算法。這是因為雖然迭代過程中增加了算子，但由于區(qū)塊具有降維的作用，且隨著問題復雜度的增加，效果越明顯，因而在一定程度上降低了運算時間。為直觀體現本算法降低復雜度，加快收斂速度的性能，以EDA-CSO、BBEDA求解 Rec09、Rec11、Rec13、Rec15為例，具體如圖13～16所示。

圖 13 Rec09收斂圖Fig. 13 Rec09 convergence graph

圖 14 Rec11收斂圖Fig. 14 Rec11 convergence graph

圖 15 Rec13收斂圖Fig. 15 Rec13 convergence graph

圖 16 Rec15收斂圖Fig. 16 Rec15 convergence graph

從圖13～16可以看出，在相同的迭代次數下，EDA-CSO與BBED算法相比，盡管兩者最優(yōu)誤差均為0，但EDA-CSO的收斂速度均優(yōu)于BBEDA算法的收斂速度。

4 結束語

本研究在貓群算法的基礎上進行改進，提出了基于分布估計算法的改進貓群算法，用以解決置換流水車間調度問題。在貓搜尋階段，運用貪婪準則于輪盤賭相結合的方式初始化種群，加快收斂速度；采用位置矩陣與相依矩陣結合的方式挖掘區(qū)塊；利用區(qū)塊競爭產生人工解；在不同的進化階段采用不同的變異方式以提高人工解的質量和多樣性；同時，為了使個體靠近全體最優(yōu)解，通過與群體最優(yōu)位置進行比較來更新個體速度與位置。針對Carlier和Reeves標準案例運用該算法進行求解，最后，將各個算法的實驗結果進行比較，驗證了該算法的有效性和魯棒性。

本研究僅將該算法應用于置換流水車間調度問題，未將該算法應用于混流生產線、TSP等其他組合優(yōu)化問題，今后可以進一步從這幾個方面展開研究。