基于關(guān)聯(lián)規(guī)則的作業(yè)車間調(diào)度問題改進遺傳算法研究

喬東平，柏文通，文笑雨，李浩，王雅靜

（1.鄭州輕工業(yè)大學(xué) 機電工程學(xué)院，河南 鄭州 450002；2.河南省機械裝備智能制造重點實驗室，河南 鄭州 450002）

0 引言

中國制造2025的明確提出加快了工業(yè)化與信息化的深度融合，將推動傳統(tǒng)制造業(yè)升級轉(zhuǎn)型，實現(xiàn)智能制造［1］。新一輪工業(yè)革命的興起，促使信息技術(shù)迅速融入到工業(yè)制造過程中，工廠積累了大量的生產(chǎn)數(shù)據(jù)，這些數(shù)據(jù)呈現(xiàn)出不規(guī)則性和多樣性［2］。傳統(tǒng)作業(yè)車間調(diào)度問題（job-shop scheduling problem，JSP）研究往往忽略了工業(yè)生產(chǎn)中歷史調(diào)度數(shù)據(jù)的潛在價值，造成大量數(shù)據(jù)資源浪費。因此，研究歷史調(diào)度數(shù)據(jù)與智能調(diào)度算法對求解作業(yè)車間調(diào)度問題的影響具有重要的現(xiàn)實意義。

由于遺傳算法不受限制性條件約束，在求解作業(yè)車間調(diào)度問題中得到了廣泛應(yīng)用［3］。采用遺傳算法求解作業(yè)車間調(diào)度問題時，初始種群質(zhì)量會對遺傳算法求解效率產(chǎn)生一定影響，初始種群質(zhì)量越高，算法求解效率越高，越能提高遺傳算法的整體性能［4］。目前主要采用隨機初始化的方法生成初始種群，很難確保初始種群質(zhì)量，從而會出現(xiàn)求解算法運行效率低、易早熟和運算周期長等問題［5］。為了提高遺傳算法的初始解質(zhì)量，國內(nèi)外學(xué)者對此開展了一系列研究。杜修力等［6］將均勻設(shè)計運用到連續(xù)變量的函數(shù)中，通過對搜索區(qū)域均勻網(wǎng)格化以優(yōu)化初始種群，雖然在一定程度上解決了遺傳算法進化緩慢的問題，但是該方法操作復(fù)雜度隨著問題規(guī)模的增大呈指數(shù)增大；周帥等［7］通過能動法和無延遲法生成的新個體替換隨機初始種群中較差的個體，從而提高初始種群質(zhì)量，但是效果不明顯；趙志偉［8］提出一種基于反向?qū)W習(xí)的自適應(yīng)差分進化算法，該算法結(jié)合標(biāo)準(zhǔn)進化算法的初始種群A和反向?qū)W習(xí)產(chǎn)生的種群B，選擇適應(yīng)度最好的N個個體作為求解算法的初始種群，并引進控制參數(shù)自適應(yīng)機制和變異參數(shù)自適應(yīng)機制，有效改善了算法的性能；I.Poikolainen等［9］提出一種基于聚類的種群初始化方法，優(yōu)化求解算法的初始種群，通過局部搜索算法對局部空間進行搜索，并利用聚類算法增強算法全局搜索能力；陳思遠等［10］提出一種基于指針網(wǎng)絡(luò)改進遺傳算法種群模型，該模型以隨機策略生成的種群S和指針網(wǎng)絡(luò)解集T，按比例取其適應(yīng)度值高的子集作為初始種群，通過改善遺傳算法初始種群結(jié)構(gòu)提高算法性能；李林瑛等［11］通過設(shè)計禁止區(qū)間法的啟發(fā)式構(gòu)造算法生成初始種群，避免了不可行個體的產(chǎn)生，互換染色體處于全等待的基因位置，提高了算法的局部搜索能力；王建華等［12］針對遺傳算法的隨機搜索問題，引入正交試驗的均衡原則，利用均衡分散原則對隨機生成的初始種群進行優(yōu)化，提高了算法初始種群質(zhì)量。

目前提出的方法有效提高了算法的求解速率，但仍存在以下問題［13］：（1）初始種群質(zhì)量提高效果并不明顯；（2）算法運行周期長，例如基于反向?qū)W習(xí)的方法，在每次迭代過程都進行反向?qū)W習(xí)，通過計算所有個體的適應(yīng)度值來選取最優(yōu)者；（3）采用優(yōu)化算法生成較優(yōu)個體替代種群中較差的個體，算法求解效率提升并不明顯。

針對上述問題，本文提出基于關(guān)聯(lián)規(guī)則的改進遺傳算法，該算法通過關(guān)聯(lián)規(guī)則獲取基因序列上的頻繁工序塊，將頻繁工序塊插入子代基因序列中結(jié)合禁忌矩陣生成初始種群。以此為基礎(chǔ)，設(shè)計3種交叉方式，根據(jù)不同待交叉?zhèn)€體選擇不同交叉方式，充分發(fā)揮不同交叉算子的特性。變異過程引入分段海明距離，使種群的變異過程具有方向性，以加快算法對最優(yōu)解的搜索。最后通過基準(zhǔn)案例驗證改進遺傳算法的有效性。

1 作業(yè)車間調(diào)度問題描述

作業(yè)車間調(diào)度問題可以描述為：在m臺機器上加工n個工件，每個工件都有m道工序，且每道工序的加工機器以及加工時間都是已知的。問題的約束條件為：（1）加工開始時，所有工件均處于待加工狀態(tài)，所有機器均處于空閑狀態(tài)；（2）不同工件的工序之間沒有先后順序約束，同一工件的工序之間有先后順序約束；（3）同一時刻，一個工件只能在一臺機器上加工，并且機器一旦開始加工中間不能中斷。

本文相關(guān)符號的定義：m臺機器表示為Mk=｛M1，M2，M3，…，Mm｝；n個工件表示為Ji=｛J1，J2，J3，…，Jn｝；Oij為第i個工件的第j道工序；sik為工件i在機器k上的開工時間；tik為工件i在機器k上的加工時間；cik為工件i在機器k上的完工時間，M是一個無窮大的數(shù)。本文的主要優(yōu)化目標(biāo)是使作業(yè)車間調(diào)度問題方案的最大完工時間Cmax最小化。模型描述如下。

式（1）為目標(biāo)函數(shù)，表示最小化最大完工時間，即各機器上加工工件的最大完工時間最??；式（2）為加工工序的前后約束關(guān)系；式（3）為工序的非阻塞約束關(guān)系；式（4）為加工工序開始/結(jié)束的時間約束；式（5）為工件的開工時間均大于0；式（6）和（7）分別為對aihk和xijk系數(shù)的定義。

2 基于關(guān)聯(lián)規(guī)則的改進遺傳算法設(shè)計

以遺傳算法為基礎(chǔ)，結(jié)合關(guān)聯(lián)規(guī)則、頻繁工序塊、禁忌矩陣和分段海明距離等概念，提出基于關(guān)聯(lián)規(guī)則的改進遺傳算法。具體求解算法流程如圖1所示，步驟如下。

圖1 JSP求解算法流程圖Fig.1 JSP solving algorithm flowchart

步驟1設(shè)置AR-GA算法參數(shù)：迭代次數(shù)Nmax，混合式比例a，最小支持度minsup，最小置信度minconf，交叉概率Pc，變異概率Pm。

步驟2隨機選取歷史調(diào)度數(shù)據(jù)集規(guī)模的50%作為測試集，尋找基因序列中的相鄰優(yōu)勢工序組。

步驟3采用關(guān)聯(lián)規(guī)則尋找歷史調(diào)度數(shù)據(jù)中具有關(guān)聯(lián)性的相鄰工序組組成頻繁工序塊。

步驟4判斷是否找到頻繁工序塊，如果沒有，跳轉(zhuǎn)步驟2，否則，繼續(xù)步驟5。

步驟5構(gòu)造禁忌矩陣，對禁忌矩陣中對應(yīng)頻繁工序塊中的工序進行標(biāo)記。

步驟6將整個頻繁工序塊插入子代基因序列中，并結(jié)合禁忌矩陣生成新的基因序列，基于關(guān)聯(lián)規(guī)則的改進遺傳算法生成初始種群的比例為a，隨機初始化策略生成初始種群規(guī)模為（1-a）。

步驟7執(zhí)行錦標(biāo)賽選擇策略。

步驟8按照交叉概率Pc選取待交叉?zhèn)€體，根據(jù)含有頻繁工序塊的待交叉?zhèn)€體數(shù)量，選擇相應(yīng)的交叉方式；如果兩個交叉?zhèn)€體都具有頻繁工序塊，進行兩點交叉；如果兩個交叉?zhèn)€體只有一個具有頻繁工序塊或兩個交叉?zhèn)€體都不具有頻繁工序塊，則進行POX交叉。

步驟9利用分段海明距離引導(dǎo)種群進行變異操作。

步驟10更新頻繁工序塊信息。

步驟11判斷是否達到結(jié)束條件，若未達到，跳轉(zhuǎn)步驟7～11，否則，結(jié)束循環(huán)并輸出最優(yōu)解。

2.1 編碼和解碼

本文采用文獻［14］提出的基于工序的編碼方式，即基因序列由n×m個基因組成，基因序列中所有的基因采用對應(yīng)的工件號表示，工件號出現(xiàn)的次數(shù)表示該工件的第幾道工序。以表1給出的一個3×3的JSP案例為例，隨機生成一條基因序列［132132213］，其中，1，2，3分別表示工件J1，J2和J3，例如基因序列中第1基因位上的1表示工件J1的第一道工序，第4基因位上的1表示工件J1的第2道工序，第8基因位上的1表示工件J1的第3道工序。

表1 一個3×3 JSP案例Tab.1 An example of 3×3 JSP

采用文獻［15］提出的插入式貪婪式解碼算法，即主動調(diào)度方法，從左到右依次讀取染色體上的工序排列順序，如果工序Oij是機器k分配的第一道工序，則機器k直接加工工序Oij；如果機器k已經(jīng)安排加工其他工件，則依次檢查該機器安排加工的第一個加工工序之前的空閑時間以及各個工序之間空閑時間段，將工序Oij插入到滿足條件的空閑時間段。對基因序列［132132213］解碼后的基因序列為［132231231］，解碼過程如圖2所示。

圖2 基于工序編碼的解碼過程Fig.2 Decoding process based on operation encoding method

2.2 種群初始化方法

在遺傳算法求解作業(yè)車間調(diào)度問題中，初始解的優(yōu)劣影響算法的收斂速率和求解質(zhì)量。通過種群初始化獲得較高質(zhì)量的初始種群，可以達到改善算法求解效率的目的。本文通過關(guān)聯(lián)規(guī)則尋找基因序列中的頻繁工序塊，結(jié)合禁忌矩陣優(yōu)化算法的初始種群。為了保持初始種群的多樣性，初始種群采用混合式生產(chǎn)方式，基于關(guān)聯(lián)規(guī)則的改進遺傳算法生成初始種群規(guī)模的比例為a，隨機初始化方法生成初始種群規(guī)模的比例為（1-a）。

2.2.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中一種常用方法，可有效挖掘基因序列中的優(yōu)良工序組合，提高算法求解性能［16］。本文利用關(guān)聯(lián)規(guī)則分析基因序列中工序排列順序，探索工序間排列順序存在的相關(guān)性，尋求具有關(guān)聯(lián)的優(yōu)勢工序組。

關(guān)聯(lián)規(guī)則（association rules）基本概念［17］是一種包括先導(dǎo)（left-hand side，LHS）和后繼（righthand side，RHS）的論斷，如果購買了先導(dǎo)項集，則很有可能對后繼項集感興趣，這表明項集之間存在一定關(guān)聯(lián)。在關(guān)聯(lián)規(guī)則中有兩個重要參考指標(biāo)，即支持度和置信度［18］，其中，支持度表示獲得的項集是否有效，置信度表示獲得項集的有效程度。

本文引入關(guān)聯(lián)規(guī)則尋找基因序列中具有關(guān)聯(lián)性的相鄰工序組，令歷史調(diào)度數(shù)據(jù)集中所有工序的集合為P=｛p1，p2，…，pn×m｝，其中n×m為基因序列的長度；L=｛l1，l2，…，ln×m｝表示在基因序列中對每一個基因位置上的工序統(tǒng)計集合，li的規(guī)模為歷史調(diào)度數(shù)據(jù)集中基因序列的數(shù)量集，liP；基因序列中第i個基因位置上的一個工序子集表示為Xi=｛x1，x2，…，xλ｝，Xili，λ＜n×m，xλ表示在該基因位置上滿足最小支持度的工序；工序xλ的發(fā)生在一定程度上引起相鄰工序yλ的發(fā)生，即xλyλ，xλ>P，yλ>P，且xλyλ=。

本文引入支持度確保獲得的相鄰工序組合有效，支持度（support（xλyλ））表示基因序列中某一基因位置上工序xλ和相鄰基因位置上工序yλ同時出現(xiàn)的總次數(shù)占population的比例，即

本文引入置信度確保相鄰工序組合的有效程度，令置信度（confidence（xλyλ））表示基因序列中某一基因位置上工序xλ出現(xiàn)頻率滿足支持度的前提下，其相鄰基因位置上工序yλ也出現(xiàn)的概率，即

式中：population為歷史調(diào)度數(shù)據(jù)集的規(guī)模；sup（xλ）為各基因序列中某一基因位置上工序xλ發(fā)生的總次數(shù)；sup（xλyλ）為各基因序列中某一基因位置上工序xλ和相鄰基因位置上工序yλ同時發(fā)生的次數(shù)；support（xλyλ）為工序xλ和相鄰工序yλ之間的支持度大小；confidence（xλyλ）為工序xλ和相鄰工序yλ之間的關(guān)聯(lián)性程度。

2.2.2 頻繁工序塊

本文提出的頻繁工序塊（frequent process blocks）概念為：在基因序列中滿足最小支持度和最小置信度的相鄰工序組稱為頻繁工序塊。通過關(guān)聯(lián)規(guī)則分析基因序列，發(fā)現(xiàn)工序排列順序之間的相關(guān)性，尋找具有關(guān)聯(lián)性的相鄰工序組組成頻繁工序塊，并將頻繁工序塊作為一個整體直接插入子代基因序列，提高算法初始種群質(zhì)量。需滿足約束條件如下：在頻繁工序塊中一道工序或者幾道相鄰工序同時出現(xiàn)的頻率滿足支持度的條件下，其相鄰的下一道工序發(fā)生概率滿足置信度條件；要求頻繁工序塊中相鄰工序數(shù)目不小于2。

如果關(guān)聯(lián)規(guī)則中的支持度和置信度都大于設(shè)置的最小支持度和最小置信度的閾值，則稱為強關(guān)聯(lián)規(guī)則［19］，為了確保頻繁工序塊的有效性，本文討論的關(guān)聯(lián)規(guī)則均為強關(guān)聯(lián)規(guī)則。本文設(shè)置的最小支持度閾值minsup=s1，最小置信度閾值minconf=c1。利用關(guān)聯(lián)規(guī)則尋找頻繁工序塊的操作流程如下。

步驟1隨機選取歷史調(diào)度數(shù)據(jù)集規(guī)模的50%作為測試集尋找相鄰優(yōu)勢工序組。

步驟2從基因序列中的第一個基因位置開始計算各個工序的出現(xiàn)次數(shù)，篩選出滿足最小支持度的工序。

步驟3如果該基因位置上的工序不滿足條件，繼續(xù)篩選下一道相鄰基因中各工序的出現(xiàn)次數(shù)。

步驟4如果找到support（xλyλ）≥s1的工序，分別計算該工序的下一道相鄰基因位置上的工序是否滿足confidence（xλyλ）≥c1，如果滿足，只保留置信度較高的相鄰工序，并對基因序列中滿足最小支持度和最小置信度的相鄰工序進行標(biāo)記，否則跳到步驟3。

步驟5將步驟4獲得的最小支持度與最小置信度的相鄰工序作為一個頻繁工序塊；在測試集中判斷步驟4獲得的頻繁工序塊是否滿足最小支持度，如果不滿足，將該頻繁工序塊輸出，跳轉(zhuǎn)步驟3；否則，計算該頻繁工序塊的下一道相鄰工序是否滿足confidence（xλyλ）≥c1。

步驟6如果confidence（xλyλ）＜c1，輸出步驟4得到的頻繁工序塊，并計算該基因位置上的工序是否滿足support（xλyλ）≥s1，如果滿足跳轉(zhuǎn)步驟4；否則，則將該道工序添加到頻繁工序塊中。

步驟7以此類推，直至基因序列中的工序全部統(tǒng)計。

步驟8判斷頻繁工序塊的數(shù)目是否大于等于1，如果是，輸出所有滿足條件的頻繁工序塊并結(jié)束循環(huán)；否則，跳轉(zhuǎn)步驟1。

2.2.3 初始種群的生成

考慮到頻繁工序塊中相鄰工序的固定位置和工序之間的排列順序?qū)Τ跏挤N群生成的影響，構(gòu)建禁忌矩陣MJ。在禁忌矩陣中，行表示工件，列表示工序，禁忌矩陣中第i行第j列的數(shù)字表示工件i的第j道工序，如圖3所示。

初始種群生成的方法：如圖3（a）所示，從禁忌矩陣MJ中找出對應(yīng)各個頻繁工序塊中的工序并進行標(biāo)記，被標(biāo)記的工序不能被選擇；填充基因序列中第一個基因位置時，首先判斷第O1列中是否有未被標(biāo)記的工序，可以得到O11，O21，O31和O41沒有被標(biāo)記，隨機選擇其中一道工序放到該基因位置上并標(biāo)記選中的工序。如圖3（b）所示，在填充第6位基因時，先判斷第O1列中是否有未被標(biāo)記的工序，發(fā)現(xiàn)第O1列中只有O31未被標(biāo)記，故選擇工序O31填充到第6基因位置上；在填充第7位基因時，第O1列中的工序全部被標(biāo)記，再去判斷第O2列中是否有未被標(biāo)記的工序，可以得到工序O32和O42未被標(biāo)記，隨機選擇其中一道工序放到該基因位置上并對選中的這道工序進行標(biāo)記。如圖3（c）所示，填充第9位基因時，第O1列和第O2列中的工序已經(jīng)全部被標(biāo)記，再判斷第O3列中的工序是否有未被標(biāo)記的工序，可以得到工序O23和O33未被標(biāo)記，則隨機選擇其中一道工序放到該基因位置上，并對選中的這道工序進行標(biāo)記，剩下一道工序插入到最后一個基因位置后并對其標(biāo)記。如圖3（d）所示，將禁忌矩陣中所有未被標(biāo)記的工序根據(jù)列的先后順序，依次插入到基因序列中的空基因位置上，生成初始種群。

圖3 初始種群的生成流程Fig.3 Generation process of initial population

2.3 選擇

選擇操作的本質(zhì)是促使種群中優(yōu)良基因得以保留，進而加快算法對最優(yōu)解或近似最優(yōu)解的探索。錦標(biāo)賽選擇算法具有更好的收斂性和較低的計算復(fù)雜性［20］，因此本文采用錦標(biāo)賽算法。錦標(biāo)賽操作流程：（1）隨機選擇兩個基因序列；（2）選擇適應(yīng)度值高的個體進行交叉操作，另一個個體繼續(xù)放回待選種群中；（3）重復(fù)以上操作，直至填滿交叉池。

2.4 交叉

初始種群采用混合式生成方法，其部分個體是隨機生成的，是基因序列中沒有被標(biāo)記的頻繁工序塊，所以交叉操作時會出現(xiàn)3種情況：（1）選擇的兩個個體都具有頻繁工序塊；（2）選擇的兩個個體只有一個具有頻繁工序塊；（3）選擇的兩個個體都不具有頻繁工序塊，詳細交叉策略如下。

當(dāng)出現(xiàn)情況（1）時，為了防止優(yōu)秀基因組合被破壞，采用兩點交叉操作［21］，如圖4所示，即對基因序列上的每一個頻繁工序塊中第一個工序位置進行標(biāo)記，然后隨機選擇其中2個標(biāo)記點之間的基因片段進行交換。如果基因序列中只有一個頻繁工序塊，就進行單點交叉方式［22］，以此降低因交叉操作對優(yōu)良基因的破壞。

圖4 兩點交叉Fig.4 Two point crossover

當(dāng)出現(xiàn)情況（2）時，采用POX交叉操作［23］，如圖5所示，因交叉操作產(chǎn)生的Child3，Child4子代個體，進行子代適應(yīng)度值大小計算。如果子代個體的適應(yīng)度值小于父代個體適應(yīng)度值，則產(chǎn)生子代個體不含頻繁工序塊；反之，則Child3，Child4個體基因序列對應(yīng)父代頻繁工序塊基因位置上的相鄰工序作為新的頻繁工序塊，并且更新頻繁工序塊信息。通過上述產(chǎn)生新的頻繁工序塊增加遺傳算法的局部搜索能力。

圖5 POX交叉Fig.5 POX crossover

當(dāng)出現(xiàn)情況（3）時，采用POX交叉操作，且經(jīng)過POX交叉操作產(chǎn)生的子代基因序列不含頻繁工序塊，其作用是增加種群的多樣性，見圖6。

圖6 POX交叉且Job=｛1，2｝Fig.6 POX crossover and Job=｛1，2｝

2.5 變異

為了使種群朝著優(yōu)化的趨勢變異，在遺傳算法的變異操作中引入“分段海明距離”，即取兩個基因序列中某一段基因片段相異的基因個數(shù)作為分段海明距離［24］。由于頻繁工序塊對子代種群質(zhì)量有著重要影響，本文選取基因序列中從第一個頻繁工序塊的首塊工序到最后一個頻繁工序塊的尾塊工序之間的基因片段計算個體之間的海明距離。如果基因序列中只有一個頻繁工序塊，則選取基因序列中從第一個頻繁工序塊的首塊工序到基因序列的最后一道工序之間的基因片段計算個體之間的海明距離。采用分段海明距離引導(dǎo)變異操作時，迭代前期種群中個體之間差異較大，分段海明距離較大，需要變異的基因位置多，加強了算法的局部搜索能力；迭代后期種群中個體之間差異變小，分段海明距離較小，需要變異的基因位置少，增強了算法的穩(wěn)定性。

從種群中選取一個適應(yīng)度值最高的個體與待變異個體計算分段海明距離。如果被選中個體的分段海明距離為0，則該個體不再進行變異操作；如果被選中的個體的分段海明距離不為0，則隨機選擇其中幾個（偶數(shù)）相異點進行基因互換，以此降低兩個個體之間的分段海明距離，見圖7。

圖7 變異操作Fig.7 Mutation operation

3 結(jié)果與分析

通過以上分析，采用C++編程語言對本文所提出的算法進行設(shè)計驗證，選用JSP問題基準(zhǔn)算例中若干組中小型的實驗進行測試，其中包含30個LA問題算例和2個FT算例。實驗環(huán)境：64位Windows7操作系統(tǒng)的計算機，CPU主頻為3.3 GHz，內(nèi)存為4 GB。整個實驗過程中，AR-GA算法的相關(guān)參數(shù)設(shè)置為：（1）JSP問題的種群規(guī)模為500；（2）最小支持度為0.35；（3）最小置信度為0.75；（4）混合式比例a=80%；（5）交叉概率Pc=0.8；（6）變異概率Pm=0.1；（7）每個JSP問題實例獨立運行20次；（8）最大迭代次數(shù)為100。本文符號定義與解釋如表2所示。

表2 符號定義與解釋Tab.2 Symbol definition

采用AR-GA算法對32個JSP問題算例進行測試，實驗結(jié)果如表3所示，為了對比AR-GA算法的初始種群能否更好地提高種群解質(zhì)量和種群穩(wěn)定性，在表3中同時給出了傳統(tǒng)GA算法求解JSP問題測試結(jié)果。

表3 案例測試結(jié)果Tab.3 Case test results

AR-GA算法的相對誤差ε和傳統(tǒng)GA算法的相對誤差ε′計算式為

為了更好地驗證AR-GA算法的可行性和有效性，本文測試了32個基準(zhǔn)算例，表格3中的LA15，LA16，LA17，LA21，LA22，LA24，LA25，LA26，LA27，LA28，LA29，LA30和FA20基準(zhǔn)案例計算結(jié)果表明，與傳統(tǒng)GA相比較，AR-GA算法在最優(yōu)解、平均最優(yōu)解、相對誤差和程序運行時間等幾個方面獲得了更好的近似最優(yōu)解，并且隨著解決問題規(guī)模增大，AR-GA算法的優(yōu)勢越明顯。

圖8為不同規(guī)模案例的收斂過程，迭代初期，AR-GA算法的初始解質(zhì)量明顯優(yōu)于傳統(tǒng)GA算法的，表明通過關(guān)聯(lián)規(guī)則改善遺傳算法初始種群的方法是有效可行的；迭代前期，AR-GA算法的最優(yōu)解曲線和平均解曲線相比傳統(tǒng)GA算法下降速率更快，AR-GA算法表現(xiàn)出收斂速度快和全局搜索能力強等特點；迭代后期，AR-GA算法獲得最優(yōu)解的迭代次數(shù)以及最優(yōu)解的質(zhì)量要優(yōu)于傳統(tǒng)GA算法的，在獲得最優(yōu)解后，AR-GA算法最優(yōu)解曲線不出現(xiàn)反彈且平均最優(yōu)解曲線仍繼續(xù)下降，AR-GA算法表現(xiàn)出較強的穩(wěn)定性和尋優(yōu)能力。因此，提高算法初始種群質(zhì)量和個體之間的關(guān)聯(lián)性，可在相同時間內(nèi)搜索更多有價值的解子集，從而能夠獲得更好的最優(yōu)解。

圖8 不同規(guī)模案例的收斂曲線Fig.8 Convergence curves of different scale cases

由圖9可知，AR-GA算法的相對誤差和程序運行時間優(yōu)于傳統(tǒng)GA算法，前者說明AR-GA算法的穩(wěn)定性更優(yōu)，后者說明AR-GA算法求解速率更快，其主要原因在于AR-GA算法利用關(guān)聯(lián)規(guī)則找到基因序列中具有關(guān)聯(lián)性的優(yōu)勢工序組合，提高了算法初始解質(zhì)量，改善了算法的穩(wěn)定性。圖10顯示了AR-GA算法求解不同規(guī)模案例的計算結(jié)果。

圖9 算法的運行時間和相對誤差Fig.9 Running time and relative error of the algorithm

圖10 AR-GA算法求解不同規(guī)模案例的計算結(jié)果Fig.10 Calculation results of different scale cases by AR-GA

4 結(jié)論

（1）通過采用頻繁工序塊提升初始種群質(zhì)量的方法是可行的，且效果較為明顯。在32個基準(zhǔn)案例的測試結(jié)果中，本文提出的AR-GA算法初始種群質(zhì)量比傳統(tǒng)的遺傳算法提升約4.573%。

（2）通過設(shè)計與頻繁工序塊相對應(yīng)的交叉、變異方式，使種群中的個體進行更有效地交叉、變異操作，引導(dǎo)子代種群向好的趨勢進化。

（3）本文所提方法在將來的研究中可以解決具有不同約束條件的多目標(biāo)作業(yè)車間調(diào)度問題，也可以將AR-GA算法和鄰域搜索機制融合，從而產(chǎn)生性能更好的混合優(yōu)化算法。