改進(jìn)的初始種群的遺傳算法在柔性車間調(diào)度中的應(yīng)用

牛 琳

(海南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，?？?571100)

改進(jìn)的初始種群的遺傳算法在柔性車間調(diào)度中的應(yīng)用

牛 琳

(海南醫(yī)學(xué)院 醫(yī)學(xué)信息學(xué)院，?？?571100)

針對(duì)柔性作業(yè)車間調(diào)度中單純的遺傳算法容易陷入局部陷阱問(wèn)題，結(jié)合柔性作業(yè)車間調(diào)度的特點(diǎn)，采用模擬退火算法融合遺傳算法對(duì)調(diào)度領(lǐng)域進(jìn)行了研究。應(yīng)用模擬退火算法能跳出局部陷阱的能力及克服了遺傳算法過(guò)早熟的現(xiàn)象，很大程度上降低算法的收斂速度，同時(shí)提高了全局的收斂性。基于Matlab2012b軟件編程實(shí)現(xiàn)混合調(diào)度算法，文中仿真實(shí)例用混合調(diào)度算法，將結(jié)果與單純的遺傳算法得到的結(jié)果進(jìn)行比較，證明了混合算法的優(yōu)勢(shì)。

遺傳算法；柔性作業(yè)車間調(diào)度；初始種群

0 引言

柔性工作車間調(diào)度問(wèn)題( Flexible Job Shop Scheduling Problem, FJSP)[1]，F(xiàn)JSP也稱為工件的排序問(wèn)題。其分析與研究目的在于企業(yè)實(shí)現(xiàn)效益最優(yōu)化—對(duì)加工工序進(jìn)行高效排序，在約束條件下，使得所選擇的某個(gè)性能指標(biāo)達(dá)到最優(yōu)狀態(tài)。遺傳算法的魯棒性好，通用性和計(jì)算性能強(qiáng)大，因此較多的用在FJSP的問(wèn)題中。但在實(shí)際應(yīng)用時(shí)由于收斂條件難以保證，所以目前國(guó)內(nèi)外很多文獻(xiàn)對(duì)遺傳算法求解FJSP問(wèn)題提出了改進(jìn)策略。例如，歐陽(yáng)珍，狄瑞坤[2]融入模擬退火算法，提高了種群個(gè)體的多樣性。柳青紅等[3]提出了基于禁忌搜索的遺傳交叉算子，改進(jìn)收斂速度。Zhang H P, Gen M[4-6]提出了一種多階段遺傳算法有效的改進(jìn)了局部收斂問(wèn)題。KACEM I，HAMMADI S, BORNE P[7-8]將遺傳算法與模糊理論相融合并應(yīng)用于柔性作業(yè)車間調(diào)度問(wèn)題。通過(guò)分析遺傳算法求解FJSP問(wèn)題方面已經(jīng)取得一些成果，但在求解過(guò)程中出現(xiàn)的問(wèn)題還有待于進(jìn)一步探究改進(jìn)。文獻(xiàn)[9]采用MPGA種群遺傳算法結(jié)合移民算子對(duì)車間調(diào)度問(wèn)題進(jìn)行了研究。劉韻[10]等采用PSO啟發(fā)搜索式的粒子群優(yōu)化算法，解決了柔性車間調(diào)度時(shí)間問(wèn)題。文獻(xiàn)[11]通過(guò)遺傳算法結(jié)合模糊算法對(duì)車間空間的搜索時(shí)間和收斂速度進(jìn)行了改進(jìn)。

鑒于此，本文在文獻(xiàn)[2]的基礎(chǔ)上對(duì)算法進(jìn)行改進(jìn)，將遺傳算法和模擬退火算法結(jié)合在一起，通過(guò)典型的柔性作業(yè)車間調(diào)度問(wèn)題，將改進(jìn)前后的調(diào)度結(jié)果進(jìn)行比較分析，調(diào)度結(jié)果有了一定程度的提高，速度也有了一定程度的縮短，并將混合算法和單純的遺傳算法進(jìn)行調(diào)度最優(yōu)解的對(duì)比，詳細(xì)的分析了兩者收斂代數(shù)、調(diào)度時(shí)間，證明了混合算法的優(yōu)于單純的遺傳算法。

1 FJSP數(shù)學(xué)優(yōu)化模型

柔性操作車間可調(diào)度問(wèn)題通常可簡(jiǎn)述為：存在N個(gè)加工工件，需要用M臺(tái)機(jī)器加工，需加工的每個(gè)工件包含多重加工工序，每道工序可以在一臺(tái)或多臺(tái)機(jī)器上加工，加工時(shí)間隨機(jī)器因素的差異而異同，規(guī)定工件的前一道工序未加工后一道工序則不能進(jìn)行，同一類工件的所有工序之間存在先后順序；每個(gè)工序同一時(shí)刻只能在一臺(tái)機(jī)器上加工。問(wèn)題目標(biāo)為每重工序需選擇最合適的機(jī)器，需要在這些工藝約束條件下，調(diào)整每一臺(tái)機(jī)器上不相同工件間的加工順序,使機(jī)器加工性能達(dá)到最優(yōu)狀態(tài)。

1.1 FJSP變量定義

(1)N：工件數(shù)量，M：機(jī)器數(shù)量，n：工序數(shù)。

(2)工件集合用數(shù)組J表示，J={J1,J2,…,Jj}，Jj為第j個(gè)工件，j=1,2，……，N。

(3)機(jī)器集合用數(shù)組P表示，P={P1,P2,…,Pp}，PP為第p個(gè)機(jī)器，p=1,2，……，M。

(4)對(duì)應(yīng)工序所用的加工機(jī)器為Ppj(1)，Ppj(2)，…，Ppj(n)。則機(jī)器的加工順序矩陣為P：

其中,Ppj(n)：j工件的工序n在機(jī)器Pp(p=1,2,…,M)上加工。

(5)加工時(shí)間集合用矩陣Tp表示:

其中,Tpj(n)：j工件的工序n的加工時(shí)間(在機(jī)器Pp上)。

(6)tjp定義為工件j在機(jī)器p上的總加工時(shí)間。

(7)cjp定義為工件j在機(jī)器p上的完工時(shí)間。

1.2 調(diào)度目標(biāo)數(shù)學(xué)模型

目標(biāo)函數(shù)為：在給定的工藝約束條件下進(jìn)行調(diào)度優(yōu)化，使最大完工時(shí)間(makespan)最小，或者最小生產(chǎn)周期，即如何安排加工使得加工所有工件的時(shí)間最短；

(1)

約束條件：

cjp-tjp+A(1-ajhp)≥cjh

(2)

cjp-cip+A(1-xijp)≥tjp

(3)

cjp≥0;xijp,ajhp=0,1

(4)

cjp-cjh≥tjh

(5)

i,j=1,2,…,N;p,h=1,2,…,M

(6)

tjp：表示工件j在機(jī)器p上的加工時(shí)間；A表示一個(gè)值較大的正數(shù)；若工件i先于工件j在機(jī)器p上加工，則Xijp=1，否則Xijp=0；

當(dāng)機(jī)器h比機(jī)器p先加工工件i時(shí)，aihp為1，否則aihp為0。

式(2)確保工序在某時(shí)刻只可在唯一機(jī)器上加工。

式(3)確保機(jī)器在某時(shí)刻僅加工唯一工件。

式(4)確保每道工序在此生產(chǎn)過(guò)程中都得到加工。

式(5)確保工件的加工順序按給定的工藝路線進(jìn)行。

同時(shí)，每個(gè)工件、同一工件的每道工序之間必須嚴(yán)格按照給定的工藝約束，工序開(kāi)始加工之后不能中止，每個(gè)工件的優(yōu)先級(jí)一樣。

2 模擬退火算法的算法設(shè)計(jì)

模擬退火算法主要由升溫過(guò)程、恒溫過(guò)程和降溫過(guò)程組成。升溫過(guò)程是初始化溫度參數(shù)的過(guò)程，一般選擇一個(gè)較高溫度作為初始溫度，這樣可以在一定程度上增加模擬退火算法搜索整個(gè)解空間最優(yōu)解的機(jī)會(huì)，溫度較高時(shí)，算法在進(jìn)行Metropolis準(zhǔn)則判斷時(shí)可以選擇較差的解作為個(gè)體解；當(dāng)算法的溫度變低時(shí)，算法收斂到最優(yōu)解的概率逐漸變高。所以算法設(shè)計(jì)時(shí)一般選擇較高的溫度作為初始溫度，用來(lái)增強(qiáng)算法跳出局部最優(yōu)解的能力。降溫過(guò)程一般用當(dāng)前溫度T乘以降溫系數(shù)q來(lái)模擬降溫過(guò)程，降溫系數(shù)決定著退火速度。

模擬退火部分的主要步驟如下：

Step1:設(shè)定主要的控制參數(shù)。初始溫度T0=1000C，降溫速率q=0.2，結(jié)束溫度Te=1e-3。

Step2:初始解。對(duì)于混合算法來(lái)說(shuō)，初始解即是遺傳算法中經(jīng)過(guò)交叉、變異后的個(gè)體。

Step3:生產(chǎn)新解。新解在初始解的鄰域生成。編程時(shí)通過(guò)隨機(jī)選擇相鄰的兩個(gè)工序，然后交換兩者的加工順序，產(chǎn)生新解。例如初始解S1=123214，新解可以是S2=213214，即交換了前兩個(gè)工件的加工順序。

Step4:Metropolis準(zhǔn)則。用f(S1)表示初始解的適應(yīng)度，f(S2)表示新解的適應(yīng)度，那么df=f(S2)-f(S1),則Metropolis準(zhǔn)則為：

(7)

3 混合調(diào)度算法的設(shè)計(jì)

分別對(duì)遺傳算法和模擬退火算法的關(guān)鍵部分進(jìn)行設(shè)計(jì)以后，得到的混合算法步驟如下：

Step1:設(shè)定混合算法的初始參數(shù)，包括種群的規(guī)模、遺傳的代數(shù)、初始溫度、降溫系數(shù)、變異概率等參數(shù)；

Step2:依據(jù)個(gè)體的加工工藝進(jìn)行染色體編碼，采用工件工藝和機(jī)器的雙層編碼方式，同時(shí)隨機(jī)初始化種群，并分析種群的適應(yīng)度；

Step3:根據(jù)步驟step2的適應(yīng)度進(jìn)行個(gè)體選擇操作，主要依據(jù)個(gè)體適應(yīng)度的好壞來(lái)進(jìn)行選擇。適應(yīng)度小的個(gè)體被選擇遺傳的概率也較??；

Step4:對(duì)選擇的個(gè)體隨機(jī)選擇基因位置，進(jìn)行交叉操作；

Step5:交叉完成后，根據(jù)變異率選擇個(gè)體進(jìn)行變異操作，產(chǎn)生新的個(gè)體，注意變異后要檢查工藝的邏輯性；

Step6:對(duì)經(jīng)過(guò)遺傳操作后的種群，在染色體解的鄰域內(nèi)產(chǎn)生新的個(gè)體擾動(dòng)解，并利用Metropolis準(zhǔn)則判定是否接受新解；

Step7:執(zhí)行參數(shù)的更新操作，如遺傳代數(shù)，當(dāng)前溫度等；

Step8:如果相關(guān)參數(shù)沒(méi)有達(dá)到規(guī)定的數(shù)值，則轉(zhuǎn)到步驟Step3，當(dāng)參數(shù)到達(dá)設(shè)定值之后，直接結(jié)束，輸出最優(yōu)解。

圖1 混合算法流程圖

4 算例分析

以FJSP生產(chǎn)系統(tǒng)為例。本算例以makespan最小為優(yōu)化目標(biāo)。對(duì)本文提出的改進(jìn)前后的方法進(jìn)行仿真并分析(軟件版本為MATLAB2014a)。表1和表2給出了調(diào)度工藝及時(shí)間要求具。

表1 工件的工序邏輯表

表2 工件各工序的加工時(shí)間

表1給出的是6個(gè)工件的工藝加工要求，對(duì)每一個(gè)單獨(dú)的工件來(lái)說(shuō)，各個(gè)工序必須一次加工作業(yè)，工藝順序不能顛倒。表中的2維數(shù)組是工件在加工相應(yīng)工序時(shí)機(jī)器的可選集，因?yàn)樵趯?shí)際制造系統(tǒng)中，通常工件的某一道工序可以有多個(gè)機(jī)器滿足加工條件，這樣可以一定程度上避免因爭(zhēng)搶機(jī)器資源而使制造系統(tǒng)陷入停頓。表2是按照表1 工序加工時(shí)對(duì)應(yīng)所用的時(shí)間。

改進(jìn)前：在單純的遺傳算法下，取初始參數(shù)個(gè)體數(shù)量為40，最大遺傳代數(shù)為50，交叉率為0.8，變異率為0.1，得到甘特圖如圖2所示。

圖2 遺傳算法下的甘特圖

圖2顯示了遺傳算法產(chǎn)生的一組最優(yōu)調(diào)度方案，所有工件按照調(diào)度方案加工完成所用的最短時(shí)間是52個(gè)時(shí)間單位；圖3是遺傳算法迭代過(guò)程中各代種群均值及最優(yōu)解的變化情況，從圖中可以看出，在經(jīng)過(guò)10代之后，種群均值及最優(yōu)解基本已經(jīng)不再變化，但實(shí)際上是遺傳算法陷入了過(guò)早熟現(xiàn)象的原因，遺傳算法并沒(méi)有搜索到真正有效的最優(yōu)解。表3是遺傳算法運(yùn)行10次的得到的比較好的最優(yōu)解情況。

圖3 種群迭代次數(shù)

通過(guò)表3可以計(jì)算出遺傳算法10次得到的調(diào)度最優(yōu)解的均值為51.2個(gè)時(shí)間單位。

改進(jìn)后：當(dāng)采用混合算法時(shí)，同樣采用表1和表2的工件工藝順序和工藝時(shí)間，并取初始溫度為1000℃，降溫速率為0.2，得到的一組甘特圖和種群均值圖如圖4和圖5所示。

圖4 混合算法下的甘特圖

圖5 種群均值及最優(yōu)解變化

從圖4 中可以看到，混合算法下按照調(diào)度方案完成所有工件加工的最優(yōu)解時(shí)間是48個(gè)時(shí)間單位，從圖5中可以看出混合算法使得種群的均值在15代以后才收斂到最小值，最優(yōu)解也是如此。綜上，從結(jié)果上可以看出混合算法由于模擬退火操作的加入，算法沒(méi)有提前結(jié)束搜索使算法染色體想入同化的情況。表4是混合算法運(yùn)行10次的結(jié)果。

表4 遺傳算法運(yùn)行10次的最優(yōu)調(diào)度結(jié)果

通過(guò)表4可以得到混合算法在降溫速率為0.2時(shí)，10次調(diào)度的平均時(shí)間是47.8個(gè)時(shí)間單位，調(diào)度方案的最優(yōu)解要好于單純的遺傳算法。當(dāng)降溫速率變化時(shí)，通過(guò)實(shí)驗(yàn)得到的實(shí)驗(yàn)數(shù)據(jù)如表5所示。

表5 不同降溫速度下混合算法及遺傳算法最優(yōu)解

從表5中可以看出，當(dāng)遺傳算法和混合算法對(duì)同一問(wèn)題進(jìn)行調(diào)度時(shí)，無(wú)論降溫系數(shù)在0.1～0.9中間任何值，混合算法的調(diào)度最優(yōu)解都要優(yōu)于單純的遺傳算法所產(chǎn)生的調(diào)度方案。通過(guò)分析種群均值穩(wěn)定的代數(shù)也可以發(fā)現(xiàn)，混合算法有效地解決了遺傳算法所存在的過(guò)早熟現(xiàn)象，使得種群迭代過(guò)程中不再過(guò)度依賴于初始解的產(chǎn)生，同時(shí)，通過(guò)模擬退火操作，使得算法搜索整個(gè)解空間的能力大大加強(qiáng)，以降溫速率為0.6的調(diào)度最優(yōu)解為例，普通的遺傳算法10次當(dāng)中沒(méi)有一次得到的最優(yōu)解在50以下，而混合算法幾乎有8次以上低于50，分析調(diào)度結(jié)果可知，調(diào)度最差的降溫速率0.1也有6 次跳出了局部陷阱。而當(dāng)降溫速率為0.9時(shí)，混合算法幾乎全部跳出了局部最優(yōu)解，可見(jiàn)混合算法相對(duì)于單純的遺傳算法有著更好的跳出局部陷阱的能力，得到更優(yōu)的調(diào)度方案。

5 結(jié)論

本文將遺傳算法和模擬退火算法結(jié)合在一起，通過(guò)典型的柔性作業(yè)車間調(diào)度問(wèn)題，將改進(jìn)前后的調(diào)度結(jié)果進(jìn)行比較分析，調(diào)度結(jié)果有了一定程度的提高，速度也有了一定程度的縮短，并將混合算法和單純的遺傳算法進(jìn)行調(diào)度最優(yōu)解的對(duì)比，詳細(xì)的分析了兩者收斂代數(shù)、調(diào)度時(shí)間，證明了混合算法的優(yōu)于單純的遺傳算法，說(shuō)明了這種混合算法在求解FJSP問(wèn)題上的優(yōu)勢(shì)。

[1] 藍(lán)萌, 徐汀榮, 黃斐. 使用混合鄰域搜索算法求解多目標(biāo)柔性JSP問(wèn)題[J]. 計(jì)算機(jī)工程與設(shè)計(jì), 2011, 32(1):293-296.

[2] 歐陽(yáng)珍.基于遺傳算法的車間調(diào)度研究與應(yīng)用[D].杭州:浙江大學(xué),2004.

[3] 柳青紅,袁逸萍,李曉娟.基于改進(jìn)遺傳算法的作業(yè)車間調(diào)度[J].機(jī)械工程與自動(dòng)化，2014(6):1-3.

[4] Zhang H P, Gen M. Multistage-based genetic algorithm for flexible job-shop scheduling problem[J].Journal Complexity, 2005, 11: 223-232.

[5] 陳振同,邢英杰.基于改進(jìn)遺傳算法的車間調(diào)度問(wèn)題研究與應(yīng)用[D]. 大連:大連理工大學(xué)，2007.

[6] 趙振勇,王力,王保華,等.遺傳算法改進(jìn)策略的研究[J].計(jì)算機(jī)應(yīng)用,2006(S2):189-191.

[7] Mastrolilli M, Gambardella L M. Effective neighbourhood functions for the flexible job shop problem[J],Journal of Scheduling, 2000, 3 (1):3-20.

[8] KACEM I，HAMMADI S, BORNE P. Pareto-optimality approach for flexible job shop scheduling problems:hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation, 2002,60(3/4/5):245-276.

[9] 李運(yùn)霞, 杜娟, 孫王路. 基于多種群遺傳算法的路徑柔性車間調(diào)度問(wèn)題[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2014(3):152-157.

[10] 劉韻, 胡毅, 羅企,等. 一種解決柔性車間作業(yè)調(diào)度問(wèn)題的粒子群優(yōu)化算法[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(12):144-147.

[11]馬磊磊, 王強(qiáng). 基于改進(jìn)遺傳算法的多目標(biāo)物料配送方法研究[J]. 組合機(jī)床與自動(dòng)化加工技術(shù), 2015(12):156-160.

(編輯 李秀敏)

Genetic Algorithm of Improved Initial Population Applying to Scheduling for Flexible Job Shop

NIU Lin

(College of Medical Information, Hainan Medical University, Haikou 571100,China)

The quality of the initial population of genetic algorithm have a decisive influence on the quality and speed. When traditional genetic algorithm is applied in solving flexible job shop scheduling problems, the initial population is randomly generated, which may result in forming many infeasible solutions at the beginning of the iteration. Only through a complex operation will form optimum solutions, it may greatly reduces convergence speed of the algorithm.After study the characteristics of flexible job shop scheduling,Initial population give rules of base on the entire Search to code and generate initial population′s strategy, has been put forward.When the quality of initial population be improved,its diversity also won′t lose. At the same time, its global convergence can be improved.The instance in this article using the improved genetic algorithm,the results are compared with the traditional genetic algorithm′s results, It proved that the advantages of improved algorithm.

genetic algorithm; flexible job shop scheduling; initial population

1001-2265(2017)08-0157-04

10.13462/j.cnki.mmtamt.2017.08.041

2016-09-10；

2016-10-21

牛琳(1978—)，女，黑龍江巴彥人，海南醫(yī)學(xué)院講師，碩士，研究方向?yàn)閿?shù)據(jù)挖掘，信息管理，(E-mail)2763253868@qq.com.

TH186;TG659

A