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

1、求解置換流水車間調度問題的一種混合算法0. 前言置換流水車間調度問題 ( PFSP 是對經典的流水車間調度問 題進行 簡化后得到的一類子問題，最早在石化工業(yè)中得到應用， 隨后擴展到制 造系統(tǒng)、生產線組裝和信息設備效勞上 1 。該問 題一般可以描述為， n 個待加工工件需要在 m 臺機器上進行加工。 問題的目標是求出這 n 個 工件在每臺機器上的加工順序， 從而使 得某個調度指標到達最優(yōu)，最 常用的指標為工件的總完工時間( makespar )最短。PFSP 最早由 Johnson 于 1954 年進行研究 2 ，具有 NP 難性 質3 。 求解方法主要有數學規(guī)劃，啟發(fā)式方法和基于人工智能 的元

2、啟發(fā)式算法 4 。數學規(guī)劃等適用于小規(guī)模問題，啟發(fā)式方 法計算便捷，卻又無法 保證解的質量。隨著計算智能的開展，基 于人工智能的元啟發(fā)式優(yōu)化算 法成為研究的重點。遺傳算法( GA 是研究與應用得最為廣泛的智能優(yōu)化算法， 利用遺 傳算法求解 PFSP 問題的研究也有很多。遺傳算法具有操 作簡單、容易 實現(xiàn)的優(yōu)點，且求解時不受約束條件限制。然而， 遺傳算法通常存在著 過早收斂， 容易陷入局部最優(yōu)的現(xiàn)象。 導致 這一現(xiàn)象的原因在于遺傳 算法的交叉、 變異操作具有一定的隨機 性，在求解 PFSP 問題的過程 中往往會破壞構造塊，產生所謂的 連鎖問題。 為了克服遺傳算法的缺 陷， 研究人員提出了一種不進

3、 行遺傳操作的分布估計算法 5 (EDA。EDA 是一種運用統(tǒng)計學 習的新型優(yōu)化算法。相比 GA EDA 在全局搜索 上有較大的優(yōu)勢， 而局部搜索能力缺乏， 同樣會導致局部最優(yōu) 67 。 以混合優(yōu)化 為思路，本文將設計一種 EDA 與 GA 吉合的混合算法來求 解 PFSP 問題，混合算法通過 EDA 的概率模型和 GA 的交叉變異操作 兩種 方式來生成個體，并引入模糊控制理論 8 來自適應調節(jié)兩種算 法 生成個體的比例。1. 置換流水車間調度問題PFSP 問題通常假設：(1) n 臺工件在 m 臺機器上加工。(2) 每個工件以相同的順序在 m 臺機器上加工。(3) 每個工件在每臺機器上的加工

4、時間是預先確定的。(4) 每臺機器只能同時加工一個工件。2. 混合算法設計2.1 種群初始化初始種群含有 PS 個個體，利用經典的啟發(fā)式方法 NEH9 算 法產 生 1 個個體，其余 PS-1 個個體采用隨機初始化的方法生成。2.2 選擇根據 PFSP 問題所給的加工時間表計算出種群中所有個體的 總完 工時間 Cmax 顯然 Cmax 越小，個體的質量就越好，據此可 將評價個體好壞的適應度函數設為1/Cmax 。本文選擇的是輪盤賭法，加工時間越小，適應度值越高，個體被選擇的概率也就越2.3 概率模型2.4 局部搜索對概率模型采樣即可得到新一代的個體， 對個體進行局部搜 索可以提高 EDA 勺性

5、能 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

6、， 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 模糊邏輯控制 混合優(yōu)化策略中， 不同算法的比例是影響算法性 能的關鍵，傳統(tǒng)的算法比例混合方法主要包括固定比例和動態(tài)比例兩種。用固定比例時， 比例值將在整個算法搜索過程中保持不變。 這種 方法 需要進行試驗來確定適宜的比例值， 其缺點在于為尋找到最 佳比例值 所需進行的試驗多， 耗時久。 而動態(tài)比例調

7、節(jié)那么只需預 先確定一個比 例的初始值， 而在運行過程中會根據搜索情況調節(jié) 比例。調節(jié)方式又 可以分為兩種： 一種是應用傳統(tǒng)的啟發(fā)式規(guī)那么 控制算法生成個體的比 例，這些規(guī)那么可以用確定的數學公式表 示；而另一種是用人工智能技術 自適應調整生成個體的比例， 最 常見的是將模糊邏輯應用于比例調節(jié)， 能根據算法性能的變化來 實現(xiàn)比例控制 12 。為了使混合算法具有優(yōu) 良的適應性， 本文采 用模糊邏輯控制來進行比例調節(jié)：在 EDA 表現(xiàn)良 好時提高 EDA 生 成個體的比例發(fā)揮其全局搜索的優(yōu)勢， 在 EDA 求 得解的質量下降 時提高 GA 生成個體的比例，以防止出現(xiàn)局部最優(yōu)。3. EDA-GA 混

8、合算法通過以上設計， EDA-GA 昆合算法的步驟如下：3.1 種群和概率模型的初始化產生初始種群，迭代次數 t=1 ，概率模型 P 中 pij=1/n3.2 對種群個體進行評價并選擇出優(yōu)勢個體以輪盤賭法選擇出用以更新 EDA 概率模型的優(yōu)勢個體和待 進行交 叉變異操作的父代個體。3.3 更新概率模型并對概率模型取樣生成個體 對優(yōu)勢 個體進行統(tǒng)計學習完成概率模型的更新， 然后對概率模型抽樣產 生 PS 個個體，局部搜索后，把最好的 rate (t) *PS 個個體參加 到下一代種 群，rate (t)為當前EDA所生成個體的比例。3.4 交叉操作和變異操作對父代分別進行交叉操作和變異操作， 共

9、產生 ( 1-rate ( t ) *PS 個個體，將這些個體參加到下一代種群中。3.5 模糊邏輯控制調節(jié)比例 新一代種群生成后， 將種群平均完工時 間與上一代進行比較，得到模糊輸入量，根據模糊判斷規(guī)那么確定下一次迭代時EDA 所生成個體的比例 rate ( t+1 )。3.6 終止條件判斷 假設滿足終止條件， 輸出此時得到的最優(yōu)解； 否那么， t=t+1 ，進入步驟 2) 。4. 實驗結果4.1 參數設置將 EDA-GA 混合算法的參數設為種群大小 PS=200, 迭代次數EDA 初 始生iteration_times=300 ，優(yōu)勢個體所占比例為 superior_rate=0.2 ， G

10、A 變異比例 mutation_rate=0.1 成個體的比例 rate=1 , 概率模型學習速率 a =0.2 。4.2 結果分析PFSP、可題的基準算例有很多，其中 Car和Rec類算例運行 時間段短， 計算快捷， 因此選用這兩種算例來驗證本文所設計混 合算 法的有效性。每個算例用 matlab 獨立運行 10次，并與 GA， EDA 的 結果進行比擬。測試結果如表3 所示。其中， BRE=< 100 、ARE=v 100為每種算法求得的最優(yōu)解 C與三種算法測試所得的最 好解 C*的相對偏差百分比的最小值和平均值。從表 3 的實驗結果可以看出，對測試問題Carl? Car8 和RecOI? Rec37 ，本文設計的 EDA-GA 昆合算法 ARE 與 BRE 均優(yōu)于 EDA 和 GA 說明 GA 的引入使得 EDA 的優(yōu)化性能有了很大的改良。 對于 Rec39、Rec41，混合算法BRE不如GA說明優(yōu)化性能稍弱 于GA但相 比 EDA 解的質量有顯著提高。 因此總體而言， EDA-GA 混合算法的性能 是要強于 GA 和 EDA5. 結論針對 EDA 和 GA 各自在全局搜索和局部搜索的不同側重，本 文設 計了一種 EDA-GA 混合算法對以最小化總完工時間為優(yōu)化目 標的 PFSP 問題進行了求解。在混合算法中，EDA 和 GA 各自生成一