求解置換流水車間調度問題的一種混合算法

劉祝智

【摘 要】置換流水車間調度問題是一類經典的組合優化問題，智能優化算法是求解該問題的首要方法。遺傳算法和分布估計算法在PFSP問題上均存在著一定的缺陷，即無法平衡局部搜索和全局搜索。為了克服它們的缺陷，本文將分布估計算法與遺傳算法結合，并引入模糊邏輯控制來調節兩種算法的參與率，最后用基準算例的測試結果證實了本文所設計的混合算法是有效的。

【關鍵詞】置換流水車間調度；分布估計算法；遺傳算法；模糊邏輯控制

0.前言

置換流水車間調度問題（PFSP）是對經典的流水車間調度問題進行簡化后得到的一類子問題，最早在石化工業中得到應用，隨后擴展到制造系統、生產線組裝和信息設備服務上[1]。該問題一般可以描述為，n個待加工工件需要在m臺機器上進行加工。問題的目標是求出這n個工件在每臺機器上的加工順序，從而使得某個調度指標達到最優，最常用的指標為工件的總完工時間（makespan）最短。

PFSP最早由Johnson于1954年進行研究[2]，具有NP難性質[3]。求解方法主要有數學規劃，啟發式方法和基于人工智能的元啟發式算法[4]。數學規劃等適用于小規模問題，啟發式方法計算便捷，卻又無法保證解的質量。隨著計算智能的發展，基于人工智能的元啟發式優化算法成為研究的重點。

遺傳算法（GA）是研究與應用得最為廣泛的智能優化算法，利用遺傳算法求解PFSP問題的研究也有很多。遺傳算法具有操作簡單、容易實現的優點，且求解時不受約束條件限制。然而，遺傳算法通常存在著過早收斂，容易陷入局部最優的現象。導致這一現象的原因在于遺傳算法的交叉、變異操作具有一定的隨機性，在求解PFSP問題的過程中往往會破壞構造塊，產生所謂的連鎖問題。為了克服遺傳算法的缺陷，研究人員提出了一種不進行遺傳操作的分布估計算法[5]（EDA）。EDA是一種運用統計學習的新型優化算法。相比GA，EDA在全局搜索上有較大的優勢，而局部搜索能力不足，同樣會導致局部最優[6][7]。以混合優化為思路，本文將設計一種EDA與GA結合的混合算法來求解PFSP問題，混合算法通過EDA的概率模型和GA的交叉變異操作兩種方式來生成個體，并引入模糊控制理論[8]來自適應調節兩種算法生成個體的比例。

1.置換流水車間調度問題

PFSP問題通常假設：

（1）n臺工件在m臺機器上加工。

（2）每個工件以相同的順序在m臺機器上加工。

（3）每個工件在每臺機器上的加工時間是預先確定的。

（4）每臺機器只能同時加工一個工件。

2.混合算法設計

2.1種群初始化

初始種群含有PS個個體，利用經典的啟發式方法NEH[9]算法產生1個個體，其余PS-1個個體采用隨機初始化的方法生成。

2.2選擇

根據PFSP問題所給的加工時間表計算出種群中所有個體的總完工時間Cmax，顯然Cmax越小，個體的質量就越好，據此可將評價個體好壞的適應度函數設為1/Cmax。本文選擇的是輪盤賭法，加工時間越小，適應度值越高，個體被選擇的概率也就越大

2.3概率模型

2.4局部搜索

對概率模型采樣即可得到新一代的個體，對個體進行局部搜索可以提高EDA的性能[11]，本文將對較好的個體進行局部搜索，分別有如下三種搜索方法：

插入：選擇一個工件并隨機插入到某一位置。

交換：隨機選擇兩個工件并交換其所在位置。

倒置：隨機選擇兩個工件，將這兩個工件之間的序列反轉。

2.5交叉算子

本文采用的交叉算子為次序保留交叉。例如，親代個體為{2，3，5，1，4，9，8，6，7，10}和{1，2，4，5，6，7，8，3，9，10}，在交叉過程中保留的片段為{4，9，8，6}，則生成的子代個體為{1，2，5，7，4，9，8，6，3，10}和{2，3，4，5，6，1，8， 7，9，10}，圖示如下：

2.6變異算子

本文選取的變異算子為移碼變異，例如，變異前的個體為{6，8，9，10，7，4，3，1，2，5}，選擇7，8這兩個位點進行變異，變異后個體為{6， 9，10，7，8，4，3，1，2，5}，如下圖所示：

2.7模糊邏輯控制

混合優化策略中，不同算法的比例是影響算法性能的關鍵，傳統的算法比例混合方法主要包括固定比例和動態比例兩種。使用固定比例時，比例值將在整個算法搜索過程中保持不變。這種方法需要進行試驗來確定合適的比例值，其缺點在于為尋找到最佳比例值所需進行的試驗多，耗時久。而動態比例調節則只需預先確定一個比例的初始值，而在運行過程中會根據搜索情況調節比例。調節方式又可以分為兩種：一種是應用傳統的啟發式規則控制算法生成個體的比例，這些規則可以用確定的數學公式表示；而另一種是用人工智能技術自適應調整生成個體的比例，最常見的是將模糊邏輯應用于比例調節，能根據算法性能的變化來實現比例控制[12]。為了使混合算法具有優良的適應性，本文采用模糊邏輯控制來進行比例調節：在EDA表現良好時提高EDA生成個體的比例發揮其全局搜索的優勢，在EDA求得解的質量下降時提高GA生成個體的比例，以避免出現局部最優。

3.EDA-GA混合算法

通過以上設計，EDA-GA混合算法的步驟如下：

3.1種群和概率模型的初始化

產生初始種群，迭代次數t=1，概率模型P中pij=1/n

3.2對種群個體進行評價并選擇出優勢個體

以輪盤賭法選擇出用以更新EDA概率模型的優勢個體和待進行交叉變異操作的父代個體。

3.3更新概率模型并對概率模型取樣生成個體

對優勢個體進行統計學習完成概率模型的更新，然后對概率模型抽樣產生PS個個體，局部搜索后，把最好的rate（t）*PS個個體加入到下一代種群，rate（t）為當前EDA所生成個體的比例。

3.4交叉操作和變異操作

對父代分別進行交叉操作和變異操作，共產生（1-rate（t））*PS個個體，將這些個體加入到下一代種群中。

3.5模糊邏輯控制調節比例

新一代種群生成后，將種群平均完工時間與上一代進行比較，得到模糊輸入量，根據模糊判斷規則確定下一次迭代時EDA所生成個體的比例rate（t+1）。

3.6終止條件判斷

若滿足終止條件，輸出此時得到的最優解；否則，t=t+1，進入步驟2）。

4.實驗結果

4.1參數設置

將EDA-GA混合算法的參數設為種群大小PS=200，迭代次數iteration_times=300，優勢個體所占比例為superior_rate=0.2，GA變異比例mutation_rate=0.1，EDA初始生成個體的比例rate=1，概率模型學習速率α=0.2。

4.2結果分析

PFSP問題的基準算例有很多，其中Car和Rec類算例運行時間段短，計算快捷，因此選用這兩種算例來驗證本文所設計混合算法的有效性。每個算例用matlab獨立運行10次，并與GA，EDA的結果進行比較。測試結果如表3所示。其中，BRE=×100、ARE=×100為每種算法求得的最優解C與三種算法測試所得的最好解C*的相對偏差百分比的最小值和平均值。

從表3的實驗結果可以看出，對測試問題Car1～Car8和Rec01～Rec37，本文設計的EDA-GA混合算法ARE與BRE均優于EDA和GA，說明GA的引入使得EDA的優化性能有了很大的改進。對于Rec39、Rec41，混合算法BRE不如GA，說明優化性能稍弱于GA，但相比EDA解的質量有顯著提高。因此總體而言，EDA-GA混合算法的性能是要強于GA和EDA。

5.結論

針對EDA和GA各自在全局搜索和局部搜索的不同側重，本文設計了一種EDA-GA混合算法對以最小化總完工時間為優化目標的PFSP問題進行了求解。在混合算法中， EDA和GA各自生成一定比例的個體進行混合，在兩種算法比例的調節上使用了模糊邏輯控制的方法，其中模糊輸入量為每一代種群個體總加工時間的平均值的變化，而模糊輸出量為EDA在下一次迭代中所生成個體的比例。由此，混合算法綜合了EDA和GA的優點，運用Car和Rec類進行算例仿真，實驗結果證明上述EDA-GA混合算法是有效的。 [科]

【參考文獻】

[1]Pan Q-K，Suganhan PN，Tasgetiren MF，Chua TJ.A discrete artificial bee colony algorithm for thelot-streaming flow shop scheduling problem. Information Sciences，2011，181（12）：2455-68.

[2]JohnsonS M.Optimal two-and three-stage production schedules with setup times included[J].Naval research logistics quarterly，1954，1（1）：61-68.

[3]Zhang Y，Li X.Estimation of distribution algorithm for permutation flow shops with total flow time minimization[J].Computers & Industrial Engineering，2011，60（4）：706-718.

[4]周馳，高亮，高海兵.基于 PSO 的置換流水車間調度算法[J].電子學報，2006，34（11）：2008-2011.

[5]LarranagaP，LozanoJA.Estimationofdistributionalgorithms：Anewtoolforevolutionary

computation[M].Springer，2002.

[6]葉寶林，高慧敏，王筱萍，等.基于分布估計算法的二階段置換流水車間調度算法[J].計算機應用研究，2011，28（10）：3702-3706.

[7]ChenSH，ChenMC，Chang P C，et al.Guidelines for developing effective estimation of distribution algorithms in solving single machine scheduling problems[J].Expert Systems with Applications，2010，37（9）：6441-6451.

[8]Chan F T S，Prakash A，Mishra N.Priority-based scheduling in flexible system using AISwithFLCapproach[J].International Journal of Production Research，2013，51（16）：4880-4895.

[9]Nawaz M，Enscore Jr E E，Ham I.A heuristic algorithm for the m-machine，n-job flow-shop sequencing problem[J].Omega，1983，11（1）：91-95.

[10]王圣堯，王凌，許燁，等.求解混合流水車間調度問題的分布估計算法[J].自動化學報，2012，38（3）：437-443.

[11]Wang S，Wang L，Liu M，et al.An effective estimation of distribution algorithm for solving the distributedpermutationflow-shopscheduling problem [J]. International Journal of Production Economics，2013，145（1）：387-396.

[12]何宏，錢鋒.遺傳算法參數自適應控制的新方法[J].華東理工大學學報：自然科學版，2006，32（5）：601-606.

[13]Kim K W，Gen M，Yamazaki G.Hybrid genetic algorithm with fuzzy logic for resource-constrained project scheduling[J].Applied Soft Computing， 2003，2（3）：174-188.

[14]Kim KW，YunYS，YoonJM，et al.Hybrid genetic algorithm with adaptive abilities for resource-constrained multipleproject scheduling[J].ComputersinIndustry，2005，56（2）：143-160.