（計(jì)算數(shù)學(xué)專業(yè)論文）遺傳算法的一些改進(jìn)及其應(yīng)用.pdf

摘要 摘要 科學(xué)理論研究與實(shí)踐中，往往存在著這樣一類問(wèn)題，就是需要在眾多的方案 中確定最優(yōu)方案的標(biāo)準(zhǔn)，并且給出尋找最優(yōu)方案的方法，此類問(wèn)題就稱為優(yōu)化問(wèn) 題。目前對(duì)于一些簡(jiǎn)單的情況，科學(xué)工作者已經(jīng)研究出了比較成熟的算法和方法。 但是，對(duì)于一些復(fù)雜的系統(tǒng)，他們往往感到力不從心，努力尋求更加有效的方法。 2 0 世紀(jì)4 0 年代以來(lái)，學(xué)者注意到生物在自然演化過(guò)程中表現(xiàn)出強(qiáng)大的適應(yīng) 能力，生物不斷復(fù)制優(yōu)勢(shì)遺傳基因，改善群體的適應(yīng)性，得到具有很強(qiáng)適應(yīng)性的 優(yōu)良物種。遺傳算法正是建立在自然演化系統(tǒng)理論研究基礎(chǔ)之上的一類優(yōu)化方 法。作為一類有效的全局優(yōu)化搜索算法，遺傳算法具有以下特點(diǎn)：( 1 ) 使用群體 搜索技術(shù)，具有隱含并行性，提高了算法的運(yùn)行效率；( 2 ) 使用基于目標(biāo)函數(shù)值 的評(píng)價(jià)信息，不需要目標(biāo)函數(shù)的代數(shù)表達(dá)式；( 3 ) 具有很強(qiáng)的穩(wěn)定性，提高了結(jié) 果的可信度；( 4 ) 簡(jiǎn)單通用，便于與其他方法結(jié)合成混合算法。 但是，遺傳算法的局部搜索能力不強(qiáng)。即便依靠強(qiáng)的全局收斂性可以很快地 達(dá)到最優(yōu)解附近，搜索到最優(yōu)解也要花很長(zhǎng)時(shí)間。造成上述現(xiàn)象的主要原因在于 子代不斷繼承父代的基因，降低了群體的多樣性程度，使得算法易于陷入局部收 斂。為充分利用遺傳算法的優(yōu)勢(shì)、避開(kāi)其缺陷、加快收斂速度，除了設(shè)計(jì)科學(xué)合 理的基本操作算子、選取適合的參數(shù)之外，一個(gè)有效的方法就是采用混合策略。 也就是在遺傳進(jìn)化的過(guò)程中引入快速收斂的局部尋優(yōu)算法，構(gòu)成混合遺傳算法。 國(guó)外研究人員在提高遺傳算法的局部搜索能力、加快尋優(yōu)速度方面取得了顯 著的成果( a l l e ng a r d n e rb ，m i c h a e lss ，2 0 0 3 ) ，( k u r t ah ，j o h ne d d y ，k e m p e r el ，2 0 0 2 ) ，( g h a s e m imr ，h i n t o ne ，w o o drd ，1 9 9 9 ) 。國(guó)內(nèi)研究人員對(duì)遺 傳算法與可變?nèi)莶罘ā⒛M退火法等的混合算法進(jìn)行了研究，也在許多不同領(lǐng)域 的應(yīng)用獲得了重要的成果。m j b o x 于1 9 6 5 年提出了復(fù)合形方法( 劉戰(zhàn)合， 2 0 0 4 ) ，通過(guò)對(duì)設(shè)計(jì)個(gè)體進(jìn)行反射、擴(kuò)張、壓縮等基本操作實(shí)現(xiàn)全局尋優(yōu)，具有 較強(qiáng)的局部尋優(yōu)能力，易于收斂。本文將研究遺傳算法與復(fù)合形法的結(jié)合，并通 過(guò)實(shí)例結(jié)果分析該混合算法的性能。 本文共六章，第一章介紹遺傳算法的特征、發(fā)展與應(yīng)用，并說(shuō)明本文的選題 依據(jù)，研究?jī)?nèi)容和基本方法。第二章介紹遺傳算法的基礎(chǔ)知識(shí)。第三章探討遺傳 算法的實(shí)現(xiàn)技術(shù)，介紹相關(guān)的基本遺傳操作算子。第四章給出遺傳算法的一些改 進(jìn)策略，包括對(duì)基本操作算子設(shè)計(jì)與算法參數(shù)選取的改進(jìn)，以及對(duì)遺傳算法早熟 收斂現(xiàn)象的改進(jìn)方案。改進(jìn)方案從兩個(gè)角度來(lái)研究遺傳算法與復(fù)合形方法的結(jié) 摘要 合，分別稱為改進(jìn)遺傳算法i 與改進(jìn)遺傳算法2 。第五章將第四章的改進(jìn)策略應(yīng) 用于配電網(wǎng)設(shè)備檢修計(jì)劃優(yōu)化模型的求解。結(jié)果顯示，與基本遺傳算法相比，改 進(jìn)算法在性能上有較大的優(yōu)越性，能夠在很大程度上降低成本，具有很好的經(jīng)濟(jì) 應(yīng)用價(jià)值。第六章給出了本文的總結(jié)以及可以進(jìn)一步研究的方向。 關(guān)鍵詞：遺傳算法復(fù)合形法改進(jìn)遺傳算法配電網(wǎng)設(shè)備檢修計(jì)劃 a b s t r a c t a bs t r a c t d u r i n gt h er e s e a r c ha n dp r a c t i c eo ft h es c i e n t i f i ct h e o r y , t h e r eo f t e ne x i s t ss u c h k i n do fp r o b l e mt h a tt od e t e r m i n et h ec r k e r i o no fa l lo p t i m a ls c h e m e ，a n dt h ew a yo f s e e k i n gt h eo p t i m a ls c h e m e t h i sk i n do fp r o b l e mi sc a l l e da no p t i m i z a t i o np r o b l e m s c i e n t i f i cr e s e a r c h e r sh a v es t u d i e do u tr a t h e rm a t u r ea l g o r i t h m sa n dm e t h o d sf o r s o m es i m p l ec i r c u m s t a n c e h o w e v e r , f o rt h ec o m p l i c a t e ds y s t e m ，t h e yu s u a l l yf e e l i n c o m p e t e n ta n dt r yt of i n dm o r ee f f e c t i v em e t h o d s s i n c e19 4 0 s ，r e s e a r c h e r sh a v en o t i c e dt h ep o w e r f u la d a p t a t i o na b i l i t yo ft h e l i v i n gb e i n g sd u r i n gt h ee v o l u t i o no ft h en a t u r e s u p e r i o rg e n e sa r ec o n s i s t e n t l y d u p l i c a t e d ，t h ea d a p t a t i o n so fc o m m u n i t y a r ei m p r o v e d ，a n dt h ee x c e l l e n ts p e c i e sw i t h p o w e r f u la d a p t a t i o ne m e r g e s t h eg e n e t i ca l g o r i t h mi ss u c ho p t i m a la l g o r i t h mt h a ti s b a s e do nt h er e s e a r c ho fn a t u r ea d a p t a t i o nt h e o r y a sag l o b a lo p t i m i z a t i o na l g o r i t h m ， t h eg e n e t i ca l g o r i t h mh a st h ef o l l o w i n gp r o p e r t i e s ：( 1 ) b yt h eg r o u ps e a r c ht e c h n i q u e a n di m p l i c i tp a r a l l e l i n gp r o p e r t y , t h ee f f i c i e n c yo ft h ea l g o r i t h mi sa c c e l e r a t e d ；( 2 ) i t r e l i e so n l yo nt h ev a l u e si n s t e a do ft h ea l g e b r a i ce x p r e s s i o no ft h eo b j e c t i v ef u n c t i o n ； ( 3 ) t h er e l i a b i l i t yo ft h es ol u t i o ni si m p r o v e db e c a u s eo ft h er o b u s t n e s so ft h e a l g o r i t h m ( 4 ) i ti ss i m p l ea n dg e n e r a ka n de a s yt ob ec o m b i n e dw i t ho t h e ra l g o r i t h m s t of o r mh y b r i da l g o r i t h m s b u tt h eg e n e t i ca l g o r i t h mi sn o te f f i c i e n ta tl o c a ls e a r c h a r h o u g hi tc a nr e a c h t h en e a r b yo ft h eo p t i m a ls ol u t i o nq u i c k l yb yt h ep o w e r f u lg l o b a lc o n v e r g e n c e p r o p e r t y , i tt a k e sv e r yl o n gt i m et of m dt h eo p t i m a ls ol u t i o n t h em a i nr e a s o no f t h e a b o v ep h e n o m e n ai st h a tt h eo f f s p r i n gc o n s t a n t l yi n h e r i t st h eg e n e so ft h ep a r e n t ， w h i c hr e d u c e dt h ed i v e r s i t yo f t h ec o m m u n i t y , s ot h a tt h ea l g o r i t h mi st r a pi n t oal o c a l c o n v e r g e n c e i no r d e rt om a k ef u l lu s eo ft h ea d v a n t a g eo ft h ea l g o r i t h m ，t oa v o i di t s w e a k n e s s ，a n dt os p e e du pt h ec o n v e r g e n c e ，o n ee f f e c t i v em e t h o di st oa d o p tt h e h y b r i ds t r a t e g yb e s i d e sw e l ld e s i g n e db a s i cg e n e t i co p e r a t o r sa n dp r o p e r l yc h o s e n p a r a m e t e r so ft h ea l g o r i t h m t h a ti s ，t ob r i n gf a s tc o n v e r g e n tl o c a lo p t i m i z a t i o n a l g o r “h mi n t ot h eg e n e t i ca l g o r i t h md u r i n gt i 汗g e n e t i ce v o l u t i o np r o c e s s 。j n dt of o r m ah y b r i dg e n e t i ca l g o r i t h m f o r e i g nr e s e a r c h e r sh a v eg a i n e dp r o m i n e n tr e s u l t si ne n h a n c i n gt h el o c a ls e a r c h m a b s l r a c t a b i l i t ya n ds p e e d i n gt h eo p t i m i z a t i o np r o c e s so fg e n e t i ca l g o r i t h m ( a l l e ng a r d n e rb e t a l ，2 0 0 3 ) ，( k u r t ahe t a l , 2 0 0 2 ) ，( g h a s e m im re t a l ，19 9 9 ) d o m e s t i cr e s e a r c h e r s a l s oh a v e g a i n e dm a n yi m p o r ta c h i e v e m e n t si n v a r i o u sf i e l d sb ys t u d y i n gt h e c o m b i n a t i o no ft h eg e n e t i ca l g o r i t h mw i t ht h ef l e x i b l et o l e r a n c em e t h o do rt h e s i m u l a t e da n n e a l i n gm e t h o d t h ec o m p l e xm e t h o d ( z h a nh el i u ，2 0 0 4 ) w a sf i r s t l y p r o p o s e db yj b o xi n 19 6 5 ，i to p t i m i z e st h eo p t i m i z a t i o ni n d i v i d u a l sb yt h er e f l e c t i o n ， e x p a n s i o n ，a n dc o m p r e s s i o no p e r a t o r i tp o s s e sp o w e r f u ll o c a lo p t i m i z a t i o nc a p a c i t y , i s e a s yt oc o n v e r g e t h i sp a p e rw i l ls t u d yt h ec o m b i n a t i o no ft h eg e n e t i ca l g o r i t h m a n dt h ec o m p l e xm e t h o d ，a n da n a l y z et h ep e r f o r m a n c eo ft h eh y b r i da l g o r i t h m t h r o u g ht h ec a s er e s u l t s t h ep a p e rc o n t a i n ss i xc h a p t e r s t h ef i r s tc h a p t e ri n t r o d u c e st h ec h a r a c t e r , e v ol u t i o n ，a n da p p l i c a t i o no ft h eg e n e t i ca l g o r i t h m ，a n di l l u s t r a t e st h ep a p e r ss e l e c t e d t o p i cb a s e ，r e s e a r c hc o n t e n t sa n db a s i ca p p r o a c h t h es e c o n dc h a p t e rp r e s e n t st h e b a s i ck n o w l e d g eo ft h eg e n e t i ca l g o r i t h m t h et h i r d c h a p t e rp r o b e s i n t ot h e i m p l e m e n t a t i o nt e c h n i q u eo ft h eg e n e t i ca l g o r i t h m ，i n t r o d u c e sr e l a t e db a s i cg e n e t i c o p e r a t o r s t h ef o u r t hc h a p t e rp r o v i d e ss o m ei m p r o v e ds t r a t e g i e so ft h eg e n e t i c a l g o r i t h m i tn o to n l yi m p r o v e st h ed e s i g no ft h eb a s i co p e r a t o ra n dt h es e l e c t i o no f t h ea l g o r i t h m i cp a r a m e t e r s ，b u ta l s o g i v e st h ei m p r o v e ds c h e m et o s o l v et h e p r e m a t u r ec o n v e r g e n c ep h e n o m e n o no ft h eg e n e t i ca l g o r i t h m t h ei m p r o v e ds c h e m e s t u d i e st h eh y b r i do ft h eg e n e t i ca l g o r i t h mw i t ht h ec o m p l e xm e t h o df r o mt w op o i n t s o ft h ev i e w , a n di sn a m e dt h ei m p r o v e da l g o r i t h m1a n dt h ei m p r o v e da l g o r i t h m2 t h ef i r hc h a p t e ra p p l i e st h ei m p r o v e ds t r a t e g i e so ft h el a s tc h a p t e rt ot h ed i s t r i b u t i o n d e v i c e sm a i n t e n a n c es c h e d u l i n go p t i m a lm o d e l t h r o u g ht h ep e r f o r m a n c eo ft h e o p t i m a lr e s u l t s ，t h es u p e r i o r i t yo ft h ei m p r o v e dg e n e t i ca l g o r i t h mt o t h eg e n e t i c a l g o r i t h mi sv e r i f i e d t h eo p t i m a lr e s u l t sc a nr e d u c et h el o s st ot h el a r g ee x t e n t ，a n d h a sp o w e r f u le c o n o m i ca p p l i e dv a l u e t h es i x t hc h a p t e rg i v e st h es u m m a r yo ft h e p a p e ra n dt h ef u r t h e rr e s e a r c ho nt h es u b j e c t k e yw o r d s ：g e n e t i ca l g o r i t h m ，c o m p l e xm e t h o d ，i m p r o v e dg e n e t i ca l g o r i t h m ， d i s t r i b u t i o nn e t w o r kd e v i c em a i n t e n a n c es c h e d u l e w 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性聲明 本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的成 果。除已特別加以標(biāo)注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫 過(guò)的研究成果。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn)均已在論文中作了明確 的說(shuō)明。 作者簽名：塑鰣 簽字日期 如z 臼) 5 - 刁 中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文授權(quán)使用聲明 作為申請(qǐng)學(xué)位的條件之一，學(xué)位論文著作權(quán)擁有者授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁 有學(xué)位論文的部分使用權(quán)，即：學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或機(jī)構(gòu)送交 論文的復(fù)印件和電子版，允許論文被查閱和借閱，可以將學(xué)位論文編入中國(guó)學(xué) 位論文全文數(shù)據(jù)庫(kù)等有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制 手段保存、匯編學(xué)位論文。本人提交的電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。 保密的學(xué)位論文在解密后也遵守此規(guī)定。 鹵鑫開(kāi)口保密( 年) 作者簽名：捏之士虹 導(dǎo)師簽名： 簽字日期： 知f q 主12 3 簽字日期： 第一章緒論 第1 章緒論 本章將闡述遺傳算法的特征、發(fā)展與應(yīng)用，據(jù)此提出本文的選題依據(jù)，研究 目的，研究?jī)?nèi)容和方法。 1 1遺傳算法的特征、發(fā)展與應(yīng)用 遺傳算法作為一種應(yīng)用比較廣泛、影響比較大的優(yōu)化算法，與其他優(yōu)化算法 相比，它主要具有下述若干獨(dú)特的性能。 ( 1 ) 遺傳算法以參數(shù)的編碼集作為運(yùn)算對(duì)象，并且在執(zhí)行搜索過(guò)程中，不受優(yōu) 化函數(shù)連續(xù)性及其導(dǎo)數(shù)求解的限制，因而具有很強(qiáng)的通用性。 ( 2 ) 遺傳算法直接使用由目標(biāo)函數(shù)確定的適應(yīng)度函數(shù)信息，以群體為單位執(zhí)行 搜索過(guò)程，加快搜索到適應(yīng)度較好的搜索空間，因而具有較強(qiáng)的全局搜索能 力。 ( 3 ) 遺傳算法簡(jiǎn)單通用，普適性強(qiáng)，易于與其他算法結(jié)合構(gòu)成混合智能算法， 并且該算法具有很強(qiáng)的魯棒性，因而在眾多領(lǐng)域得到了廣泛的應(yīng)用。 鑒于以上特征，遺傳算法受到了越來(lái)越廣泛的重視。其具體發(fā)展過(guò)程如下所 述： ( 1 ) 1 9 6 2 年，j o h nh o l l a n d 提出了利用群體進(jìn)化模擬適應(yīng)性系統(tǒng)的思想( h o l l a n d ， j h 。1 9 6 2 ) ，引進(jìn)了群體、適應(yīng)值、選擇、變異、交叉等基本概念。 ( 2 ) 1 9 6 7 年，h o l l a n d 的學(xué)生j d b a g l e y 在其博士論文中首次提出“遺傳算法” 一詞( b a g l e y , j d ，1 9 6 7 ) 。 ( 3 ) 1 9 7 5 年，h o l l a n d 出版了專著自然與人工系統(tǒng)中的適應(yīng)性行為( a d a p t a t i o n i nn a t u r a la n da r t i f i c i a ls y s t e m s ) ( h o l l a n d ，j h ，19 9 2 ) 提出了對(duì)遺傳算法的 理論發(fā)展極為重要的模式理論。同年，d ej o n g 在其博士論文研究中首次把 遺傳算法用于函數(shù)優(yōu)化問(wèn)題( d ej o n g ，k a ，1 9 7 5 ) ，并給出了適用于大多數(shù) 優(yōu)化問(wèn)題的遺傳算法的參數(shù)，建立了著名的d ej o n g 五函數(shù)測(cè)試平臺(tái)。 ( 4 ) 8 0 年代，h o l l a n d 教授開(kāi)g , j t 基于遺傳算法的機(jī)器學(xué)習(xí)的新概念，為分類 器系統(tǒng)構(gòu)造出了一個(gè)完整的框架( h o l i a ：, djh ，r e i t m a n ! s ，1 9 7 0 ) ( 5 ) 1 9 8 9 年，d a v i dg o l d b e r g 出版了專著搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算 法( g e n e t i ca l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) 第一章緒論 ( g o l d b e r gd e ，19 8 9 ) 這是第一本遺傳算法教科書，總結(jié)了當(dāng)時(shí)關(guān)于遺傳算 法領(lǐng)域的研究工作，為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。 ( 6 ) 1 9 9 2 年，k o z a 將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提 出了遺傳編程的概念( k o z ajr 1 9 9 4 ) ，( k o z ajr ，1 9 9 2 ) ，并且為基于符號(hào) 表示的函數(shù)學(xué)習(xí)問(wèn)題提供了一個(gè)有力的工具。 當(dāng)前因特網(wǎng)的出現(xiàn)，加速了遺傳算法的推廣。g e c c o ( g e n e t i ca n d e v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ) 國(guó)際會(huì)議，p p s n ( p a r a l l e lp r o b l e ms o l v i n g f r o mn a t u r e ) 會(huì)議，f o g a ( f o u n d a t i o no fg e n e t i ca l g o r i t h m ) 會(huì)議，c e c ( c o n g r e s so n e v o l u t i o n a r yc o m p u t a t i o n ) l 垂l 際會(huì)議，以及e v o l u t i o n a r yc o m p u t a t i o n 和a d a p t i v e b e h a v i o r 雜志等，更進(jìn)一步加速了遺傳算法理論的研究，拓展了遺傳算法的應(yīng)用 領(lǐng)域，使得其成為一個(gè)多學(xué)科、多領(lǐng)域的重要研究方向。 遺傳算法具有很強(qiáng)的全局搜索能力，通用性強(qiáng)，魯棒性高，因而被廣泛應(yīng)用 于很多領(lǐng)域，下面簡(jiǎn)要介紹一些主要的應(yīng)用領(lǐng)域： ( 1 ) 函數(shù)優(yōu)化。函數(shù)優(yōu)化不僅是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，而且各類復(fù)雜的測(cè) 試函數(shù)也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的依據(jù)。另外，對(duì)于一些使用其他優(yōu)化 方法很難求解的非線性、多目標(biāo)函數(shù)優(yōu)化問(wèn)題，應(yīng)用遺傳算法一般可以得到 滿意的優(yōu)化結(jié)果。 ( 2 ) 調(diào)度問(wèn)題。遺傳算法在生產(chǎn)調(diào)度中得到了廣泛的應(yīng)用，不僅避免了只依據(jù) 靠經(jīng)驗(yàn)調(diào)度的不可靠性，而且避免了在傳統(tǒng)求解過(guò)程中由于對(duì)模型的大幅度 簡(jiǎn)化，而導(dǎo)致求得結(jié)果與實(shí)際結(jié)果之間的巨大差異。 ( 3 ) 圖像處理。遺傳算法在模式識(shí)別、圖像恢復(fù)、圖像邊緣特征提取等方面得 到了廣泛的應(yīng)用。 ( 4 ) 自動(dòng)控制領(lǐng)域。遺傳算法在參數(shù)辨識(shí)、模糊控制器的優(yōu)化設(shè)計(jì)、模糊控制 規(guī)則的學(xué)習(xí)中的應(yīng)用取得了很顯著的成果。另外，遺傳算法在航空控制系統(tǒng) 的優(yōu)化、空間交會(huì)控制器的設(shè)計(jì)、故障診斷( z h o n gb i n g l i nc ta l , 1 9 9 2 ) ， ( z h a n g ，j ，a n dr o b e r t , p d 19 9 2 ) 和機(jī)器人行走路徑規(guī)劃( g i l l ，m a c ，a n d z o m a y a ，a y ，1 9 9 8 ) ，( d o r i g o ，m ，a n ds c h n e p h ，u ，e ta 1 ，1 9 9 3 ) ，( d a v i d o r , y ， 1 9 9 1 ) d 尸的應(yīng)用也取得了成功。 ( 5 ) 機(jī)器學(xué)習(xí)?；谶z傳算法的機(jī)器學(xué)習(xí)，在很多領(lǐng)域中都得到了廣泛的應(yīng)用。 其中比較典型的是h o l l a n d 設(shè)計(jì)的分類器系統(tǒng)( g o l d b e r g ，d e ，1 9 8 9 ) ，以及 機(jī)器人規(guī)劃、模式識(shí)別、概念學(xué)習(xí)等m c a u l a y , a d ，a n do h ，j c 1 9 9 4 ) ， ( d o r i g o ，me ta l , 19 9 3 ) ，( ( k a d a b a ，n ，n y g a r d ，k e ，a n dj u e l l ，p j ，19 91 ) ( l i e p i n s ，qe ，a n dw a n g ，l a ，1 9 9 1 ) 。 ( 6 ) 社會(huì)與經(jīng)濟(jì)領(lǐng)域?；谶z傳算法的思想，軟件開(kāi)發(fā)人員設(shè)計(jì)了很多的軟件 第一章緒論 包，服務(wù)于各類社會(huì)和經(jīng)濟(jì)行業(yè)，比如金融系統(tǒng)和股票投資分析行業(yè)。 ( 7 ) 人工智能與科學(xué)計(jì)算。因?yàn)楹芏嗲蠼鈫?wèn)題的復(fù)雜性，往往得不到問(wèn)題的解 析解，人們嘗試運(yùn)用各種算法求出最優(yōu)解的近似解來(lái)逼近最優(yōu)解。遺傳算法 是這類算法中一種典型的方法，被廣泛應(yīng)用在很多問(wèn)題求解中。例如本文給 出了遺傳算法在配電網(wǎng)設(shè)備檢修優(yōu)化模型中的應(yīng)用實(shí)例，如果將優(yōu)化結(jié)果應(yīng) 用在配電網(wǎng)設(shè)備檢修計(jì)劃中，能從很大程度上降低因檢修而帶來(lái)的損耗，具 有很好的經(jīng)濟(jì)應(yīng)用價(jià)值。 至此，我們可以看出遺傳算法具有很高的應(yīng)用價(jià)值。但是，遺傳算法并不是 一種完美的算法，其存在著不足之處，導(dǎo)致有時(shí)優(yōu)化結(jié)果并不理想。因而，為了 充分利用遺傳算法的優(yōu)勢(shì)，克服其缺陷，還需要開(kāi)展進(jìn)一步相關(guān)的研究工作。 1 2 本文的選題依據(jù)，研究?jī)?nèi)容和基本方法 ( 1 ) 選題依據(jù) 由前面所述，遺傳算法具有顯著的性能優(yōu)勢(shì)，被廣泛地應(yīng)用于各種領(lǐng)域。但 遺傳算法自身存在一些不足，如搜索時(shí)間過(guò)長(zhǎng)、易發(fā)生早熟收斂、局部尋優(yōu)能力 差等。而今，隨著“改革開(kāi)放”的深入，各種理論、思想的交流不斷得到加強(qiáng)， 產(chǎn)生了越來(lái)越多的新發(fā)明、新創(chuàng)造。因而，為了克服遺傳算法自身的不足，嘗試 在遺傳算法基本操作的設(shè)計(jì)過(guò)程中，融入能克服遺傳算法缺陷的新方法、新思想。 于是，我們希望能夠找到一個(gè)有效的具有快速收斂能力的局部尋優(yōu)算法，將其引 入到遺傳進(jìn)化的過(guò)程中，最終獲得一類新的混合智能算法，其不僅保持了遺傳算 法全局搜索能力強(qiáng)的特點(diǎn)，而且其局部尋優(yōu)能力得到了極大的改善和提高。而復(fù) 合形方法具有這方面的特征，因而本文重點(diǎn)在研究遺傳算法與復(fù)合形法融合的角 度。 ( 2 ) 研究?jī)?nèi)容和基本方法 本文重點(diǎn)研究遺傳算法的改進(jìn)策略，使得其在保留強(qiáng)的全局收斂能力的同 時(shí)，能極大地改善其容易限于局部收斂的缺陷。為了讀者能更好的理解本文的研 究?jī)?nèi)容，本文采用如下方式展開(kāi)。 第二章中簡(jiǎn)要的介紹了遺傳算法的相關(guān)理論，包括該算法描述的一般模型、 基本操作算子的確定、參數(shù)的選取、收斂性的充要條件等。 第三章中詳細(xì)的介紹了遺傳算法實(shí)現(xiàn)的相關(guān)操作，包括編碼方法、群體規(guī)模、 初始群體、適應(yīng)值、復(fù)制算子、交叉算子、變異算子、收斂準(zhǔn)則等。在描述相關(guān) 操作時(shí)，不僅介紹了操作實(shí)現(xiàn)的具體步驟，而且給出了操作中需要注意和改進(jìn)的 地方。 第四章中具體的給出了遺傳算法實(shí)現(xiàn)中相關(guān)操作的一些改進(jìn)策略，包括改進(jìn) 第一章緒論 初始群體構(gòu)造方法、改進(jìn)罰函數(shù)方法、改進(jìn)復(fù)制算子、改進(jìn)交叉算子、改進(jìn)變異 算子、改進(jìn)收斂準(zhǔn)則，并且針對(duì)遺傳算法容易早熟的現(xiàn)象，本文也探索了針對(duì)該 問(wèn)題的改進(jìn)方法。在遺傳算法基礎(chǔ)上，引入一個(gè)易收斂、局部尋優(yōu)能力強(qiáng)的復(fù)合 形法。我們從兩個(gè)角度來(lái)融合遺傳算法與復(fù)合形法，稱為改進(jìn)遺傳算法1 與改進(jìn) 遺傳算法2 。為便于讀者有個(gè)形象的理解，本文給出了改進(jìn)遺傳算法1 和改進(jìn)遺 傳算法2 的流程圖。 改進(jìn)遺傳算法l 中，首先，由遺傳算法對(duì)搜索空間進(jìn)行一次優(yōu)化，搜尋到最 優(yōu)解的附近時(shí)停止，轉(zhuǎn)而通過(guò)復(fù)合形法對(duì)當(dāng)前尋優(yōu)結(jié)果進(jìn)行二次優(yōu)化，最終獲得 全局最優(yōu)解。改進(jìn)遺傳算法2 中，遺傳算法在每次進(jìn)化過(guò)程中，通過(guò)復(fù)合形法不 斷排序、繼承、更新的操作過(guò)程，不斷改善種群，把整個(gè)種群向最優(yōu)解的方向收 縮，同時(shí)也維持了種群的多樣性。在該改進(jìn)遺傳算法2 中，復(fù)合形法實(shí)質(zhì)上成為 了遺傳算法的一個(gè)算子。 第五章中主要是檢驗(yàn)兩種改進(jìn)遺傳算法的實(shí)用性與有效性。本文將改進(jìn)遺傳 算法與遺傳算法分別應(yīng)用到配電網(wǎng)設(shè)備檢修計(jì)劃優(yōu)化模型中。通過(guò)算例結(jié)果分 析，改進(jìn)遺傳算法不僅尋優(yōu)速度快、效率高，而且其優(yōu)化結(jié)果在很大程度上降低 了因檢修而帶來(lái)的損耗，驗(yàn)證了改進(jìn)遺傳算法相比遺傳算法的優(yōu)越性。 4 第二章遺傳算法 第2 章遺傳算法 2 1 遺傳算法概述 遺傳算法主要借鑒了生物進(jìn)化的一些特征，模擬生物的自然選擇和遺傳機(jī)制 而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法。依據(jù)達(dá)爾文“適者生存”的理論， 在不斷變化的自然環(huán)境中，只有那些適應(yīng)性好的個(gè)體才能存活下來(lái)，并通過(guò)遺傳 機(jī)制將好的特性傳遞給其后代。與此同時(shí)，在遺傳過(guò)程或適應(yīng)環(huán)境過(guò)程中，個(gè)體 發(fā)生了變異，具有了適應(yīng)環(huán)境的能力。這樣，在進(jìn)化過(guò)程中，生物群體將逐漸地 產(chǎn)生優(yōu)良的群體，適應(yīng)生態(tài)環(huán)境的變化。其在形式上是一種迭代方法，從選定的 初始解出發(fā)，通過(guò)不斷迭代計(jì)算過(guò)程，逐步改善當(dāng)前解，直至最后搜到最優(yōu)解或 滿意解。 為便于讀者更好的理解算法，本文對(duì)文中將要出現(xiàn)的相關(guān)術(shù)語(yǔ)做了簡(jiǎn)要的說(shuō) 明。在后文實(shí)例分析中，本文又將相關(guān)一些術(shù)語(yǔ)放到實(shí)例中再次解釋，以便給讀 者留下形象的理解。目前，遺傳算法的相關(guān)術(shù)語(yǔ)還沒(méi)有得到統(tǒng)一，本文中采用的 術(shù)語(yǔ)及其含義解釋如下： 個(gè)體：遺傳算法要優(yōu)化的基本對(duì)象，也就是說(shuō)個(gè)體中包含了各個(gè)參數(shù)屬性的 對(duì)象。 群體：個(gè)體的集合。 群體規(guī)模：群體中個(gè)體的個(gè)數(shù)。 染色體：個(gè)體的編碼。其用來(lái)表征個(gè)體，并且反映了個(gè)體的特征。 基因：組成染色體的元素，表示不同的特征。 基因長(zhǎng)度：組成染色體基因的個(gè)數(shù)。 等位基因：同一基因位的基因取值。 適應(yīng)值：反映個(gè)體對(duì)于環(huán)境的適應(yīng)能力。 復(fù)制：實(shí)質(zhì)上就是保留那些在選擇機(jī)制下存活的個(gè)體。 交叉：染色體相應(yīng)基因的交換。 變異：染色體上某個(gè)基因的變化。 進(jìn)化：復(fù)制、交叉、變異是遺傳算法的基本操作算子，這些算子執(zhí)行一次就 相當(dāng)于進(jìn)化一次，它們反映了物種的進(jìn)化、淘汰過(guò)程。 第二章遺傳算法 2 2 遺傳算法描述的一般模型 學(xué)者注意到，生物在其進(jìn)化過(guò)程中，顯示出強(qiáng)大的適應(yīng)環(huán)境的能力。于是， 很多基于生物該生存特性的新思想和方法被研制出來(lái)，并且取得了很多重要的成 果。遺傳算法正是基于模擬生物遺傳和進(jìn)化的一種自適應(yīng)算法。為研究需要，本 文參照h o l l a n d 關(guān)于復(fù)雜適應(yīng)系統(tǒng)的建模理論，給出遺傳算法描述的一般數(shù)學(xué)模 型。 遺傳算法本質(zhì)上采用“進(jìn)化論”思想，在問(wèn)題處理過(guò)程中，往往采用離散化 過(guò)程，假定其進(jìn)化次數(shù)為f = 1 ? ；假定長(zhǎng)度為 的染色體表示為符號(hào)串 x = 五j c 2 ，其中：記號(hào)薯o = l ，2 ，m ) 代表一個(gè)遺傳基因，它的所有可能取值稱 為等位基因；所有等位基因的組合構(gòu)成了解的基本空間： a = j c l 藝= 兀：l 薯 ( 2 1 ) 處于f 進(jìn)化次數(shù)的群體記為a ( t ) ；與此進(jìn)化次數(shù)對(duì)應(yīng)的環(huán)境記為b ( t ) ，并假定各 進(jìn)化次數(shù)對(duì)應(yīng)的環(huán)境召( r ) 是相互獨(dú)立的：群體對(duì)環(huán)境的適應(yīng)能力記為c ( t ) ；自 然選擇和遺傳機(jī)制d ，作用下生成新的解集群體彳( f + 1 ) ： a ( t + 1 ) = z ( 4 ( f ) ，c ( f ) ) ( 2 2 ) 依據(jù)達(dá)爾文的自然進(jìn)化理論，適應(yīng)環(huán)境的物種生存下來(lái)，而不適應(yīng)環(huán)境的物 種則被淘汰。由此看出，環(huán)境在生物群體的進(jìn)化過(guò)程中起著至關(guān)重要的作用，因 此，我們不能簡(jiǎn)單的考察群體對(duì)某一特定環(huán)境的適應(yīng)情況，而應(yīng)該將群體融入到 一個(gè)動(dòng)態(tài)的環(huán)境之中，來(lái)研究群體的進(jìn)化過(guò)程，因此上一模型中僅考慮到群體對(duì) 當(dāng)前進(jìn)化次數(shù)對(duì)應(yīng)的環(huán)境的適應(yīng)能力是不合理的。為此，我們引入一個(gè)新的變量 島( f ) = ，它反映了此進(jìn)化次數(shù)之前群體與環(huán)境的動(dòng)態(tài)適應(yīng) 歷史信息，更貼切的再現(xiàn)了群體的自然進(jìn)化過(guò)程。故上述模型修改為： a ( t + 1 ) = 4 ( 彳( f ) ，c ( r ) ，( f ) ) ( 2 3 ) 其中：e s ( f + 1 ) 的生成反映了在群體自然進(jìn)化過(guò)程中，自然選擇和遺傳機(jī)制的處 理方式： ( f + 1 ) = a , ( e b ( ，) ，c ( f ) ) ( 2 4 ) 新的解集群體的生成可以理解為一個(gè)隨機(jī)過(guò)程。對(duì)于有限的解集空間， x = 【薯，而，再，而】，刀= i 卅，當(dāng)么窖) 硝識(shí)) 刀 ，在自然選擇和遺傳機(jī)制 d ，作用下生成新的解集群體彳o + 1 ) = lq = 1 , 2 ，療) 的概率為 6 第二章遺傳算法 則上述改進(jìn)模型可以改寫為： p ( f ) = 仍。( f ) i a ，。o ) - - 1 ( 2 5 ) 礙= l 尸( f + 1 ) = d t ( a ( t ) ，c o ) ，島( ，) ) ( 2 6 ) 群體彳( f ) 對(duì)環(huán)境b ( f ) 的適應(yīng)性測(cè)度一般采用大于等于0 的實(shí)數(shù)表示，表示為： l x s ( a ( t ) ) = 盧口，( 4 ( f ) ，b ( f ) ) ( 2 7 ) 其中：盯表示處于f 進(jìn)化次數(shù)的群體4 u ) 對(duì)環(huán)境b ( f ) 的適應(yīng)性。一旦群體或環(huán) 境發(fā)生變化，那么群體適應(yīng)環(huán)境的能力也隨之發(fā)生變化，適應(yīng)性測(cè)度函數(shù)也會(huì)做 相應(yīng)的調(diào)整： 鰳，川= 4 ( ，i 耵，4 p ) ，c ( f ) ) ( 2 8 ) 在t 進(jìn)化次數(shù)，群體對(duì)環(huán)境的適應(yīng)能力c ( t 1 可以表示為： c ( f ) = 口，( 彳p ) )( 2 9 ) 當(dāng)環(huán)境和群體變化時(shí)，自然選擇和遺傳機(jī)制d ，也需要進(jìn)行適應(yīng)性調(diào)整，使得 群體具有更好的適應(yīng)性。自然選擇和遺傳機(jī)制的調(diào)整應(yīng)該考慮當(dāng)前機(jī)制作用的群 體，當(dāng)前群體對(duì)環(huán)境的適應(yīng)能力c ( t ) ，群體與環(huán)境的動(dòng)態(tài)適應(yīng)歷史信息e b ( f ) ， 歷史自然選擇和遺傳機(jī)制e d ( t ) - 等，表述如下： d ( t + 1 ) = g ( 彳( f ) ，c ( f ) ，e b ( f ) ，易( f ) ) ( 2 1 0 ) 群體適應(yīng)環(huán)境的整個(gè)進(jìn)化階段中，群體的適應(yīng)性測(cè)度為 r f ( r ) = ， ( 2 1 1 ) t = l 群體對(duì)環(huán)境的適應(yīng)過(guò)程與自然選擇和遺傳機(jī)制日( d 緊密相關(guān)。在自然選擇和遺 傳機(jī)制毛( d = 下，整個(gè)進(jìn)化階段，群體的適應(yīng)性測(cè)度為： r f ( t ，( 丁) ) = 心，( 4 ( f ) ) f ；i ( 2 1 2 ) 對(duì)于全局最小值優(yōu)化模型，假設(shè)進(jìn)化階段獲得最小累計(jì)支付的適應(yīng)計(jì)劃是最佳 的： ，( 丁) = m ! n f ( e 4 ( r ) ) ) ( 2 1 3 ) w 參考控制理論的相關(guān)信息，一個(gè)復(fù)雜系統(tǒng)的適應(yīng)計(jì)劃 第二章遺傳算法 f ( 吃( n ) = ( 2 1 4 ) 稱為滿意適應(yīng)計(jì)劃，如果滿足： 娶m 【f ( 毛( 功，( 乃】_ l ( 2 1 5 ) - - + a o 稱f ( e ( r ) ) 是一個(gè)滿意的適應(yīng)計(jì)劃，如果對(duì)于某一給定的環(huán)境變化 馬= 口0 ，口是一個(gè)很小的實(shí)數(shù)，則稱f ( 日( r ) ) 是一個(gè)滿意的適應(yīng)計(jì)劃。 綜合以上內(nèi)容，我們給出描述復(fù)雜系統(tǒng)適應(yīng)過(guò)程的數(shù)學(xué)模型如下： a ( t + 1 ) = 吐( 4 ( ，) ，c ( f ) ，e b ( r ) ) e 8 ( f + 1 ) = 4 ( o ) ，c ( f ) ) ，如( 彳o ) ) = ，( 彳( r ) ，占( f ) ) c ( ) 2 r ( ) ( 2 1 8 ) ”l = 4 ( 心，彳( ，) ，c ( f ) ) 。 d ( t + 1 ) = g ( 彳( f ) ，c ( o ，e b ( r ) ，歷( f ) ) 7 ，( 丁) = 心， 其中：o ) = ；髟o ) = ；彳o ) 表示r 進(jìn)化次數(shù)的群體；聊) 表示與此進(jìn)化次數(shù)對(duì)應(yīng)的環(huán)境：c ( f ) 表示群體對(duì)環(huán) 境的適應(yīng)能力；吐表示自然選擇和遺傳機(jī)制；耵表示處于f 進(jìn)化次數(shù)的群體么( f ) 對(duì)環(huán)境b ( f ) 的適應(yīng)性。 基于上述模型，我們懂得在進(jìn)行遺傳算法的研究中時(shí)，有關(guān)鍵的幾點(diǎn)必須明 確： ( 1 ) 要明確算法研究的對(duì)象，優(yōu)化的對(duì)象，以便確定算法中的個(gè)體、群體。 ( 2 ) 要明確群體的生存環(huán)境，也就是優(yōu)化變量需要滿足的約束條件。 ( 3 ) 要明確環(huán)境對(duì)群體的選擇機(jī)制，也就是優(yōu)化變量滿足哪些條件時(shí)才能被保 留下來(lái)。 ( 4 ) 要明確群體的適應(yīng)機(jī)制是什么，也就是優(yōu)化變量如何向優(yōu)化問(wèn)題最優(yōu)解的 方向靠近、進(jìn)化。 第二章遺傳算法 ( 5 ) 要明確算法的一些改進(jìn)策略，以便保證算法的收斂，提高算法的運(yùn)行效率 與精確度。 2 3 遺傳算法的基本操作算子和參數(shù)選取 群體多樣性的性質(zhì)的好壞關(guān)系著遺傳算法的搜索能力、收斂性質(zhì)。環(huán)境對(duì)群 體的選擇機(jī)制下，群體不斷向著更好適應(yīng)環(huán)境的方向進(jìn)化，導(dǎo)致群體的多樣性程 度降低，群體搜索的領(lǐng)域越來(lái)越小。如若沒(méi)有其他操作算子，那么在選擇機(jī)制下， 群體最終將趨向穩(wěn)定，并將一直保持穩(wěn)定，此時(shí)算法也就達(dá)到了收斂。但是該收 斂點(diǎn)未必是最優(yōu)解，甚至與最優(yōu)解相差很多，無(wú)法逼近最優(yōu)解。因而，從某種程 度上講，仿照生物自然進(jìn)化過(guò)程，遺傳算法加入交叉、變異基本操作，就是為了 改善群體的多樣性而設(shè)計(jì)的。第4 章中的一些改進(jìn)策略，也是在保證群體多樣性 性質(zhì)的基礎(chǔ)上，為了提高算法運(yùn)行效率，加速收斂而做的一些改進(jìn)。 文獻(xiàn)( 李敏強(qiáng)等，2 0 0 2 ) 1 6 6 中的相關(guān)結(jié)論為基本遺傳操作設(shè)計(jì)提供了理論 上的支持。該文獻(xiàn)中提及：如果遺傳算法設(shè)計(jì)中只包含環(huán)境對(duì)群體的選擇機(jī)制， 那么搜尋的結(jié)果停留在初始群體中適應(yīng)值最好的個(gè)體而不再改變。如果算法只包 含環(huán)境對(duì)群體的選擇機(jī)制，以及群體中個(gè)體間的交叉操作，那么當(dāng)群體多樣性測(cè) 度降到0 時(shí)，搜尋操作停止，算法只能收斂到最優(yōu)解的鄰近點(diǎn)。只有算法包含環(huán) 境對(duì)群體的選擇機(jī)制，個(gè)體間的交叉操作，以及個(gè)體的變異操作時(shí)，算法才能夠 收斂到最優(yōu)解。 遺傳算法基本操作確定后，我們就要考慮相應(yīng)參數(shù)的設(shè)計(jì)。參數(shù)設(shè)計(jì)的合理 與否關(guān)系到算法的執(zhí)行效率和優(yōu)化結(jié)果。文獻(xiàn)( 李敏強(qiáng)等，2 0 0 2 ) 1 6 3 2 1 5 同樣為 參數(shù)設(shè)計(jì)提供了選擇依據(jù)。相關(guān)結(jié)論為：算法運(yùn)行初始階段，選取較大的群體規(guī) 模、較松的選擇機(jī)制、較大的交叉率，以便加大算法搜索的空間。算法運(yùn)行中期 階段，選取較小的群體規(guī)模、較嚴(yán)的選擇機(jī)制、較大的變異概率，以便突破局部 最優(yōu)解的控制。算法運(yùn)行后期階段，選取較小的群體規(guī)模，較嚴(yán)格的選擇機(jī)制、 較小的交叉、變異概率，加快算法的收斂。 2 4 遺傳算法收斂性的相關(guān)理論 評(píng)價(jià)算法優(yōu)越性與否的關(guān)鍵指標(biāo)是其運(yùn)行效率和收斂性。高的運(yùn)行效率可通 過(guò)選用合理的操作算子和參數(shù)來(lái)保證，那么其收斂性如何來(lái)保證呢? 文獻(xiàn)( 邢文 訓(xùn)，謝金星，1 9 9 9 ) 1 6 4 中得到的與收斂性相關(guān)的結(jié)論如下： 定理如果遺傳算法按交配、變異、種群選取之后更新當(dāng)前最優(yōu)染色體的進(jìn) 化循環(huán)過(guò)程，則收斂于全局最優(yōu)。 9 第二章遺傳算法 由此可知，文獻(xiàn)( 邢文訓(xùn)，謝金星，1 9 9 9 ) 嘲給出了保證遺傳算法收斂的充分 條件，