劉興剛

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

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

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）07-1496-04

1 概述

隨著經(jīng)濟全球化趨勢的發(fā)展，各國制造業(yè)進入全球供應(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)性，通用性很強的運算機制。遺傳算法借鑒生物進化論機制，從一個較大的初始解空間入手，結(jié)合生物界優(yōu)勝劣汰的法則進行求解，具有全局優(yōu)化、隱含并行、自組織、自適應(yīng)等特點。

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

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

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

3 遺傳算法的改進

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

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

3.2 設(shè)計約束條件

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

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

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

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

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

通過分析要改進的遺傳算法的進化過程可知，最需要改進的階段就是算法即將進入早熟狀態(tài)階段，因此把“接近或進入早熟收斂狀態(tài)”作為引入輔助種群的進行修正的條件。早熟收斂具體分以下表現(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 選擇操作

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

5 結(jié)束語

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

參考文獻：

[1] 趙燕偉，吳斌，蔣麗.車輛路徑問題的雙種群遺傳算法求解方法[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].小型微型計算機系統(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)度問題的改進自適應(yīng)遺傳算法[J].系統(tǒng)工程理論與實踐 2004，2（25）：58-62.

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