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

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