一種基于GA－SA－TS算法的車間調(diào)度方法的研究

劉紅軍 趙 帥 趙 雷

(①沈陽理工大學(xué)機(jī)械工程學(xué)院，遼寧沈陽 110159;②北京城建設(shè)計(jì)研究總院有限責(zé)任公司，北京 100037)

隨著科學(xué)技術(shù)的不斷發(fā)展，社會(huì)節(jié)奏的不斷加快，將科學(xué)的管理調(diào)度技術(shù)與車間生產(chǎn)調(diào)度緊密結(jié)合起來，在現(xiàn)代加工車間中已得到了普遍的應(yīng)用。而如何將科學(xué)技術(shù)與車間生產(chǎn)調(diào)度更好地融合到一起，成為了當(dāng)今科學(xué)領(lǐng)域普遍重視的問題。車間調(diào)度問題實(shí)質(zhì)上就是研究在已有的資源條件和一定的約束條件下，對(duì)加工任務(wù)進(jìn)行加工時(shí)間、機(jī)器、順序等的合理分配，從而使生產(chǎn)加工達(dá)到最優(yōu)化的狀態(tài)。

本文針對(duì)遺傳算法的局部搜索能力差，易限于局部最優(yōu)等缺點(diǎn)，提出了一種適用于車間調(diào)度研究中的混合遺傳算法(GA－SA－TS)，即將模擬退火算法、禁忌搜索算法與遺傳算法混合使用。該算法的核心在于:在遺傳算法的交叉機(jī)制中引入模擬退火算法的思想，形成模擬退火－交叉機(jī)制，從而避免了遺傳算法本身易早熟的缺陷。在變異機(jī)制中使用禁忌搜索算法的思想，形成禁忌搜索－變異機(jī)制，以此解決遺傳算法變異壓力問題。通過這些方面的改進(jìn)，提高了遺傳算法的優(yōu)化效率。

1 車間調(diào)度問題的描述

車間調(diào)度問題就是研究N(N1，N2，…，NN)個(gè)工件在M(M1，M2，…，MM)臺(tái)機(jī)器上進(jìn)行加工，每個(gè)工件具有一定數(shù)量的工序J(J1，J2，…，JJ)，每道工序可以在若干臺(tái)機(jī)器上加工，加工的過程按照工件的工藝順序完成。工件在加工的過程中要遵循以下約束:

(1)每臺(tái)機(jī)器在每個(gè)時(shí)刻只能加工一個(gè)工件的一道工序;

(2)每道工序只能被一臺(tái)機(jī)器加工;

(3)每個(gè)工件按給定的工藝路線和指定的次序在機(jī)器上進(jìn)行加工;

(4)每個(gè)工件在每臺(tái)機(jī)器上開始加工后不可停止，直到完成該道工序的加工;

(5)每個(gè)工件只能在上道工序加工完成后才能開始下一道工序的加工［1－2］。

2 改進(jìn)的遺傳算法

遺傳算法［3］(GA －Genetic Algorithms)主要是借鑒了生物進(jìn)化過程中“適者生存”的規(guī)律，并將算法的整個(gè)過程都與生物進(jìn)化過程中的各種概念對(duì)應(yīng)起來，例如:遺傳算法中的解稱為個(gè)體，算法中對(duì)解進(jìn)行的編碼稱為染色體等。圖1即為遺傳算法的流程圖。

模擬退火算法(SASimulated Annealing)是局部搜索算法的擴(kuò)展，是以一定的接受概率選擇鄰域中的較優(yōu)值，從而使SA成為一個(gè)全局最優(yōu)算法。

禁忌搜索算法［4－5］(TS － Tabu Search)也是局部鄰域搜索算法的推廣。它的特點(diǎn)是采用了禁忌技術(shù)，即禁止重復(fù)前面的工作，從而跳出局部最優(yōu)。

本文提出的混合遺傳算法(GA－SA－TS)，就是基于遺傳算法的整體流程，在其交叉機(jī)制中引入模擬退火算法的思想，在變異機(jī)制中引入禁忌搜索算法的思想。從而改善遺傳算法的局部搜索能力差的特點(diǎn)，進(jìn)一步提高了優(yōu)化的質(zhì)量，彌補(bǔ)單一遺傳算法在優(yōu)化方面的不足，達(dá)到取長補(bǔ)短的作用。

2.1 編碼方式

運(yùn)用到車間調(diào)度系統(tǒng)中的編碼方式有:基于“串”的編碼、基于位置“列表”的編碼、基于工序的編碼、基于工件的編碼、基于偏好列表的編碼、基于優(yōu)先規(guī)則的編碼、基于機(jī)器的編碼和基于完成時(shí)間的編碼等。針對(duì)車間調(diào)度的實(shí)際情況，本文選擇的是基于工件的編碼方式。這種編碼方式把調(diào)度編碼為工序的序列，每個(gè)基因代表一道工序。一般采用自然數(shù)來命名工序。由于基于工序的編碼方式本身就能滿足車間作業(yè)調(diào)度問題中的占用約束和順序約束的關(guān)系，因此該編碼方式常用于車間作業(yè)調(diào)度問題中。

2.2 適應(yīng)度函數(shù)

遺傳算法中，主要就是依靠對(duì)各染色體的適應(yīng)度函數(shù)的數(shù)值來確定染色體的優(yōu)劣。因而適應(yīng)度函數(shù)的確定對(duì)于優(yōu)化過程起著至關(guān)重要的作用。適應(yīng)度值高的染色體被保留操作的幾率就高，反之就低。本文將工件的加工時(shí)間作為調(diào)度的評(píng)定標(biāo)準(zhǔn)，即加工完成的時(shí)間越少越好，所以可視車間調(diào)度問題為最小值問題。根據(jù)適應(yīng)度函數(shù)的種類，確定其適應(yīng)度函數(shù)為

式中，cmax為一個(gè)適當(dāng)?shù)南鄬?duì)比較大的數(shù)，是f(x)的最大值估計(jì)［3］。

2.3 選擇操作

選擇操作是在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過程。通過對(duì)每條染色體進(jìn)行選擇概率的計(jì)算，選擇概率較高的個(gè)體被保留下來遺傳到下一代進(jìn)行操作的概率就高，反之就低。選擇操作算子包括輪盤賭選擇、隨機(jī)競(jìng)爭選擇、最佳保留選擇、無回放隨機(jī)選擇、確定性選擇、柔性分段選擇、均勻排序、穩(wěn)態(tài)復(fù)制、復(fù)制評(píng)價(jià)等。本文選擇最佳保留選擇算子進(jìn)行選擇操作，因?yàn)檫@種算子能夠保證迭代終止結(jié)果為歷代最高適應(yīng)度個(gè)體。選擇操作的基本流程為:

(1)計(jì)算出個(gè)每條染色體所對(duì)應(yīng)的適應(yīng)度函數(shù)值fi;

(2)將各條染色體按照計(jì)算出的fi進(jìn)行由高到低排序;

(3)按照選擇概率，從排序好的染色體群中按由高到低的順序選擇出n條染色體，并將這n條染色體完整的復(fù)制到下一代群體中。

2.4 模擬退火－交叉

本文通過對(duì)模擬退火算法的研究，提出一種模擬退火－交叉機(jī)制。所謂模擬退火－交叉，就是在遺傳算法的交叉機(jī)制中引入模擬退火算法的思想完成遺傳算法中的交叉操作。而模擬退火算法之所以成為全局尋優(yōu)算法，是因?yàn)槠洳捎昧薓etropolis［6］準(zhǔn)則。該準(zhǔn)則也被稱為接受準(zhǔn)則，其內(nèi)容為:

接受概率計(jì)算公式為

設(shè)初始狀態(tài)為i，該狀態(tài)的能量為Ei，然后從i的鄰域N(i)中隨機(jī)選一個(gè)新狀態(tài)j，新狀態(tài)的能量為Ej。如果Ei≥Ej，那么接受當(dāng)前狀態(tài)i為新狀態(tài);如果Ei＜Ej，則隨機(jī)產(chǎn)生一個(gè)數(shù) ζ∈(0，1)，如果 ζ＜Pij，就以j取代i成為當(dāng)前狀態(tài)。再重復(fù)以上新狀態(tài)的產(chǎn)生過程，直到系統(tǒng)趨于能量較低的平衡狀態(tài)。

本文提出的模擬退火－交叉機(jī)制就是借鑒了以上的思想，其具體操作流程如下:

Step1:令t0=k·Δ0(t0為模擬退火算法中的初始溫度，k為充分大的數(shù)，可選取k=10，20，100，…，Δ0=max{f(i)|i∈D}－ min{f(i)|i∈D})。

Step2:從區(qū)域D中選取兩條染色體 father1，father2。

Step3:判斷是否滿足終止條件(終止條件可以分為零度法，循環(huán)總數(shù)控制法，基于不改進(jìn)規(guī)則的控制法，接受概率控制法，鄰域法，Lundy和Mees法，Aarts和van Laarhoven法等［7］。本文選擇循環(huán)總數(shù)控制法，即給定一個(gè)溫度下降次數(shù)K，當(dāng)溫度迭代次數(shù)達(dá)到該值時(shí)，停止運(yùn)算)，若滿足則退出交叉操作，輸出結(jié)果，否則轉(zhuǎn)至Step4。

Step4:對(duì)染色體father1、father2進(jìn)行交叉操作，產(chǎn)生新的染色體son1、son2。

Step5:計(jì)算染色體 father1、father2、son1、son2 的適應(yīng)度值。

Step6:根據(jù)Metropolis準(zhǔn)則判定son1是否替代father1，son2是否替代 father2。

Step7:計(jì)算退溫函數(shù):tk=λ·tk－1(其中k＞0，0 ＜λ＜1，λ取值越接近1，溫度下降越慢，所以可以取λ=0.95，0.9，…)，轉(zhuǎn)至 Step3。

2.5 禁忌搜索－變異

采用了禁忌技術(shù)，是禁忌搜索算法的一大特點(diǎn)。所謂禁忌，就是禁止重復(fù)之前的工作。為了避免局部搜索過早陷入局部最優(yōu)的缺點(diǎn)，禁忌搜索算法用一個(gè)禁忌表將已經(jīng)到達(dá)過的局部最優(yōu)點(diǎn)或者到達(dá)局部最優(yōu)的過程記錄下來，以便在后面的搜索中不再或者有選擇地對(duì)禁忌表中的這些點(diǎn)進(jìn)行搜索，從而跳出局部最優(yōu)。禁忌搜索是在一個(gè)染色體所產(chǎn)生的鄰域中進(jìn)行尋優(yōu)搜索操作，其中鄰域中的染色體是否替代原有染色體，需要運(yùn)用特赦準(zhǔn)則(也稱為藐視準(zhǔn)則)進(jìn)行判定。特赦準(zhǔn)則保證了搜索過程在全部候選解被禁或是有優(yōu)于當(dāng)前最優(yōu)解的候選解(或狀態(tài))被禁時(shí)，能夠釋放特定解(或狀態(tài))，從而實(shí)現(xiàn)高效的全局優(yōu)化搜索［8］。

本文通過對(duì)禁忌搜索算法的研究，提出一種禁忌搜索－變異機(jī)制，即在遺傳算法的變異機(jī)制中融入禁忌搜索的思想。

禁忌搜索－變異的操作流程如下:

Step1:選擇一組染色體進(jìn)入禁忌搜索棧中等待操作。

Step2:從禁忌搜索棧中選出一條染色體A1，并令A(yù)best=A1，將禁忌表中內(nèi)容清零。

Step3:由A1產(chǎn)生N個(gè)候選解(x1、x2、x3、…、xi)，形成一個(gè)以A1為基礎(chǔ)的鄰域。

Step4:計(jì)算出Step3產(chǎn)生的鄰域中所有染色體的適應(yīng)度函數(shù)f，然后根據(jù)特赦準(zhǔn)則判定新產(chǎn)生的染色體是否替代原有染色體，成為Abest，本文設(shè)定的特赦準(zhǔn)則為:

如果f(Abest)≥f(xi)，則Abest值不變，并同時(shí)將xi放入禁忌表中，禁忌長度設(shè)為L=n;如果f(Abest)＜f(xi)，則Abest=xi，同時(shí)將原來的Abest的值放入禁忌表中，禁忌長度設(shè)為L=n。

Step5:判定是否滿足終止條件(設(shè)定終止條件為:禁忌搜索次數(shù)n);如果滿足轉(zhuǎn)至 Step6，否則轉(zhuǎn)至Step3。

Step6:判定禁忌搜索棧中的染色體是否全部完成禁忌搜索－變異操作，如果是，轉(zhuǎn)至Step7，否則轉(zhuǎn)至Step2。

Step7:輸出禁忌搜索－變異操作的結(jié)果。

3 實(shí)際算例的仿真驗(yàn)證

下面就GA－SA－TS混合遺傳算法的可操作性在某廠的加工車間進(jìn)行了實(shí)際驗(yàn)證。實(shí)際參數(shù)如表1所示。

表1 工廠實(shí)際加工參數(shù)

通過MATLAB實(shí)際仿真，得到一條最優(yōu)染色體為:

［5 2 5 3 1 3 4 2 4 1 5 1 2 2 4 3 2 5 3 1 3 4 4 5 1］

其對(duì)應(yīng)甘特圖如圖2所示。

按照該染色體解碼后的參數(shù)，在車間實(shí)際加工以上5個(gè)工件僅需耗費(fèi)30個(gè)單位時(shí)間。而該車間以往加工這批任務(wù)是憑借工人的經(jīng)驗(yàn)進(jìn)行調(diào)度，一般需耗費(fèi)37～40個(gè)單位時(shí)間。通過這個(gè)實(shí)例仿真可以看出，運(yùn)用GA－SA－TS混合遺傳算法求解車間調(diào)度中的實(shí)際問題不但可行，還能減少加工用時(shí)。

在設(shè)定循環(huán)次數(shù)相等的情況下，對(duì)該例分別進(jìn)行了混合遺傳算法和遺傳算法的仿真運(yùn)算。如圖3b所示為該例在使用遺傳算法的過程中交叉和變異機(jī)制到達(dá)過的值。在相同初始條件的情況下，交叉機(jī)制中得到了最小值為31，但該結(jié)果在變異機(jī)制中產(chǎn)生了變化，使得相對(duì)最優(yōu)值31丟失，并且在變異的過程中，搜索的范圍任停留在32～47之間，陷入局部最優(yōu)，導(dǎo)致最終結(jié)果為32。

圖3a所示為該例在使用GA－SA－TS混合遺傳算法運(yùn)算過程中模擬退火－交叉機(jī)制和禁忌搜索－變異機(jī)制分別到達(dá)過的值。可以看出，在初始條件相同的情況下，混合遺傳算法在交叉機(jī)制中得到的最優(yōu)值為30;并且將其傳遞到了變異機(jī)制中進(jìn)行操作，使得變異機(jī)制在操作的過程中搜索范圍由交叉機(jī)制中的30～55縮小到30～35，且在搜索的過程中多次到達(dá)了最優(yōu)值30，并輸出。出現(xiàn)這樣的情況是由于模擬退火－交叉機(jī)制在操作的過程中通過Metropolis準(zhǔn)則將交叉所得的最優(yōu)值記錄下來，避免了最優(yōu)值的遺失，并將最優(yōu)值傳遞給變異機(jī)制進(jìn)行操作。而禁忌搜索－變異機(jī)制通過基本變異方法，產(chǎn)生了一個(gè)以原有染色體為基礎(chǔ)的鄰域，從而提升了尋得最優(yōu)解的可能性，擴(kuò)大了搜索范圍。同時(shí)，每一條變異所得的染色體都進(jìn)行特赦準(zhǔn)則的判定，最終在所有變異的染色體中得到一條相對(duì)最優(yōu)的染色體，而不是單純的進(jìn)行變異操作。這樣的變異機(jī)制不但提高了遺傳算法的搜索能力，而且對(duì)每條變異的染色體和原始染色體都進(jìn)行了優(yōu)勝劣汰的操作，縮小了搜索范圍，因此避免了優(yōu)秀個(gè)體在變異機(jī)制中的遺失。

4 結(jié)語

基于對(duì)遺傳算法易早熟和搜索能力差等缺點(diǎn)的考慮，本文提出了一種以遺傳算法為主體，融模擬退火算法和禁忌搜索算法思想于其中的混合遺傳算法(GASA－TS)。即在遺傳算法的交叉機(jī)制中融入模擬退火算法的思想，形成模擬退火－交叉機(jī)制。在遺傳算法的變異機(jī)制中融入禁忌搜索算法的思想，形成禁忌搜索－變異機(jī)制。通過將SA、TS融入到GA的操作中，使得遺傳算法的交叉和變異機(jī)制中都對(duì)染色體進(jìn)行了優(yōu)勝劣汰的操作，而不是待交叉和變異操作全部完成后再對(duì)染色體進(jìn)行優(yōu)劣評(píng)定，從而避免了優(yōu)秀個(gè)體在交叉和變異操作過程中的遺失。并且通過對(duì)車間調(diào)度生產(chǎn)的實(shí)際算例仿真對(duì)以上論點(diǎn)進(jìn)行了論證，通過仿真的結(jié)果可以看出，運(yùn)用這種混合遺傳算法，對(duì)于解決車間調(diào)度系統(tǒng)的問題是可行的，并且較單純的使用GA算法而言，在解的質(zhì)量方面有所提高。

［1］陶思南，傅鸝，蔡斌.一種求解車間作業(yè)調(diào)度的自適應(yīng)混合遺傳算法［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2010，4(19):53 －57.

［2］何燕.基于遺傳算法的車間調(diào)度優(yōu)化及其仿真［D］.武漢:武漢理工大學(xué)，2006.

［3］邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法［M］.北京:清華大學(xué)出版社，2007.

［4］GLOVER F.Future paths for integer programming and links to artificial intelligence［J］.Computers and Operations Research，1986(13):533－549.

［5］GLOVER F.Tabu search:partⅠ［J］.ORSA Journal on Computing，1989(1):190－206.

［6］METROPOLIS N，ROSENBLUTH A，ROSENBLUTH M，et al.Equation of state calculations by fast computing machines［J］.Journal of Chemical Physics，1953(21):1087 －1092.

［7］雷英杰，張善文，李續(xù)武，等.MATLAB遺傳算法工具箱及應(yīng)用［M］.西安:西安電子科技大學(xué)出版社，2009.

［8］董宗然，周慧.禁忌搜索算法評(píng)述［J］.軟件工程師，2010(3):96－98.