改進(jìn)學(xué)習(xí)型遺傳算法求解柔性車(chē)間調(diào)度問(wèn)題*

張 亮，毛劍琳，王妮婭，李睿祺

(昆明理工大學(xué)a.信息工程與自動(dòng)化學(xué)院；b.機(jī)電工程學(xué)院，昆明 650500)

0 引言

柔性作業(yè)車(chē)間調(diào)度問(wèn)題(flexible job-shop scheduling problem，F(xiàn)JSP)是對(duì)傳統(tǒng)作業(yè)車(chē)間調(diào)度問(wèn)題(job-shop scheduling problem，JSP)的延伸。由于柔性作業(yè)車(chē)間調(diào)度問(wèn)題減少了機(jī)器約束，增加了不確定性，目前已被說(shuō)明是NP-Hard問(wèn)題[1]。目前求解柔性作業(yè)車(chē)間的調(diào)度問(wèn)題的算法主要有粒子群算法，禁忌搜索算法，遺傳算法等。

遺傳算法具有魯棒性強(qiáng)、算法易設(shè)計(jì)、全局搜索能力強(qiáng)等優(yōu)點(diǎn)，因此許多學(xué)者用來(lái)求解FJSP。張國(guó)輝等[2]設(shè)計(jì)了一種全局搜索、局部搜索和隨機(jī)產(chǎn)生相結(jié)合的初始化種群方法。該方法有效的提高了初始種群的質(zhì)量及收斂速度。徐文星等[3]進(jìn)一步提出了一種基于關(guān)鍵工序的全局隨機(jī)選擇初始化的方法，并加入了再激活機(jī)制避免了遺傳算法陷入局部最優(yōu)而停滯。李尚函等[4]采用了超啟發(fā)式遺傳算法有效的提高了局部搜索能力。張立果等[5]采用兩級(jí)交叉的方式，并將雙層遺傳應(yīng)用在多目標(biāo)問(wèn)題中，該方法提升了遺傳算法的局部搜索能力但收斂速度有所下降。GU、王玉芳等[6-8]在遺傳算法加入變鄰域搜索(variable neighborhood search，VNS)，該算法加入鄰域搜索以彌補(bǔ)遺傳算法的局部搜索能力。NING等[9]提出了一種改進(jìn)的雙鏈量子遺傳算法求解FJSP，該算法采用了雙鏈編碼構(gòu)成種群，后期采用量子粒子群來(lái)保證種群的多樣性。WANG等[10]提出了一種基于協(xié)同進(jìn)化算法的多種群協(xié)同遺傳算法，該算法協(xié)同探索了機(jī)器選擇和工序安排的解空間，為解決包含多個(gè)子目標(biāo)的問(wèn)題提供了一種新的思路。

近年來(lái)學(xué)習(xí)型智能優(yōu)化算法得到了學(xué)者的關(guān)注，陳英武等[11]采用學(xué)習(xí)型蟻群算法求解多星任務(wù)規(guī)劃問(wèn)題。邢立寧等[12]采用學(xué)習(xí)型遺傳算法求解雙層有能力約束的弧路徑優(yōu)化問(wèn)題。胡蓉等[13]采用學(xué)習(xí)型蟻群算法求解綠色多車(chē)場(chǎng)車(chē)輛路徑問(wèn)題。上述文獻(xiàn)表明學(xué)習(xí)型智能優(yōu)化算法可以有效地求解實(shí)際問(wèn)題。

由于傳統(tǒng)的遺傳算法在求解柔性車(chē)間調(diào)度問(wèn)題時(shí)存在搜索效率低，易過(guò)早收斂等問(wèn)題，本文提出了一種基于關(guān)鍵機(jī)器的學(xué)習(xí)型遺傳算法。以知識(shí)體的形式在迭代的過(guò)程中不斷向最優(yōu)個(gè)體學(xué)習(xí)，同時(shí)利用知識(shí)體來(lái)生成新的個(gè)體來(lái)替代原始種群中適應(yīng)度值差的個(gè)體，并設(shè)計(jì)了三種鄰域結(jié)構(gòu)，在知識(shí)體更新以及鄰域搜索中引入關(guān)鍵機(jī)器的概念，以此來(lái)對(duì)解空間進(jìn)行有效的搜索。

1 柔性車(chē)間調(diào)度問(wèn)題模型

n個(gè)工件J={J1,J2,J3,…,Jn}需要在m臺(tái)機(jī)器M={M1,M2,M3,…,Mm}上加工。每一個(gè)工件Ji由多道工序{Oi1,Oi2,Oi3,…,Ois}組成。s表示工件Ji的總工序數(shù)。每一道工序Oij(i=1,2,…,n；j=1,2,…,s)必須在給定的機(jī)器集中選擇Mij?M。在不同機(jī)器上的加工時(shí)間可以不同。因此FJSP問(wèn)題主要包含兩個(gè)子問(wèn)題：機(jī)器選擇和工序排序。

在建立問(wèn)題模型之前，根據(jù)實(shí)際情況本文做出以下假設(shè)：

(1)所有的機(jī)器和工件在0時(shí)刻都是可用的。

(2)不同工件的工序之間沒(méi)有優(yōu)先級(jí)的約束。

本文選取“最大完工時(shí)間CT最小”作為優(yōu)化目標(biāo)，如式(1)所示：

(1)

(2)

(3)

Si(j+1)>Fij,?i,j

(4)

式(2)表示每道工序只能被一臺(tái)機(jī)器加工一次；式(3)表示工件一旦開(kāi)始就不能被打斷；式(4)表示工件i的第j+1道工序的開(kāi)始時(shí)間不能早于第j道工序的開(kāi)始時(shí)間；同一臺(tái)機(jī)器在同一時(shí)間只能加工一道工序。

2 基于關(guān)鍵機(jī)器的改進(jìn)學(xué)習(xí)型遺傳算法

為了更好地利用問(wèn)題本身的特征，引入關(guān)鍵機(jī)器的概念。針對(duì)遺傳算法求解FJSP設(shè)計(jì)了知識(shí)模型，利用該模型對(duì)遺傳算法進(jìn)行引導(dǎo)。最后將遺傳算法的全局搜索能力與變鄰域算法的局部搜索能力相結(jié)合，對(duì)遺傳的優(yōu)秀個(gè)體進(jìn)行變鄰域搜索。提出了基于關(guān)鍵機(jī)器的學(xué)習(xí)型遺傳算法。

2.1 染色體的編碼與解碼

本文采用集成整數(shù)編碼方式，每一個(gè)染色體有兩部分組成。因此染色體長(zhǎng)度為所有工序總數(shù)的兩倍。表1為隨機(jī)生成的調(diào)度案例。

圖1所示為表1染色體編碼示例圖，在OS部分基因位的值代表工件號(hào)，工件號(hào)以出現(xiàn)的次數(shù)則為該工件的工序號(hào)。如在圖1中OS的第4個(gè)基因位為數(shù)字2，2是第二次出現(xiàn)，該位置2則表示為工件2的第2道工序。在MS部分基因位按照工件工序的大小依次排列，在圖2中6個(gè)位置則依次為O11、O12、O13、O21、O22、O23?；蛭坏闹祫t表示在可選機(jī)器集中的序號(hào)。解碼方式則采用文獻(xiàn)[14]的插入式貪婪解碼。

圖1 FJSP染色體編碼示例圖

表1 2×3隨機(jī)生成柔性車(chē)間調(diào)度方案

2.2 基于關(guān)鍵機(jī)器的學(xué)習(xí)型遺傳算法的實(shí)現(xiàn)

由于算法在搜索過(guò)程中得到的解了隱含問(wèn)題的內(nèi)在特征和求解經(jīng)驗(yàn)，故采用學(xué)習(xí)型思想對(duì)遺傳算法的迭代進(jìn)行引導(dǎo)，其核心思想就是不斷獲取優(yōu)秀個(gè)體的知識(shí)并不斷的對(duì)迭代過(guò)程進(jìn)行引導(dǎo)。通過(guò)知識(shí)體存儲(chǔ)優(yōu)秀個(gè)體的知識(shí)，然后再利用知識(shí)體中的知識(shí)生成新的染色體替代原來(lái)適應(yīng)度值差的染色體，完成對(duì)遺傳算法的引導(dǎo)過(guò)程，從而提高遺傳算法的搜索效率。

2.2.1 改進(jìn)遺傳算法

本文采用遺傳算法對(duì)問(wèn)題進(jìn)行求解，并采用保留精英種群的策略。遺傳部分設(shè)計(jì)如下：種群規(guī)模為NP。選擇算子采用輪盤(pán)賭的方式。交叉算子將NP平均分為兩個(gè)子種群。第一個(gè)子種群內(nèi)個(gè)體相互交叉；第二個(gè)種群則與第一個(gè)種群交叉，每?jī)蓚€(gè)父代交叉產(chǎn)生一個(gè)子代。精英種群采用種群內(nèi)的交叉的方式。工序排序部分(OS)采用POX交叉方式，機(jī)器選擇(MS)部分采用單點(diǎn)交叉的方式。工序排序(OS)部分的變異算子選取n個(gè)基因位置(n大于0小于OS部分編碼長(zhǎng)度的1/4)，翻轉(zhuǎn)其順序。機(jī)器選擇(MS)部分隨機(jī)選擇m個(gè)基因位(m大于0小于MS部分編碼長(zhǎng)度的1/4)，從可選機(jī)器集中從新隨機(jī)安排它們的加工機(jī)器。

文獻(xiàn)[4]表明隨著迭代次數(shù)的增加遺傳算法的種群多樣性會(huì)降低，進(jìn)一步導(dǎo)致遺傳算法的“早熟收斂”，并設(shè)計(jì)了一種是自適應(yīng)算子使得變異概率隨著迭代次數(shù)的增加而變大從而幫助算法跳出局部最優(yōu)。但是他所設(shè)計(jì)的自適應(yīng)因子與迭代次數(shù)呈線性關(guān)系，這樣會(huì)使算法最初的變異概率過(guò)小，且增長(zhǎng)過(guò)慢，本文采用非線性映射來(lái)動(dòng)態(tài)調(diào)整變異因子。采用正玄曲線在[0,π/2]上非線性遞增將遺傳的迭代次數(shù)映射到到[0,π/2]區(qū)間,其變異概率p的表達(dá)式為：

(5)

2.2.2 關(guān)鍵機(jī)器的定義及判斷

本文提出了一種關(guān)鍵機(jī)器的概念。在柔性作業(yè)車(chē)間調(diào)度中，某一工序可選機(jī)器唯一，其加工耗時(shí)為該機(jī)器的不可調(diào)度時(shí)間，該機(jī)器記為Mk(k=1,2,…,m)，時(shí)間記為tijk(i表示工件號(hào)，j表示工序號(hào)，k表示機(jī)器號(hào))。計(jì)算每臺(tái)機(jī)器上的不可調(diào)度時(shí)間，機(jī)器Mk的不可調(diào)度時(shí)間計(jì)算表達(dá)式為：

(6)

本文定義擁有不可調(diào)度時(shí)間的機(jī)器為關(guān)鍵機(jī)器即本文的目標(biāo)為最小化最大完工時(shí)間，要想完工時(shí)間最短所有機(jī)器的加工時(shí)間應(yīng)該趨于平衡，所以工序應(yīng)當(dāng)優(yōu)先分配給非關(guān)鍵機(jī)器或者不可調(diào)度時(shí)間短的機(jī)器，這樣所有機(jī)器上的加工時(shí)間才會(huì)趨于平衡。

2.2.3 工序-機(jī)器選擇知識(shí)體的構(gòu)造及學(xué)習(xí)更新

圖2 表1中工序1.1知識(shí)體示例

表1中工序1.1的可選機(jī)器有兩個(gè)，因此其對(duì)應(yīng)知識(shí)體長(zhǎng)度為6。5，6位的數(shù)值為可選機(jī)器，即工序1.1可以在機(jī)器1和機(jī)器2上加工。1，2數(shù)值則用來(lái)記錄知識(shí)，其初始值為對(duì)應(yīng)5，6位置在可選機(jī)器上加工時(shí)間的倒數(shù)。3，4位分別表示選中5，6位置機(jī)器的概率，其數(shù)值計(jì)算規(guī)則如下，假設(shè)可選機(jī)器集長(zhǎng)度為N，則概率分布部分從N+1開(kāi)始。則cell{j}(N+i)的數(shù)值為式(7)所示(j當(dāng)前知識(shí)體(cell)在知識(shí)體結(jié)構(gòu)中的位置索引)。

(7)

知識(shí)體的更新是從優(yōu)秀個(gè)體中獲取經(jīng)驗(yàn)的過(guò)程，將優(yōu)秀個(gè)體的經(jīng)驗(yàn)以知識(shí)體的結(jié)構(gòu)進(jìn)行存儲(chǔ)，并利用以獲取的知識(shí)引導(dǎo)種群的迭代。

每進(jìn)行一次迭代，判斷出當(dāng)前最優(yōu)個(gè)體，根據(jù)其染色體機(jī)器選擇(MS)部分的基因數(shù)值對(duì)知識(shí)體更新，判斷每一道工序所選擇的機(jī)器，并對(duì)知識(shí)主體部分對(duì)應(yīng)機(jī)器的數(shù)值進(jìn)行更新。如果當(dāng)前機(jī)器選擇不是關(guān)鍵機(jī)器KM則更新規(guī)則如式(8)所示，否則保持原數(shù)值不變。式中，Q為學(xué)習(xí)率，由于學(xué)習(xí)的為優(yōu)秀個(gè)體Q應(yīng)大于1這樣才能使優(yōu)秀個(gè)體部分的經(jīng)驗(yàn)數(shù)值不斷變大。更新完知識(shí)主體部分?jǐn)?shù)值后，再根據(jù)知識(shí)主體中的數(shù)值從新計(jì)算概率分布部分的數(shù)值。工序-知識(shí)體的學(xué)習(xí)更新表達(dá)式為：

cell{j}(i)=cell{j}(i)×Q

(8)

2.2.4 工序-機(jī)器選擇知識(shí)體對(duì)改進(jìn)遺傳算法的引導(dǎo)

過(guò)程

已知知識(shí)體中概率分布部分的總和為1，把所有機(jī)器被選中概率連續(xù)的分布在[0,1]的區(qū)間內(nèi)，在生成新的種群時(shí)，本文采用隨機(jī)生成一個(gè)[0,1]的隨機(jī)數(shù)r，判斷r所在的區(qū)間來(lái)確定工序所選擇機(jī)器。這樣就生成了染色中機(jī)器選擇(MS)部分的基因。工序排序(OS)部分的基因有兩種生成方式，一部分個(gè)體繼承種群中優(yōu)秀個(gè)體的基因，另一部分個(gè)體則隨機(jī)生成，這樣既能保證種群的多樣性又能保留優(yōu)秀個(gè)體的基因。新生成的個(gè)體來(lái)替換原有種群中適應(yīng)度值差的個(gè)體。知識(shí)體得以表達(dá)，學(xué)習(xí)型完成對(duì)遺傳算法的引導(dǎo)過(guò)程。

2.2.5 變鄰域搜索

變鄰域搜索通過(guò)調(diào)整鄰域結(jié)構(gòu)來(lái)增加搜索范圍，進(jìn)而得到局部最優(yōu)。本文應(yīng)用了文獻(xiàn)[16]的兩種鄰域機(jī)構(gòu)(鄰域結(jié)構(gòu)1,2)。并基于調(diào)整調(diào)整工序順序的思想設(shè)計(jì)了鄰域結(jié)構(gòu)3和4，基于關(guān)鍵機(jī)器的思想設(shè)計(jì)了鄰域結(jié)構(gòu)5。

結(jié)構(gòu)1：N1調(diào)整機(jī)器選擇，隨機(jī)選擇染色體中MS若干基因，從可選機(jī)器集中隨機(jī)再選擇一臺(tái)對(duì)其進(jìn)行加工。

結(jié)構(gòu)2：N2隨機(jī)選取兩個(gè)工件，讓他們?cè)贠S中的位置互換。

結(jié)構(gòu)3：N3隨機(jī)選取染色體中OS部分的一段基因，隨機(jī)打亂其順序。

結(jié)構(gòu)4：N4隨機(jī)選取染色體中OS部分的兩個(gè)基因，將一個(gè)插入到另外一個(gè)旁邊。

結(jié)構(gòu)5：N5選取關(guān)鍵機(jī)器上的工序更換其加工機(jī)器。

每一次迭代對(duì)種群中的優(yōu)秀個(gè)體進(jìn)行變鄰域搜索。如果個(gè)體在變鄰域后被改進(jìn)，則保留改進(jìn)，否則保持變鄰域之前的結(jié)構(gòu)。

2.3 算法整體流程框架

算法的整體流程框架圖如圖3所示。

圖3 算法整體流程框架圖

3 仿真測(cè)試與分析

上述算法采用MATLAB2020B進(jìn)行編程，操作系統(tǒng)為Windows10，11th Gen Intel(R) Core(TM) i7-11700KF@3.60 GHz，內(nèi)存32 GB，64位操作系統(tǒng)上運(yùn)行。算法參數(shù)設(shè)置為：種群規(guī)模NP=100，最大迭代次數(shù)200代；知識(shí)體每次生成個(gè)體數(shù)為20；交叉概率0.9，w取0.7。

3.1 學(xué)習(xí)型思想對(duì)算法的改進(jìn)效果

為了說(shuō)明學(xué)習(xí)型能夠有效對(duì)遺傳算法進(jìn)行引導(dǎo)，本文以MK03為例，分別使用本文算法和去除算法中的學(xué)習(xí)型進(jìn)行對(duì)比實(shí)驗(yàn)，圖4為兩種算法的迭代曲線由圖可不加學(xué)習(xí)型算法在150代左右才收斂，加入學(xué)習(xí)型滯后算法在40代左右就收斂了，因此知識(shí)體能學(xué)習(xí)到優(yōu)秀個(gè)體的知識(shí)，并對(duì)遺傳算法進(jìn)行了有效的引導(dǎo)，提高算法的搜索效率。

圖4 去除學(xué)習(xí)型前后迭代曲線對(duì)比

3.2 算法對(duì)比

為了說(shuō)明本文所提出的基于關(guān)鍵機(jī)器的學(xué)習(xí)型遺傳算法在求解FJSP問(wèn)題的性能，將其應(yīng)用于Benchmark算例中的MK01-MK10基準(zhǔn)算例以及Kacem算例，分別運(yùn)行20次，取最優(yōu)解。

Kacem算例與ZIAEE等[17]提出的基于結(jié)構(gòu)的啟發(fā)式算法(heuristic)、NOUIRI等[18]提出的分布式粒子群算法(distributed particle swarm optimization，DPSO)、姜天華[19]的灰狼算法(grey wolf optimization，GWO)進(jìn)行對(duì)比。

表2為Kacem算例對(duì)比結(jié)果，粗體為相同算例中的最優(yōu)解?？梢钥闯霰疚乃惴ㄔ谇蠼釱acem算例時(shí)具有較為優(yōu)秀的求解能力。

表2 Kacem算例對(duì)比

MK算例與姜天華等[19-20]提出的灰狼優(yōu)化算法(grey wolf optimization，GWO)以及混合灰狼優(yōu)化算法(hybrid grey wolf optimization，HGWO)、PRASERT等[21]提出的改進(jìn)微分進(jìn)化算法(improved differential evolution，IDE)、ZHANG等[22]提出的混合量子粒子群優(yōu)化(hybrid quantum particle swarm optimization，HQPSO)進(jìn)行對(duì)比。

表3為MK算例對(duì)比結(jié)果，粗體為相同算例中的最優(yōu)解，圖5為5種算法取得最優(yōu)解個(gè)數(shù)的折線圖。由圖5可以發(fā)現(xiàn)，在Benchmark的10個(gè)基準(zhǔn)算例中，GWO算法有3個(gè)取得了最優(yōu)解，HGWO、IDE、HQPSO有4個(gè)算例取得了最優(yōu)解本文所使用的算法有8個(gè)都取得了最優(yōu)解或者優(yōu)于其他算法。由表3可知除了MK10算例效果不理想以外，MK05和MK06雖然不是最優(yōu)解，也接近最優(yōu)解。在整體求解的數(shù)量上也優(yōu)于其他4種算法。

表3 Benchmark算例對(duì)比

續(xù)表

圖5 表3算法取得最優(yōu)解個(gè)數(shù)折線圖

圖6中每一個(gè)小方塊為一道工序，其中y軸為該工序選擇加工的機(jī)器，x軸的長(zhǎng)度代表加工時(shí)間，圖6為MK04算例在最大完工時(shí)間為64下的一個(gè)調(diào)度方案。由實(shí)驗(yàn)結(jié)果可以說(shuō)明本文算法的可行性，該算法具有較強(qiáng)的搜索能力，能夠有效的求解FJSP。

圖6 MK04(Makespan=64)調(diào)度甘特圖

4 結(jié)束語(yǔ)

本文所提出的基于關(guān)鍵機(jī)器的學(xué)習(xí)型遺傳算法在以最小化最大完工時(shí)間為目標(biāo)求解FJSP問(wèn)題時(shí)取得不錯(cuò)的效果，說(shuō)明了該方法的可行性。本文首先提出了關(guān)鍵機(jī)器的概念，并基于關(guān)鍵機(jī)器進(jìn)行知識(shí)體的更新以及變鄰域搜索，針對(duì)遺傳算法求解FJSP編碼設(shè)計(jì)了知識(shí)體，實(shí)現(xiàn)學(xué)習(xí)型對(duì)遺傳算法的引導(dǎo)過(guò)程，并設(shè)計(jì)了5種鄰域結(jié)構(gòu)，提高算法的局部搜索能力。在未來(lái)的研究中可以考慮使用學(xué)習(xí)型對(duì)其他智能優(yōu)化算法的迭代進(jìn)行引導(dǎo)，并將該算法運(yùn)用到求解多目標(biāo)柔性車(chē)間調(diào)度問(wèn)題的研究中去。