（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）兩個求解jsp問題的遺傳算法.pdf

童璽鎏堊三查耋三蘭堡圭蘭竺鎏圣 兩個求解j s p 問題的遺傳算法 摘要 車間作業(yè)調(diào)度( j o bs h o pp r o b l e m ) 是一類典型的n p h a r d 問題，已被證明 在多項式時間內(nèi)得不到最優(yōu)值。該問題是生產(chǎn)管理中的核心問題，好的求解 方法可以促進(jìn)企業(yè)提高生產(chǎn)率。因此，該研究無論從理論還是實際都有重要 意義。近年來，對于j s p 問題的求解主要有啟發(fā)式算法和元啟發(fā)式算法，但 各有其不足之處：元啟發(fā)式方法的運行時間長，可獲得較好的解，但其解不 穩(wěn)定；啟發(fā)式方法可在較短的時間內(nèi)得到魯棒性較強(qiáng)的解，但是極少獲得較 優(yōu)的解。為了更好地解決問題，將一些解決某類問題較好的算法組合起來， 使所形成的混合算法具有兩者不可比擬的優(yōu)勢，成為目前研究的熱點。本文 分別應(yīng)用病毒遺傳算法和混合遺傳算法來求解車間作業(yè)問題j s p ( j o bs h o p p r o b l e m s ) 。 針對遺傳算法求解的早熟和收斂速度慢等問題，提出面向車間作業(yè)調(diào)度 的病毒遺傳算法j v g a ( j o bs h o po r i e n t e dv i r u sg e n e t i ca l g o r i t h m ) ，從橫 向和縱向同時搜索解空間；并提出一種新的病毒濃度概念不僅可以增強(qiáng)病毒 群體模式的多樣性還可以定量地評價染色體中某段基因的數(shù)量，克服了遺傳 算法固有的早熟問題；其次，定義了基于工件序的十進(jìn)制編碼方式，既避免 了死鎖的產(chǎn)生也便于解空間和染色體空間轉(zhuǎn)換。根據(jù)1 9 個典型j s p 問題的 對比實驗，證明了該理論對于求解j s p 問題的有效性。 遺傳算法初始解的質(zhì)量對于算法的收斂速度有重要的影響，將解決j s p 較理想的改進(jìn)瓶頸移動啟發(fā)式算法m s b 得到的解作為遺傳算法的一個初始 解，主群體中其它體隨機(jī)產(chǎn)生，提出混合遺傳算法h g a ( h y b r i dg e n e t i c a l g o r i t h m ) 。由于m s b 所得解的質(zhì)量較高，而g a 算法的精英策略保證 h g a 所得解的質(zhì)量不低于m s b 算法所得解的質(zhì)量。兩種算法的結(jié)合，使算 法的時間性能有較大的提高。 關(guān)鍵詞車間作業(yè)調(diào)度；病毒遺傳算法；瓶頸移動算法；混合算法 哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 t w og e n e t i ca l g o r i t h mf o r j o bs h o pp r o b l e m s a b s t r a c t j s p ( j o bs h o pp r o b l e m ) i st y p i c a l l yn p h a r d ，w h i c hm e a n st h a t i ti s i m p o s s i b l et of i n dt h eg l o b a lo p t i m u mi np o l y n o m i a lc o m p l e x i t y j s pi so n eo f t h ek e yp r o b l e m si nt h ep r o d u c t i o nm a n a g e m e n t g o o da l g o r i t h m s f o rt h i s p r o b l e mc a np r o m o t ep r o d u c t i v i t yo fe n t e r p r i s e s s ot h i st h e s i sc a np r o v i d eg o o d r e s u l t sf o rb o t ht h e o r ya n dp r a c t i c e i nr e c e n t y e a r s ，m e t a - h e u r i s t i c s a n d h e u r i s t i c sa r et w ok i n d so fa l g o r i t h mf o rj s p h o w e v e r , t h e ya r ed i f f e r e n ti n c p u t i m ea n dp e r f o r m a n c e m e t a - h e u r i s t i e sc a na l w a y so b t a i nb e t t e rs o l u t i o n s t h a nh e u r i s t i c sb u tt h e yn e e dm u c hm o r ec p u t i m e s a sw e l l ，r o b u s t n e s so f h e u r i s t i c si sg o o db u to p t i m u mc a ns e l d o mb eo b t a i n e d c p u t i m ei sn o tc r i t i c a l a st h ed e v e l o p m e n to fc o m p u t e rt e c h n i q u e s s ot h eq u a l i t yo fs o l u t i o n si sp u r s u e d b ym o s tr e s e a r c h e r sa tp r e s e n tb yi n t e g r a t i n gs o m eh e u r i s t i cw i t ham e t a h e u r i s t i c i n t h i st h e s i s ，av i r u se v o l u t i o n a r yg e n e t i ca l g o r i t h m ( v e g a ) a n dah y b r i d g e n e t i ca l g o r i t h m ( h g a ) a r er e s p e c t i v e l yp r o p o s e df o rj s p p r e m a t u r i t y a n ds l o w c o n v e r g e n c ea r et w oi s s u e se x i s t i n gi ng e n e t i c a l g o r i t h m ( g a ) f o rj s p f o rt h ea b o v et w oi s s u e s ，j v g a ( j o bs h o po r i e n t e d v i r u se v o l u t i o n a r yg e n e t i ca l g o r i t h m ) i sd e v e l o p e df o rj s pw i t ht h eo b j e c t i v eo f m a k e s p a nm i n i m i z a t i o n j v g as e a r c h e st h es o l u t i o ns p a c ei nb o t hd e p t ha n d w i d t h an e wv i r u sd e n s i t ys c h e m ei si n t r o d u c e dt oi m p r o v et h ed i v e r s i t yo ft h e p o p u l a t i o na n dt oe v a l u a t es o m ep a r to fg e n e si nt h ec h r o m o s o m e si nq u a n t i t y t h i ss c h e m ec a no v e r c o m et h ei n t r i n s i cp r e m a t u r eo fg a b e s i d e s ，ad e c i m a l e n c o d i n gm e t h o db a s e do np r o c e s s i n gr o u t e si sp r e s e n t e dw h i c hc a na v o i d d e a d l o c ka n ds w i t c hs o l u t i o n st oc h r o m o s o m e sa n dv i c ev e r s a e a s i l y e x p e r i m e n t a lr e s u l t so f1 7t y p i c a lb e n c h m a r k ss h o wt h a tj v g a c a l le f f i c i e n t l y s o l v ej s p t h ec o n v e r g e n ts p e e di sg r e a t l ya f f e c t e db yt h eq u a l i t yo ft h ei n i t i a ls o l u t i o n o fg a s om o d i f i e ds h i f t i n gb o t t l e n e c k ( m s b ) a l g o r i t h mf o rj s pi sa d o p t e dt o g e n e r a t e as e e df o rt h ei n i t i a l p o p u l a t i o n o fg a ，t h er e m a i n i n gs e e d sa r e - i l 矍堡堡矍三奎蘭王：罌圭耋堡簍塞 r a n d o m l yp r o d u c e d b yc o m b i n i n gm s bw i t h g a ，h g a ( h y b r i dg e n e t i c a l g o r i t h m ) i sd e s c r i b e dw i t he l i t i s ts t r a t e g y p e r f o r m a n c eo fh g ai sg o o dd u et o t h eg o o dp e r f o r m a n c eo fm s b k e y w o r d sj o b 。s h o ps c h e d u l i n g ；v i r u se v o l u t i o n a r y g e n e t i ca l g o r i t h m ；s h i f t i n g b o t t l e n e c ka l g o r i t h m ；h y b r i d a l g o r i t h m i i l 堡璽堡耋三盔蘭三蘭堡圭蘭堡耋三 1 1 課題背景與意義 第1 章緒論 作業(yè)排序問題“1 有著深刻的實際背景，是工農(nóng)業(yè)生產(chǎn)、國防、科研、交通 運輸以及各種服務(wù)行業(yè)中普遍遇到的問題：一般地說，j 屯是有多個不同項目要 完成，就有排序問題的存在。這些問題的共同特征就是要將不同的工作任務(wù)安 排一個執(zhí)行的順序和時間，使預(yù)定的目標(biāo)最優(yōu)化。所以，排序?qū)嵸|(zhì)上是要解決 如何按時間的先后，將有限的人力物力資源分配給不同的工作任務(wù)，使預(yù)定的 目標(biāo)達(dá)到最優(yōu)。尤其是隨著市場競爭的加劇，企業(yè)的生產(chǎn)正朝著多品種、小批 量方向發(fā)展。在多品種、小批量制造企業(yè)里，由于生產(chǎn)的產(chǎn)品品種多、批量 小，生產(chǎn)組織工作復(fù)雜，尤其是企業(yè)的生產(chǎn)作業(yè)計劃安排工作難度很大，計劃 的編制往往憑主觀經(jīng)驗，計劃的及時性、應(yīng)變性差，導(dǎo)致產(chǎn)品生產(chǎn)周期長，在 制品占用量大，機(jī)床利用效率低等，從而影響了多品種、小批量生產(chǎn)的經(jīng)濟(jì)效 益。企業(yè)的目的是要以最低成本制造出顧客滿意的產(chǎn)品，因此如何進(jìn)行生產(chǎn)的 組織管理，安排生產(chǎn)計劃、進(jìn)行排序都是我們面臨的問題。其中車間作業(yè)排序 是實現(xiàn)生產(chǎn)高效率、高柔性和高可靠性的關(guān)鍵，對有效實用的排序方法和優(yōu)化 技術(shù)的研究與應(yīng)用已成為先進(jìn)制造技術(shù)實踐的基礎(chǔ)。 車間作業(yè)調(diào)度( j o bs h o pp r o b l e m ) ，簡稱j s p ，是c i m s 領(lǐng)域中研究的重要 課題。同時也是在實際中應(yīng)用最廣的運籌學(xué)分支之一，研究它對于在現(xiàn)有資源 條件下提高工作效率和經(jīng)濟(jì)效益有重要作用。理論上已經(jīng)證明車間調(diào)度問題是 一個n p 難題，要想用多項式復(fù)雜度的時間算法找到最優(yōu)解是不可能的。但 是，在實際生產(chǎn)中即便一個較優(yōu)解也能帶來極大的經(jīng)濟(jì)效益，所以人們探索了 許多途徑以尋求最佳近似解結(jié)果卻不令人滿意。目前大部分研究集中在車間 作業(yè)調(diào)度上，沒有考慮資源分配，一般都直接將資源作為約束處理。因此j s p 的研究有其實際工程意義而且也有深遠(yuǎn)的理論意義。這是由于：一方面，車間 作業(yè)調(diào)度問題的研究不僅可以推動相關(guān)算法的研究，如：模擬退火算法、遺傳 算法、神經(jīng)網(wǎng)絡(luò)、免役算法“等，而且還能在此基礎(chǔ)上提出新的算法，這為其 他領(lǐng)域類似問題的解決提供了條件和手段；另一方面，車間作業(yè)調(diào)度問題的解 決本身具有實際意義，一個好的車間作業(yè)調(diào)度方案不儀可以降低生產(chǎn)成本，而 且可以提高企業(yè)產(chǎn)品的準(zhǔn)時交貨能力，從而增強(qiáng)企業(yè)的競爭力。 略爾濱理 i 大學(xué)工學(xué)碩士學(xué)位論文 1 2 排序問題的描述及分類 1 2 1 排序問題的描述 由于j s p 是排序問題的一種，為便于理解，我們先說明排序問題。排序問 題的名詞術(shù)語來自加工制造行業(yè)，這里所說的“機(jī)器”代表服務(wù)者，“工件” 代表服務(wù)對象。對于一般的排序問題，“機(jī)器”和“工件”都有多個，要解決 的是服務(wù)者對服務(wù)對象的服務(wù)順序和時間安排問題。從最一般的意義上講，調(diào) 度問題可以表述為：一個或多個服務(wù)者為兩個或兩個以上服務(wù)對象服務(wù)時，如 何確定服務(wù)順序，使預(yù)定目標(biāo)( 調(diào)度成本的指標(biāo)，如：加工費用、在線庫存費 用等；調(diào)度性能的指標(biāo)等，如：生產(chǎn)周期、平均流動時間；用戶要求的指標(biāo)： 最大拖期時間、平均拖期時間、拖期零件的數(shù)量等) 達(dá)到最優(yōu)。假定有n 個工 件j ：，jj 要經(jīng)過m 臺機(jī)器，m ：，m 。j 加工。一個工件在一臺機(jī)器上的 加工稱為一道“工序”。加工順序要求表示工件加工在技術(shù)上的約束，即工件 的加工工藝過程，這是事先給定的。用“加工順序”表示各臺機(jī)器上工件加工 的先后順序。加工順序是排序要解決的問題。 1 2 2 排序問題的分類 排序問題有不同的分類方法，最常用的分類方法是按機(jī)器、工件和目標(biāo)函 數(shù)的特征分類。按機(jī)器的種類和數(shù)量不同，可以分成單臺機(jī)器的排序問題和多 臺機(jī)器的排序問題。對于多臺機(jī)器的排序問題，按工件加工路線的特征不同， 可以分成單件車r n ( j o b s h o p ) 的排序問題和流水車p 司( f l o w s h o p ) ”1 的排序問題。 每個工件的加工路線各不相同，是單件車間排序問題的基本特征；而所有工件 的加工路線完全相同，則是流水車間排序問題的基本特征。按工件到達(dá)車間的 情況不同，可以分成靜態(tài)的排序問題和動態(tài)的排序問題。當(dāng)進(jìn)行排序時，所有 的工件都己到達(dá)車間，可以一次對它們進(jìn)行排序，這是靜態(tài)的排序問題?；蚬?件陸續(xù)到達(dá)車間，要隨時安排它們的加工順序，這是動態(tài)的排序問題。按目標(biāo) 函數(shù)的不同，也可以得到性質(zhì)不同的排序問題。譬如，同是單臺機(jī)器的排序問 題，使平均流程時間最短和使誤期完工的工件數(shù)最少，實質(zhì)是兩種不同的排序 問題。由機(jī)器、工件和目標(biāo)函數(shù)的不同性質(zhì)以及一些其他因素的差別，構(gòu)成了 多種多樣的排序問題。 哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 另外，按參數(shù)性質(zhì)的不同，可以劃分為確定型排序問題與隨機(jī)型排序問 題。所謂確定型排序問題，指加工時問和其他有關(guān)參數(shù)是己知的確定的量。而 隨機(jī)型排序問題的加工時間和其他有關(guān)參數(shù)是隨機(jī)變量。確定型排序問題與隨 機(jī)型排序問題的解決方法有實質(zhì)的差別。應(yīng)該說，在實際的排序問題中，動態(tài) 的、隨機(jī)型的占的比重較大。但是，也確有很多排序問題是確定型的。而且， 有很多問題，其中隨機(jī)因素所占的比重很小，用確定型的模型來處理不僅方 便，而且足夠精確。其次解決排序問題及其困難，很多確定型問題尚不能很好 解決，更何況求解隨機(jī)型排序問題。 1 3 車間調(diào)度問題現(xiàn)狀及發(fā)展 1 3 1 車間調(diào)度問題的研究現(xiàn)狀 調(diào)度問題是一個典型的n p h a r d 問題，理論上已經(jīng)證明在多項式時間復(fù)雜 度內(nèi)使這一類問題找到全局最優(yōu)解是不可能的。由于調(diào)度問題的復(fù)雜性”“。【，導(dǎo) 致不同的研究者從不同的角度研究某一方面的問題，并隨著對各類調(diào)度問題研 究的深入及各種交叉學(xué)科的發(fā)展，涌現(xiàn)出了許多新的車間調(diào)度理論與方法，其 主要分為兩類，一類是近似方法，一類是最優(yōu)化方法。用近似方法求解作業(yè)調(diào) 度問題時，它們可以很快得到問題的解，但它們不能保證得到的解是最優(yōu)的； 用最優(yōu)化方法求解這一問題時，它們可以得到全局最優(yōu)解，但它們只能解決小 規(guī)模的作業(yè)調(diào)度問題，而且速度很慢。 對于作業(yè)調(diào)度問題的研究，從開始到現(xiàn)在已有幾十年的歷史”1 。早在1 9 5 4 年，j o h n s o n 對兩臺機(jī)床的f l o w s h o p 型調(diào)度問題進(jìn)行了研究后，便開始了對 調(diào)度問題的廣泛研究。b g i f f l e r 和g l t h o m p s o n 在1 9 6 0 年提出了用于生產(chǎn) 調(diào)度的優(yōu)先分派規(guī)則方法。g e r ew s 在1 9 6 6 年提出了用于j o b s h o p 調(diào)度問題 一組基于優(yōu)先分派規(guī)則的啟發(fā)式算法。b a l a se 在1 9 6 9 年第一個應(yīng)用基于析取 圖( d i s j u n c t i v eg r a p h ) 的列舉方法來處理機(jī)器的調(diào)度問題。這是一些較早的關(guān) 于j o b s h o p 問題研究的文獻(xiàn)報道。 6 0 年代，在求解j o b s h o p 調(diào)度問題時，強(qiáng)調(diào)通過列舉方法( e n u m e r a t i v e m e t h o d ) 去求解這一問題。用列舉算法在求解j o b s h o p 調(diào)度這一問題時，需要 對求解過程有精細(xì)完備的數(shù)學(xué)表達(dá)。雖然列舉算法的策略對這一問題有著巨大 的理論價值，但從很多的研究工作可以看出，應(yīng)用列舉法來求解這一問題的結(jié) 果是極其令人失望的，這些算法主要是對很多調(diào)度問題不能得到可行解。因 窒查堡堡三查竺三竺堡圭蘭堡蘭蘭 此，它們在實際使用中受到了限制。 其中分枝定界方法( b r a n c h & b o u n d ，簡稱b b ) 是主要的列舉策略之一。 它用動態(tài)結(jié)構(gòu)分枝來描述所有的可行解排序的解空間，這些分枝隱含有要被搜 索的可行解。這個方法可以用數(shù)學(xué)式和規(guī)則來描述，在對最優(yōu)解搜索過程中， 它允許把大部分的分枝從搜索過程中去掉。這種方法從它誕生之曰起，流行了 很多年。它對解決總工序數(shù)n ：加護(hù)淞u ( 2 2 ) 鬲 下標(biāo)f 為執(zhí)行操作的病毒的編號；h 為被病毒i 感染后宿主的集合。病毒感 染的次數(shù)是由病毒的感染率來控制。如果f i t v i r u s 。取e 值，病毒的傳染率增 加。反之則減少。進(jìn)而，每個病毒都有一個生命力如下： l i f e , ，f + 1 = ，l i f e , ，t + f i t v i r u s t( 2 - 3 ) 其中，t 和r 分別表示群體的代數(shù)和生命遞減率。 在j v g a 進(jìn)化的過程中，為了避免非成熟收斂，需保持主群體的多樣性。 如果一段病毒的基因串感染主群體并使之趨優(yōu)，那么這段病毒易被代代保持下 去，導(dǎo)致主群體中含該病毒模式的染色體數(shù)過大，會加速算法的局部收斂。為 避免類似情況發(fā)生，定義病毒的濃度v d e n s i t y 。如果病毒的濃度超過一定的 值，就要對病毒實行變異，加大病毒的變種。 v d e n s i t y = 一f c v f 2 4 1 m m ：包含病毒串的主群體數(shù)目： 耽：主群體數(shù)目。 為了更清楚地說明面向j s p 的病毒遺傳算法( j v g a ) 以圖2 3 說明病毒 v 的產(chǎn)生、傳染和增長過程： l - 123 i456 l789 。 j 加h ；出舶h p p - 4 5 6 _ 立竺盟皇竺且一9 2 m 5 舊斗 = 7 92 1 4 56m lm c r 口雒_ 一- 45 6 8 p 圖2 3 病毒v 的產(chǎn)生、傳染、增長過程 f i g 2 3t h ep r o c e d u r e d u r i n g t h eg e n e r a t e ，i n f e c t i o n ，i n c r c a s m e n to f v i r u s 哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 病毒傳染的步驟如圖2 - 4 所示。首先，病毒個體對從宿主群中隨機(jī)選出的 主個體執(zhí)行轉(zhuǎn)錄操作。接下來，算法評價每個被傳染個體的適應(yīng)度值并且計算 其生命力。如果生命力為正值，從隨機(jī)選擇的主個體中抽取一個新的予串增加 原病毒的長度：否則，執(zhí)行病毒個體的轉(zhuǎn)導(dǎo)操作。 圖2 - 4 病毒傳染的步驟 f i g2 4t h es t e po f t h ei n f e c t i o no f t h ev i r u s 2 2 車間作業(yè)問題的描述 單件車間的調(diào)度問題( j s p ) 是最一般的排序問題，也是最復(fù)雜的一種排 序問題。前面介紹的單臺機(jī)器和流水車間的排序問題都可以看作是一般單件車 間問題的特殊情況。相對于一般單件車間問題的排序來說，對這兩類排序問題 的研究所取得的成果比較多。j o bs h o pp r o b l e m ( j s p ) n 題描述為：設(shè)有一個工 件 j 。，j2 - ，。 在m 臺機(jī)器。， f ：，m ， 上加工。第i 臺機(jī)器上加工作業(yè)j 的時 間為f ，。確定一個作業(yè)的排列順序 ，如，。 使得最后一臺機(jī)器上最后完工 件的完工時間c 。( m a k e s p a n ) 最小。滿足如下約束條件： 1 每臺機(jī)器每次只加工一個工件； 2 每個工件不能同時在多臺機(jī)器上加工； 3 ：每個工件的加工順序預(yù)先確定，滿足技術(shù)要求； 4 每個工件在每臺機(jī)器上只加工次； 5 加工過程中不允許中斷。 問題可以描述為： 哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 r r f i n “ 卉0 f a t j t i 面 ( f ，j ) a 0 - t , - d t v f f 一0 西( f ，j ) e k ，k m 在此該問題也可以用析取圖“”來表示，如圖2 5 所示。 0 圖2 - 5j s p 問題( n = 3 ，m = 2 ) 的析取圖 f i g 2 - 5t h ed i s j u n c t i v eo f j s p ( n = 3 ，m = 2 ) 圖2 5 可以表示為g ；( n ，a ，e ) ，n 表示工件在機(jī)器上加工的工序的集 合；a 表示受工件偏序關(guān)系約束的含取邊的集合，即連接同一工件的鄰接工序 的邊；e 表示第k 臺機(jī)器加工的工序?qū)Φ奈鋈∵叺募稀 ；和t ；分別代表每 個工序的開始時間和加工時間。調(diào)度將固定所有非連接邊的方向，以確定同一 機(jī)器上的工序順序，一旦對于某臺機(jī)器的順序確定下來，連接工序的析取邊將 被帶優(yōu)先箭頭的合取邊取代。析取邊集合e 分解成子集系 e 。e = 巨u 巨u 島u 已，每臺機(jī)器一個系。圖2 5 是3 個工件、2 臺機(jī)器的 析取圖實例，其中每個工件包含2 道工序，節(jié)點n - - - - ( 0 ，l ，2 ，3 ，4 ，5 ， 6 ，7 ) 對應(yīng)工序，其中0 和7 分別為表示起始工序和終止工序的虛結(jié)點。合取 邊a = ( ( 1 ，2 ) ，( 3 ，4 ) ，( 5 ，6 ) ，) 對應(yīng)工各個工件的前后約束。析取邊= ( ( 1 ，4 ) ，( 1 ，6 ) ，( 4 ，6 ) ) 對應(yīng)機(jī)器1 的加工的工序；析取邊= ( 2 ，3 ) ， ( 3 ，5 ) 。( 2 ，5 ) ) 對應(yīng)機(jī)器2 的加工的工序；車間調(diào)度問題是找出每臺機(jī)器 上工序的加工順序，即確定非連接邊的方向，使得產(chǎn)生的結(jié)果是非循環(huán)的f 工 序間先后沖突) 。并使起始點到終止點的最大加權(quán)路徑的長度最小，其路徑的 長度對應(yīng)于最大流程時間。 墮璽鎏登三查蘭三蘭堡圭蘭竺竺蘭 2 3j v g a 的編碼和解碼方法 不同的編碼方法對遺傳算法“的求解速度有較大影響，在遺傳算法編碼 方式的問題上，h o l a n d 建議采用二進(jìn)制編碼，并得到了許多學(xué)者的支持。q i 和p a l m i e f i 對浮點數(shù)編碼的遺傳算法進(jìn)行了嚴(yán)密的數(shù)學(xué)分析。v o s e 等擴(kuò)展了 h o l l a n d 的模式概念，揭示了不同編碼之間的同構(gòu)性。從整體上來講，二進(jìn)制 編碼的進(jìn)化層次是基因，而浮點數(shù)編碼的進(jìn)化層次是個體。同時對于非二進(jìn)制 編碼，可以結(jié)合具體問題領(lǐng)域的知識，設(shè)計合適的遺傳算予。編碼是遺傳算法 應(yīng)用中的首要問題，因此建立完善的理論指導(dǎo)十分必要。 染色體編碼一般應(yīng)能直接或間接表達(dá)問題的一個有效解，通常是將解映射 為一組符號串，這個符號串為染色體，上面的每一符號都是一個基因。由于車 間作業(yè)調(diào)度問題的解就是所有操作的排列順序，所以利用這一個排列順序作為 染色體是很方便的。 本文基于遺傳算法求解車間作業(yè)問題并提出如下的編碼方法及對應(yīng)的解碼 方法。將問題的工藝路線約束和加工時間分別用加工矩陣d 。和時間矩陣丁k 。 表示，編碼存放于矩陣晶。，中。矩陣d 、r 中行號f 都代表工件，列號，都代 表工序，如矩陣d 中的元素講，_ k ，代表著第i 2 f , - 工件的第個工序在第k 臺 機(jī)器上加工，而矩陣t 中的元素卉，代表著第f 個工件的第，個工序需要t 。 個單位的加工對間。 編碼：島j = i x l 0 2 + 歹1 0 4 + 七；( i n t ( m 1 0 p ) = 0 夕) 解碼：k = 白，m o d ( 1 0 4 ) ：j = ( e l 。j k ) m o d ( 1 0 2 4 ) ；i = i n t ( e u 1 0 2 4 ) f 1 2 3 1 1 1 1 2 2 1 3 3 風(fēng)3 。；j 牛雹2 1 3 ，2 2 2 2 3 2 由上可以看出，一個加工矩陣協(xié)。能通過編碼產(chǎn)生唯一的編碼矩陣 厶。，而任何一個編碼矩陣厶?？梢酝ㄟ^解碼得到一個整數(shù)矩陣k 。( 但 厶?？赡懿皇羌觮 矩陣上l 。) 。 墮璽堡塞三查耋三蘭璧當(dāng)耋竺蘭蘭 2 4j v g a 主要的進(jìn)化操作 2 4 1 初始種群 初始種群一般是在工藝約束下隨機(jī)產(chǎn)生的，對于初始種群的隨機(jī)性，不同 學(xué)者的觀點差距很大。一種意見認(rèn)為，為了保證群體具有良好的分散性，初始 種群應(yīng)該隨機(jī)產(chǎn)生；另一種意見認(rèn)為，初始種群對g a 的收斂性和算法速度有 很大的影響，需要采用一些技術(shù)來產(chǎn)生“較好”的初始種群。群體中個體的適 應(yīng)值f i t n e s s 通常取作目標(biāo)函數(shù)值。在j v g a 中采用隨機(jī)方法初始種群。 基于編碼矩陣e 和工藝路線要求，運用參考文獻(xiàn)【1 6 仲提供的思想。設(shè)一 維數(shù)組a l 玎m l 存放產(chǎn)生的一個初始解，隨機(jī)取矩陣e 中某一行的第一個不為 零的元素存入數(shù)組a l n m i 中，矩陣e 中的相應(yīng)元素置零。直至矩陣e 中的元 素全部為零。用這種基于加工路線的方法初始解空間，滿足上述的約束條件， 可以避免死鎖的發(fā)生，從而提高算法的執(zhí)行效率。如下是上例的一個可行解： 醫(yī)五基匝西五醫(yī)五五函： 2 4 2 主個體的遺傳操作 遺傳操作包括復(fù)制、交叉( f ：l o $ $ o v e r ) 、變異 和選擇 ( s c l e c t i o n ) ：采用單點交叉，每個個體以概率p c r o s s 發(fā)生交叉；以很小的概率 ，。發(fā)生變異：為使最優(yōu)值得以保持在每代交叉完后選擇父代和子代中較優(yōu) 的個體參與下一代進(jìn)化。 2 4 2 1 復(fù)制通過復(fù)制將父代個體信息傳遞到予代，考慮到生物的優(yōu)勝劣汰原 則，一般適應(yīng)值高的個體復(fù)制的可能性越大，然而，為了保證生物的多樣性， 適應(yīng)值低的個體也并非完全沒有可能被復(fù)制，復(fù)制策略的不同選擇對g a 的性 能有很大影響。通常都是根據(jù)個體適應(yīng)度值進(jìn)行復(fù)制。如個體的適應(yīng)值為， 復(fù)制概率p ，為： a = 其中n n 為群體釣規(guī)模大小( 邸個體數(shù)) 2 4 2 2 交叉算子交叉是在一對個體之間進(jìn)行，適當(dāng)?shù)慕徊婵梢允馆^優(yōu)的基因 片段相結(jié)合，產(chǎn)生更優(yōu)秀的個體，以便增加搜索到更優(yōu)個體的機(jī)會，在算法尋 鷹 啥爾演理工大學(xué)工學(xué)頸士學(xué)位論文 優(yōu)的過程中起著重要的作用。對于車間作業(yè)調(diào)度問題”，由于一般交叉可能會 產(chǎn)生不可行解( 即不滿足工藝路線的約束) ，因此，許多文獻(xiàn)都設(shè)計了交叉算 子，提出了一些新的交叉算子，如部分匹配算子( p a r t i a lm a p p e dc r o s s o v e r , p m x ) 、線性順序算子( l i n e a ro r d e rc r o s s o v e r , l o x ) 、循環(huán)算子( c y c l e c r o s s o v e r , c x ) 、正則算子( u n i f o r mc r o s s o v e r ，u n ) 等。 本文采用一點交叉的方法，以概率p 一隨機(jī)選取群體中的兩個個體a 和 b ，再隨機(jī)選取交叉位鼴i ( 2 f m 阼一2 ) 。取a 中從位置1 到f 的基因串 保持不變。將b 中沒有出現(xiàn)在a 前半部分的基因順序保留，用其替代a 中f 位 黑后的基因，如此便產(chǎn)生了新的主個體a 。同理產(chǎn)生新個體日。這種交叉方 法保證在交叉操作時不會產(chǎn)生死鎖。舉例說明如下： a ：31257 8 64b ：l5736i428 彳：3l257 648 ：l5 7 36 284 2 4 2 3 變異算子變異為新個體的產(chǎn)生提供了機(jī)會，同生物進(jìn)化進(jìn)程一樣， g a 中出現(xiàn)變異的可能性很小，因此，一般個體的變異率p m 都取得很小，通 常在o o s 左右。 在車間作業(yè)調(diào)度問題中，變異操作也可能出現(xiàn)不可行解，因此，許多學(xué)者 對變異算予進(jìn)行研究。提出了二種變異方法：一種是隨機(jī)地選擇染色體中給定 兩個不相鄰的基因進(jìn)行交換，這種變異算子稱為互換變異( e x c h a n g e m u t a t i o n ) ；另一種是先在染色體上隨機(jī)確定一個變異點，然后再將浚點上的 基因向前或后移動一段距離，這個距離可以是隨機(jī)的，也可以根據(jù)具體問題確 定，這種變異算子稱為移位變異( s h i rm u t a t i o n ) 。一些學(xué)者認(rèn)為移位變異的效果 優(yōu)于互換變異。 由于j s p 問題的約束條件較多，為避免死鎖的發(fā)生，變異時不能簡單地改 變某位基因的值。本文采用向后變異的方法；隨機(jī)產(chǎn)生一個變異位置；然后解 碼該位置和下一位的基因，解碼后所得工序不屬于同一個工件，則交換兩個基 因。舉例說明如下： “：31257 | 86 4 b ：31257684 2 4 3 病毒個體的感染操作 病毒個體的感染操作包括以下兩個步驟：( a ) 反向轉(zhuǎn)錄( r e v e r s e t r a n s c r i p t i o n ) ，即病毒傳染操作，病毒以概率p 。用自身的基因覆蓋主染色體中 啥爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 的相應(yīng)基因片段從而產(chǎn)生新的主染色體；( b ) 轉(zhuǎn)導(dǎo)算子( t r a n s d u c t i o n o p e r a t o r ) ，病毒以概率p 。，從主染色體中復(fù)制一定長度的基因子串，生成新的 病毒。 另外。j s p 約束條件較多為使被感染的主個體不產(chǎn)生死鎖，則必須滿足 病毒串基因組成的集合v 與被感染主串的相應(yīng)基因串集合f 具有相同的元 素，即兩個集合滿足m = 淵。 病毒感染算子的基本的思想如下：對于兩個主個體h o s t p o p 。= p ： p 2 p ，p m p m ”一p 和h o s t p o p 2 。w lw 2 w i w i + l w i 十川w m 月。從 h o s t p o p 中轉(zhuǎn)導(dǎo)產(chǎn)生病毒個體v i r u s i = p i p i 小，印+ ( 病毒基因串長為l ) 用 v i r u s ，感染h o s t p o p ：，根據(jù)v = p i + l ，d + l ) ：f = w t + h ，w l + l ) 且川= f f 即v i r u s i 替換h o s t p o p ：中基因串+ 1 w f + 。產(chǎn)生新的主個體 h o s t p o p 3 = p i p 2 。w f w j + p m x n 。 由于主群體h o s t p o p ，h o s t p o p ：在初始時就滿足技術(shù)要求，所以它們的子 翠 a t 。p l 【p 2 p t 一1 ； a 2 ”p ia + l i ； 雞= p i + l + i p i + l i 2 p m x n ： v 【- w i w t + 1 。w + l 也是按技術(shù)要求排序的，由于v 、與a 。中所含元素相同，所以 用y ，替換4 并不改變4 、a ，中的技術(shù)要求，而v 。同樣也是來自可行解，所以 v i 也是符合技術(shù)要求的這樣由a 、v ，、4 形成的新個體 h o s t p o p 3 = p l p 2 w i + 肌。也是滿足技術(shù)要求的。所以病毒感染后形 成的新個體不會產(chǎn)生死鎖。 采用上述給出的遺傳算子、病毒感染算子以及相關(guān)參數(shù)的定義，面向車間 作業(yè)調(diào)度的病毒遺傳算法j v g a ( j o bs h o po r i e n t e dv i r u sg e n e t i ca t g o r i f i a m ) 描 述如下： 1 t = 0 ，初始化參數(shù)，產(chǎn)生初始主群體h o s t p o p 和病毒群體v i r u s p o p ； 2 評價主群體，并置病毒初始生命； 3 若停止規(guī)則滿足，算法停止。否則，轉(zhuǎn)4 ： 4 進(jìn)行遺傳操作：交叉( c r o s s o v e r ) 、選擇( s e l e c t i o n ) 、變異 ( m u t 丑t i o n ) ： 5 計算相應(yīng)參數(shù)，并進(jìn)行相關(guān)的感染操作：感染、病毒的死亡、病毒長度 的變化、病毒變異； 6 ，t 代操作結(jié)束，評價主群體和病毒群體； 7 t = t + l ，轉(zhuǎn)3 。 圖2 - 6 為病毒遺傳算法流程圖： 哈爾濱理工大學(xué)工學(xué)碩士學(xué)位論文 ln i t iblh os p o p u la t lo n h a n d tr 8 n s d u c t i o nv ir u 5 v 。j 條n 渺 t - t + 1 ： 上 l p s e 。1 i e u c i t a “p 。a n p ( u t l a i t ) i 。“。“ ， 訃船5 1 dp a r e n t “s i s2 ) ， 。0 8 8 0 ”。( 8 l ，82 ) ：m “9 。( 87 。) ；而“2 a t c ( 52 ) o u t pu tt h eb es cs o i u t i o n j 1 np o p u i a t i o n t ；、r 蘭。； 刊 j 。1 各、7 n ：l ! ：一 上y w i n i f t h e c v t ir u s f h os i t 】p 。p u l8 t i o l i “l(fā) f 一； n ： 0n 。廠抄i 。 i n e r e r s ct h ev i r a3 d c cr c a s ct h ov i r us 盯+ ；j 。毒 、 圖2 - 6 病毒遺傳算法流程圖 f l 菩2 - 6f | o wd i a g r a mo f v i r u se v o j u t i o n a r yg e n e t i ca l g o r i t h m 2 0 - 蘭璽耋塞三查蘭三蘭堡圭耋竺墼耋 ! ： 一 2 5 模擬實驗 算法j v g a 用b o d a n d c + 十實現(xiàn)，在1 2 8 m r a m 的p c 機(jī)上運行了1 9 個典 型b e n c h m a r k 實例，每個b e n c h m a r k 實例均作l o 次仿真。由于不同實例的規(guī) 模不同，同一個算法a 得到的完工時間c 一( 彳) 差距較大，為比較c 。( 4 ) 與相 應(yīng)實例的最優(yōu)值的接近程度，定義相對偏差為： g o ( 4 ) ：型籌竺1 0 0 = 警1 0 0 一1 ( c + 為問題的已知最優(yōu)值c 。( 為1 0 次實驗平均值) j v g a 與g a 的性能指標(biāo)作比較，統(tǒng)計結(jié)果如表2 1 所示( c + 為1 0 次實驗 的最優(yōu)值) 。 表2 - 1 兩種算法的平均相對偏芹 爿g a l n s 覆n c e 囂c + c r d ( ) c r d ( ) m t 0 6665 55 506 25 54 4 5 l a o l 1 0s6 6 66 6 604 16 6 624 2 l a 0 21 056 5 56 5 50 76 5 918 3 l a 0 3 1 055 9 76 i8 46 0 633 5 l a 0 41 055 9 05 9 01 3 55 9 52 8 8 l a o s 1 0 5 5 9 35 9 30 5 9 3o 5 l m 1 1 01 01 09 3 09 7 484 91 0 1 21 2 1 5 l a l 61 01 09 4 59 4 63 1 09 8 266 6 l a 0 7 1 5 5 8 9 0 8 9 0 02 7 8 9 008 0 l a 0 6 l5 59 2 69 2 609 2 606 6 l a 0 9 1 5 5 9 5 l 9 5 l 0 9 5 10 l a 2 l1 51 01 0 5 81 0 8 458 l1 1 5 71 23 6 l a 3 61 5j 51 2 9 21 3 記1 0 1 9 1 3 8 91 2 7 6 l a 0 8 1 5 1 58 6 38 6 30 138 6 303 3 l a l l2 051 2 2 21 2 2 202 l t 2 2 20 、9 8 l a l 4 2 0 51 2 9 21 2 9 2o2 81 2 9 911 6 m t 2 02 051 1 6 51 1 8 264 31 2 4 21 l8 4 l a 2 62 01 01 2 181 2 5 l53 5 1 3 0 394 4 l a 3 13 01 01 7 8 41 7 8 40 9 7 1 8 2 46 6 l a v e r a g e 24 3 48 0 啥爾演理工大學(xué)工學(xué)碩士學(xué)位論文 實驗的相對偏差比較曲線，如圖2 7 所示。圖2 8 為j v g a 與g a 對表2 1 中的 b e n c h m a r k ( l a 0 6 ) 的迭代曲線。j v g a 與g a 的初始群體規(guī)模皆為l5 0 ，遺傳代數(shù) 為1 0 0 。實驗數(shù)據(jù)來源于文獻(xiàn)“”。 由圖2 6 和表2 1 可以看出：j v g a 對于1 2 個實例( m t 0 6 、l a 0 1 、l a 0 2 、 l a 0 4 一l a 0 9 、l a l l 、l a l 4 、l a 3 1 ) 均可達(dá)到已知最優(yōu)值而g a 只對8 個實例問 題達(dá)到了最優(yōu)值；對于未能達(dá)到最優(yōu)值的實例，j v g a 所獲得的最優(yōu)值較g a 小得多；j v g a 的相對偏差明顯小于g a 的相對偏差，最大相對偏差為 1 0 1 9 ，平均相對偏差為2 4 3 ，僅為g a 的5 0 6 ：圖2 ，7 表明j v g a 的收斂 速度較g a 有較大提高。 _ j v g ag a 圖2 7j v g a 和g a 的相對偏差比較 f i g 2 - 7r e l a t i v ed e r i s i o nc ) , i r v e so f j v g aa n dg a 8 5 0 - l l 一一l 一一l 一。 0 l o2 03 0 4 0 5 0 6 07 08 09 0 f m 圈2 - 8 一個實例的j v g a 和g a 迭代曲線 f i g 2 - 8i t e r a t i o nc u t v c so f j v g aa n dg af o rt h es a m ei n s l a n c e - 2 2 ， 瑚姍瑚瑚m m 哪咖啪 ， ：墜璽鎏竺三查蘭三蘭堡圭蘭竺簍苧 2 6 本章小結(jié) 本章提出的面向j s p 的病毒遺傳算法克服了遺傳算法的早熟和收斂速度慢 等問題，運算效率也比遺傳算法有較大提贏- 。通過1 9 個典型的實驗表明 j v g a 無論是最優(yōu)解的獲取錐力，還是實驗結(jié)果的平均偏差以及收斂速度方面 均明顯優(yōu)于g a ，因此j v g a 其有較強(qiáng)的工程實用性。當(dāng)然，病毒遺傳算法是 一種新型基于生物進(jìn)化理論所形成的模擬進(jìn)化算法，在求解較大規(guī)模的問題時 還需要較長的搜索時間。為進(jìn)一步提高算法的時間性能，j v g a 還需要與其它 啟發(fā)式算法結(jié)合，以獲得更好的解和更快的收斂速度，這也是近年來研究的熱 點。 竺璽鎏苧三查蘭王蘭鎏圭蘭堡墼蘭 第3 章面向車間作業(yè)問題的一個混合遺傳算法 m e t a - h e u f i s t i c 算法，如模擬退火、遺傳算法、禁忌搜索、進(jìn)化規(guī)劃、進(jìn)化 策略、混沌搜索和蟻群系統(tǒng)“7 1 等，以其高效的優(yōu)化性能、無需問題特殊信息等 優(yōu)點，受到各領(lǐng)域廣泛的關(guān)注和應(yīng)用，并成為解決n p h a r d 問題的有力工具。 但當(dāng)問題的規(guī)模和復(fù)雜度增加時，單一算法的優(yōu)化能力大為削減，要確定合適 的算法參數(shù)也是非常困難的。由于優(yōu)化算法的多樣性，對具體問題應(yīng)用何種算 法往往取決子研究人員的經(jīng)驗和愛好。探討各種算法的適用域是一項龐大而困 難的工作，而基于自然機(jī)理提出新的優(yōu)化算法也并非易事。鑒于這種現(xiàn)狀，算 法混合”7 “的思想已成為提高算法性能的一個重要而有效的途徑，其出發(fā)點是 使單一算法互相取長補(bǔ)短，產(chǎn)生更好的優(yōu)化能力和效率。近年來學(xué)術(shù)界提出了 類型和名稱繁多的混合算法，算法