改進(jìn)遺傳算法求解基于MPN混流制造車間調(diào)度問題

王美林，曾俊杰，成克強(qiáng)，陳曉航

（廣東工業(yè)大學(xué) 信息工程學(xué)院，廣東 廣州 510006）

混流制造(Hybrid Flow Shop，HFS)是一種常用且主流的大批量定制生產(chǎn)(Mass Customization Production，MCP)組織模式，可以通過定制階段并行機(jī)上的工藝參數(shù)滿足客戶多樣化的產(chǎn)品需求。HFS本質(zhì)上是一個(gè)NP-Hard難題[1]，而其系統(tǒng)規(guī)模大、資源約束多的特性，導(dǎo)致了解空間過大難以求解的問題。

國(guó)內(nèi)外很多研究團(tuán)隊(duì)對(duì)混流制造的調(diào)度問題進(jìn)行了深入的研究。何軍紅等[2]針對(duì)在MES系統(tǒng)(Manufacturing Execution System，MES)生產(chǎn)調(diào)度模塊的柔性作業(yè)車間問題，提出了3個(gè)階段的優(yōu)化調(diào)度算法，對(duì)具有10個(gè)庫所、6個(gè)工件的HFS問題進(jìn)行求解。王秀萍[3]針對(duì)柔性車間提出一種具有優(yōu)先級(jí)的啟發(fā)式算法，能夠?qū)?0個(gè)庫所、10個(gè)工件的問題求解。而何濤[4]針對(duì)智能制造柔性車間采用了改進(jìn)過的遺傳算法，將機(jī)器的選擇與工件的順序進(jìn)行分段，對(duì)6個(gè)庫所、4個(gè)工件的加工問題進(jìn)行求解。在求解調(diào)度問題中，研究人員嘗試了各類智能算法。如黃亞平[5]在基于汽輪機(jī)的智能調(diào)度系統(tǒng)上采用改進(jìn)的蟻群算法解決生產(chǎn)調(diào)度問題，在調(diào)度任務(wù)發(fā)生變化時(shí)快速地根據(jù)上次調(diào)度結(jié)果進(jìn)行重調(diào)度。又如田松齡[6]針對(duì)柔性車間，采用異步仿真時(shí)鐘的蟻群并行搜索算法，減低資源共享型系統(tǒng)的運(yùn)算成本。白俊峰[7]針對(duì)車間調(diào)度問題采用包含了精英保留策略與逆轉(zhuǎn)變異機(jī)制的遺傳算法，其在求解7個(gè)工件、5臺(tái)機(jī)器的案例中能夠有較好的效果。余璇[8]針對(duì)柔性調(diào)度問題提出一種混合遺傳禁忌搜索算法，對(duì)問題模型進(jìn)行優(yōu)化并能夠在10×10的案例中獲得不錯(cuò)的效果。吳大立和田海霖等[9-10]針對(duì)Petri網(wǎng)建模的車間作業(yè)調(diào)度問題，采用數(shù)學(xué)的方法對(duì)染色體編碼并提出基于GA(Genetic Algorithm)算法的優(yōu)化求解。但是以上算法多是針對(duì)特定場(chǎng)景較小規(guī)模問題進(jìn)行求解，在面臨大規(guī)模問題時(shí)都無法避免地形成巨大的解空間或陷入局部解。

本文針對(duì)HFS大規(guī)模HFS系統(tǒng)的調(diào)度難題，使用MPN(Manufacturing Petri Net)[11]建模方式進(jìn)行模型壓縮，采用2段編碼方式重塑染色體限定搜索范圍，用包含粒子群機(jī)制(Particle Swarm Optimization，PSO)交叉子、模擬退火機(jī)制(Simulated Annealing Algorithm，SAA)變異子與鄰域搜索機(jī)制的改進(jìn)遺傳算法來改進(jìn)解搜索方向以優(yōu)化大規(guī)模HFS問題的求解。

1 問題描述

混合流水車間問題可以描述為：一共有n個(gè)待加工工件，它們需要經(jīng)過s道工序進(jìn)行加工，每道工序會(huì)存在Mi臺(tái) 并行機(jī)器(Mi≥1;i=1，2，···，s)；同一工序上不同類型的機(jī)器加工同一工件的加工時(shí)間會(huì)有所不同；而且每個(gè)工件都要經(jīng)過每一道工序進(jìn)行加工；當(dāng)工件被排產(chǎn)到第i道工序時(shí)可以被該工序中的Mi臺(tái)并行機(jī)中的任意一臺(tái)機(jī)器加工；而且車間中的所有機(jī)器都是非搶占式。

以圖1為例，圖1描述了一個(gè)包括了2個(gè)階段工序的HFS系統(tǒng)。工序1有M型并行機(jī)2臺(tái)和N型并行機(jī)2臺(tái)，共4臺(tái)，工序2有H型并行機(jī)2臺(tái)和G型并行機(jī)2臺(tái)一個(gè)共4臺(tái)。對(duì)圖1中的HFS系統(tǒng)采用MPN模型進(jìn)行同類并行機(jī)壓縮建模后，可以將一個(gè)4×2的HFS模型壓縮成一個(gè) 2 ×2的HFS MPN模型，其中資源約束相同的同型設(shè)備被建模成MPN中的一個(gè)place節(jié)點(diǎn)。在MPN模型中，HFS作業(yè)的調(diào)度問題轉(zhuǎn)換為在制品工件Token，在目標(biāo)函數(shù)監(jiān)督下，全部從庫所p0轉(zhuǎn)移到pl的路徑搜索問題。

圖1 混合流水車間案例Fig.1 Case of hybrid flow workshop

2 模型構(gòu)建

2.1 模型建立

本文針對(duì)以上基于MPN的HFS調(diào)度，為了適應(yīng)改進(jìn)GA算法壓縮解搜索空間的需求，在MPN的Petri模型基礎(chǔ)上，加入用于描述工件加工可選路徑的約束和生成作業(yè)集約束，避免算法運(yùn)行時(shí)的盲目搜索。模型案例如圖2所示。

圖2 基于案例的MPN模型Fig.2 Case-based MPN model

本文的MPN模型定義如下[11]：

(1)P={p1，p2，···，pl}是模型中庫所的有限集合，表示生產(chǎn)車間中的同類型并行機(jī)集合。

(2)E={t1，t2，···，tl}是有限的集合，用于生產(chǎn)狀態(tài)變化的觸發(fā)器。

(3)I，O分別表示工件離開庫所和進(jìn)入庫所的路徑。

(4)S是MPN模型中所有庫所令牌的狀態(tài)向量，Sτ(pi)表 示庫所pi在時(shí)間τ 時(shí) 的所有令牌數(shù)量。S0表示MPN的初始狀態(tài)，Sl表示MPN的結(jié)束狀態(tài)。

(5)K(pi) 是 一個(gè)函數(shù)表示庫所pi內(nèi)并行機(jī)的數(shù)量也就是庫所的容量。

(6) Θ (θ)={Φ}是工件類型函數(shù)，能夠計(jì)算得出工件 θ的 類 型 集 合Φ ，Φ 表 示 工 件 類 型 的 集 合 即Φ ∈{c1，c2，···，cμ}。

(7)D是各種不同類型的工件在庫所中進(jìn)行加工的時(shí)間矩陣。

(8)W(M)是 MPN模型中從庫所p0到pl的加工路徑所組成的向量集合。r為路徑向量的索引。W(M)r表示W(wǎng)(M) 中的第r條路徑。如圖2所示，其W(M)={，T，T， T}。

( 9 )Q(θ，pi)={(θ，pi)|θ ∈Order，pi∈P，(θ，pi)∈θ×W(M)r}，是表示工件θ 選擇了路徑W(M)r完成所有操作所產(chǎn)生的作業(yè)集合。如工件1選擇了2號(hào)路徑(W(M)2 )則其作業(yè)集為{Q(1，p1)，Q(1，p4)}。

(10)s((θ，pi))、c((θ，pi)) 分別表示工件θ 在庫所pi上的進(jìn)入時(shí)間與離開時(shí)間。且s((θ，pi))-c((θ，pi))≥D(Θ(θ)，pi)。

(11) Order是進(jìn)入MPN的一個(gè)加工訂單，包含了一定數(shù)量不同類型工件token集合。

2.2 優(yōu)化目標(biāo)

2.3 基于MPN模型的染色體編碼

目前處理柔性加工問題的染色體結(jié)構(gòu)有兩種，將作業(yè)的選擇與安排混合考慮[12]或分開考慮[13]。本文采用后者，將一個(gè)完整的染色體分為：路徑選擇段，作業(yè)安排段。選擇段為染色體的第一段genestring0用于描述約束(式(2))。其余部分為每個(gè)工序階段對(duì)應(yīng)一個(gè)安排段，描述每個(gè)階段所有加工作業(yè)的優(yōu)先約束(式(3))和資源約束(式(4))。

以圖2的Petri網(wǎng)為例。假定place容量設(shè)置為{K(pi)}T={(2，2，2，2)|(i∈[1，4])}，Order由4個(gè)不同類型的工件組成，表示為 {θ1，θ2，θ3，θ4}、 Φ 分別為{c1，c2，c3，c4}。圖3為算法1生成的一個(gè)用染色體編碼方案。genestring0記錄了Order中4個(gè)工件分別選擇了1，4，4，4號(hào)路徑，形成了p1作 業(yè)的作業(yè)集合{Q(1，p1)}、p2作業(yè)的作業(yè)集合{Q(2，p2)，Q(3，p2)，Q(4，p2)}、p3作業(yè)的作業(yè)集合{Q(1，p3)}、p4作業(yè)的作業(yè)集合{Q(2，p4)，Q(3，p4)，Q(4，p4) }。g enestring1記 錄了工序1庫所p1和p2的 工件處理順序：p1只 有工件1，p2工件處理順序?yàn)?、4、3。

圖3 染色體編碼結(jié)果Fig.3 Chromosome coding results

由染色體的編碼算法1，可看出染色體將具體的調(diào)度方案分成了選擇段與安排段。選擇段確定了工件要以經(jīng)過哪條加工路線的庫所完成加工，即每個(gè)庫所pi會(huì)接收到什么作業(yè)，而安排段記錄庫所pi內(nèi)接收作業(yè)的處理順序。當(dāng)給出一個(gè)D矩陣時(shí)，圖3中的染色體便能夠獲得該編碼在MPN模型下所有作業(yè)的s((θ，pi))、c((θ，pi))，并可以將它們記錄在一個(gè)schedule中。

3 染色體約束與優(yōu)化

很多使用染色體對(duì)車間問題進(jìn)行求解時(shí)都會(huì)采用調(diào)整算法去掉部分的無用解[14-15]，但由于調(diào)整方法簡(jiǎn)單且無法壓縮解空間，所以對(duì)本文的大規(guī)模HFS問題不適用。在此本文設(shè)計(jì)了染色體安排段優(yōu)化算法對(duì)染色體(解空間)的編碼過程進(jìn)行補(bǔ)充。

染色體安排段優(yōu)化算法是在算法1編碼的基礎(chǔ)上，對(duì)pi內(nèi)接收作業(yè)(即其對(duì)應(yīng)安排段)的處理順序進(jìn)行有限次數(shù)有反饋的調(diào)整。反饋機(jī)制是尋找拖慢調(diào)度的起始作業(yè)操作，并調(diào)整下次迭代中工序1的相應(yīng)操作順序來優(yōu)化該操作。由于該算法通過反饋解決了調(diào)整方向的問題，而且該算法對(duì)相同選擇段的染色體，執(zhí)行一定次數(shù)迭代調(diào)整后，獲得唯一最優(yōu)的染色體安排段。

染色體安排段優(yōu)化算法2:

4 算法設(shè)計(jì)

為了探索本文所研究的MPN模型下的HFS問題的優(yōu)解，提出了一種改進(jìn)的遺傳算法(Improved Genetic Algorithm，IGA)。目前很多的遺傳算法都會(huì)為其交叉變異添加新的機(jī)制[16]，但是無法處理大規(guī)模問題。本算法結(jié)合了3種方法從3個(gè)方面解決了遺傳算法在求解問題中所遇到的難題。(1) 本文會(huì)使用如圖4的方式將染色體選擇段與適應(yīng)度進(jìn)行關(guān)聯(lián)，讓遺傳算法(IGA)把搜索的精力集中在搜尋最優(yōu)的染色體選擇段上，壓縮可行解空間。(2) 本文的算法所使用的交叉子將采用粒子群優(yōu)化(PSO)機(jī)制，而變異子將采用模擬退火算法(SAA)機(jī)制，這樣的組合有利于改善遺傳算法過早收斂的問題。(3) 算法還會(huì)對(duì)每次迭代的最優(yōu)個(gè)體(Optimal Individual，OI)進(jìn)行鄰域搜索挖掘該個(gè)體的“潛力”。

圖4 以染色體選擇段代替完整染色體與適應(yīng)度進(jìn)行關(guān)聯(lián)Fig.4 Using chromosome selection segments to connect with fitness

4.1 以染色體選擇段代替完整染色體與適應(yīng)度進(jìn)行關(guān)聯(lián)

交叉、變異、鄰域搜索的運(yùn)算只需要使用選擇段即可，當(dāng)需要進(jìn)行染色體間比較時(shí)，染色體能夠通過，獲取詳細(xì)信息并使用式(5)得出染色體的適應(yīng)度來進(jìn)行比較。這樣便可在無需考慮無用解(不合理的染色體)的同時(shí)讓遺傳算法只去篩選選擇段，壓縮了解空間。之后出現(xiàn)的遺傳算法的各種操作都是對(duì)染色體選擇段進(jìn)行操作，而且認(rèn)為選擇段就是一個(gè)完整的個(gè)體適應(yīng)度函數(shù)。

Cmax為schedule table中最大的值(最后一個(gè)作業(yè)的完成時(shí)間)。

4.2 粒子群算法與模擬退火法在遺傳算法上的結(jié)合運(yùn)用

4.2.1 交叉算子

為了提高算法收斂性，本文引入PSO機(jī)制(其中GI1表 示guided individual、P I1表示 parent individual1、PI2表示 parent individual2、O I1表示Offspring individual1、 OI2表示Offspring individual2)。它們使用了特殊的交叉方式 (GI1+PI1+PI2→OI1&OI2)，從群內(nèi)個(gè)體兩兩交叉生成兩個(gè)子代，變?yōu)槿和庖粋€(gè)( GI1)與群內(nèi)兩個(gè)( PI1& P I2)個(gè)體交叉獲得兩個(gè)子代，保證了后代個(gè)體 OI1、 O I2有明確的優(yōu)化方向，使種群的收斂性提高。

然后為交叉引入k1、k2、L三個(gè)變量，k1表示從GI1個(gè) 體中學(xué)習(xí)的學(xué)習(xí)率，k2表示從另一個(gè)父代個(gè)體中學(xué)習(xí)的學(xué)習(xí)率，L表示選擇段的長(zhǎng)度。具體交叉方式為(如圖5)：使用當(dāng)前迭代所得的最優(yōu)個(gè)體作為引導(dǎo)個(gè)體 ( GI1) 并隨機(jī)抽出兩個(gè)父代個(gè)體(P I1& P I2)。后代 OI1以P I1為 基 礎(chǔ)(O I2以P I2為 基 礎(chǔ))，并 學(xué) 習(xí)(L/2)×k1個(gè) GI1的基因，學(xué)習(xí)方式為直接將選中的基因覆蓋在 PI1( PI2)上如圖5的黃色基因，然后再學(xué)習(xí)(L/2)×k2個(gè)P I2(P I1)的基因，學(xué)習(xí)方式為直接將選中的基因覆蓋在 PI1(P I2) 上，但不可以選之前在G I1中選中的位置，如圖5的藍(lán)色基因。

圖5 交叉算子Fig.5 Crossover operator

由于PSO機(jī)制的添加，引導(dǎo)個(gè)體(本群內(nèi)最優(yōu)染色體)參與群內(nèi)交叉能夠引導(dǎo)染色體的生產(chǎn)方向，提高收斂性。

4.2.2 變異算子

為了避免遺傳算法過早收斂的弊端，本文改進(jìn)了變異算子，引入新的模擬退火(SAA)機(jī)制，使用接收概率實(shí)現(xiàn)變異結(jié)果的條件接受，使用變異傾向函數(shù)實(shí)現(xiàn)變異的方向性指導(dǎo)，從而提高未出現(xiàn)基因序列的出現(xiàn)概率。兩者組合可以幫助算法跳出局部最優(yōu)解。

在本節(jié)中，變異算子設(shè)計(jì)如下：

Step1: 在個(gè)體中隨機(jī)選擇一個(gè)位置。

Step2: 在選擇的位置上，通過突變趨勢(shì)函數(shù)(式(6))和(式(7))所得出的可選基因元素(路徑)的概率分布，從中按概率選取一個(gè)基因值(路徑)替換原基因。

Step3：通過模擬退火法的接受概率判斷是否接受該變異所得的染色體。

Step4：當(dāng)代總?cè)褐械乃袀€(gè)體都執(zhí)行過變異后，按照模擬退火中Ta=Ta×K的規(guī)則執(zhí)行退火(Ta為當(dāng)前溫度，K為退火常數(shù))，改變溫度，影響下一次算法迭代的接受率。

其中，突變趨勢(shì)函數(shù)將對(duì)每次迭代后出現(xiàn)在個(gè)體上每個(gè)位置的值進(jìn)行計(jì)數(shù)，并獲得在每個(gè)位置突變?yōu)椴煌档南鄳?yīng)概率，從而影響個(gè)體變異的傾向。

其中 θ ∈{Token}，rn∈{Path}，N∈|Path|，G為當(dāng)前的種群代數(shù)，G0是開始的種群代數(shù)。fs(rn，θ，g)表示在第g代中的所有個(gè)體在某個(gè)位置(工件θ)上選擇了某個(gè)基因值(路徑rn)的頻率。

4.3 鄰域搜索摸索最優(yōu)個(gè)體

由于Petri網(wǎng)模型的拓?fù)浣Y(jié)構(gòu)的原因，Chromosome個(gè)體的細(xì)微差別，會(huì)導(dǎo)致適應(yīng)度存在巨大差異。為了能夠激發(fā)當(dāng)前系統(tǒng)發(fā)現(xiàn)的最優(yōu)個(gè)體(OI)，在遺傳算法執(zhí)行過交叉與變異后都會(huì)進(jìn)行最優(yōu)個(gè)體鄰域搜索。

鄰域搜索算法：

其中基本鄰域搜索函數(shù)是一個(gè)輸入為最優(yōu)個(gè)體選擇段，輸出為其鄰域(只有一個(gè)位置的值與genestring0不同)內(nèi)的最優(yōu)染色體選擇段。如果鄰域內(nèi)有多個(gè)適應(yīng)度相同的染色體則選擇每個(gè)工件完成時(shí)間的總和最小的個(gè)體。

4.4 IGA算法框架

綜合上述的算法模塊，改進(jìn)遺傳算法的算法流程如圖6所示。

圖6 算法流程圖Fig.6 Algorithm flowchart

5 實(shí)例分析

采用本團(tuán)隊(duì)所研究的基于覆銅板層壓廠混流加工環(huán)境所構(gòu)建的Petri 網(wǎng)模型為基礎(chǔ)[11]，并用同樣的訂單對(duì)本文的算法與所采用的模型的論文所提出的算法進(jìn)行比較。該案例為某覆銅板生產(chǎn)車間案例。

Petri網(wǎng)模型中每個(gè)庫所的容量參數(shù)：

每個(gè)種類在庫所中的加工時(shí)間矩陣D見圖7，訂單加工內(nèi)容見表1，其中矩陣行為工件專利，列為庫所p0到pl。

表1 加工訂單案例Table 1 Case of processing orders

圖7 加工時(shí)間矩陣DFig.7 Processing time matrix D

5.1 參數(shù)設(shè)置

可設(shè)置的參數(shù)一共有7個(gè)：交叉率pc，學(xué)習(xí)因子k1、k2，初始溫度T0， 降溫次數(shù)tn，最優(yōu)適應(yīng)度保持不變的最大忍耐迭代數(shù)tc，染色體安排段優(yōu)化算法的參數(shù)DN 。最優(yōu)參數(shù)的測(cè)試一共分為兩組，前6個(gè)(pc，k1，k2，T0，tc，tn) 與最后一個(gè)參數(shù)D N 。前6個(gè)參數(shù)在D N固定的前提下采用田口實(shí)驗(yàn)獲得最優(yōu)的參數(shù)。參數(shù) DN在使用之前獲得的最優(yōu)6組參數(shù)后采用控制變量測(cè)出。

前6個(gè)參數(shù)的實(shí)驗(yàn)范圍如表2所示，分別為：pc∈[0.6，1] ，k1∈[0.1，0.5] ，k2∈[0.1，0.5] ，T0∈[50，250]，tc∈[5，25]，tn∈[5，25] 。水平劃分：前6個(gè)參數(shù)(pc，k1，k2，T0，tc，tn) ，在種群數(shù)ps為100，最大迭代數(shù)Gmax為250，DN=2的參數(shù)前提下按水平劃分進(jìn)行分組測(cè)試，不同實(shí)驗(yàn)組每組10次實(shí)驗(yàn)，并取對(duì)應(yīng)指標(biāo)的平均值。

表2 前6個(gè)參數(shù)的實(shí)驗(yàn)范圍Table 2 The experimental range of the first 6 parameters

從表3得知RA>RE>RB>RD>RF>RC，RA、RB、RC、RD、RE、RF它們分別代表表中ABCDEF列相應(yīng)因素的級(jí)差，級(jí)差越大影響越明顯(7.8>6.6>6.3>6.1>4.7>3.9) ，所以參數(shù)為：pc=0.9，k1=0.5，k2=0.2，T0=50，tc=25，tn=20。

表3 田口實(shí)驗(yàn)Table 3 Taguchi experiment

從圖8可以獲得最終的參數(shù)pc=0.9 ，k1=0.5，k2=0.2 ，T0=50 ，tc=25 ，tn=20 ， D N=3 ， p s=100，Gmax=250。

圖8 參數(shù)DN在之前所獲得的最優(yōu)的參數(shù)的基礎(chǔ)上對(duì)其進(jìn)行討論Fig.8 Parameters discussion on the basis of the optimal parameters obtained before

5.2 最優(yōu)結(jié)果

圖9中，藍(lán)色曲線所代表的遺傳算法使用了具備粒子群優(yōu)化(PSO)機(jī)制的交叉子，而棕色曲線則代表使用了普通交叉子的遺傳算法。從圖9可知，改進(jìn)后的交叉子對(duì)遺傳算法的收斂性有所改善。其曲線所代表的種群內(nèi)各個(gè)體的Cmax值(適應(yīng)度的絕對(duì)值)的均值在大約140代收斂于最優(yōu)值，收斂性明顯提高。普通的交叉子由于HFS問題的巨大規(guī)模再加上其輪賭式的交叉規(guī)則，使在個(gè)體產(chǎn)生細(xì)微變化就會(huì)導(dǎo)致適應(yīng)度大幅變化的環(huán)境下，卻實(shí)行無方向式的概率交配。通過給改進(jìn)遺傳算法添加改進(jìn)的交叉算子，提高了總?cè)汉蟠^承前代優(yōu)秀基因片段的能力，讓算法達(dá)到更好的收斂效果。

圖9 在250次迭代過程中，種群內(nèi)個(gè)體的均值變化曲線對(duì)比Fig.9 Comparison of mean change curves of individuals in the population during 250 iterations

圖10代表當(dāng)前迭代次數(shù)出現(xiàn)過的最優(yōu)個(gè)體的Cmax。藍(lán)色曲線代表添加了最優(yōu)個(gè)體鄰域搜索，而且使用了具備模擬退火算法(SAA)機(jī)制變異子的改進(jìn)遺傳算法，而棕色曲線則代表普通遺傳算法。從圖10可知，添加了最優(yōu)個(gè)體鄰域搜索，而且使用改進(jìn)的變異子對(duì)遺傳算法的搜索能力有所提高。對(duì)比普通的遺傳算法，可以看出藍(lán)色曲線的最優(yōu)Cmax值為373在大約第77代獲得，而棕色曲線的最優(yōu)Cmax值為390在第87代獲得，算法的搜索能力有明顯的提高。通過給改進(jìn)遺傳算法添加改進(jìn)的變異算子，提高了群內(nèi)個(gè)體探索新基因組合的能力；通過給改進(jìn)遺傳算法添加鄰域搜索，提高了最優(yōu)個(gè)體主動(dòng)探索的能力，讓算法達(dá)到更好的搜索效果。

圖10 在250次迭代過程中，最優(yōu)解的變化過程對(duì)比。Fig.10 Comparison of the change process of the optimal solution during 250 iterations.

5.3 效果對(duì)比

表4為相同MPN模型下相同案例中，采用文獻(xiàn)[11]中的蟻群優(yōu)化算法、標(biāo)準(zhǔn)遺傳算法和采用本文的改進(jìn)遺傳算法進(jìn)行對(duì)比所得的結(jié)果。采用改進(jìn)遺傳算法所得出的最優(yōu)解373明顯優(yōu)于文獻(xiàn)[11]蟻群算法中所得出的最優(yōu)解393與標(biāo)準(zhǔn)遺傳算法的523，而且達(dá)到最優(yōu)的次數(shù)在100次中出現(xiàn)了83次，優(yōu)化結(jié)果穩(wěn)

表4 效果對(duì)比Table 4 Effect comparison

定。而文獻(xiàn)[11]中的蟻群優(yōu)化達(dá)到最優(yōu)的次數(shù)有79次，雖然較為穩(wěn)定但最優(yōu)解卻只有393。標(biāo)準(zhǔn)遺傳算法因?yàn)闊o法適應(yīng)大規(guī)模的混流車間問題，在最優(yōu)解上只得到了523，到達(dá)的次數(shù)也只有25次。從中可以看出改進(jìn)遺傳算法相比于蟻群優(yōu)化算法與標(biāo)準(zhǔn)遺傳算法能夠獲得相對(duì)更優(yōu)的優(yōu)化結(jié)果且達(dá)到最優(yōu)解更為穩(wěn)定。如圖11為案例最優(yōu)結(jié)果甘特圖。

圖11 實(shí)驗(yàn)結(jié)果甘特圖Fig.11 Gantt chart of experimental results

6 結(jié)論

為了解決基于MPN模型下的混流車間問題，本文采用了一種改進(jìn)的遺傳算法對(duì)優(yōu)化的目標(biāo)進(jìn)行求解，并通過實(shí)驗(yàn)證明其有效性。最后獲得的結(jié)論如下。

(1) 在每個(gè)染色體進(jìn)行編碼時(shí)，利用染色體安排段優(yōu)化算法對(duì)染色體進(jìn)行補(bǔ)全，并采用固定的求解過程讓染色體的選擇段與適應(yīng)度進(jìn)行綁定，可以有效壓縮遺傳算法的搜索空間，為HFS大規(guī)模問題的求解提供一個(gè)縮減后的解空間。

(2) 改進(jìn)式遺傳算法通過染色體進(jìn)行交叉與變異時(shí)，分別使用粒子群與模擬退火的機(jī)制，可以提高遺傳算法的搜索效率，為求解大規(guī)模HFS問題提供優(yōu)質(zhì)個(gè)體。

(3) 改進(jìn)式遺傳算法通鄰域搜索讓當(dāng)前代所得的最優(yōu)染色體(優(yōu)質(zhì)染色體)主動(dòng)對(duì)自己進(jìn)行優(yōu)化，實(shí)現(xiàn)求解大規(guī)模HFS問題的精確搜索。

（責(zé)任編輯：楊耀輝）