（計算機軟件與理論專業(yè)論文）erp車間作業(yè)調(diào)度模型優(yōu)化及遺傳算法求解.pdf

摘要 摘要 企業(yè)資源計劃e r p 是當(dāng)今世界各類制造業(yè)普遍采用的一種管理信息 集成系統(tǒng)。本文簡要地介紹了e r p 在制造業(yè)中的地位和作用、發(fā)展史、 特點、e r p 在我國企業(yè)的應(yīng)用現(xiàn)狀以及與制造資源計劃m r p1 1 的主要區(qū) 別。 車間作業(yè)調(diào)度問題是最困難的組合優(yōu)化問題之一，也是計算機集成制 造系統(tǒng)中的一個關(guān)鍵環(huán)節(jié)，在實際生產(chǎn)中具有廣泛應(yīng)用。本文根據(jù)工廠車 間生產(chǎn)模式給出了基于工序模式的遺傳算法編碼設(shè)計方式，并且基于這種 編碼方式對車間作業(yè)調(diào)度的成本模型做了優(yōu)化。該模型是一個在時間、可 重復(fù)使用和不可重復(fù)使用資源約束下的多模式車間作業(yè)調(diào)度問題，加入了 不同工序在不同模式下最小延遲，從而使基于該模型的車間作業(yè)調(diào)度問題 能夠達到時間一成本雙優(yōu)的效果。 算法的設(shè)計是解決問題的關(guān)鍵，由于標(biāo)準(zhǔn)遺傳算法求解車間作業(yè)調(diào)度 問題存在過早收斂問題，會產(chǎn)生局部最優(yōu)解，所以本文采用雙倍體遺傳算 法進行求解。雙倍體遺傳算法提供了一種記憶以前有用的基因塊的功能， 提高了算法的適應(yīng)能力。本文以一個簡單例子，討論了車間作業(yè)調(diào)度問題， 隨后利用訓(xùn)練數(shù)據(jù)隨機生成了遺傳算法中的初始群體，并利用雙倍體遺傳 算法進行了調(diào)整，通過仿真實例，給出了算法的性能尋優(yōu)跟蹤曲線由此得 出的結(jié)論，可以看到這是一種行之有效的方法。 關(guān)鍵詞企業(yè)資源計劃；車間作業(yè)調(diào)度；作業(yè)排序：生產(chǎn)計劃；遺傳算法 成本優(yōu)化 燕山大學(xué)工學(xué)碩士學(xué)位論文 a b s t r a c t e n t e r p r i s er e s o u r c ep l a n n i n g ( e r p ) i sak i n do fi n t e g r a t e dm a n a g e m e n t i n f o r m a t i o ns y s t e m , w h i c hh a sb e i n gw i d e l y a d o p t e db ya l ls o r t so f t h ew o r l d t h i s p a p e r i n t r o d u c e ds t a t u so fe r pi nt h e m a n u f a c t u r i n g ，i t sh i s t o r y , c h a r a c t e r i s t i c ，p r e s e n ta p p l i e dc o n d i t i o n so fi n t e r n a lm a n u f a c t u r i n ga n dt h e m a i nd i s t i n g u i s hf r o mm a n u f a c t u r i n gr e s o u r c ep l a n n i n g ( m r p i i ) j o b - s h o ps c h e d u l i n gp r o b l e m ( j s p ) i so n eo f t h eh a r d e s tc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s ，i ti sap i v o t a ll i n ko nc i m sa n dw i l d l ya p p l i e dt ot h e e n g i n e e r i n g ag e n e t i ca l g o r i t h m sc o d ed e s i g nm o d eb a s e do nt h ew o r k i n g p r o c e d u r ep a t t e r n i sb r o u g h tf o r w a r d b yf a c t o r yw o r k s h o pp r o d u c em o d e ，a n d ac o s to p t i m i z a t i o nm o d e lb a s e do nt h i sm o d ef o rj s pi sb u i l ti nt h i sp a p e r , w h i c hi sam u l t i m o d ej s ps u b j e c tt ot h ec o n s t r a i n t so ft i m e ，r e n e w a b l e r e s o u r c e sa n dn o n r e n e w a b l er e s o u r c e s j o i n e dt h ed i f f e r e n tw o r k i n g p r o c e d u r e t h em i n i m u md e l a yt oe n a b l ei tu n d e rt h ed i f f e r e n tp a t t e r nt oa c h i e v et h e t i m e - c o s td o u b l cs u p e r i o rp u r p o s e a l g o r f f h md e s i g ni s t h ep i v o t a lf a c t o ro f s o l v i n gt h ep r o b l e m b e c a u s e t h es t a n d a r d g e n e t i ca l g o r i t h m s ( g a ) s o l v et h e j s pt oe x i s t p r e m a t u r e l y r e s t r a i nt h eq u e s t i o na n dc a nh a v et h ep a r t i a lo p t i m a ls o l u t i o n ，t h e r e f o r et h e d o u b l ec h r o m o s o m e s g e n e t i ca l g o r i t h m si su s e d t oc a r r yo nt h es o l u t i o ni nt h i s p a p e r b e c a u s e t h ea l g o r i t h mr e m e m b e r i n gt h eu s e f u lg e n ep i e c e si sp r o v i d e d ， t h ea d a p t a t i o no f a l g o r i t h mi si n c r e a s e d t h i st h e s i st a k e s as i m p l ei n s t a n c ea s e x a m p l e t od i s c u s sj s p w er a n d o m g e n e r a t et h e i n i t i a lc o l o n yo fg a b yu s i n g t h el a r g en u m b e r so fd a t aa n dw ea d j u s ti tb yd o u b l ec h r o m o s o m e sg e n e t i c a l g o r i t h m b yt h es i m u l a t i o ne x a m p l e ，w er e c e i v et h et r a c k i n gc u r ea n dt h e c o n e l u s i o n t h es i m u l a t i o nr e s u k si n d i c a t et h a tt h i sm e t h o di se f f e c t i v e k e y w o r d se n t e r p r i s er e s o u r c ep l a n n i n g ；j o b - s h o ps c h e d u l i n g ；s e q u e n c i n g ； p r o d u c t i o ns c h e d u l i n g ；g e n e t i ca l g o r i t h m ；c o s to p t i m i z a t i o n 第1 章緒論 1 1 選題意義 第1 章緒論 中國正式宣告進入w t o ，并將成為亞太地區(qū)制造中心，全球眾多制 造業(yè)巨頭都在等待爭奪中國這個大市場。我國企業(yè)的外部經(jīng)濟環(huán)境也面臨 著市場競爭的巨大壓力，諸如：競爭使得產(chǎn)品生產(chǎn)的批量越來越??；產(chǎn)品 的生產(chǎn)周期越來越短；顧客對產(chǎn)品性能、質(zhì)量的要求越來越高；一般水平 的產(chǎn)品及制造能力嚴(yán)重過剩；環(huán)保意識、綠色制造的要求越來越強；能參 與全球競爭的企業(yè)越來越多。從企業(yè)的內(nèi)部條件看，多數(shù)企業(yè)新產(chǎn)品設(shè)計 開發(fā)能力弱，管理粗放且工藝技術(shù)裝備落后。 改革開放以來，我國從計劃經(jīng)濟逐步轉(zhuǎn)變?yōu)樯鐣髁x市場經(jīng)濟，國有 企業(yè)在管理上存在諸多的不適應(yīng)【1 】： ( 1 ) 原材料實行市場調(diào)節(jié)，導(dǎo)致企業(yè)物料成本大幅度上升，整個企業(yè) 的利潤減少； ( 2 ) 計劃經(jīng)濟下“庫存生產(chǎn)型”的計劃及按產(chǎn)品品種與批量的輪番投 產(chǎn)的生產(chǎn)方式造成產(chǎn)、成品大量積壓； ( 3 ) 重產(chǎn)出的管理方式造成庫存資金占用大，資金周轉(zhuǎn)率低； ( 4 ) 人工粗放型管理和縱向直線職能式的組織機構(gòu)不能有效利用企業(yè) 資源； ( 5 ) 企業(yè)的管理人員多數(shù)靠經(jīng)驗管理，知識老化，觀念陳舊，缺少先 進的管理思想； ( 6 ) 人工經(jīng)驗設(shè)計，致使產(chǎn)品技術(shù)附加值低，更新?lián)Q代慢，對市場的 快速反應(yīng)能力差。 從市場經(jīng)濟下企業(yè)面臨的嚴(yán)峻形式上看，為保證國民經(jīng)濟的持續(xù)發(fā) 展，必須采用信息技術(shù)和現(xiàn)代管理技術(shù)，用先進制造技術(shù)c a d 、m r pi i 、 e r p 、c i m s l 2 1 來提高我國企業(yè)的技術(shù)創(chuàng)新能力和市場競爭能力。e r p 正 是在這樣的國情和背景下轉(zhuǎn)變?yōu)槠髽I(yè)的需求，從政府行為、單純計算機技 術(shù)的推廣應(yīng)用行為轉(zhuǎn)變?yōu)橐蕴岣咂髽I(yè)市場競爭力為目標(biāo)的企業(yè)行為。 燕山大學(xué)工學(xué)碩士學(xué)位論文 實施e r p 是企業(yè)由計劃經(jīng)濟下形成的粗放生產(chǎn)型管理向市場經(jīng)濟要 求的現(xiàn)代化企業(yè)的經(jīng)營效益型管理轉(zhuǎn)化的過程，其中包括企業(yè)的改革、改 組、改制，涉及管理機制、管理方法、管理觀念等，是企業(yè)管理的一項重 大改革，充分認(rèn)識e r p 具有深遠的意義。而e k p 系統(tǒng)中生產(chǎn)模塊式企業(yè) 生產(chǎn)的核心。企業(yè)的生產(chǎn)計劃往往是個從粗到細的t o p d o w n 過程，從 企業(yè)的生產(chǎn)經(jīng)營計劃( b p ) 、生產(chǎn)計劃( p p ) 、主生產(chǎn)計劃( m p s ) 、物料需求 計劃( m r p ) 至u 車間作業(yè)計劃( p a c ) 等，下一層計劃是對上一層計劃的細化 和落實，計劃的執(zhí)行單位在車間層，生產(chǎn)計劃的優(yōu)化是一個從p a c 開始 逐層向上的b o s o m u p 過程，因此，車間作業(yè)調(diào)度的優(yōu)化對于整個企業(yè)的 生產(chǎn)重要作用。 1 2e r p 的發(fā)展史 e r p ( e m e r p r i s e r e s o u r c e sp l a n n i n g ) & p 企業(yè)資源計劃，是由制造業(yè)發(fā)展 起來的，目前主要還是在制造業(yè)中應(yīng)用，因此認(rèn)識e r p 必須從制造業(yè)開 始。 制造企業(yè)從社會化大市場中獲得資金、物資、人才等資源，又將資源 轉(zhuǎn)化為某種社會需求的產(chǎn)品，并將商品銷售到用戶手中。制造企業(yè)自身就 以生產(chǎn)物質(zhì)商品為自己的贏利和生產(chǎn)手段。因而制造企業(yè)必須用最少的資 源消耗，獲取最大的增值。有效的資源獲取、轉(zhuǎn)換和分配就成為制造企業(yè) 經(jīng)營活動的主要內(nèi)容。獲取資源、轉(zhuǎn)化和分配是通過它的計劃與控制來完 成的。編制滿足需求數(shù)量和交付期的計劃，監(jiān)督和控制該計劃的實現(xiàn)，并 且所編制的計劃使企業(yè)在滿足需求的前提下，資源的分配最合理和消耗最 少、生產(chǎn)最經(jīng)濟的，就成為現(xiàn)代制造企業(yè)的核心。 制造企業(yè)同時滿足不斷變化的用戶需求和生產(chǎn)過程資源消耗最少這 兩個原則之間是相互矛盾的。解決這矛盾的理論和方法成為現(xiàn)代化制造 管理研究的焦點和進步的動力。隨著企業(yè)在社會中的作用范圍的擴大和企 業(yè)對資源理解的深化，制造計劃理論和應(yīng)用就這樣不斷地發(fā)展和深化了。 從1 9 5 7 年美國生產(chǎn)與庫存控制協(xié)會( a m e r i c a np r o d u c t i o n a n d i n v e n t o r yc o n t r o ls o c i e t y , a p t c s ) 的成立與1 9 6 0 年前后j o s e p ho r l i c k y 等人 2 第1 蘋緒論 開發(fā)的第套物料需求- 計戈l j ( m a t e r i a lr e q u f f e m e n sp l a n n i n g ，m r p ) 軟件的 面世到現(xiàn)階段，縱觀近四十年的發(fā)展歷程，e r p 的發(fā)展大體上經(jīng)歷了四個 階段口】： ( 1 ) 作為一種庫存定貨計劃一m r p ，即物料需求計劃階段，或稱基本 m r p 階段”1 ： ( 2 ) 作為一種生產(chǎn)計劃與控制系統(tǒng)一閉環(huán)m r p 階段口1 。在這兩個階段， 出現(xiàn)了豐田生產(chǎn)方式( 看板管理) f 6 1 、全面質(zhì)量管理( t q c ) n 準(zhǔn)時生產(chǎn)( j i t ) 陋 以及數(shù)控機床等支撐技術(shù)： ( 3 ) 作為一種企業(yè)經(jīng)營生產(chǎn)管理信息系統(tǒng)一m r pi i 階段 9 】。這一階段的 代表技術(shù)是c i m s ”1 ； ( 4 ) e r p 的形成階段融合了其他現(xiàn)代管理思想和技術(shù)，面向全球市 場，建設(shè)“國際優(yōu)秀制造業(yè)”【“l(fā) 。這一階段倡導(dǎo)的觀念是精益生產(chǎn)、約 束理論( t o c ) 、先進制造技術(shù)、靈敏制造以及現(xiàn)在熱門的i n t e r n e t i n t r a n e t ； ( 5 ) e r p i i 一擴展型e r p 。這個概念提出時間是2 0 0 0 年，在g a r t n e r g r o u p 率先提出e r p 的概念1 0 年之后，g a r t n e r 又提出了一個新的概念 e r p i i 。這一階段的管理范圍更加擴大，繼續(xù)支持與擴展企業(yè)的流程重組， 運用最先進的計算機技術(shù)，基于協(xié)同商務(wù)，面向e b u s i n e s s 環(huán)境f 的虛擬 企業(yè)集成，e r p l l 是一個發(fā)展中的概念，還未完全形成。e r p i i 是e r p 的 未來。 可以發(fā)現(xiàn)，e r p 系統(tǒng)發(fā)展中的每一次進步都與社會經(jīng)濟的發(fā)展階段， 企業(yè)所處經(jīng)營環(huán)境的變化息息相關(guān)，尤其重要的是，新的管理哲學(xué)、管理 理論、管理技術(shù)的出現(xiàn)，必然地成為e r p 系統(tǒng)發(fā)展的直接催化劑。 1 2 1 庫存控制定貨點法 早在四十年代初期，西方的經(jīng)濟學(xué)家就提出了定貨點法理論【”】，它 根據(jù)每種物料需求量和訂購( 生產(chǎn)) 時間的歷史記錄以及經(jīng)驗來估算未來 的物料需求，即庫存物料數(shù)量隨物料消耗而減少，當(dāng)某一時刻庫存量可供 消耗的時間等于此種物料的生產(chǎn)提前期0 13 1 時，就要進行訂貨以補充庫存。 決定訂貨時的數(shù)量和時間即定貨點9 1 。 燕山大學(xué)工學(xué)碩士學(xué)位論文 定貨點法的假設(shè)條件是：物料需求是相互獨立且連續(xù)發(fā)生的；提前期 是已知和固定的；物料短缺應(yīng)及時填滿。由于這些假設(shè)條件在現(xiàn)實中很難 滿足，比如制造業(yè)生產(chǎn)中的零部件的需求就是根據(jù)由它們裝配而成的最終 成品的需求所決定的，是不獨立需求，或稱相關(guān)需求，所以定貨點法存在 著嚴(yán)重的不足和局限。 1 2 2 時段式m r p 為了解貨點法存在的缺陷，6 0 年代人們又提出了時段式m r p 。 m r p ( m a t e r i a lr e q u k e m e n tp l a n n i n g ) ，即物料需求計劃。它在傳統(tǒng)方法的 基礎(chǔ)上引入了時間段和物料清單f b o m ) 【1 4 】的概念，依據(jù)產(chǎn)品結(jié)構(gòu)和庫存情 況，以完工日期為準(zhǔn)則，按制造和采購提前期的不同而倒排計劃，確定 b o m 上所有物料的需求和訂貨時間，從而達到了能夠及時、準(zhǔn)確、動態(tài) 地反映生產(chǎn)系統(tǒng)中物料需求情況。 時段式m r p 先通過產(chǎn)品結(jié)構(gòu)文件將主生產(chǎn)計劃中對產(chǎn)品的需求進行 分解，生成對部件、零件以及材料的毛需求量計劃。進而利用毛需求量、 庫存情況、計劃期內(nèi)各零部件定貨或在制品情況等數(shù)據(jù)進行計算，以確定 在產(chǎn)品結(jié)構(gòu)各層次上零部件的凈需求量，以及零部件生產(chǎn)計劃。時段式 m r p 將產(chǎn)品計劃轉(zhuǎn)化為零部件生產(chǎn)( 訂購) 計劃，計算出為完成生產(chǎn)計劃的 要求，應(yīng)生產(chǎn)哪些零件，生產(chǎn)多少數(shù)量，何時下達零部件生產(chǎn)任務(wù)，何時 交貨。 但是時段式m r p 仍存在著缺陷，比如它沒有解決如何保證零部件生 產(chǎn)計劃成功實施的問題，它缺乏對完成計劃所需的各種資源進行計劃與保 證的功能，也缺乏根據(jù)計劃實施實際情況的反饋信息和對計劃進行調(diào)整的 功能。因此時段式m r p 主要應(yīng)用于訂購的情況，涉及的是企業(yè)與市場的 界面，而沒有深入到企業(yè)生產(chǎn)管理的核心中去。 1 2 3 閉環(huán)m r p 進入7 0 年代后，人們針對m r p 的缺陷，又提出了閉環(huán)式m r p 。其 原理是在m r p 的基礎(chǔ)上，增加生產(chǎn)能力負荷 1 5 】分析，只有當(dāng)生產(chǎn)能力得 4 第1 蘋緒論 到及時確認(rèn)后，才能繼續(xù)執(zhí)行物料需求計劃、能力需求計劃 16 】和車間作 業(yè)計劃，并且建立車間現(xiàn)場、采購信息反饋機制，以便及時地控制和調(diào)整 計劃的執(zhí)行。閉環(huán)m r p 理論認(rèn)為，只有在考慮能力的約束，或者對能力 提出需求計劃，在滿足能力需求的前提下，物料需求計j a j ( m r p ) j 能保證 物料需求的執(zhí)行和實現(xiàn)。在物料需求計劃執(zhí)行之前，要由能力需求計劃核 算企業(yè)的工作中心的生產(chǎn)能力和需求負荷之間的平衡情況。 在閉環(huán)式m r p 中，主生產(chǎn)計劃及物料需求計劃計算以后，要通過粗 能力計劃、能力需求計劃等模式進行生產(chǎn)能力平衡。若生產(chǎn)能力不能滿足 計劃要求，應(yīng)根據(jù)能力調(diào)整相應(yīng)的計劃。同時，它還能收集生產(chǎn)( 采購) 活 動的執(zhí)行結(jié)果，以及外界環(huán)境變化的反饋信息，作為制定下一周期計劃或 調(diào)整計劃的依據(jù)。由于增加了上述功能，使之形成“計劃一執(zhí)行一反饋” 的生產(chǎn)管理循環(huán)，使得物料需求計劃的可執(zhí)行性和可操作性大大提高，同 時也增強了生產(chǎn)管理對市場的應(yīng)變能力。 1 2 4 制造資源計劃一m r p i i 閉環(huán)式m r p 系統(tǒng)的出現(xiàn)，使得生產(chǎn)活動形成了一個較完整的環(huán)形回 路，但是卻忽略了一個重要的問題。在企業(yè)管理中，不僅要涉及以制造為 主線的物流和信息流，還有與之密切相關(guān)的資金流。于是進入八十年代后， 人們逐漸認(rèn)識到，應(yīng)建立一個一體化的管理系統(tǒng)，把生產(chǎn)、財務(wù)、銷售、 庫存、工程技術(shù)、采購等子系統(tǒng)緊密結(jié)合起來，形成一個系統(tǒng)整體，這便 是m r p i i 。 1 2 5企業(yè)資源計劃一e r p 1 9 9 0 年，美國g a r t n e rg r o u p 公司在當(dāng)時流行的工業(yè)企業(yè)管理軟件 m r p l i 的基礎(chǔ)上，提出了評估m(xù) r p i i 的內(nèi)容和效果的軟件包，這些軟件 包被稱之為e r p 。g a r t n e r 給e r p 的界定為：超越m r p i i 范圍的集成功能； 支持混合方式的制造環(huán)境；支持能動地監(jiān)控能力，模擬分析和決策支持； 支持開放的客戶服務(wù)器計算環(huán)境。集成范圍是面向供需鏈的需求市場、 制造企業(yè)、供應(yīng)市場信息集，克服m r pi i 局限；實現(xiàn)和供應(yīng)企業(yè)、需求 燕山大學(xué)工學(xué)碩士學(xué)位論文 企業(yè)信息集成。 1 2 6擴展型e r p e r pi i e r p i i 一擴展型e r p 。這個概念最早提出時間是2 0 0 0 年，在g a r t n e r g r o u p 率先提出e r p 的概念1 0 年之后，g a r t n e r 又提出一個新的概念一 e r p i i 。這一階段的管理范萄更加擴大，繼續(xù)支持與擴展企業(yè)的流程重組， 運用最先進的計算機技術(shù)，基于協(xié)同商務(wù)，面向e b u s i n e s s 環(huán)境下的虛擬 企業(yè)集成，e r p i i 是一個發(fā)展中的概念，還未完全形成。e r p t l 是e r p 的 未來。 1 3 e i 沖在我國企業(yè)的應(yīng)用現(xiàn)狀分析及對策 7 0 年代苯到8 0 年代初，沈陽鼓風(fēng)機廠引進了i b m 公司的計算機并 實施其c o p i c s ( c o m m u n i c a t i o no r i e n t e d o fp r o d u c t i o na n di n f o r m a t i o n c o n t r o ls y s t e m ) 軟件，即面向通信的生產(chǎn)和信息控制系統(tǒng)。c o p i c s 系統(tǒng) 是一種i b m 商業(yè)化的m r p i i 軟件包，它的引進標(biāo)志著e r p 的管理概念和 方法開始引入我國。2 0 0 3 年初本人參與山東魯能電纜有限公司e r p 實施 項目，親身感受e r p 在我國的發(fā)展情況。e r p 系統(tǒng)越來越受到我國眾多 制造企業(yè)的重視。據(jù)抽樣調(diào)查統(tǒng)計，近二十多年以來，我國不同程度引進 e r p 系統(tǒng)的企業(yè)近千家，總投資額約8 0 億元l 2 2 。 按實施過程的不同階段，可以將這些企業(yè)分為三類1 2 3 】。第類的企 業(yè)是指進行了系統(tǒng)總體規(guī)劃，計劃的編制已開始由手工完成向計算機輔助 完成轉(zhuǎn)變，對基礎(chǔ)數(shù)據(jù)進行糇理，開展了前期工作的企業(yè)；第二階段的企 業(yè)是指在第一階段基礎(chǔ)上，已經(jīng)應(yīng)用了系統(tǒng)的部分模塊進行庫存管理、采 購管理、訂單管理、材料用量管理等，基本上形成了時段式m r p 的企業(yè)； 第三階段的企業(yè)是指向能力需求計劃擴展，把車間作業(yè)計劃、銷售、財務(wù) 導(dǎo)入系統(tǒng)，基本上形成閉環(huán)m r p ，或者已經(jīng)形成e r p 的企業(yè)。 然而真正實現(xiàn)了e r p 系統(tǒng)的企業(yè)畢竟是少數(shù)，這是因為改革開放后， 我國企業(yè)的經(jīng)營機制由生產(chǎn)型向生產(chǎn)經(jīng)營型轉(zhuǎn)變，改革是一個相當(dāng)長的過 程，因此工業(yè)企業(yè)中有許多情況與e r f 系統(tǒng)的應(yīng)用條件和假設(shè)相矛盾， 6 第1 蕈緒論 傳統(tǒng)生產(chǎn)模式與e r p 思維之間主要差距【2 4 】。 除此之外，企業(yè)內(nèi)部還存在著其它一些因素，制約了e r p 作用的充 分發(fā)揮，比如： ( 1 ) 企業(yè)領(lǐng)導(dǎo)對什么是e r p 系統(tǒng)并不了解，因此往往出現(xiàn)項目組織和 人選不當(dāng)，不能有效地進行企業(yè)管理改革，不能克服傳統(tǒng)管理思想和模式 的阻力，阻礙系統(tǒng)實施； ( 2 ) 企業(yè)對應(yīng)用e r p 系統(tǒng)的緊迫性認(rèn)識不足，因此延誤時機，不利于 提高企業(yè)在國內(nèi)外市場的競爭力； ( 3 ) 缺乏規(guī)范有效的數(shù)據(jù)。作為一種管理信息系統(tǒng)，e r p 要進行大量 的數(shù)據(jù)處理，而數(shù)據(jù)處理的準(zhǔn)確性、及時性和完整性是計算機輔助企業(yè)管 理的最基本要求。但由于外部環(huán)境的不確定因素很多，在企業(yè)內(nèi)部的生產(chǎn) 作業(yè)、在制品定額和原材料采購等環(huán)節(jié)的控制決策又要有人來完成，難以 得到準(zhǔn)確有效的基礎(chǔ)數(shù)據(jù)，這直接影響到e r p 的實施效果； ( 4 ) 目前國內(nèi)缺乏既有權(quán)威又富有實踐經(jīng)驗的管理咨詢機構(gòu)為企業(yè)的 e r p 項目服務(wù)，導(dǎo)致不必要的浪費。 結(jié)合e r p 在我國的實施現(xiàn)狀，應(yīng)注意以下幾個方面的問題【2 5 】： ( 1 ) 企業(yè)決策層應(yīng)加強對e r p 的支持和直接參與。e r p 的開發(fā)與實施 是對企業(yè)管理模式、管理思想及管理方式的一場變革，而不是局部的技術(shù) 改造，因而需要管理層的支持與調(diào)控，以便能在設(shè)計的有關(guān)部門順利實行； ( 2 ) 徹底轉(zhuǎn)變觀念，包括市場觀念、時間觀念、質(zhì)量觀念、成本意識、 信息意識等： ( 3 ) 根據(jù)企業(yè)的需求選用適用的e r p 軟件； ( 4 謂j 科學(xué)的方法組織系統(tǒng)的開發(fā)、實施； ( 5 ) 注意e r p 的應(yīng)用范圍，減少不必要的浪費。 1 4 研究e i 沖系統(tǒng)中生產(chǎn)調(diào)度問題解決方法的重要性 柔性制造系統(tǒng)作為一類復(fù)雜的人造系統(tǒng)，具有復(fù)雜性、遞階結(jié)構(gòu)、不 確定性、多目標(biāo)、多約束、多資源相互協(xié)調(diào)等特點。鑒于其重要的應(yīng)用價 值和理論意義，相關(guān)的分析與控制的研究方法已受到工業(yè)界和控制界的廣 燕山大學(xué)工學(xué)碩士學(xué)位論文 泛關(guān)注。制造系統(tǒng)的分析，是基于系統(tǒng)的已知配置和決策，在一定的假設(shè) 條件下，對系統(tǒng)的各種性能進行評估；而制造系統(tǒng)的控制，則是根據(jù)一定 的目標(biāo)和約束來確定系統(tǒng)的配置和決策。研究控制策略的目的是提高系統(tǒng) 的性能，而系統(tǒng)分析的目的則是更好地優(yōu)化和控制系統(tǒng)。制造系統(tǒng)的分析 和控制方法，從理論體系上可分為運籌學(xué)方法、馬爾可夫鏈、排隊論、極 大極小代數(shù)、攝動分析法、p e t r i 網(wǎng)、自動機形式語言和仿真方法等。它 們涉及系統(tǒng)的邏輯層次、時間層次和隨機層次，進而形成離散事件動態(tài)系 統(tǒng)的理論框架。 生產(chǎn)調(diào)度是制造系統(tǒng)的個研究熱點，也是理論研究中最為困難的問 題之一。調(diào)度的任務(wù)是根據(jù)生產(chǎn)目標(biāo)和約束，為每個加工對象確定具體的 加工路徑、時間、機器和操作等。優(yōu)良的調(diào)度策略對于提高生產(chǎn)系統(tǒng)的最 優(yōu)性和提高企業(yè)經(jīng)濟效益有著極大的作用。由于系統(tǒng)建模方法的多樣性 以及問題的側(cè)重點不同，調(diào)度方法和研究對象也有明顯的不同。就對象而 言，有確定性和隨機性調(diào)度、離散事件和連續(xù)事件調(diào)度、靜態(tài)和動態(tài)調(diào)度 等。就調(diào)度方法而論，有g(shù) a n t t 圖法、構(gòu)造型方法、動態(tài)規(guī)劃、分支定界 法、排隊論方法、規(guī)則調(diào)度方法和仿真方法等。調(diào)度的優(yōu)化指標(biāo)包括正規(guī) 性能指標(biāo)和非正規(guī)性能指標(biāo)，常用的指標(biāo)有最大完成時間、平均加工時間、 平均延遲時間、生產(chǎn)成本和e 廠r 指標(biāo)等。 目前，對調(diào)度理論的研究已受到廣泛的關(guān)注，并取得了較大的進展， 但還很不成熟。其中，對調(diào)度問題的復(fù)雜性研究已成為工程背景很強的一 個應(yīng)用數(shù)學(xué)分支。在算法研究方面，基于知識的方法和算法技術(shù)相結(jié)合的 趨勢正變得日趨顯著，概率分析方法在算法效率和性能方面的研究日益增 多。對于難以求得最優(yōu)解的問題，給出多項式時間的搜索方法具有很大的 現(xiàn)實意義。同樣，算法的隨機性能分析也是比較有效的分析手段。算法研 究中，最優(yōu)化性能的漸近性分析具有理論指導(dǎo)性，而基于啟發(fā)式算法的誤 差估計來確定次優(yōu)度無疑同樣具有很大的意義。由于約束條件的存在導(dǎo)致 難以建立數(shù)學(xué)模型，純數(shù)學(xué)的方法往往不易奏效，也不易處理并發(fā)現(xiàn)象， 因此，從工程中“滿意”即可的實際需求出發(fā)，尋求滿足約束條件的快速 有效的優(yōu)化算法正變得更有現(xiàn)實意義。迄今，計算復(fù)雜性理論表明，多數(shù) 第1 章緒論 調(diào)度問題都屬于n p 難題。線性規(guī)劃、動態(tài)規(guī)劃、分支定界和梯度下降等 傳統(tǒng)方法，或是需要目標(biāo)函數(shù)的特殊信息，或是復(fù)雜度大，或是優(yōu)化性能 差，因而一般只能處理小規(guī)模問題，難以高效高質(zhì)量地求解大規(guī)模復(fù)雜的 調(diào)度問題。 人們正是由于意識到基于計算和數(shù)值式的優(yōu)化技術(shù)的弱點，以及調(diào)度 問題的約束性、非線性、多極小性、不確定性、大規(guī)模性、多目標(biāo)性等復(fù) 雜性，才努力研究和發(fā)展了統(tǒng)計式全局搜索技術(shù)和人工智能的方法，例如 模擬退火、遺傳算法、禁忌搜索、進化規(guī)劃、進化策略、神經(jīng)網(wǎng)絡(luò)方法、 l a g r a n g i a n 松弛方法和混沌優(yōu)化法等。這些優(yōu)化算法通過模擬或者揭示某 些自然現(xiàn)象、過程和規(guī)律而得到發(fā)展，以人類知識和理解客觀事物的知識、 經(jīng)驗等作為解決問題的方法，其思想和內(nèi)容涉及數(shù)學(xué)、物理學(xué)、生物進化、 人工智能、神經(jīng)科學(xué)和統(tǒng)計力學(xué)等，為解決復(fù)雜問題提供了新的思路和手 段。迄今，這些算法獨特的優(yōu)點、機制及其非凡的優(yōu)化能力，引起了國內(nèi) 外學(xué)者的廣泛重視，并掀起了該領(lǐng)域的研究熱潮，而且在諸多領(lǐng)域得到了 成功應(yīng)用，較滿意地解決了一大批傳統(tǒng)優(yōu)化方法難以解決的復(fù)雜問題。為 此，國際上已設(shè)立了相應(yīng)的學(xué)術(shù)協(xié)會和諸多相關(guān)的學(xué)術(shù)期刊與會議，而遺 傳算法則是其中研究與應(yīng)用最廣的一類優(yōu)化算法。 1 5 課題來源及論文的結(jié)構(gòu)安排 本課題研究內(nèi)容分為三部分，第一部分是本人在山東魯能電纜有限公 司實習(xí)期間對該公司應(yīng)用的e r p 系統(tǒng)所用的韓國三星公司的u n i e r p 軟 件包和實際生產(chǎn)模式的理解，提出了基于工序模式的遺傳算法編碼設(shè)計方 案，對基于工序模式編碼方式加以研究和分析；第二部分是給出車間作業(yè) 調(diào)度問題面向成本優(yōu)化的模型；第三部分是利用雙倍體遺傳算法根據(jù)第二 部分提出的模型對車間作業(yè)調(diào)度問題進行求解。 論文的結(jié)構(gòu)安排如下： 第l 章簡要介紹了本研究課題的意義，e r p 的歷史和現(xiàn)狀以及對e r p 在我國發(fā)展前景進行分析，隨后進一步介紹了應(yīng)用在e r p 系統(tǒng)中的車間 作業(yè)調(diào)度問題。在本章的最后給出了本課題的來源和論文結(jié)構(gòu)的安排。 燕山大學(xué)上學(xué)碩士學(xué)位論文 第2 章首先簡要敘述了基本生物進化理論和遺傳學(xué)基本知識和遺傳 算法的理論基礎(chǔ)以及遺傳算法的基本流程。隨后介紹了關(guān)于e r p 系統(tǒng)生 產(chǎn)管理的一些必要的基礎(chǔ)知識，對車間作業(yè)調(diào)度問題做了簡要的介紹。最 后簡要介紹了一下仿真工具m a t l a b 的知識。 第3 章首先根據(jù)本人親身參與的實施項目介紹e r p 項目實施實際情 況，對u n i e r p 系統(tǒng)做了簡要的性能分析，其次介紹了遺傳算法的編碼設(shè) 計方法，列舉了一些比較常見編碼方式，并且根據(jù)評價標(biāo)準(zhǔn)對這幾種編碼 方式進行了分析；提出了基于工序模式的遺傳算法編碼設(shè)計方案，對基于 工序模式編碼方式加以研究。 第4 章介紹了車間作業(yè)排序問題有很多不同的分類，相當(dāng)一部分書籍 都對流水車間的排序問題作了介紹，根據(jù)第三章提出了基于工序模式的遺 傳算法編碼設(shè)計方案，給出了一種成本和時間雙優(yōu)的優(yōu)化模型。 第5 章首先介紹了對于解決車間作業(yè)調(diào)度問題的幾種解決方法，給出 了雙倍體遺傳算法解決車間作業(yè)調(diào)度問題的設(shè)計方案并用m a t l a b 軟件 對該算法進行仿真，最后用提出設(shè)計一個存儲過程來實現(xiàn)算法功能，給出 了源程序的初步框架。 1 0 第2 章理論知識簡介 第2 章理論知識簡介 2 1 遺傳算法簡介 遺傳算法是人工智能的重要新分支，是基于達爾文進化論在計算機上 模擬生命進化機制雨發(fā)展起來的一門新學(xué)科。該算法建立在自然選擇和自 然遺傳學(xué)機理基礎(chǔ)上，是一種迭代自適應(yīng)概率性搜索算法，雖早由美國的 j h h o l l a n d 教授提出，模擬了自然選擇和自然遺傳過程中的選擇、交叉、 變異現(xiàn)象，根據(jù)適者生存、優(yōu)勝劣汰的自然法則，利用遺傳算子，逐代產(chǎn) 生優(yōu)選個體，最終搜索到較優(yōu)的個體，具有不需要求梯度、能得到全局最 優(yōu)解、算法簡單、可并行處理等優(yōu)點。目前隨著計算機技術(shù)的發(fā)展，它愈 來愈得到人們的重視，并在機器學(xué)習(xí)、模式識別、神經(jīng)網(wǎng)絡(luò)、優(yōu)化控制等 領(lǐng)域得到廣泛應(yīng)用 2 6 。 2 1 1生物進化理論和遺傳學(xué)的基本知識 生命自從在地球上誕生以來，就開始了漫長的生物進化歷程，從低級、 簡單的生物類型逐漸發(fā)展成高級、復(fù)雜的生物類型。在達爾文的自然選擇 學(xué)說中認(rèn)為，生物要生存下去，就必須進行包括種內(nèi)斗爭、種間斗爭以及 生物跟無機環(huán)境之間的斗爭的生存斗爭。在生存斗爭中，具有有利變異的 個體容易存活下來，并且有更多的機會將有利變異傳給后代；具有不利變 異的個體容易被淘汰，產(chǎn)生后代的機會也少的多。達爾文的自然選擇學(xué)說 表明，遺傳和變異是決定生物進化的內(nèi)在因素。遺傳是指父代與子代在性 狀上存在的相似現(xiàn)象。變異是指父代與子代之間，以及子代的不同個體之 間，在性狀上或多或少的存在差異的現(xiàn)象。遺傳和變異的關(guān)系十分密切。 一個生物體的遺傳性狀往往會發(fā)生變異，而變異的性狀有的可以遺傳。遺 傳能使生物的性狀不斷地傳送給后代，因此保持物種的特性，變異能夠使 生物的性狀發(fā)生改變，從而適應(yīng)新的環(huán)境而不斷向前發(fā)展。 因為遺傳算法效法的是基于自然選擇的生物進化論，是一種模仿生物 進化過程的隨機方法，所以生物學(xué)的一些基本概念對于理解遺傳算法十分 燕山大學(xué)工學(xué)碩士學(xué)位論文 重要。染色體是生物細胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的 主要載體?；蚴沁z傳效應(yīng)的有效片段，它儲存著遺傳信息，可以準(zhǔn)確地 復(fù)制，也能發(fā)生突變。染色體中基因位置稱作基因座，而基因所取的值叫 做等位基因。染色體又有兩種相應(yīng)模式，基因型和表現(xiàn)型。表現(xiàn)型是指生 物個體所表現(xiàn)出來的性狀，而基因型指與表現(xiàn)型密切相關(guān)的基因組成。同 一種基因型的生物個體在不同環(huán)境條件下可以有不同的表現(xiàn)型，因此表現(xiàn) 型是基因型和環(huán)境條件相互作用的結(jié)果。生物體自身通過對基因的復(fù)制 ( r e p r o d u c t i o n ) 和交叉( c r o s s o v e r l ，即基因分離、基因自由組合和基因連鎖 互換的操作使其性狀的遺傳得到選擇和控制。同時通過基因重組、基因變 異和染色體上的變異產(chǎn)生豐富多彩的變異現(xiàn)象。生物的遺傳特性，使得生 物界的物種能夠保持相對的穩(wěn)定；生物的變異特性，使生物個體產(chǎn)生新的 性狀，以至于形成新的物種，推動生物的進化和發(fā)展。 遺傳算法是自然遺傳學(xué)和計算機科學(xué)相互結(jié)合滲透而成的新的計算 方法，所以遺傳算法中使用了自然進化中的基礎(chǔ)用語。了解這些用于對學(xué) 習(xí)和應(yīng)用遺傳算法是十分必要的。 在遺傳算法中，染色體對應(yīng)的是數(shù)據(jù)或數(shù)組，串上各個位置對應(yīng)的是 基因座，而各個位置上所取得的值對應(yīng)的是等位基因。生物體的復(fù)制、交 叉和變異對應(yīng)是遺傳算法中的選擇操作( s e l e c t i o n ) 、交叉操作( c r o s s o v e r ) 和 變異操作( m u t a t i o n ) 。遺傳算法處理的是染色體，或者叫基因型個體 ( i n d i v i d u a l s ) 。一定數(shù)量的個體組成了群體( p o p u l a t i o n ) ，也叫做集團。群 體中的個體的數(shù)目稱為群體的大小( p o p u l a t i o ns i z e ) ，也可以叫做群體規(guī) 模。而每個個體對環(huán)境的適應(yīng)程度叫做適應(yīng)度( f i t n e s s ) 。執(zhí)行遺傳算法包 括兩個必需的數(shù)據(jù)轉(zhuǎn)換操作，一個是表現(xiàn)型到基因型的轉(zhuǎn)換，另一個是基 因型到表現(xiàn)型的轉(zhuǎn)換。前者是編碼( c o d i n g ) 操作，后者叫做譯碼( d e c o d i n g ) 操作【2 ”。 2 1 2 遺傳算法的基礎(chǔ)知識 遺傳算法已經(jīng)被應(yīng)用到了很多方面，但是其理論基礎(chǔ)卻相對比較薄 弱，如模式定理、積木塊假設(shè)、最小騙問題以及它的隱含并行性，在這些 第2 章理論知彭j 簡介 理論基礎(chǔ)中比較成熟的理論也就是模式定理，在這里簡要介紹下模式定 理和積木塊假設(shè)。 模式是某些固定位置上取相同字符的字符串的集合，它一般用日表 示。以長度為5 的串為例，模式h 1 * 0 0 1 表示在1 、3 、4 、5 的位置非別 是1 、0 、0 、1 的所有串，即f 1 1 0 0 1 ，1 0 0 0 1 ，又比如模式$ 1 十 o 描述了 所有位置2 為1 、位置5 為0 的所有字符串，即 0 1 0 0 0 ，0 1 0 1 0 ，0 1 1 0 0 ，0 1 1 1 0 ， 1 1 0 0 0 ，1 1 0 1 0 ，1 1 1 0 0 ，1 1 1 1 0 l ，從中可以看到一個串隱含著多個模式( 長為 的串隱含著2 。個模式) ，而一個模式可以隱含在多個字符串中，從而不同 的串可以通過模式相互聯(lián)系。遺傳算法中串的運算實際上是模式的運算。 因此下面看一下模式在遺傳操作下的變化。 首先看如下兩個定義【2 7 j ： 定義2 1 ：模式日中所有確定位置的個數(shù)稱作該模式的模式階，記作 d ( h 1 。 定義2 2 ：模式日中第一個確定位置和最后一個確定位置之間的距離 稱作該模式的定義距，記作6 ( h ) 。 先考慮選擇操作對模式的作用。假設(shè)在第f 代群體a ( t ) 中模式h 所能 匹配的個數(shù)為m ，記為m ( h ，r 1 。在選擇中，一個串的選擇是根據(jù)其適應(yīng) 度進行復(fù)制的。更確切地說，一個串是以概率只：f ff 進行選擇，則在 ，+ l 代模式日所匹配的樣本數(shù)是m ( h ，+ 1 ) = m ( 1 4 ，) - f ( h ) f ，其中廠( 日) 是模式所有樣本的平均適應(yīng)度，廠是群體的平均適應(yīng)度?？梢姡Ｊ降钠?均適應(yīng)度高于群體的平均適應(yīng)度，模式樣本數(shù)在下一代中增加，反之減少。 如果這里設(shè)實際群體適應(yīng)度高出群體平均適應(yīng)度的部分為叮，c 為常數(shù)， 則m ( h ，t + 1 ) = m ( h ，f ) ( 夕+ 于) 于= m ( h ，小( 1 + c ) ，假設(shè)t = 0 開始，則 ，”( 日，t + 1 ) = m ( h ，0 ) - 【1 + c j ( 2 1 ) 可見在選擇算子作用下，平均適應(yīng)度高于群體平均適應(yīng)度的模式將呈 指數(shù)級增長，平均適應(yīng)度低于群體平均適應(yīng)度的模式將呈指數(shù)級減少。 接著考慮一下交叉操作對模式的作用，模式在交叉算子作用下只有交 叉點落在定義距之外才能生存，所以在簡單交叉下日的生存概率 尸= 1 6 ( h ) ( l 一1 ) ，而交叉本身也是以一定的概率p 發(fā)生，如果與模式日 燕山大學(xué)工學(xué)碩士學(xué)位論文 的一個樣本a 的配對的樣本4 在模式h 所有的固定位置都與4 相同，則 交叉點即使落在定義距之內(nèi)它也可以生存，所以模式h 的生存概率為 只1 一只6 ( h ) ( l 1 )( 2 2 ) 考慮在選擇算子和交叉算子的共同作用下，模式丑第t + 1 代的樣本數(shù) 是 m ( h ，t + 1 ) m ( h ，f ) ( ，( 日) ，廠) l l 一6 ( h ) i ( l 1 ) j( 2 3 ) 最后，在考慮一下在變異算子作用下模式h 樣本數(shù)的變化。假設(shè)某 一位發(fā)生變異概率為已，那么這一位不變異的概率為1 一p 卅，而要想模式 不變就要使其所有固定位置的值保持不變，因此模式日保持不變的概率 為 ( 1 一己) d ( 日) 當(dāng)只 1 時，模式打在變異算子作用下的生存概率為： 只“1 一d ( 日) - b( 2 4 ) 綜上所述，模式h 在遺傳算子選擇、交叉和變異的共同作用下，其 下一代的樣本數(shù)為 m ( h ，t + 1 ) m ( h ，r ) ( ( 日) ，) 1 一只f i ( h ) ( l 一1 ) 一0 ( 日) 己 ( 2 - 5 ) 從而可以看出，在三種遺傳算子共同作用下，具有低階、短定義距及 平均適應(yīng)度高于群體平均適應(yīng)度的模式在子代中得以指數(shù)級增長，這就是 模式定理的內(nèi)容口7 1 。 符合模式定理的那些具有低階、短定義距以及高適應(yīng)度的模式我們稱 之為積木塊。 假設(shè)2 1 ：積木塊假設(shè) 2 7 】，低階、短距、高平均適應(yīng)度的模式( 積木 塊) 在遺傳算子作用下，相互結(jié)合，能生成高階、長距、高適應(yīng)度的模式， 可最終生成全局最優(yōu)解。 模式定理保證了較優(yōu)的模式的樣本的數(shù)目成指數(shù)級增長，從而滿足了 尋找最優(yōu)解的必要條件，即遺傳算法存在著找到全局最優(yōu)解的可能性。而 積木塊假設(shè)則指出，遺傳算法具備尋找到全局最優(yōu)解的能力，即積木塊在 遺傳算子作用下，能生成高階、長距、高平均適應(yīng)度的模式，最終生成全 局最優(yōu)解。 1 4 第2 章理論知識簡介 2 1 3 遺傳算法的特點 遺傳算法利用生物進化和遺傳的思想實現(xiàn)優(yōu)化過程，區(qū)別于傳統(tǒng)優(yōu)化 算法，它具有以下特點 2 7 , 2 8 , 2 9 】： ( 1 ) 傳統(tǒng)優(yōu)化算法通常是直接處理函數(shù)和它們的控制變量，而遺傳算 法通過編碼將優(yōu)化問題的參數(shù)編碼成有限長度的數(shù)字串即“染色體”后， 再進行操作，而不是針對參數(shù)本身，這使得g a 不受函數(shù)約束條件( 如連 續(xù)性、可導(dǎo)性、單調(diào)性等) 的限制，能在極其廣泛的問題求解過程中發(fā)揮 作用。 犯) 傳統(tǒng)搜索法基本上是點到點的搜索方法，在多極點的搜索空間里 常陷入局部極小點，而g a 的搜索過程是從問題解的一個集合開始的，而 不是從單個個體開始，具有隱含并行搜索特性，從而大大減小了陷入局部 極小的可能。 f 3 1 在遺傳算法的交叉操作過程中，這種點間的信息交換可明顯加速 遺傳算法的進化過程。h o l l a n d 證明了在一個規(guī)模為n 的種群中，o ) 模 式是有效的，即每一代遺傳算法在處理行個串的模式同時，實際上有效的 處理大約”個模式。這是非常重要的性質(zhì)，h o l l 跚d 稱之為隱并行性。 ( 4 ) 遺傳算法在選擇過程中，依據(jù)一定概率隨機的選擇個體，模仿了 自然界進化過程中的“適者生存，優(yōu)勝劣汰”的競爭規(guī)則，它雖然以隨機 化的方法來進行搜索，但實際上是朝著有可能改進解的質(zhì)量的搜索方向進 行搜索，即為一種有導(dǎo)向的隨機化搜索方法。 大多數(shù)傳統(tǒng)搜索方法都需要使用較多的附加特性，而遺傳算法僅用適 應(yīng)度函數(shù)來評估個體的好壞，并在此基礎(chǔ)上進行各種遺傳操作，且適應(yīng)度 函數(shù)不受連續(xù)、可微、單調(diào)等性質(zhì)的約束，其定義域可以任意設(shè)定，因此， 與傳統(tǒng)搜索算法相比，遺傳算法具有更強的魯棒性，能適用于更廣泛的應(yīng) 用領(lǐng)域。遺傳算法的優(yōu)越性主要表現(xiàn)在： ( 1 ) 算法進行全空問并行搜索，并且將搜索重點集中于性能高的部分， 從而能夠提高效率且不易陷入局部極??； ( 2 ) 算法具有固有的并行性，通過對種群的遺傳進化可處理大量的模 式，并且容易并行實現(xiàn)。 燕山大學(xué)工學(xué)碩士學(xué)位論文 2 1 4 遺傳算法的基本流程 遺傳算法是一類隨機優(yōu)化算法，通過對染色體的評價和對染色體中基 因的作用，有效的利用已有信息來指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。 標(biāo)準(zhǔn)遺傳算法的主要步驟可描述如下： ( 1 ) 隨機地產(chǎn)生一組初始個體構(gòu)成初始種群，每個個體必須以某種編 碼形式表示，每個初始個體表示問題的初始解，并評價每一個體的適應(yīng)值； ( 2 ) 判斷算法收斂準(zhǔn)則是否滿足，若滿足則輸出搜索結(jié)果；否則執(zhí)行 以下步驟； ( 3 ) 根據(jù)適應(yīng)度值大小進行遺傳操作； ( 4 ) 返回步驟( 2 ) 。 標(biāo)準(zhǔn)遺傳算法的流程圖如圖2 1 所示。 圖2 - 1標(biāo)準(zhǔn)遺傳算法的流程圖 f i g 2 - 1t h e f l o wc h a r to f s t a n d a r dg e n e t i ca l g o r i t h m 2 1 5 逮傳算法的基礎(chǔ)理論 遺傳算法早期的基礎(chǔ)理論主要是h o l l a n d 的s c h e m a 定理及隱含并行 1 6 第2 章理論知識簡介 性原理，后來又有了建筑塊假設(shè)( b u i l d i n gb l o c k h y o t h e s i s ) 。但是，s c h e m a 定理卻無法解釋遺傳算法實際操作中的許多現(xiàn)象，隱合并行性的論證存在 嚴(yán)重的漏洞，而建筑塊假設(shè)卻從未得到過哪怕是啟發(fā)式的證明。目前，關(guān) 于遺傳算法基礎(chǔ)理論的研究在三個方面進行著，它們是：s c h e m a 理論的 拓廣與深入；遺傳算法的馬氏鏈分析；遺傳算法的收斂理論f 5 “。 以下對三個方面作簡要的介紹： f 1 ) s c h e m a 理論的拓廣和深入。這一方面的工作主要包括s c h e m a 公 式