濟(jì)南大學(xué)碩士學(xué)位論文 摘要 從人工智能跨越到計(jì)算智能是計(jì)算機(jī)科學(xué)發(fā)展史上的一次重大變革。以進(jìn)化算法 和神經(jīng)網(wǎng)絡(luò)為核心的計(jì)算智能理論得到了長足的發(fā)展。最近十幾年來，各種新的進(jìn)化 算法也紛紛被提出。這些算法都具有與問題無關(guān)、通用性好、收斂速度快、容易跳出 局部最優(yōu)等優(yōu)點(diǎn)，因此在許多領(lǐng)域都得到了廣泛的應(yīng)用。 進(jìn)化算法是一種具有高度計(jì)算復(fù)雜性的智能算法。當(dāng)求解問題較復(fù)雜時(shí)，其計(jì)算 所需的時(shí)間復(fù)雜度也比較高，同時(shí)，由于解集的龐大和局部最優(yōu)問題的存在，在其中 篩選出精確解所花費(fèi)的過程也比較復(fù)雜。因此我們希望有一種能夠有效降低進(jìn)化算法 時(shí)間復(fù)雜度的策略，以節(jié)約進(jìn)化算法的計(jì)算時(shí)間。 目前存在著大量的進(jìn)化算法模型，研究它們會(huì)發(fā)現(xiàn)有一些共同的規(guī)律，比如都存 在一組優(yōu)劣程度不等的候選解，經(jīng)過一輪輪的反復(fù)迭代計(jì)算，每輪新生成的候選解總 體上比上一輪精度更好，且存在著一定的相關(guān)性。每輪迭代所產(chǎn)生的最好候選解之間 也存在著一定的相關(guān)性。那么能否研究這些算法的共同規(guī)律，優(yōu)化這些規(guī)律，就能使 計(jì)算智能算法模型的計(jì)算時(shí)間和性能都會(huì)得到整體上的提高。 本文介紹了目前主流的一些進(jìn)化算法模型，并在總結(jié)它們共同規(guī)律的基礎(chǔ)上，提 ? 出了一種分析解集進(jìn)化規(guī)律來預(yù)測新的解集的算法思想，被稱做附加統(tǒng)計(jì)一預(yù)測算法。 它能夠智能猜測最優(yōu)解的取值范圍，跳過進(jìn)化算法中的適應(yīng)值函數(shù)計(jì)算。通過這種方 法可以對解集的演變規(guī)律進(jìn)行分析，以誘使新的解集啟發(fā)式的生成在最優(yōu)解可能出現(xiàn) 的范圍內(nèi)。從而大大減少了計(jì)算時(shí)間。具體內(nèi)容如下： ( 1 ) 對進(jìn)化算法的基本理論、基本思想和主流算法進(jìn)行了詳細(xì)的綜述。論述了 進(jìn)化算法的發(fā)展歷史、應(yīng)用領(lǐng)域和發(fā)展趨勢，并著重介紹了本文所闡述算法需要用到 的進(jìn)化算法的共同規(guī)律。 ( 2 ) 介紹了本文所論述的附加統(tǒng)計(jì)一預(yù)測算法。首先分析該算法的來源和實(shí)現(xiàn)原 理，然后闡述了其對應(yīng)的基本思想和算法實(shí)現(xiàn)過程，并依次分析了適合應(yīng)用該算法的 一些進(jìn)化算法模型。 ( 3 ) 研究了使用附加統(tǒng)計(jì)一預(yù)測算法改進(jìn)了的一些進(jìn)化算法模型。結(jié)合了當(dāng)今主 v l l 流的幾種進(jìn)化算法，即遺傳算法、粒子群優(yōu)化算法和分布估計(jì)算法。列舉附加統(tǒng)計(jì)一 預(yù)測算法的嵌入位置和附加效果，以闡明本算法的普適性和可行性。 ( 4 ) 將使用了附加統(tǒng)計(jì)一預(yù)測算法的進(jìn)化算法用于最優(yōu)化求解等問題進(jìn)行對比實(shí) 驗(yàn)。這些實(shí)驗(yàn)包括最優(yōu)化求解等問題，對比這幾種進(jìn)化算法結(jié)合附加統(tǒng)計(jì)一預(yù)測算法 后在計(jì)算時(shí)間和性能上的改進(jìn)，以闡述本算法的有效性和可推廣性。 關(guān)鍵字：附加統(tǒng)計(jì)一預(yù)測算法；進(jìn)化算法；計(jì)算智能；計(jì)算復(fù)雜性 v i i i 濟(jì)南大學(xué)碩士學(xué)位論文 a b s t r a c t a c r o s sf r o mt h ea r t i f i c i a li n t e l l i g e n c et oc o m p u t a t i o n a li n t e l l i g e n c ei n c o m p u t e rs c i e n c ei st h eh i s t o r yo ft h ed e v e l o p m e n to fam a j o rc h a n g e ag e n e t i c a l g o r i t h ma n dn e u r a ln e t w o r ka st h ec o r eo fc o m p u t a t i o n a li n t e l li g e n c et h e o r y h a sb e e nd e v e l o p e db yl e a p sa n db o u n d s t h ep a s td e c a d e ，av a r i e t yo fn e w e v o l u ti o n a r ya l g o r it h m sh a v eb e e np r o p o s e d t h e s ea l g o r it h m sh a v en o t h in gt o d ow i t ht h ep r o b l e m ，c o m m o ng o o d ，f a s tc o n v e r g e n c e ，e a s yt oj u m po u to fl o c a l o p t i m u m ，e t c ，s oi nm a n ya r e a sh a sb e e nw i d e l yu s e d e v o l u t i o n a r ya l g o r i t h mi sah i g h l yc o m p u t a t i o n a lc o m p l e x i t y o ft h e i n t e lli g e n ta l g o r it h m w h e nt h e s o l v i n gp r o b l e mm o r ec o m p li c a t e d ，t h e c a l c u l a t i o no ft h er e q u i r e dt i m ec o m p l e x i t yi sa l s or e l a t i v e l yh i g h ，a tt h e s a m et i m e ，a st h es o l u t i o ns e to ft h e1 a r g ea n dl o c a lo p t i m i z a t i o np r o b l e m ， i nw h i c ht h ee x a c ts o l u t i o n so f s e l e c t e ds p e n tm o r ec o m p li c a t e dp r o c e s s t h e r e f o r e ，w eh o p et oh a v ea na l g o r i t h mc a ne f f e c t i v e l yr e d u c et h et i m e c o m p l e x i t yo ft h es t r a t e g yt or e d u c et h ec o m p u t a t i o nt i m eo fe v o l u t i o n a r y a l g o r i t h m s t h e r ea r eal a r g en u m b e ro fe v o l u t i o n a r ya l g o r i t h mm o d e l ，t h e yw i l lf i n d an u m b e ro fc o m m o nl a w ，f o re x a m p l e ，t h e r ea r ea d v a n t a g e sa n dd is a d v a n t a g e s o fag r o u po fc a n d i d a t es o l u t i o n so fv a r y i n gd e g r e e s ，a f t e rr e p e a t e dr o u n d s o fa ni t e r a t i v ec a l c u l a t i o n ，e a c hr o u n do ft h en e wc a n d i d a t es o l u t i o n g e n e r a t e dt h eo v e r a lla c c u r a c yo fb e t t e rt h a nt h el a s tr o u n d ，a n dt h e r eis ac e r t a i nd e g r e eo fc o r r e l a t i o n g e n e r a t e db ye a c hr o u n do fi t e r a t i o nt h eb e s t s o l u t i o na m o n gt h ec a n d i d a t e st h e r ei sac e r t a i nd e g r e eo fc o r r e l a t i o n t h e s e a l g o r i t h m sc a nt h e ns t u d yt h ec o m m o nl a w ，a n do p t i m i z et h e s ei a w s ，w ew i l l b ea b l et om o d e lc o m p u t a t i o n a li n t e l l i g e n c ea l g o r i t h mf o rc a l c u l a t i n gt h et i m e i x a n do v e r a llp e r f o r m a n c ew i11b ei m p r o v e d t h i sa r t i c l ed e s c r i b e ss o m eo ft h ec u r r e n tm a i n s t r e a mm o d e lo f e v o l u t i o n a r ya l g o r i t h m s ，a n dt ot a k es t o c ko ft h e i rc o m m o nl a w ，b a s e do nt h e a n a l y s i so fas o l u t i o ns e tt op r e d i c tt h ee v o l u t i o no ft h el a wo ft h es o l u t i o n s e to ft h en e wt h i n k i n go ft h ea l g o r i t h m ，k n o w na st h ea d d i t i o n a ls t a t i s t i c s p r e d i c t i o na l g o r i t h m i tc a ng u e s st h es m a r tr a n g eo fo p t i m a ls o l u t i o n ，s k i p t h ee v o l u t i o n a r ya l g o r i t h mi nt h ec a l c u l a t i o no ff i t n e s sf u n c t i o n t h i sm e t h o d c a nb ea d o p t e df o rt h es o l u t i o ns e to fa na n a l y s i so ft h ee v o l u t i o no ft h e l a wi no r d e rt oi n d u c ean e wg e n e r a t i o nh e u r i s t i cs o l u t i o ns e to ft h eo p t i m a l s o l u t i o ni nt h ef r a m e w o r ko ft h ep o s s i b l e t h ec o m p u t a t i o nt i m ea r er e d u c e d a sf o l l o w s ： ( 1 ) o fe v o l u t i o n a r ya l g o r i t h m sb a s i ct h e o r y ，t h o u g h ta n dm a i n s t r e a m a l g o r i t h ms u m m a r i z e di nd e t a i l d i s c u s st h eh i s t o r yo ft h ed e v e l o p m e n to f e v o l u t i o n a r ya l g o r i t h m s ，a p p li c a t i o na r e a sa n dd e v e l o p m e n tt r e n d s ，w i t ha n e m p h a s i so nt h ea l g o r i t h mi nt h i sp a p e rr e q u i r e db yt h ee v o l u t i o n a r ya l g o r i t h m u s e di nt h ec o m m o np a t t e r n ( 2 ) t h i sa r t i c l ed i s c u s s e st h ea d d i t i o n a ls t a t i s t i cp r e d i c t i o na l g o r i t h m s t h ea l g o r i t h mf i r s ta n a l y z e st h es o u r c e sa n dp r i n c i p l e so fi m p l e m e n t a t i o n ， a n dt h e nt h e i rc o u n t e r p a r t so nt h eb a s i ci d e aa n da l g o r i t h mo ft h e i m p l e m e n t a t i o np r o c e s s ，a n df o l l o w e db ya na n a l y s i so ft h ea l g o r i t h mi s s u i t a b l ef o ran u m b e ro fe v o l u t i o n a r ya l g o r i t h mm o d e l s ( 3 ) r e s e a r c hs o m ee v o l u t i o n a r ya l g o r i t h mm o d e lw i t ht h e - a d d i t i o n a l s t a t i s t i cp r e d i c t i o n a l g o r i t h m s c o m b i n a t i o n t h es e v e r a lo f t o d a y s m a i n s t r e a me v o l u t i o n a r ya l g o r i t h m ，s u c ha s g a ，p s oa n de d a a d d i t i o n a l s t a t i s t i cp r e d i c t i o na l g o r i t h m1 i s t e de m b e d d e dp o s i t i o na n dt h ea d d i t i o n a l x 濟(jì)南大學(xué)碩士學(xué)位論文 e f f e c t s ，t oc l a r i f yt h ea l g o r i t h ma n dt h ef e a s i b i l i t yo ft h eu n i v e r s a l ( 4 ) a d d i t i o n a ls t a t i s t i cp r e d i c t i o na l g o r i t h m sf o ro p t i m i z a t i o no f e v o l u t i o n a r ya l g o r i t h m st os o l v ei s s u e ss u c ha sc o m p a r a t i v ee x p e r i m e n t t h e s e e x p e r i m e n t si n c l u d eo p t i m i z a t i o np r o b l e ms o l v i n g ，e t c ，c o m p a r e dt ot h e s e t y p e so fe v o l u t i o n a r ya l g o r i t h m sc o m b i n e dw i t h a d d i t i o n a ls t a r i s t i c a l p r e d i c t i o na l g o r i t h mi nt h ec o m p u t a t i o nt i m ea n dp e r f o r m a n c ei m p r o v e m e n t st o t h ee f f e c tiv e n e s so ft h isa lg o r it h m k e y w o r d s ： a d d i t i o n a ls t a t i s t i cp r e d i c t i o n a l g o r i t h m s ： e v o l u t i o n a r y a l g o r i t h m ；c o m p u t a t i o n a li n t e l l i g e n c e ：c o m p u t a t i o n a lc o m p l e x i t y x i 濟(jì)南大學(xué)碩士學(xué)位論文 原創(chuàng)性聲明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立 進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不包含 任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過的科研成果。對本文的研究作出 重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本人完全意識到 本聲明的法律責(zé)任由本人承擔(dān)。 論文作者簽名： 日 期： 關(guān)于學(xué)位論文使用授權(quán)的聲明 本人完全了解濟(jì)南大學(xué)有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué) 校保留或向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論 文被查閱和借鑒；本人授權(quán)濟(jì)南大學(xué)可以將學(xué)位論文的全部或部分內(nèi) 容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或其他復(fù)制手段保 存論文和匯編本學(xué)位論文。 ( 保密論文在解密后應(yīng)遵守此規(guī)定) 論文作者簽名： 磐m 訊 濟(jì)南大學(xué)碩士學(xué)位論文 1 1 引言 第一章緒論 從人工智能跨越到計(jì)算智能是計(jì)算機(jī)科學(xué)發(fā)展史上的一次重大變革 1 5 】。以進(jìn)化 算法和神經(jīng)網(wǎng)絡(luò)為核心的計(jì)算智能理論得到了長足的發(fā)展。計(jì)算智能以生物進(jìn)化的觀 點(diǎn)認(rèn)識和模擬智能，以數(shù)據(jù)為基礎(chǔ)，通過訓(xùn)練建立聯(lián)系而進(jìn)行問題求解。按照這一觀 點(diǎn)，智能是在生物的遺傳、變異、生長以及外部環(huán)境的自然選擇中產(chǎn)生的。在用進(jìn)廢 退、優(yōu)勝劣汰的過程中，適應(yīng)度高的結(jié)構(gòu)保存下來，智能水平也隨之提蒯卜5 1 。 進(jìn)化算法是依靠模擬生物種群進(jìn)化的過程來實(shí)現(xiàn)解集向精確解逐步演化的。正如 大自然演化過程的漫長，大部分進(jìn)化算法求解的精確化過程也需要消耗大量機(jī)器運(yùn)算 時(shí)間。例如使用進(jìn)化算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)有時(shí)需要數(shù)天之久。為了降低程序的計(jì)算復(fù)雜 度，節(jié)約計(jì)算時(shí)間，我們希望能夠找到一種在解集中智能地發(fā)現(xiàn)最優(yōu)解的快速算法。 而這種算法還必須具有相當(dāng)?shù)钠者m性和推廣性，以應(yīng)付形形色色的進(jìn)化計(jì)算模型。這 就需要我們研究分析現(xiàn)有和將來可能出現(xiàn)的進(jìn)化計(jì)算模型的共性，從共性中找到一種 通用的方法。 如果我們分析現(xiàn)有的和將來可能出現(xiàn)的這些進(jìn)化計(jì)算模型，則會(huì)發(fā)現(xiàn)其有共同規(guī) 律即目前幾乎所有的進(jìn)化算法，均是由一組解集經(jīng)過若干代演算后逐步逼近更精 確的解集。那么如果我們找到一種分析解集變化規(guī)律的方法，則能有效地預(yù)測出更精 確的解集的取值可能，從而達(dá)到上述目的。這就是本論文所要闡述的主題。 1 2 研究背景 進(jìn)化算法作為計(jì)算智能理論的核心問題之一。最近十幾年來，各種新算法也紛紛 被提出。比如遺傳算法( g e n e t i ca l g o r i t h m ，g a ) i 糾0 1 、免疫算法( i m m u n ep r o g r a m m i n g ， i p ) 1 1 - 1 4 1 、遺傳編程( g e n ep r o g r a m m i n g ，g p ) 19 1 、基因表達(dá)式編程( g e n ee x p r e s s i o n p r o g r a m m i n g ，g e p ) 2 0 - 2 2 1 、概率增強(qiáng)式程序進(jìn)化算法( p r o b a b i l i s t i ci n c r e m e n t a lp r o g r a m e v o l u t i o n ，p i p e ) 1 2 3 、人工蟻群算法( a n tc o l o n yo p t i m i z a t i o n 、a c a ) i 2 們6 1 、粒子群 - l 一 優(yōu)化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 2 7 - 3 1 1 、分布估計(jì)算法( e s t i m a t i o no f d i s t r i b u t i o na l g o r i t h m s ，e d a ) t 3 2 - 3 3 1 、入侵草算法( i n v a s i v ew e e do p t i m i z a t i o n ，i w o ) 1 4 0 l 、 區(qū)域再生算法( r e g i o nr e p r o d u c t i o na l g o r i t h m s 、r r a ) 等。 這些算法都具有與問題無關(guān)、通用性好、收斂速度快、容易跳出局部最優(yōu)等優(yōu)點(diǎn)， 因此在許多領(lǐng)域都得到了廣泛的應(yīng)用。研究這些新興的計(jì)算智能算法模型，會(huì)發(fā)現(xiàn)它 們都有如下基本步驟： 1 ) 都要求有一組隨機(jī)數(shù)據(jù)作為初始解集。 2 ) 將這組初始解集代入該計(jì)算模型后，得到了一組近似的解集。并有專門的適 應(yīng)度函數(shù)來判斷現(xiàn)存所有解集哪些比較精確，去粗存精保留較好的解集。 3 ) 利用步驟2 的解集為初始數(shù)據(jù)，重做若干次步驟2 ，每次得到的保留解集比 前次循環(huán)更為精確，直到解集比較滿意為止。 研究這些計(jì)算智能算法模型的基本步驟，我們會(huì)發(fā)現(xiàn)這些算法具有下面一些共同 特征。 a ：存在一組優(yōu)劣程度不等的候選解。 b ：經(jīng)過若干輪的反復(fù)迭代計(jì)算，每輪新生成的候選解總體上比上一輪精度更好， 且存在著一定的相關(guān)性。每輪迭代所產(chǎn)生的最好候選解之間也存在著一定的相關(guān)性。 c ：利用步驟b 的解集為初始數(shù)據(jù)，重做若干次步驟b ，每次得到的保留解集比 前次循環(huán)更為精確，直到解集比較滿意為止。 上面的步驟b 所生成的每一輪的解集，雖然和上下輪的解集相比，總體上是不 斷演化的。但由于求解問題的高度復(fù)雜性，往往會(huì)導(dǎo)致算法收斂速度過于緩慢，需要 幾小時(shí)甚至幾天的時(shí)間，來完成平時(shí)看起來或許很簡單的收斂過程。這就需要我們找 到一種新方法來智能地優(yōu)化進(jìn)化計(jì)算模型的收斂軌跡。這里，我們提出了一種方法來 分析每輪循環(huán)中最優(yōu)解產(chǎn)生的時(shí)間序列的變化過程，通過這個(gè)時(shí)間序列矩陣，來預(yù)測 若干輪循環(huán)以后最優(yōu)解的可能變化趨勢，從而提前猜測出可能的最優(yōu)解取值，減輕算 法的計(jì)算量。 這個(gè)被稱為附加統(tǒng)計(jì)預(yù)測算法( a d d i t i o n a ls t a t i s t i c - p r e d i c t i o n a l g o r i t h m s ，以下簡稱為a s p a ) 的通用進(jìn)化算法改進(jìn)策略，就是本文所論述的主題。 通過對它的研究。我們實(shí)現(xiàn)了下列一些目的： 2 濟(jì)南大學(xué)碩士學(xué)位論文 a ：使用a s p a 算法來優(yōu)化幾個(gè)有代表性的進(jìn)化計(jì)算模型，包括遺傳算法( g e n e t ic a l g o r i t h m 、g a ) 、粒子群優(yōu)化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 、分布 估計(jì)算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s ，e d a ) 。 b ：使用經(jīng)過a s p a 改進(jìn)的進(jìn)化計(jì)算模型，來解決幾個(gè)典型的最優(yōu)化求解問題。這 些問題包括s c h w e f e l sp r o b l e m 、s h i f t e dr a s t r i g i n sf u n c t i o n 、5 0 維最優(yōu)化 問題等。 c ：使用經(jīng)過a s p a 改進(jìn)的進(jìn)化計(jì)算模型，來解決幾個(gè)典型的生物信息學(xué)問題。 1 3 論文內(nèi)容安排 第一章緒論，主要簡介進(jìn)化計(jì)算模型的共性，引出了本論文的研究背景。 第二章進(jìn)化算法與預(yù)測理論，主要介紹了進(jìn)化計(jì)算的基本理論、基本思想和基 本方法。以及一些典型的進(jìn)化計(jì)算模型。和一些預(yù)測理論。 第三章附加統(tǒng)計(jì)一預(yù)測算法，主要闡述了a s p a 的設(shè)計(jì)思路，算法流程，和典型 用法。系統(tǒng)地介紹了a s p a 的基本理論基礎(chǔ)以及其的實(shí)現(xiàn)方法。 第四章附加統(tǒng)計(jì)一預(yù)測算法與其他算法結(jié)合，主要闡述了a s p a 與幾種典型的進(jìn) 化算法相結(jié)合的方法，以及其對典型測試用例的改進(jìn)程度。 第五章總結(jié)和展望，對附加統(tǒng)計(jì)一預(yù)測算法的研究和應(yīng)用做出了總結(jié)，同時(shí)指出 存在的問題，并對未來的研究和發(fā)展做出了展望。 濟(jì)南大學(xué)碩士學(xué)位論文 2 1 進(jìn)化算法概述 第二章進(jìn)化算法與預(yù)測理論 進(jìn)化算法是計(jì)算智能理論的核心組成之一。進(jìn)化算法是基于達(dá)爾文的進(jìn)化論，在 計(jì)算機(jī)上模擬生命進(jìn)化機(jī)制而發(fā)展起來的一門新學(xué)科n 1 。近年來，由于進(jìn)化計(jì)算在機(jī) 器學(xué)習(xí)、過程控制、經(jīng)濟(jì)預(yù)測和工程優(yōu)化等領(lǐng)域取得了巨大的成功，引起了數(shù)學(xué)、物 理學(xué)、化學(xué)、生物學(xué)、計(jì)算機(jī)科學(xué)、社會(huì)科學(xué)、經(jīng)濟(jì)學(xué)及工程應(yīng)用領(lǐng)域的科學(xué)家們的 極大興趣。自2 0 世紀(jì)8 0 年代中期以來，世界上許多國家就掀起了進(jìn)化計(jì)算的研究熱 潮口3 。 地球上的生物，部是經(jīng)過長期進(jìn)化而形成的。根據(jù)達(dá)爾文的自然選擇學(xué)說，地球 上的生物具有很強(qiáng)的繁殖能力。在繁殖過程中，大多數(shù)生物通過遺傳，使物種保持相 似的后代；部分生物由于變異，后代具有明顯差別，甚至形成新物種。正是由于生物 的不斷繁殖后代，生物數(shù)目大量增加，而自然界中生物賴以生存的資源卻是有限的。 因此，為了生存，生物就需要競爭。生物在生存競爭中，根據(jù)對環(huán)境的適應(yīng)能力，適 者生存，不適者消亡。自然界中的生物，就是根據(jù)這種優(yōu)勝劣汰的原則，不斷地進(jìn)行 進(jìn)化。進(jìn)化算法就是借用生物進(jìn)化的規(guī)律，通過繁殖一競爭一再繁殖一再競爭，實(shí)現(xiàn) 優(yōu)勝劣汰，一步一步地逼近問題的最優(yōu)解。進(jìn)化算法中的“進(jìn)化 二字，就是由此而 來的啼1 。 進(jìn)化計(jì)算采用簡單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，并通過對一組編碼進(jìn)行簡 單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導(dǎo)學(xué)習(xí)和確定搜索的方向。由于它采用種群 的方式組織搜索，可以同時(shí)搜索解空間的多個(gè)區(qū)域。而且用種群組織搜索的方式使得 進(jìn)化算法特別適合大規(guī)模并行計(jì)算。在賦予進(jìn)化計(jì)算自組織、自適應(yīng)和自學(xué)習(xí)等特征 的同時(shí)，優(yōu)勝劣汰的自然選擇和簡單的遺傳操作使得進(jìn)化計(jì)算具有不受其搜索空間限 制性條件的約束及不需要其他輔助信息的特點(diǎn)。這些特點(diǎn)也使得進(jìn)化計(jì)算不僅能獲得 較高的效率而且具有簡單、易操作和通用的特性n 1 。 2 2 目前流行的部分進(jìn)化算法 由于設(shè)計(jì)者對進(jìn)化規(guī)則的不同理解和詮釋，以致目前有許多種進(jìn)化算法得到廣 泛的使用。在此，我們簡述了大約1 0 種進(jìn)化計(jì)算算法，同時(shí)再從里面選擇了三種具 有代表性的進(jìn)化算法加以詳細(xì)的介紹，總結(jié)出它們的共同特征。同時(shí)作為實(shí)際用例來 進(jìn)行具體分析。 2 2 1 遺傳算法 1 9 7 5 年，h o l l a n d 首先提出了遺傳算法( g e n e t i ca l g o r i t h m ，g a ) 哺1 。遺傳算 法是一種借鑒生物界自然選擇和自然遺傳學(xué)機(jī)理上的迭代自適應(yīng)概率性搜索算法。遺 傳算法主要由選擇、交叉和變異三個(gè)算子組成。它應(yīng)用于實(shí)際問題時(shí)，要對優(yōu)化問題 進(jìn)行編碼，稱為個(gè)體，個(gè)體的集合稱為種群，每一個(gè)個(gè)體都表示問題的一個(gè)潛在解。 遺傳算法首先隨機(jī)產(chǎn)生的初始種群，然后通過選擇、交叉、變異使種群一代代向最優(yōu) 解進(jìn)化。選擇機(jī)制基于適者生存理論，它應(yīng)用于群體中的每一個(gè)個(gè)體，使這些個(gè)體按 照其適應(yīng)值進(jìn)化到下一代群體中。標(biāo)準(zhǔn)遺傳算法利用交叉和變異算子對解空間進(jìn)行搜 索，交叉算子是兩者中的主要算子。交叉算子組合了父輩個(gè)體特征，是產(chǎn)生新個(gè)體的 主要途徑。它和選擇算子相結(jié)合，構(gòu)成算法中信息交換的重要方法。 遺傳算法是一種魯棒的搜索方法，具有計(jì)算簡單及功能強(qiáng)的特點(diǎn)，它通過目標(biāo)函 數(shù)來計(jì)算適應(yīng)度，不需要其他的推導(dǎo)和輔助信息，對問題的依賴較小。遺傳算法對待 尋優(yōu)函數(shù)基本無限制，它既不要求函數(shù)連續(xù)，也不要求可微。遺傳算法從許多初始點(diǎn) 開始并行操作，而不是從一個(gè)點(diǎn)開始，因而可以有效地防止搜索過程收斂于局部最優(yōu)， 而且有較大的可能求得全部的最優(yōu)解，同時(shí)也可通過大規(guī)模并行計(jì)算來提高計(jì)算速 度，更適合復(fù)雜問題的優(yōu)化。 遺傳算法在解空間內(nèi)不是盲目窮舉或完全隨機(jī)的測試，而是一種啟發(fā)式搜索，它 不是簡單的隨機(jī)走動(dòng)，它可以有效地利用已經(jīng)有的信息處理來搜索那些有希望改善解 質(zhì)量的串，類似于自然進(jìn)化，遺傳算法通過作用于染色體上的基因，尋找好的染色體 來求解問題。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是 對算法所產(chǎn)生的每個(gè)染色體進(jìn)行評價(jià)，并基于適應(yīng)度值來改造染色體，使適用性好的 6 濟(jì)南大學(xué)碩士學(xué)位論文 染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。 遺傳算法一般按照以下步驟執(zhí)行礴1 ： 1 ) 對于待處理的問題確定一個(gè)表示某組可能解適應(yīng)度的目標(biāo)函數(shù)。 2 ) 將候選解的種群初始化為服從特定的約束。一般情況下，將每組試驗(yàn)解編碼為 向量x ，稱為染色體，其中的元素稱為基因，特定位置的不同值稱為等位基因。 3 ) 種群中每個(gè)染色體x i ，i = 1 ，p 解碼為一個(gè)適于估價(jià)的形式，算出對于目標(biāo)的 適應(yīng)度值1 t ( x ：) 。 4 ) 算出每個(gè)染色體的繁殖概率p ：，i = 1 ，p ，使得它被選擇的可能性正比于它相 對于種群中其他染色體的適應(yīng)度。如果每個(gè)染色體的適應(yīng)度取正數(shù)的值，通常使用輪 盤賭選擇。 5 ) 一個(gè)新的染色體種群從當(dāng)前種群中的概率選擇串取決于繁殖概率p = ，i = l ，p 而產(chǎn)生。被選中的染色體通過交叉和比特突變等特定基因操作產(chǎn)生它的“后代 。交 叉應(yīng)用于兩個(gè)( 父代) 染色體間，選擇一些位置，把第一個(gè)串的某些位置的值和第二 個(gè)串相應(yīng)位置交換形成兩個(gè)新的( 后代) 染色體。最簡單的單點(diǎn)交叉操作是隨機(jī)選擇 一個(gè)位置，把第二個(gè)串這個(gè)位置后的內(nèi)容拼接到第一個(gè)串這個(gè)位置前的內(nèi)容后，反之 亦然( 見圖2 ) 。比特突變指形成新解的時(shí)候有一定概率在某位發(fā)生突變。交叉的概 率值通常取0 6 n 0 9 5 范圍，突變概率通常取0 0 0 l n 0 0 1 。 進(jìn)化算法中的選擇通常取決于不同后代的適應(yīng)度。在典型的方法中，每個(gè)染色體給 定一個(gè)復(fù)制進(jìn)入下一代的概率，這個(gè)概率正比于它相對于種群中其他染色體的適應(yīng) 度。通過連續(xù)試驗(yàn)管理哪個(gè)染色體應(yīng)當(dāng)被選中，直到所有可能的位置都被遍歷。適應(yīng) 度高的染色體比適應(yīng)度低的有更多機(jī)會(huì)給下一代提供復(fù)本。 n o s t r 噸 f i t n e s sdt c x a l 7 ( 圖1 ) 進(jìn)化算法中的輪盤賭選擇法 6 ) 如果找到一個(gè)可行解或者可供計(jì)算的時(shí)間已到則結(jié)束算法，否則記錄新的染 色體回到第( 3 ) 步重復(fù)執(zhí)行過程 2 2 2 粒子群優(yōu)化算法 ( 圖2 ) 單點(diǎn)交叉操作 粒子群優(yōu)化算法( p a r t i c l es w a r mo p t i m i z a t i o n ，p s o ) 乜引是近年來發(fā)展起來 的一種新的進(jìn)化算法，屬于進(jìn)化算法的一種，和遺傳算法相似，它也是從隨機(jī)解出發(fā)， 通過迭代尋找最優(yōu)解，它也是通過適應(yīng)度來評價(jià)解的品質(zhì)但是它比遺傳算法規(guī)則更 為簡單，它沒有遺傳算法的“交叉”( c r o s s o v e r ) 和“變異 ( m u t a t i o n ) 操作它 通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu) p s o 同遺傳算法類似，是一種基于疊代的優(yōu)化工具。系統(tǒng)初始化為一組隨機(jī)解， 通過疊代搜尋最優(yōu)值。但是并沒有遺傳算法用的交叉( c r o s s o v e r ) 以及變異 ( m u t a t i o n ) 。而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。同遺傳算法比較，p s o 的 優(yōu)勢在于簡單容易實(shí)現(xiàn)并且沒有許多參數(shù)需要調(diào)整。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神 經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域 如前所述，p s o 模擬鳥群的捕食行為。設(shè)想這樣一個(gè)場景：一群鳥在隨機(jī)搜索食 物。在這個(gè)區(qū)域里只有一塊食物。所有的鳥都不知道食物在那里。但是他們知道當(dāng)前 的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么昵。最簡單有效的就是搜尋 目前離食物最近的鳥的周圍區(qū)域。p s o 從這種模型中得到啟示并用于解決優(yōu)化問題。 p s o 中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。我們稱之為“粒子 。所有的 例子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值( f i t n e s sv a l u e ) ，每個(gè)粒子還有一個(gè)速 度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。 8 l o o o t o l l 口 o o o l l o o l k 左 莓 聾 代 代 予 予 一 l o o o t l l d l o l 夸 o o l o o l l o l 2 # 襻 代 代 父 父 濟(jì)南學(xué)碗l 學(xué)忙論文 ( 圖3 ) p s o 算法流程 p s o 初始化為一群隨機(jī)粒子( 隨機(jī)解) 。然后通過疊代找到最優(yōu)解。在每一次疊代 中，粒子通過跟蹤兩個(gè)”極值”來更新自己。第個(gè)就是粒子本身所找到的最優(yōu)解。這 9 個(gè)解叫做個(gè)體極值p b e s t 另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全 局極值g b e s t 。另外也可以不用整個(gè)種群而只是用其中一部分最為粒子的鄰居，那么 在所有鄰居中的極值就是局部極值。 p s o 的基本算法步驟描述如下位7 1 ： 1 ) 初始化粒子群，即隨機(jī)設(shè)定每個(gè)粒子的初始位置x i 和初始速度v i ； 2 ) 計(jì)算各個(gè)粒子的適應(yīng)度值； 3 ) 對每個(gè)粒子，比較它的適應(yīng)度值和它經(jīng)歷過的最好位置p i 的適應(yīng)度值，如果 更好，更新p i ； 4 ) 對每個(gè)粒子，比較它的適應(yīng)度值和群體經(jīng)歷過的最好位置p g 的適應(yīng)度值， 如果更好，更新p g ； 5 ) 根據(jù)公式l 和公式2 調(diào)整粒子的速度x i 和位置v i ； 6 ) 如果達(dá)到結(jié)束條件，則結(jié)束；否則轉(zhuǎn)步驟2 。 2 2 3 分布估計(jì)算法 分布估計(jì)算法( e s t i m a t i o no fd i s t r i b u t i o na l g o r i t h m s ，e d a ) m 刪提出了一 種全新的進(jìn)化模式。在傳統(tǒng)的遺傳算法中，用種群表示優(yōu)化問題的一組候選解，種群 中的每個(gè)個(gè)體都有相應(yīng)的適應(yīng)值，然后進(jìn)行選擇、交叉和變異等模擬自然進(jìn)化的操作， 反復(fù)進(jìn)行，對問題進(jìn)行求解。而在分布估計(jì)算法中，沒有傳統(tǒng)的交叉、變異等遺傳操 作，取而代之的是概率模型的學(xué)習(xí)和采樣。分布估計(jì)算法通過一個(gè)概率模型描述候選 解在空間的分布，采用統(tǒng)計(jì)學(xué)習(xí)手段從群體宏觀的角度建立一個(gè)描述解分布的概率模 型，然后對概率模型隨機(jī)采樣產(chǎn)生新的種群，如此反復(fù)進(jìn)行，實(shí)現(xiàn)種群的進(jìn)化，直到 終止條件。 根據(jù)概率模型的復(fù)雜程度以及不同的采樣方法，分布估計(jì)算法發(fā)展了很多不同的 具體實(shí)現(xiàn)方法，但是都可以歸納為下面兩個(gè)主要步驟： 1 ) 構(gòu)建描述解空間的概率模型通過對種群的評估，選擇優(yōu)秀的個(gè)體集合，然 后采用統(tǒng)計(jì)學(xué)習(xí)等手段構(gòu)造一個(gè)描述當(dāng)前解集的概率模型。 2 ) 由概率模型隨機(jī)采樣產(chǎn)生新的種群。一般的，采用蒙特卡羅方法，對概率模 l o 濟(jì)南大學(xué)碩士學(xué)位論文 型采樣得到新的種群。 分布估計(jì)算法作為一種新型的進(jìn)化算法，它的科學(xué)價(jià)值主要體現(xiàn)在以下幾個(gè)方 面。首先，從生物進(jìn)化的數(shù)學(xué)模型上來看，分布估計(jì)算法與傳統(tǒng)進(jìn)化算法不同：傳統(tǒng) 進(jìn)化算法是基于對種群中的各個(gè)個(gè)體進(jìn)行遺傳操作( 交叉、變異等) 來實(shí)現(xiàn)群體的進(jìn) 化的，是對生物進(jìn)化“微觀”層面上的數(shù)學(xué)建模；而分布估計(jì)算法則是基于對整個(gè)群 體建立數(shù)學(xué)模型，直接描述整個(gè)群體的進(jìn)化趨勢，是對生物進(jìn)化“宏觀”層面上的數(shù) 學(xué)建模。其次，分布估計(jì)算法給人類解決復(fù)雜的優(yōu)化問題提供了新的工具，它通過概 率模型可以描述變量之間的相互關(guān)系，從而對解決非線性、變量耦合的優(yōu)化問題更加 有效，試驗(yàn)表明，分布估計(jì)算法能更加有效的解決高維問題，降低時(shí)間復(fù)雜性。最后， 分布估計(jì)算法是一種新的啟發(fā)式搜索策略，是統(tǒng)計(jì)學(xué)習(xí)理論與隨機(jī)優(yōu)化算法的結(jié)合， 與其他智能優(yōu)化算法的混雜設(shè)計(jì)，將極大豐富混雜優(yōu)化算法的研究內(nèi)容，給優(yōu)化算法 的研究提供了新的思路。 2 2 4 其他進(jìn)化算法 為了充實(shí)對進(jìn)化算法共性的研究，論文中還或多或少地提到了下列一些進(jìn)化算 法。它們是免疫算法( i m m u n ep r o g r a m m i n g ，i p ) 、基因表達(dá)式編程( g e n ee x p r e s s i o n p r o g r a m m in g ，g e p ) 、遺傳編程( g e n ep r o g r a m m in g ，g p ) 、概率增強(qiáng)式程序進(jìn)化算法 ( p r o b a b i l i s t i ci n c r e m e n t a lp r o g r a me v o l u t i o n ，p i p e ) 、人工蟻群算法( a n tc o l o n y o p t i m i z a t i o n 、a c o ) 、多表達(dá)式編程( m u l t ie x p r e s s i o np r o g r a m m i n g ，m e p ) 、區(qū) 域再生算法( r e g i o nr e p r o d u c t i o na l g o r i t h m s 、r r a ) 等等。這些算法也是實(shí)際工作 中相對常用的進(jìn)化計(jì)算模型 2 3 預(yù)測的理論基礎(chǔ) 在經(jīng)濟(jì)、工程、自然科學(xué)和社會(huì)科學(xué)等領(lǐng)域的實(shí)際工作者和研究人員，都不可避 免地要和一系列的歷史觀察、統(tǒng)計(jì)數(shù)據(jù)打交道，我們把按時(shí)間順序產(chǎn)生和排列的觀察 數(shù)據(jù)序列稱為時(shí)間序列。而對時(shí)間序列進(jìn)行預(yù)測則成為一個(gè)具有相當(dāng)實(shí)際價(jià)值的應(yīng)用 研究領(lǐng)域。傳統(tǒng)的時(shí)間序列分析是從純數(shù)學(xué)的角度來分析的，多基于對數(shù)據(jù)的某種分 1 1 步假設(shè)和對預(yù)測模型的簡化，但是由于實(shí)際應(yīng)用中時(shí)間序列具有不規(guī)則、混沌等非 線性特征，簡化假設(shè)條件難以與實(shí)際相符，所以很難對系統(tǒng)建立理想的模型，預(yù)測更 是無能為力，導(dǎo)致預(yù)測結(jié)果往往與實(shí)際偏差較大，計(jì)算智能技術(shù)的發(fā)展讓研究者找到 了新的問題解決思路，把它們用在這里可以解決在時(shí)間序列中難以解決或解決得不好 的優(yōu)化問題，發(fā)揮他們對目標(biāo)函數(shù)要求不高的優(yōu)勢。利用它們優(yōu)越的逼近性能來逼近 序列，但由于其自身算法的一些缺陷，這些預(yù)測方法還在不斷完善和發(fā)展之中。“1 側(cè) 隨著社會(huì)經(jīng)濟(jì)系統(tǒng)日趨復(fù)雜，預(yù)測面臨前所未有的困難。針對不同的環(huán)境及要求， 預(yù)測理論的研究者提出了大量的方法。目前已有近2 0 0 種預(yù)測方法。這些預(yù)測方法都 是建立在如下的預(yù)測的基本原理之上的，它們是：可知性原理、可能性原理、連續(xù)性 原理、相似性原理、反饋性原理、可控性原理、系統(tǒng)性原理h 2 1 。 2 3 1 可知性原理 又稱規(guī)律性原理，是關(guān)于預(yù)測對象服從某種發(fā)展規(guī)律的原理。它認(rèn)為，預(yù)測對象 由于其發(fā)展規(guī)律可以被人們所掌握，因而其未來發(fā)展趨勢和狀況便可以被人們所知 曉。人們的預(yù)測活動(dòng)，不論其形式如何，都與這一原理有關(guān)。 2 3 2 可能性原理 預(yù)測對象未來發(fā)展的趨勢和狀況，它是在內(nèi)因與外因的共同作用下出現(xiàn)的，它的 結(jié)果具有不同的可能性，而常常不是只存在單一的可能性，但是預(yù)測對象演化到不同 結(jié)果的可能性大小不同。對研究對象所作的預(yù)測，就是對它的未來發(fā)展的可能性進(jìn)行 預(yù)測。這一原理是建立在預(yù)測對象發(fā)展變化的結(jié)果與內(nèi)外因共同作用有一定關(guān)系的基 礎(chǔ)上。 2 3 3 連續(xù)性原理 把預(yù)測對象的發(fā)展看成是一個(gè)連續(xù)的、統(tǒng)一的過程，其未來的發(fā)展是這個(gè)過程的 繼續(xù)。該原理強(qiáng)調(diào)，預(yù)測對象總是從過去發(fā)展到現(xiàn)在，再從現(xiàn)在發(fā)展到未來，如果沒 有預(yù)測對象的過去和現(xiàn)在，就沒有它發(fā)展變化的未來。要對該對象的未來發(fā)展進(jìn)行預(yù) 1 2 所麗大字壩士字位論文 測，就必須了解它的過去和現(xiàn)在，預(yù)測對象發(fā)展過程中的過去、現(xiàn)在和未來，處于一 種辯證的、統(tǒng)一的、連續(xù)的關(guān)系之中。連續(xù)性原理適用于那些發(fā)展極其緩慢、幾乎沒 有變化的預(yù)測對象。 2 3 4 相似性原理 在許多情況下，被人們作為預(yù)測和研究對象的一個(gè)事物，其現(xiàn)在的發(fā)展過程和發(fā) 展?fàn)顩r往往與一個(gè)己知的過去事物的一定階段的發(fā)展過程和發(fā)展?fàn)顩r類似，相似性原 理就是反映這種情況的原理。當(dāng)甲事物現(xiàn)在的發(fā)展過程和發(fā)展?fàn)顩r與乙事物過去一定 階段的發(fā)展過程和發(fā)展?fàn)顩r相似時(shí)，乙事物后來階段的發(fā)展過程和發(fā)展?fàn)顩r就可能相 似于甲事物的未來發(fā)展過程。因此，預(yù)測者就可以根據(jù)乙事物后來的發(fā)展過程和狀況， 預(yù)測出甲事物的未來發(fā)展過程和狀況。應(yīng)用這樣的原理來分析和預(yù)測研究對象，被稱 為類推法或歷史類比預(yù)測方法。 2 3 5 可控性原理 作為人們預(yù)測對象的大量事物，其未來發(fā)展過程往往呈現(xiàn)出可以調(diào)節(jié)和控制的可 能性。人們在考查事物發(fā)展的機(jī)制和過程時(shí)發(fā)現(xiàn)，把預(yù)測到的未來信息傳遞給可以影 響、調(diào)節(jié)和控制研究對象未來發(fā)展的人或其它因素，就可以通過人的行為或其它因素 的變化來達(dá)到調(diào)節(jié)和控制研究對象未來發(fā)展的目的?？煽匦栽砭褪顷P(guān)于預(yù)測對象的 未來發(fā)展可以得到調(diào)節(jié)和控制的原理?？煽匦栽韺︻A(yù)測活動(dòng)具有重要指導(dǎo)意義。它 強(qiáng)調(diào)，只要研究對象的未來發(fā)展趨勢是可以調(diào)節(jié)、可以控制的，人類就可以通過對它 的調(diào)節(jié)和控制，使它朝著符合人類目標(biāo)和需要的方向發(fā)展。這正是有目的預(yù)測活動(dòng)所 希望達(dá)到的效果。 2 3 6 反饋性原理 人們在預(yù)測和研究事物的未來發(fā)展趨勢和發(fā)展?fàn)顩r時(shí)，預(yù)測結(jié)果往往和預(yù)測目的 有不同程度的差距。只有對預(yù)測依據(jù)進(jìn)行反饋調(diào)節(jié)，才能縮小這種差距，做出符合活 動(dòng)目的的預(yù)測。依據(jù)這種原理，預(yù)測者要有效地進(jìn)行反饋調(diào)節(jié)，必須抓住三個(gè)環(huán)節(jié)。 首先，他必須認(rèn)真地分析預(yù)測的結(jié)果與目的之間的差距，了解這種差距；其次，他必 須了解產(chǎn)生這種差距的原因；第三