改進(jìn)多種群雜交遺傳算法在作業(yè)車間調(diào)度的研究

劉興剛

摘要：通過提出應(yīng)用最廣泛的混合型作業(yè)車間的調(diào)度問題以及遺傳算法的基本原理，并結(jié)合生產(chǎn)車間調(diào)度問題的特點，對傳統(tǒng)單種群遺傳算法改進(jìn)了改進(jìn)。新遺傳算法中加入輔助種群，保證種群的多樣性，解決單個種群的遺傳算法容易陷入局部收斂而出現(xiàn)早熟的情況。并應(yīng)用實例對比分析，表明算法在車間調(diào)度系統(tǒng)的有效性和合理性。

關(guān)鍵詞：車間調(diào)度；遺傳算法；多種群；并行

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）07-1496-04

1 概述

隨著經(jīng)濟(jì)全球化趨勢的發(fā)展，各國制造業(yè)進(jìn)入全球供應(yīng)鏈生產(chǎn)體系。大型生產(chǎn)型企業(yè)相繼轉(zhuǎn)入生產(chǎn)高效率，多品種、小批量和定制化生產(chǎn)模式。供需鏈環(huán)境下的制造業(yè)生產(chǎn)調(diào)度系統(tǒng)模式，最終提出了生產(chǎn)調(diào)度系統(tǒng)的集成化、動態(tài)化、高效智能化、柔性化等發(fā)展方向。作業(yè)車間調(diào)度問題（JSP）尤為突出，由于問題計算的復(fù)雜性，各種不同規(guī)模的車間，生產(chǎn)類型的交叉，很難找到一個適應(yīng)性，通用性很強(qiáng)的運算機(jī)制。遺傳算法借鑒生物進(jìn)化論機(jī)制，從一個較大的初始解空間入手，結(jié)合生物界優(yōu)勝劣汰的法則進(jìn)行求解，具有全局優(yōu)化、隱含并行、自組織、自適應(yīng)等特點。

傳統(tǒng)的遺傳算法有幾個較大的缺陷，應(yīng)用求解JSP問題時存在不足：（1）容易表現(xiàn)近親結(jié)合現(xiàn)象，出現(xiàn)早熟收斂問題；（2）進(jìn)化后期搜索效率低，使得最終得到的結(jié)果往往是局部最優(yōu)解，不是全局最優(yōu)解；（3）所求得的最優(yōu)解的受初始種群的影響較大。

為了克服這些局限性，國內(nèi)外都對其進(jìn)行改進(jìn)。文獻(xiàn)[4]應(yīng)用傳統(tǒng)遺傳算法（Genetic Algo-rithm，GA）來求解各類車間調(diào)度問題，簡單、容易實現(xiàn)，說明GA在求解調(diào)度問題中的可行性和有效性。文獻(xiàn)[2]通過改變交叉和變異概率設(shè)計新的算子以及引入新個體，進(jìn)行多種改進(jìn)。但綜合各個改進(jìn)，其改進(jìn)局限于單一種群遺傳算法，不能在理論上突破思維界限，故本文引入輔助種群進(jìn)行改進(jìn)。

2 建立車間調(diào)度的模型

3 遺傳算法的改進(jìn)

3.1 編碼方式的設(shè)計

目前已經(jīng)提出的編碼方式包括：基于工序、工件、優(yōu)先規(guī)則、完成時間、優(yōu)先表、機(jī)器等。結(jié)合已有的工作經(jīng)驗，大型生產(chǎn)型企業(yè)會將生產(chǎn)步驟簡化，以求各種水平的員工都能盡快適應(yīng)車間工作。故只需采用經(jīng)典的基于工序的字符串編碼方法即可。定義工件編號為01， 02，…n，每個工件的工序編號為01，02，…k，機(jī)床編號為01，02，…m。則每個基因由n、k和m按順序組成，如：基因010101表示工件01的01工序在設(shè)備01上完成。絕大多數(shù)生產(chǎn)工序都是路徑柔性，在個體生成過程中，隨機(jī)的機(jī)床中選擇一個，生成個體的一個基因。這樣生成的一個個體表示一個確定路徑的工序排序。個體的長度是所有工件的工序數(shù)量之和，與機(jī)床的數(shù)量無關(guān)。

3.2 設(shè)計約束條件

在大型生產(chǎn)型企業(yè)車間調(diào)度中， 調(diào)度方案應(yīng)滿足3.1中設(shè)定的約束條件。綜合各類文獻(xiàn)，常用的約束條件處理方法有懲罰函數(shù)法、解碼器法和算子修正法等。結(jié)合數(shù)學(xué)最優(yōu)化算法的理念，提高約束條件的處理效率，引入可能解的概念，即符合可行解的一個或多個必要約束條件的解集。定義可能解約束條件：每個個體中，表示同一工件工序的基因按照工序號從小到大的順序排列，即表示同一工件工序的基因中，工序號小的在前面。初始種群生成過程是：

1）隨機(jī)產(chǎn)生個體的部分基因；（2）由解約束條件決定，生成個體的其他基因，使個體其他基因都屬于可能解；（3）根據(jù)可行解約束條件， 判斷其是否屬于可行解，如果是則其加入種群，否則拒絕加入；（4）判斷是否達(dá)到種群規(guī)模要求，是則結(jié)束，否則轉(zhuǎn)（1）。經(jīng)過以上循環(huán)，使種群生成過程中大大減少了隨機(jī)試探的次數(shù)，節(jié)約了遺傳算法的運行時間。

3.3 優(yōu)化輔助子種群的生成

首先明確多種群并行遺傳算法的基本思想：利用多個種群并行進(jìn)化，引入輔助種群中部分優(yōu)良個體參與主種群進(jìn)化，以打破主種群的平衡態(tài)達(dá)到更高的平衡態(tài)， 跳出局部最優(yōu)。用多個子種群代替原始種群在可行解域進(jìn)行搜索，生成對原種群進(jìn)行優(yōu)化的輔助子種群，將遺傳算法分解為在多個子種群間并行進(jìn)行，并通過子種群間交換信息來增加基因模式數(shù)，避免未成熟收斂。為選擇出最優(yōu)個體，需要設(shè)置輔助種群的修正條件，并判斷個體的優(yōu)劣。

3.3.1 設(shè)置種群的修正條件

通過分析要改進(jìn)的遺傳算法的進(jìn)化過程可知，最需要改進(jìn)的階段就是算法即將進(jìn)入早熟狀態(tài)階段，因此把“接近或進(jìn)入早熟收斂狀態(tài)”作為引入輔助種群的進(jìn)行修正的條件。早熟收斂具體分以下表現(xiàn)：種群不能繼續(xù)增加最大適值；種群中個體的具有很大的相似性，使得種群的多樣性大大降低。結(jié)合多位學(xué)者的研究表明個體的相似性越高，相應(yīng)的算法的計算量越大。故通過設(shè)定臨界遺傳代數(shù)τ來界定最大適應(yīng)值增加的幅度。修正條件定義為：大于遺傳代數(shù)τ后，種群的最大適值沒有增加。成熟的遺傳算法一般設(shè)定遺傳代數(shù)τ為20～50。

3.3.2 適應(yīng)度高的個體的選擇

3.5 選擇、交叉和變異操作

3.5.1 選擇操作

采用改進(jìn)的輪盤賭來選擇：首先選擇父代個體和交叉變異得到的個體適應(yīng)值最高的個體，進(jìn)入下一代進(jìn)化；然后按照輪盤賭的方法選擇p-1個個體進(jìn)入下一代。使父代個體和其交叉變異得到的個體具有同等的選擇機(jī)會。不僅將適應(yīng)度高的個體保留到下一代，而且保證子代的多樣性。經(jīng)實例驗證，與傳統(tǒng)的輪盤賭比較，大大的提高了收斂速度和質(zhì)量。

5 結(jié)束語

傳統(tǒng)的對單一種群的遺傳算法改進(jìn)包括引入各種算子和各種搜索方法進(jìn)行改進(jìn)。而此文提出了多種群雜交的改進(jìn)遺傳算法，跳出思維限制并對算法的約束條件處理、編碼設(shè)計、選擇、交叉和變異操作進(jìn)行了改進(jìn)。在進(jìn)化過程中，不斷引入輔助種群中優(yōu)良個體，保持了種群的多樣性。與普通改進(jìn)的自適應(yīng)遺傳算法對比分析表明算法穩(wěn)定可靠，所提出的新算法不僅收斂速度快，而且收斂效率高，有其自己的特色。

參考文獻(xiàn)：

[1] 趙燕偉，吳斌，蔣麗.車輛路徑問題的雙種群遺傳算法求解方法[J].計算機(jī)集成制造系統(tǒng)（CIMS），2004 3（10）：303-306.

[2] 余琦瑋.基于遺傳算法的車間調(diào)度研究[D].杭州：浙江大學(xué)，2004.

[3] Solimanpura M，Vratb P，Shankarc R.A heuristic to minimize makespan of cell scheduling problem[J].International Joural of Production Economics，2004，88：231-241.

[4] 王凌.車間調(diào)度及其遺傳算法[M].北京：清華大學(xué)出版社，2003.

[5] Sujay Malvea，Reha Uzsoyb.A genetic algorithm for minimizing maximum lateness on Parallel identical batch Processing machines with dynamic job arrivals and Incompatible job families[J]. Computers & OperationsResearch，2007，34：3016-3028.

[6] LiYongming，ZhangSujuan，Expert Systems with Applications，2009，36（9）：

[7] 李軍華，黎明，袁麗華.一種改進(jìn)的雙種群遺傳算法[J].小型微型計算機(jī)系統(tǒng)，2008（11）：2099-2102.

[8] 薛明志，鐘偉才.正交Multi-agent遺傳算法及其性能分析[J].控制與決策，2004，19（3）.

[9] T S Rappaport.Wireless Communications： Principles and Practice[M].Second Edition，Upper Saddle River NJ： Prentice Hall，2002：111-12.

[10] Kevin J Krizmant，Thomas E Biedkatt，Theodore S Rappaportt.Wire-less Position Location： Fundamentals， Implementation Strategies， and Sources of Error[C].In：IEEE 47th Vehicular Technology Conference，Phoenix， AZ：IEEE Computer Society Press，2007.

[11] 王萬良，吳啟迪，宋毅.求解作業(yè)車間調(diào)度問題的改進(jìn)自適應(yīng)遺傳算法[J].系統(tǒng)工程理論與實踐 2004，2（25）：58-62.

[12] 楊曉梅，曾建潮.采用多個體交叉的遺傳算法求解作業(yè)車間問題[J].計算機(jī)集成制造系統(tǒng)， 2004，9（10）：1114-1119.