中文摘要 中文摘要 在管理科學(xué)、信息科學(xué)、系統(tǒng)科學(xué)以及工業(yè)工程等眾多領(lǐng)域都存在著客觀的或 人為的隨機(jī)性，相應(yīng)地存在著大量的隨機(jī)優(yōu)化問(wèn)題。進(jìn)化計(jì)算方法，如遺傳算法、 進(jìn)化策略、蟻群算法、微粒群算法等用于求解隨機(jī)優(yōu)化問(wèn)題在最優(yōu)性方面得到了很 好的結(jié)果，但由于其適應(yīng)值估計(jì)( 隨機(jī)仿真) 非常費(fèi)時(shí)而限制了其實(shí)際應(yīng)用。因此， 本論文研究如何在微粒群算法過(guò)程中，利用已有適應(yīng)值估計(jì)的信息預(yù)測(cè)一些變量的 適應(yīng)值，以減少運(yùn)行隨機(jī)仿真的次數(shù)，從而從總體上減少計(jì)算時(shí)間。 首先，采用廣義回歸神經(jīng)網(wǎng)絡(luò)作為適應(yīng)值預(yù)測(cè)模型，通過(guò)對(duì)廣義回歸神經(jīng)網(wǎng)絡(luò) 的分析給出它與微粒群算法的結(jié)合機(jī)制、預(yù)測(cè)策略及模型更新策略，由此來(lái)決定個(gè) 體的適應(yīng)值是用預(yù)測(cè)模型進(jìn)行預(yù)測(cè)還是用隨機(jī)仿真進(jìn)行估計(jì)及何時(shí)更新預(yù)測(cè)模型， 從而提出一種將廣義回歸神經(jīng)網(wǎng)絡(luò)與微粒群算法相結(jié)合求解隨機(jī)優(yōu)化問(wèn)題的智能算 法，通過(guò)實(shí)例仿真說(shuō)明了該算法在保證算法性能的前提下，在適應(yīng)值計(jì)算方面大大 減少了計(jì)算量從而從總體上節(jié)省了大量時(shí)間，體現(xiàn)了它在求解隨機(jī)優(yōu)化問(wèn)題中優(yōu)勢(shì)。 其次，采用k r i g i n g 模型作為適應(yīng)值預(yù)測(cè)模型，由k r i g i n g 模型與微粒群算法的結(jié)合 機(jī)制及預(yù)測(cè)策略選擇部分個(gè)體的適應(yīng)值進(jìn)行預(yù)測(cè)，其余個(gè)體的適應(yīng)值則用隨機(jī)仿真 進(jìn)行估計(jì)，提出一種將k r i g i n g 模型與微粒群算法相結(jié)合求解隨機(jī)優(yōu)化問(wèn)題的算法， 為隨機(jī)優(yōu)化問(wèn)題的處理提供了一條新的有效途徑。 關(guān)鍵詞：隨機(jī)優(yōu)化問(wèn)題；微粒群算法；隨機(jī)仿真；廣義回歸神經(jīng)網(wǎng)絡(luò)；k r i g i n g 模型 a b s t r a c t a b s t r a c t t h e r ei sm u c ho b je c t i v eo rm a n - m a d er a n d o m n e s smt h ef i e l d so f m a n a g e m e n ts c i e n c e ，i n f o r m a t i o ns c i e n c e ，s y s t e m ss c i e n c e ，i n d u s t r i a l e n g i n e e r i n ga n ds oo n ，w h e r eal a r g en u m b e ro fs t o c h a s t i co p t i m i z a t i o n p r o b l e m se x i s ta c c o r d i n g l y a l t h o u g he v o l u t i o n a r yc o m p u t a t i o n ( e g g e n e t i c a l g o r i t h m ，e v o l u t i o n a r ys t r a t e g y , p a r t i c l es w a r mo p t i m i z a t i o ne r e ) h a sb e e n s h o w e dt ob e p o w e r f u lg l o b a lo p t i m i z e r s f o rs t o c h a s t i c o p t i m i z a t i o n p r o b l e m s ，i th a st h ed i s a d v a n t a g eo fh i g h e rc o s tw h i c hl i m i t si t sa p p l i c a t i o n s b e c a u s ea l li n d i v i d u a l s f i t n e s si se s t i m a t e db yr a n d o ms i m u l a t i o n 。i ti s s u g g e s t e dt op r e d i c tt h ef i t n e s so fs o m ei n d i v i d u a l s ，t a k i n gt h ei n f o r m a t i o no f t h ef i t n e s st h a th a sb e e nc a l c u l a t e di n t oa c c o u n t t m sm e t h o dc a nr e d u c et h e t i m e so fr a n d o ms i m u l a t i o n ，a n da c c o r d i n g l yi tr e d u c e st h ec o m p u t i n gt i m ei n t o t a l f i r s t l y , g e n e r a l i z e dr e g r e s s i o nn e u r a ln e t w o r k ( g r n n ) i su s e da sa f i t n e s sp r e d i c t i o nm o d e la n da ni n t e l l i g e n ta l g o r i t h mc o m b i n e dg r n nw i t h p a r t i c l e s w a r mo p t i m i z a t i o ni s p r e s e n t e d i nt h i si n t e l l i g e n ta l g o r i t h m ， a c c o r d i n gt ot h ea n a l y s i so f t h eg r n n ，t h em e c h a n i s mw h i c hc o m b i n e s g r n nw i t hp a r t i c l es w a r mo p t i m i z a t i o n ，p r e d i c t i o ns t r a t e g ya n dp r e d i c t i o n m o d e lt r a i n i n ga r e p r o p o s e d ，b y w h i c hw ec a nd e c i d ew h e t h e rt h e i n d i v i d u a l sf i t n e s si sp r e d i c t e db yt h eg r n no re s t i m a t e db yr a n d o m s i m u l a t i o na n dw h e nt ou p d a t et h eg r n n r e s u l t so fs i m u l a t i o ns h o wt h a t t h ei n t e l l i g e n ta l g o r i t h mr e d u c e st h ec o m p u t a t i o n a lc o s tg r e a t l yi nt h e p r e m i s eo fp e r f o r m a n c eg u a r a n t e e d n e x t ，k r i g i n gm o d e li su s e da sa f i t n e s s p r e d i c t i o nm o d e la n dan e wa l g o r i t h mw h i c hc o m b i n e sk r i g i n gm o d e lw i t h p a r t i c l es w a r mo p t i m i z a t i o ni sp r o p o s e d i nt h i sa l g o r i t h m ，a c c o r d i n gt ot h e m e c h a n i s mc o m b i n e dk r i g i n gm o d e lw i t hp a r t i c l es w a r mo p t i m i z a t i o na n d p r e d i c t i o ns t r a t e g y , s o m eo f t h ei n d i v i d u a l s f i t n e s si sp r e d i c t e da n dt h er e s ti s e s t i m a t e db yr a n d o ms i m u l a t i o n r e s u l t so fs i m u l a t i o ns h o wt h ec o r r e c t n e s s a n de f f e c t i v e n e s so ft h i sn e w a l g o r i t h m i l l 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 k e yw o r d s ：s t o c h a s t i co p t i m i z a t i o np r o b l e m ；p a r t i c l es w a r mo p t i m i z a t i o n ； r a n d o ms i m u l a t i o n ；g e n e r a l i z e dr e g r e s s i o nn e u r a ln e t w o r k ；k r i g i n gm o d e l i v 聲明尸明 本人鄭重聲明：所呈交的學(xué)位論文，是本人在指導(dǎo)教師的指導(dǎo)下， 獨(dú)立進(jìn)行研究所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文 不包含其他個(gè)人或集體已經(jīng)發(fā)表或撰寫(xiě)過(guò)的科研成果。對(duì)本文的研究 做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本聲明的 法律責(zé)任由本人承擔(dān)。 作者簽名： 日期：竺乏墨芝 關(guān)于學(xué)位論文使用權(quán)的說(shuō)明 本人完全了解太原科技大學(xué)有關(guān)保管、使用學(xué)位論文的規(guī)定，其 中包括：學(xué)校有權(quán)保管、并向有關(guān)部門送交學(xué)位論文的原件、復(fù)印 件與電子版；學(xué)?？梢圆捎糜坝?、縮印或其它復(fù)制手段復(fù)制并保存 學(xué)位論文；學(xué)校可允許學(xué)位論文被查閱或借閱；學(xué)校可以學(xué)術(shù)交 流為目的，復(fù)制贈(zèng)送和交換學(xué)位論文；學(xué)?？梢怨紝W(xué)位論文的全 部或部分內(nèi)容( 保密學(xué)位論文在解密后遵守此規(guī)定) 。 作者簽名： 導(dǎo)師簽名： 日期： 日期： x _ 占?xì)?第一章緒論 第一章緒論 1 1 概述 在進(jìn)化計(jì)算中，其計(jì)算復(fù)雜性主要取決于所解決問(wèn)題適應(yīng)值函數(shù)的計(jì)算次數(shù)。 對(duì)于一般的非線性函數(shù)優(yōu)化問(wèn)題，由于其適應(yīng)值函數(shù)的計(jì)算量較少，因而如何提高 收斂速度、減少進(jìn)化代數(shù)等是進(jìn)化類優(yōu)化方法的主要目標(biāo)。但是，在進(jìn)化計(jì)算的實(shí) 際應(yīng)用中，往往會(huì)遇到一些適應(yīng)值估計(jì)非常耗時(shí)的問(wèn)題，如基于仿真模型的仿真優(yōu) 化問(wèn)題、目標(biāo)函數(shù)中含有隨機(jī)變量的問(wèn)題或者適應(yīng)值需要通過(guò)一系列復(fù)雜計(jì)算才能 近似估計(jì)的問(wèn)題等等，這時(shí)，適應(yīng)值的一次估計(jì)要運(yùn)行一系列軟件才能得到。采用 進(jìn)化計(jì)算解決這些問(wèn)題將非常費(fèi)時(shí)，具有很高的計(jì)算復(fù)雜性。如何減少適應(yīng)值的精 確估計(jì)次數(shù)，以減少計(jì)算復(fù)雜性，是進(jìn)化計(jì)算能否成功應(yīng)用于這些問(wèn)題的關(guān)鍵。 隨機(jī)優(yōu)化問(wèn)題廣泛存在于工程、管理、控制等領(lǐng)域，對(duì)于該類問(wèn)題的求解，雖 然理論上已發(fā)展了一些方法，但仍存在著許多問(wèn)題。進(jìn)化計(jì)算方法，如遺傳算法、 進(jìn)化策略、蟻群算法、微粒群算法等用于求解隨機(jī)優(yōu)化問(wèn)題也得到了一些嘗試，但 在計(jì)算中，適應(yīng)值的每一次估計(jì)都要通過(guò)運(yùn)行隨機(jī)仿真軟件來(lái)近似得到，這將是非 常耗時(shí)的。所以雖然進(jìn)化計(jì)算應(yīng)用于隨機(jī)優(yōu)化問(wèn)題在最優(yōu)性方面得到了很好的結(jié)果， 但由于其適應(yīng)值估計(jì)( 隨機(jī)仿真) 非常費(fèi)時(shí)而限制了其實(shí)際應(yīng)用。一種可行的思想 就是如何在進(jìn)化計(jì)算過(guò)程中，利用已有適應(yīng)值估計(jì)的信息預(yù)測(cè)一些變量的適應(yīng)值， 以減少運(yùn)行隨機(jī)仿真的次數(shù)，從而從總體上減少計(jì)算時(shí)間。 微粒群算法( 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 ) 作為一種新的智能技術(shù)，它采 用基于種群的并行全局搜索策略，但不具有選擇、變異等操作，僅采用簡(jiǎn)單的速度一 位置模型實(shí)現(xiàn)對(duì)整個(gè)空間的尋優(yōu)操作。由于該算法概念簡(jiǎn)單、易于實(shí)現(xiàn)、優(yōu)化性能 好，目前已在許多問(wèn)題中得到了成功的應(yīng)用，所以本文試圖將p s o 算法與適應(yīng)值預(yù)測(cè) 方法相結(jié)合用于解決隨機(jī)優(yōu)化問(wèn)題。 1 2 國(guó)內(nèi)外研究動(dòng)態(tài) 1 2 1 適應(yīng)值預(yù)測(cè)方法的研究動(dòng)態(tài) 迄今為止，適應(yīng)值預(yù)測(cè)方法已被廣泛應(yīng)用于進(jìn)化計(jì)算中。 a 多項(xiàng)式模型 多項(xiàng)式模型通常稱為表面響應(yīng)法，是應(yīng)用最廣泛的一種適應(yīng)值預(yù)測(cè)模型，其二 階形式為： 1 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 多= 風(fēng)+ 盧，薯+ f l , , - l + ，+ j x , x j 1 s ” 1 s s ，s 打 ( 1 1 ) 其中系數(shù)風(fēng)、盧，可用最小二乘法和梯度法進(jìn)行估計(jì)【l , 3 1 。二階多項(xiàng)式模型適合解決連 續(xù)、單峰問(wèn)題，而多峰問(wèn)題則可用多項(xiàng)式樣條函數(shù)來(lái)解決 2 1 。 bk r i g i n g 模型 k r i g i n g 模型可看作是一個(gè)全局模型和局部偏差的結(jié)合： y ( x ) = g ( x ) + z ( x ) r 1 ，、 其中g(shù) ( x ) 為原適應(yīng)值函數(shù)的全局模型，是一個(gè)關(guān)于x 的已知函數(shù)；z ( x ) 是一個(gè)期望 值為零、協(xié)方差非零的高斯隨機(jī)函數(shù)，它代表偏離全局模型的局部偏差。g ( x ) 通常 是一個(gè)多項(xiàng)式，在很多情況下被簡(jiǎn)化為一個(gè)常數(shù)。k r i g i n g 模型中的參數(shù)可用極大似 然法來(lái)估計(jì)。在k r i g i n g 模型中只需進(jìn)行少量計(jì)算便可獲得估計(jì)的置信區(qū)間。然而， 隨著維數(shù)的增高，其計(jì)算量會(huì)越來(lái)越大【1 1 。 高斯模型( g a u s s i a np r o c e s s e s ，g p s ) 【4 1 是一種常用的k r i g i n g 模型，它是一個(gè)給 定數(shù)據(jù)點(diǎn)集上的概率模型，該概率模型被用來(lái)預(yù)測(cè)新數(shù)據(jù)點(diǎn)上函數(shù)值的均值和標(biāo)準(zhǔn) 差。g p s 中的參數(shù)可用典型長(zhǎng)度、噪音水平等來(lái)設(shè)置，也可用極大似然法優(yōu)化得到。 由于g p s 不需要預(yù)先定義結(jié)構(gòu)、擁有有意義的參數(shù)及最優(yōu)化這些參數(shù)的理論框架、 能夠逼近任意函數(shù)，所以比其他模型更有優(yōu)勢(shì)，但其計(jì)算代價(jià)比較高【2 ，5 1 。 c 人工神經(jīng)網(wǎng)絡(luò)( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) a n n 是由大量高度互聯(lián)的處理單元組成的并行分布式處理器，它具有通過(guò)學(xué)習(xí) 獲取知識(shí)并解決問(wèn)題的能力，且知識(shí)是分布儲(chǔ)存在連接權(quán)中。若給予足夠多的處理 單元，a n n 能逼近任何函數(shù)。通過(guò)向環(huán)境學(xué)習(xí)獲取知識(shí)并改進(jìn)自身性能是a n n 的 一個(gè)重要特點(diǎn)。一般情況下，a n n 性能的改善是按某種預(yù)定的度量通過(guò)調(diào)節(jié)自身參 數(shù)( 如權(quán)值) 而逐步達(dá)到的。誤差反向傳播學(xué)習(xí)算法是a n n 現(xiàn)在最流行的學(xué)習(xí)算法。 前饋多層感知器和徑向基函數(shù)網(wǎng)絡(luò)已被廣泛應(yīng)用于適應(yīng)值函數(shù)估計(jì)。 多層感知器( m u l t i l a y e rp e r c e p t r o n s ，m l p ) 由三部分組成：一組感知單元( 源節(jié) 點(diǎn)) 組成輸入層，一層或多層計(jì)算節(jié)點(diǎn)的隱層和一層計(jì)算節(jié)點(diǎn)的輸出層。輸入信號(hào) 在層層遞進(jìn)基礎(chǔ)上前向傳播通過(guò)網(wǎng)絡(luò)。m l p 的隱節(jié)點(diǎn)基函數(shù)采用線性函數(shù)，它的每 個(gè)神經(jīng)元模型都包括一個(gè)非線性激活函數(shù)( 一般采用s i g m o i d a l 函數(shù)或硬極限函數(shù)) 。 徑向基函數(shù)網(wǎng)絡(luò)( r a d i a lb a s i sf u n c t i o nn e t w o r k ，r b f n ) 與m l p 相比，結(jié)構(gòu)更 簡(jiǎn)潔，學(xué)習(xí)速度更快。r b f n 采用距離函數(shù)( 如歐氏距離) 作為隱節(jié)點(diǎn)權(quán)值函數(shù)，并 使用徑向基函數(shù)( r a d i a lb a s i sf u n c t i o n ，i m f )( 如高斯函數(shù)) 作為激活函數(shù)。特別 2 第一章緒論 的，r b f n 的每個(gè)隱節(jié)點(diǎn)都具有一個(gè)數(shù)據(jù)中心。 a n n 的主要缺點(diǎn)是在訓(xùn)練網(wǎng)絡(luò)時(shí)產(chǎn)生的權(quán)值難以解釋以及很難確定一個(gè)適當(dāng)?shù)?網(wǎng)絡(luò)拓手| 、【2 ，6 ，7 8 】。 d 支持向量機(jī) 支持向量機(jī)理論是在統(tǒng)計(jì)學(xué)理論基礎(chǔ)上發(fā)展起來(lái)的，它的主要優(yōu)點(diǎn)是訓(xùn)練過(guò)程 中不會(huì)產(chǎn)生局部最小值，并且泛化的錯(cuò)誤不依賴空間維數(shù)1 。 由于適應(yīng)值預(yù)測(cè)模型的性能與所解決的實(shí)際問(wèn)題有關(guān)，所以判斷一個(gè)預(yù)測(cè)模型 的好壞還沒(méi)有一個(gè)明確的標(biāo)準(zhǔn)，但很多文獻(xiàn)研究表明r b f n 和g p s 的性能相對(duì)較好 1 0 ，1l ，1 2 o 適應(yīng)值預(yù)測(cè)模型與進(jìn)化算法的結(jié)合機(jī)制大致可以分為：( 1 ) 拓?fù)浣Y(jié)構(gòu)的改善 t 3 - 1 s l ；( 2 ) 初始化種群的改善陋1 9 1 ；( 3 ) 基于函數(shù)適應(yīng)值的繼承機(jī)制1 2 0 - 3 4 1 。第一種 方式通過(guò)引入遷移等特定算子，以提高適應(yīng)值的預(yù)測(cè)準(zhǔn)確度，但實(shí)驗(yàn)結(jié)果表明該策 略的效果不是很明顯。而第二種方式則著眼于強(qiáng)化初始種群的質(zhì)量，但這種策略容 易陷入局部極值。第三種策略是在算法運(yùn)行過(guò)程中，動(dòng)態(tài)的預(yù)測(cè)某些位置的適應(yīng)值， 由于算法的隨機(jī)性，因此，這種預(yù)測(cè)對(duì)于過(guò)早收斂具有一定的免疫力。而對(duì)于預(yù)測(cè) 策略而言，又分兩種情況：( 1 ) 算法運(yùn)行過(guò)程中，所有的適應(yīng)值都預(yù)測(cè)；( 2 ) 在算 法運(yùn)行的每代中，都選擇部分適應(yīng)值預(yù)測(cè)，而其余的適應(yīng)值則使用實(shí)際的適應(yīng)值， 而對(duì)于需要預(yù)測(cè)的個(gè)體的選擇方式又可分為隨機(jī)選擇【3 5 】及代數(shù)固定選擇兩種。此外， 適應(yīng)值預(yù)測(cè)模型的訓(xùn)練方法也分為兩種：( 1 ) 離線訓(xùn)練：在預(yù)測(cè)模型用于算法之前 訓(xùn)練好就不再更新；( 2 ) 在線訓(xùn)練：在算法運(yùn)行過(guò)程中，用實(shí)際的適應(yīng)值來(lái)進(jìn)一步 訓(xùn)練模型以不斷更新適應(yīng)值預(yù)測(cè)模型。 1 2 2 微粒群算法的研究背景和現(xiàn)狀 微粒群算澍3 6 。3 繃是在1 9 9 5 年由美國(guó)社會(huì)心理學(xué)家j a m e sk e n n e d y 和電氣工程師 r u s s e l le b e r h a r t 受啟于對(duì)鳥(niǎo)類群體行為的研究并利用了生物學(xué)家f r a n kh e p p n e r 的生 物群體模型而提出的一種智能算法【4 0 1 。p s o 算法同時(shí)將微粒的位置與速度模型化， 給出了一組顯式的進(jìn)化方程，這是p s o 算法不同于其它進(jìn)化類算法的顯著之處，也 是其顯示出許多優(yōu)良特性的關(guān)鍵。 基本微粒群算法的速度進(jìn)化方程可以分成三個(gè)部分【4 l 】：微粒先前的速度、表示 微粒本身思考的“認(rèn)知”部分及表示微粒間社會(huì)信息共享的“社會(huì) 部分。基本的 微粒群算法可分為兩種基本進(jìn)化模型：全局模型( g b e s t 模型) 及局部模型( l b e s t 模型) 。g b e s t 模型以犧牲算法的魯棒性為代價(jià)提高算法的收斂速度【4 2 1 ，但易發(fā)生過(guò) 3 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 早收斂現(xiàn)象。為此，l b e s t 模型采用多吸引子代替g b e s t 模型的單一吸引子。雖然收 斂速度低于g b e s t 模型，但收斂的全局最優(yōu)性明顯改善。 p s o 算法常應(yīng)用于復(fù)雜優(yōu)化問(wèn)題的求解，它最早應(yīng)用于人工神經(jīng)網(wǎng)絡(luò)的訓(xùn)練， e n g e l b r e c h t 等【4 3 1 利用p s o 來(lái)訓(xùn)練神經(jīng)元網(wǎng)絡(luò)；j u a l l g 畔】將遺傳算法與p s o 相結(jié)合來(lái) 設(shè)計(jì)遞歸模糊神經(jīng)元網(wǎng)絡(luò)；m e s s e r s c h m i d t 等【4 5 】利用基于p s o 的神經(jīng)元網(wǎng)絡(luò)來(lái)預(yù)測(cè) t i c t a c t o eg a m e 樹(shù)葉節(jié)點(diǎn)的狀態(tài)。應(yīng)用結(jié)果都顯示利用p s o 設(shè)計(jì)神經(jīng)元網(wǎng)絡(luò)是一種 快速、高效并具有潛力的方法。在圖像處理方面，y i n t 4 6 應(yīng)用k e i l i l e d y 等的離散p s o 方法解決多邊形近似問(wèn)題，有效提高了多邊形近似效果；p a r s o p o u l o s 等h 利用p s o 對(duì)用于放射治療的模糊認(rèn)知圖的模型參數(shù)進(jìn)行優(yōu)化；c a o r s i 等【4 8 】利用基于p s o 的微 波圖像法來(lái)確定電磁散射體的絕緣特性；w a c h o w i a k 等【4 9 j 利用結(jié)合局部搜索的混合 p s o 算法對(duì)生物醫(yī)學(xué)圖像進(jìn)行配準(zhǔn)。在調(diào)度問(wèn)題方面，l i u 等 5 0 , 5 1 】將標(biāo)準(zhǔn)微粒群算法 擴(kuò)展到離散生產(chǎn)調(diào)度問(wèn)題，提出了針對(duì)典型流水線調(diào)度問(wèn)題的一種有效混合p s o 算 法。在此基礎(chǔ)上，結(jié)合特定問(wèn)題信息，提出了解決零等待流水線調(diào)度、帶有限緩沖 區(qū)的流水線調(diào)度、多目標(biāo)流水線調(diào)度和加工時(shí)間隨機(jī)分布的流水線調(diào)度等一系列復(fù) 雜問(wèn)題的混合p s o 算法。t a s g e t i r e n 等【5 2 1 則提出置換f l o w s h o p 問(wèn)題的基于可變鄰域 搜索的微粒群算法?？傊琾 s o 算法在函數(shù)優(yōu)化、約束優(yōu)化、極大極小問(wèn)題、多目 標(biāo)優(yōu)化等問(wèn)題中均得到了成功的應(yīng)用。在實(shí)際應(yīng)用領(lǐng)域它己成功應(yīng)用于機(jī)器人領(lǐng)域、 電力系統(tǒng)、交通運(yùn)輸領(lǐng)域、工程設(shè)計(jì)與優(yōu)化領(lǐng)域、計(jì)算機(jī)領(lǐng)域、電磁學(xué)領(lǐng)域等【5 3 5 9 j 。 p s o 算法自提出以來(lái)，由于它概念簡(jiǎn)單、實(shí)現(xiàn)方便，而且容易與其它優(yōu)化算法 相結(jié)合，短短十幾年時(shí)間內(nèi)p s o 算法已獲得了很大的進(jìn)展。目前主要有以下幾個(gè)研 究方向：算法的改進(jìn)、算法的理論基礎(chǔ)的分析、算法的生物學(xué)基礎(chǔ)、算法與其它優(yōu) 化算法的比較和融合、算法在實(shí)際應(yīng)用中的問(wèn)題以及算法的應(yīng)用領(lǐng)域的拓展。 1 3 本文的主要內(nèi)容 p s o 算法具有模型簡(jiǎn)單、易于實(shí)現(xiàn)、收斂速度快、精度高等優(yōu)點(diǎn)，引起了國(guó)內(nèi) 外眾多學(xué)者的關(guān)注，它已在各類問(wèn)題的求解及應(yīng)用中展現(xiàn)了它的特點(diǎn)和魅力。p s o 算法用于求解隨機(jī)優(yōu)化問(wèn)題在最優(yōu)性方面得到了很好的結(jié)果，但由于其適應(yīng)值估計(jì) ( 隨機(jī)仿真) 非常費(fèi)時(shí)而限制了其實(shí)際應(yīng)用。因此，本文研究如何在微粒群算法過(guò) 程中，利用已有適應(yīng)值估計(jì)的信息預(yù)測(cè)一些變量的適應(yīng)值，以減少運(yùn)行隨機(jī)仿真的 次數(shù)，從而從總體上減少計(jì)算時(shí)間。本文具體研究?jī)?nèi)容為： 第二章介紹了標(biāo)準(zhǔn)p s o 算法的基本概念、基本原理、算法流程及算法的設(shè)計(jì)原 4 第一章緒論 則與步驟。然后通過(guò)與其它優(yōu)化算法相比較，說(shuō)明了微粒群算法所具有的優(yōu)越性。 第三章采用廣義回歸神經(jīng)網(wǎng)絡(luò)作為適應(yīng)值預(yù)測(cè)模型，通過(guò)對(duì)廣義回歸神經(jīng)網(wǎng)絡(luò) 的分析給出它與微粒群算法的結(jié)合機(jī)制、預(yù)測(cè)策略及模型更新策略，由此來(lái)決定個(gè) 體的適應(yīng)值是用預(yù)測(cè)模型進(jìn)行預(yù)測(cè)還是用隨機(jī)仿真進(jìn)行估計(jì)及何時(shí)更新預(yù)測(cè)模型， 從而提出一種將廣義回歸神經(jīng)網(wǎng)絡(luò)與微粒群算法相結(jié)合求解隨機(jī)優(yōu)化問(wèn)題的智能算 法，通過(guò)實(shí)例仿真說(shuō)明了該算法在保證算法性能的前提下，在適應(yīng)值計(jì)算方面大大 減少了計(jì)算量從而從總體上節(jié)省了大量時(shí)間，體現(xiàn)了它在求解隨機(jī)優(yōu)化問(wèn)題中優(yōu)勢(shì)。 第四章采用k r i g i n g 模型作為適應(yīng)值預(yù)測(cè)模型，由k r i g i n g 模型與微粒群算法的 結(jié)合機(jī)制及預(yù)測(cè)策略選擇部分個(gè)體的適應(yīng)值進(jìn)行預(yù)測(cè)，其余個(gè)體的適應(yīng)值則用隨機(jī) 仿真進(jìn)行估計(jì)，提出一種將k x i g i n g 模型與微粒群算法相結(jié)合求解隨機(jī)優(yōu)化問(wèn)題的算 法，為隨機(jī)優(yōu)化問(wèn)題的處理提供了一條新的有效途徑。 第五章對(duì)本論文工作進(jìn)行了總結(jié)和展望。 5 第二章微粒群算法 第二章微粒群算法 微粒群算法是群智能理論研究領(lǐng)域中的一個(gè)重要分支，所謂“群智能”指一組 相互之間可以進(jìn)行直接或間接通訊的主體，能通過(guò)合作對(duì)問(wèn)題進(jìn)行分布求解，即一 組無(wú)智能的主體通過(guò)合作可以表現(xiàn)出智能行為特征。e b e r h a r t 和k e n n e d y 于1 9 9 5 年 提出p s o 算法【3 6 3 7 , 3 8 , 4 ，其基本思想是受他們?cè)缙趯?duì)鳥(niǎo)類群體行為研究結(jié)果的啟發(fā) 并利用了生物學(xué)家f r a n kh e p p n e r 的生物模型。它的進(jìn)化規(guī)則與“優(yōu)勝劣汰，適者生 存 的遺傳算法截然不同：它強(qiáng)調(diào)的是群體中個(gè)體之間信息的社會(huì)共享和協(xié)同進(jìn)化。 2 1 標(biāo)準(zhǔn)微粒群算法 假設(shè)有如下數(shù)值優(yōu)化模型： m i n f ( x ) ，x 【x 。缸，x 一】”互r ” ( 2 1 ) 設(shè) x ，= ( xj 1 ，z ，2 ，z j 。) 為微粒，的當(dāng)前位置： k = ( v j lp v 2 ，v 加) 為微粒- 的當(dāng)前飛行速度； 弓= ( p 1 ，p 2 ，p 加) 為微粒7 所經(jīng)歷的最優(yōu)位置，也就是微粒，所經(jīng)歷過(guò)的具有 最優(yōu)適應(yīng)值的位置，稱為個(gè)體歷史最優(yōu)位置。對(duì)于最小化問(wèn)題，目標(biāo)函數(shù)值越小， 對(duì)應(yīng)的適應(yīng)值越優(yōu)。 設(shè)群體中的微粒數(shù)為s ，群體中所有微粒所經(jīng)歷過(guò)的最優(yōu)位置為r , j t ) ，稱為全 局歷史最優(yōu)位置。 有了以上定義，標(biāo)準(zhǔn)微粒群算法的進(jìn)化方程可描述為： v j t , ( t + 1 ) = z o v j 嗽( t ) + c 1 吒( p 弦( f ) 一x j 瞻( t ) ) + c 2 r 2 ( p s k ( t ) 一z 皿( f ) ) ( 2 2 ) x j k ( f + 1 ) = z 承( f ) + 秒球( f + 1 ) ( 2 3 ) 其中：下標(biāo)“k ”表示微粒的第k 維，“，表示微粒j ，t 表示第t 代，w 為慣性權(quán) 重，介于0 ，1 之間，認(rèn)知系數(shù)c ，與社會(huì)系數(shù)c ，稱為加速度常數(shù)，通常在0 2 間取值， r , - u ( o ，1 ) ，r 2 u ( 0 ，1 ) 為兩個(gè)相互獨(dú)立的隨機(jī)數(shù)。 從上述微粒進(jìn)化方程可以看出，w 用于調(diào)節(jié)自身慣性所占的比重，g 調(diào)節(jié)微粒 飛向自身最優(yōu)位置方向的步長(zhǎng)，c ，調(diào)節(jié)微粒向群體歷史最優(yōu)位置飛行的步長(zhǎng)。為了 減少在進(jìn)化過(guò)程中，微粒離開(kāi)搜索空間的可能性，v m 通常限定于一定范圍內(nèi)，即 v 承【一，z ，一】。如果問(wèn)題的搜索空間限定在卜x 一，x 一】?jī)?nèi)，則可設(shè)定 = j ：( z 一，0 1 k 1 0 。 7 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 在式( 2 2 ) 所描述的速度進(jìn)化方程中，其第一部分為微粒先前的速度；其第二部 分為“認(rèn)知( c o g n i t i o n ) ”部分，因?yàn)樗鼉H考慮了微粒自身的經(jīng)驗(yàn)，表示微粒本身的思考。 如果基本微粒群算法的速度進(jìn)化方程僅包含認(rèn)知部分，即 v j k ( t + 1 ) = z ) 影毋( f ) + c 1 吒( p 癬( f ) 一x 毋( f ) ) ( 2 4 ) 則其性能變差。主要原因是不同的微粒之間缺乏信息交流，即沒(méi)有社會(huì)信息共享， 微粒間沒(méi)有交互，使得一個(gè)規(guī)模為s 的群體等價(jià)于運(yùn)行了s 個(gè)單個(gè)微粒，因而得到最 優(yōu)解的概率非常小。 式( 2 2 ) 的第三部分為“社會(huì)( s o c i a l ) ”部分，表示微粒間的社會(huì)信息共享。若速度進(jìn) 化方程中僅包含社會(huì)部分，即 v j k ( f + 1 ) = 加移m ( f ) + c 2 r 2 ( p s k ( f ) 一x j k ( f ) ) ( 2 5 ) 則微粒沒(méi)有認(rèn)知能力，也就是“只有社會(huì)( s o c i a l o n l y ) ”的模型。這樣，微粒在相互作 用下，有能力到達(dá)新的搜索空間，雖然它的收斂速度比基本微粒群算法更快，但對(duì) 于復(fù)雜問(wèn)題，則容易陷入局部最優(yōu)點(diǎn)。 標(biāo)準(zhǔn)微粒群算法的初始化過(guò)程為： ( 1 ) 設(shè)定群體規(guī)模n ； ( 2 ) 對(duì)任意微粒，的任意維k 的位置分量z 諏在卜x 一，x 一】?jī)?nèi)服從均勻分布產(chǎn)生； ( 3 ) 對(duì)任意微粒，的任意維k 的速度分量v 承在【一v 一，1 ，一】?jī)?nèi)服從均勻分布產(chǎn)生； ( 4 ) 個(gè)體歷史最優(yōu)位置弓( o ) 取各微粒初始位置，群體最優(yōu)位置b ( o ) 為適應(yīng)值最優(yōu) 的微粒所對(duì)應(yīng)的位置。 2 2 標(biāo)準(zhǔn)微粒群算法流程 標(biāo)準(zhǔn)微粒群算法流程如圖2 1 所示。 8 第二章微粒群算法 圖2 - 1 標(biāo)準(zhǔn)微粒群算法流程圖 f i g u r e2 - 1f l o wc h a to fs t a n d a r dp a r t i c l es w a r mo p t i m i z a t i o n 標(biāo)準(zhǔn)微粒群算法流程如下： ( 1 ) 種群初始化：按照上述初始化過(guò)程選擇，并置進(jìn)化代數(shù)f 為o ； 9 n n 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 ( 2 ) 參數(shù)初始化：設(shè)置慣性權(quán)重w 、認(rèn)知系數(shù)c 。、社會(huì)系數(shù)c ：及最大速度上限1 ，一； ( 3 ) 由式( 2 2 ) 計(jì)算微粒下一代的速度； ( 4 ) 調(diào)整各微粒的速度； ( 5 ) 由式( 2 3 ) 計(jì)算微粒下一代的位置； ( 6 ) 更新個(gè)體歷史最優(yōu)位置及群體歷史最優(yōu)位置； ( 7 ) 若結(jié)束條件滿足，輸出得到的最優(yōu)位置；否則，轉(zhuǎn)步驟3 。 2 3 微粒群算法的設(shè)計(jì)原則與步驟 1 、設(shè)計(jì)p s o 算法的基本原則 ( 1 ) 適用性原則 一個(gè)算法的適用性，是指該算法所能適用問(wèn)題種類，這取決于算法所需的限制 與假設(shè)。如果優(yōu)化問(wèn)題的性質(zhì)不同，則相應(yīng)的具體處理方式也不同。 ( 2 ) 可靠性原則 一個(gè)算法的可靠性，是指算法具有以適當(dāng)?shù)木惹蠼獯蠖鄶?shù)問(wèn)題的能力，即能 對(duì)大多數(shù)問(wèn)題提供一定精度的解。 與其他眾多的進(jìn)化算法一樣，p s o 同樣是一種隨機(jī)的優(yōu)化算法，因此在求解不 同問(wèn)題時(shí)，其結(jié)果具有一定的隨機(jī)性與不確定性。故設(shè)計(jì)算法試驗(yàn)時(shí)，應(yīng)盡量經(jīng)過(guò) 較多樣本的檢驗(yàn)，以確定算法的可靠性。 ( 3 ) 收斂性原則 p s o 算法的收斂性是指算法能否以概率1 收斂到全局最優(yōu)解，并具有一定的收 斂速度和收斂精度。通常評(píng)價(jià)算法的收斂性能，可通過(guò)比較在有限時(shí)間代內(nèi)算法所 求解的精度來(lái)實(shí)現(xiàn)。 ( 4 ) 穩(wěn)定性原則 算法的穩(wěn)定性是指算法對(duì)其控制參數(shù)及問(wèn)題數(shù)據(jù)的敏感程度。一個(gè)性能穩(wěn)定的 算法，應(yīng)該具有以下兩種特性：一是對(duì)一組固定的控制參數(shù)，算法能用于較廣泛的 問(wèn)題求解；二是對(duì)給定的問(wèn)題數(shù)據(jù)，算法的求解結(jié)果應(yīng)不會(huì)隨控制參數(shù)的微小擾動(dòng) 而波動(dòng)。 ( 5 ) 生物類比原則 微粒群算法的設(shè)計(jì)思想源于對(duì)生物群體社會(huì)行為的模擬，因此生物界中相關(guān)的 進(jìn)化理論、策略、方法，均可通過(guò)類比的原則，引入到算法中以求提高算法性能。 2 、p s o 算法的設(shè)計(jì)步驟 1 0 第二章微粒群算法 ( 1 ) 確定問(wèn)題的表示方案( 編碼方案) 和其他的進(jìn)化算法一樣，p s o 算法在求解問(wèn)題時(shí)，首先應(yīng)將問(wèn)題的解從解空間 映射到具有某種結(jié)構(gòu)的表示空間，即用特定的碼串表示問(wèn)題的解。根據(jù)問(wèn)題的特性 選擇適當(dāng)?shù)木幋a方法，將會(huì)對(duì)算法的性能及求解結(jié)果產(chǎn)生直接的影響。 p s o 算法的早期研究均集中在數(shù)值優(yōu)化領(lǐng)域中，其標(biāo)準(zhǔn)計(jì)算模型適用于具有連 續(xù)特征的問(wèn)題函數(shù)，因此目前的算法大多采用實(shí)數(shù)向量的編碼方案。用p s o 算法求 解具有離散特征的問(wèn)題對(duì)象，正是此領(lǐng)域內(nèi)的一個(gè)研究重點(diǎn)。 ( 2 ) 確定優(yōu)化問(wèn)題的評(píng)價(jià)函數(shù) 在求解過(guò)程中，借助于適應(yīng)值來(lái)評(píng)價(jià)解的質(zhì)量。因此在求解問(wèn)題時(shí)，必須根據(jù) 問(wèn)題的具體特性，選取適當(dāng)?shù)哪繕?biāo)函數(shù)或費(fèi)用函數(shù)來(lái)計(jì)算適應(yīng)度。適應(yīng)度是唯一能 夠反映并引導(dǎo)優(yōu)化過(guò)程不斷進(jìn)行的參量。 ( 3 ) 選取控制參數(shù) p s o 算法的控制參數(shù)，通常包括微粒群的規(guī)模( 微粒的數(shù)目) 、算法執(zhí)行的最大代 數(shù)、慣性系數(shù)、認(rèn)知參數(shù)、社會(huì)參數(shù)和其他一些輔助控制參數(shù)等。針對(duì)不同的算法 模型，選取適當(dāng)?shù)目刂茀?shù)，直接影響算法的優(yōu)化性能。 ( 4 ) 設(shè)計(jì)微粒的飛行模型 在微粒群算法中，最關(guān)鍵的操作是如何確定微粒的速度。由于微粒是多維向量 來(lái)描述的，故相應(yīng)的微粒的飛行速度也表示為一個(gè)多維向量。在飛行過(guò)程中，微粒 借助自身的記憶與社會(huì)信息共享，沿著每一分量方向動(dòng)態(tài)地調(diào)整自己的飛行速度與 方向。 ( 5 ) 確定算法的終止準(zhǔn)則 與其他進(jìn)化算法一樣，p s o 算法中最常用的終止準(zhǔn)則是預(yù)先設(shè)定一個(gè)最大的飛 行代數(shù)，或者是當(dāng)搜索過(guò)程中的解的適應(yīng)度在連續(xù)多少代后不再發(fā)生明顯改進(jìn)時(shí)， 終止算法。 ( 6 ) 編程上機(jī)運(yùn)行 根據(jù)所設(shè)計(jì)的算法結(jié)構(gòu)編程，并進(jìn)行具體優(yōu)化問(wèn)題的求解。通過(guò)所獲得問(wèn)題的 解的質(zhì)量，可以驗(yàn)證算法的有效性，準(zhǔn)確與可靠性。 2 4 與其它進(jìn)化算法的比較 微粒群算法與其他進(jìn)化算法，如進(jìn)化規(guī)劃、進(jìn)化策略和遺傳算法等相比，有許 多相似之處。它們都使用“種群 概念，用于表示一組解空間中的個(gè)體集合。兩者 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 都隨機(jī)初始化種群，而且都使用適應(yīng)值來(lái)評(píng)價(jià)系統(tǒng)，而且都根據(jù)適應(yīng)值來(lái)進(jìn)行一定 的隨機(jī)搜索。兩個(gè)系統(tǒng)都不是保證一定找到最優(yōu)解。如果將微粒所持有的最好位置 也看作種群的組成部分，則微粒群的每一步迭代都可以看作是一種弱化的選擇機(jī)制。 在進(jìn)化策略算法中，子代與父代競(jìng)爭(zhēng)，若子代具有更好的適應(yīng)值，則子代將替換父 代，而p s o 算法的進(jìn)化方程式也具有與此類似的機(jī)制，其唯一的差別在于，p s o 算法 只有當(dāng)粒子的當(dāng)前位置與所經(jīng)歷的最好位置相比具有更好的適應(yīng)值時(shí)，其粒子所經(jīng) 歷的最好位置才一會(huì)唯一地被該粒子當(dāng)前的位置所替代。 微粒群算法( p s o ) 與遺傳算法( g a ) 相比，還有以下異同之處： p s o 和g a 的相同點(diǎn)： ( 1 ) 都屬于仿生算法。p s o 主要模擬鳥(niǎo)類覓食、人類認(rèn)知等社會(huì)行為而提出；g a 主要借用生物進(jìn)化中“適者生存的規(guī)律。 ( 2 ) 都屬全局優(yōu)化方法。在解空間都隨機(jī)產(chǎn)生初始種群，因而算法在全局的解空 間進(jìn)行搜索，且將搜索重點(diǎn)集中在性能高的部分。 ( 3 ) 都屬隨機(jī)搜索算法。p s o 中認(rèn)知項(xiàng)和社會(huì)項(xiàng)前都加有隨機(jī)數(shù)；而g a 的遺傳操 作均屬隨機(jī)操作。 ( 4 ) p s o 的速度更新方程與實(shí)數(shù)編碼的遺傳算法的算術(shù)交又算子很類似。通常， 算術(shù)交叉算子由兩個(gè)父代個(gè)體的線性組合產(chǎn)生兩個(gè)子代個(gè)體；而在p s o 算法的速度更 新方程中，如果不考慮第一項(xiàng)，也就是帶慣性權(quán)重的速度項(xiàng)，就可以將方程理解成 由兩個(gè)父代個(gè)體產(chǎn)生一個(gè)子代個(gè)體的算術(shù)交叉運(yùn)算。從另一個(gè)角度上看，同樣不考 慮第一項(xiàng)，速度更新方程也可以看作是一個(gè)變異算子，其變異的強(qiáng)度大小取決于個(gè) 體最好位置和全局最好位置之間的距離，可以把個(gè)體最好位置和全局最好位置看作 父代，變異就可以看作是由兩個(gè)父代到子代的變異。至于前面略去的慣性速度項(xiàng)， 也可以理解為一種變異的形式，其變異的大小與速度相乘的慣性因子相關(guān)，慣性因 子越接近1 ，則變異強(qiáng)度越??；越遠(yuǎn)離1 ，則變異強(qiáng)度越大。 ( 5 ) 隱含并行性。搜索過(guò)程是從問(wèn)題解的一個(gè)集合開(kāi)始的，而不是從單個(gè)個(gè)體開(kāi) 始，具有隱含并行搜索特性，從而減小了陷入局部極小的可能性。并且由于這種并 行性，易在并行計(jì)算機(jī)上實(shí)現(xiàn)，以提高算法性能和效率。 ( 6 ) 根據(jù)個(gè)體的適配信息進(jìn)行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性可 導(dǎo)性等。 ( 7 ) 對(duì)高維復(fù)雜問(wèn)題，往往會(huì)遇到早熟收斂和收斂性能差的缺點(diǎn)，都無(wú)法保證收 斂到最優(yōu)點(diǎn)。 1 2 第二章微粒群算法 p s o 和g a 的不同點(diǎn)： ( 1 ) p s o 有記憶，好的解知識(shí)的所有粒子都保存，而g a ，以前的知識(shí)隨著種群的 改變被破壞。 ( x ) p s o 具有獨(dú)特的信息共享機(jī)制。g a 中，染色體之間相互共享信息，使得整個(gè) 種群比較均勻地向最優(yōu)區(qū)域移動(dòng)。而p s o 中的粒子僅僅通過(guò)當(dāng)前搜索到最優(yōu)點(diǎn)進(jìn)行共 享信息，所以很大程度上這是一種單向信息共享機(jī)制，整個(gè)搜索更新過(guò)程是跟隨當(dāng) 前最優(yōu)解的過(guò)程。與遺傳算法比較，所有的粒子很可能更快的收斂于最優(yōu)解。 ( 3 ) g a 的編碼技術(shù)和遺傳操作比較簡(jiǎn)單，而p s o 相對(duì)于g a ，沒(méi)有交叉和變異操 作，粒子只是通過(guò)內(nèi)部速度進(jìn)行更新，因此原理更簡(jiǎn)單、參數(shù)更少、實(shí)現(xiàn)更容易。 ( 4 ) 在收斂性方面，g a 己經(jīng)有了較成熟的收斂性分析方法，并且可對(duì)收斂速度進(jìn) 行估計(jì)；而p s o 這方面的研究還比較薄弱，盡管已經(jīng)有簡(jiǎn)化確定性版本的收斂性分析， 但將確定性向隨機(jī)性的轉(zhuǎn)化尚需進(jìn)一步研究。 ( 5 ) 在應(yīng)用方面，p s 0 算法主要應(yīng)用于連續(xù)問(wèn)題，包括神經(jīng)網(wǎng)絡(luò)訓(xùn)練和函數(shù)優(yōu)化 等，而g a 除了連續(xù)問(wèn)題之外，還可應(yīng)用于離散問(wèn)題，比如t s p 問(wèn)題、貨郎擔(dān)問(wèn)題、 工作車間調(diào)度等。 通常在進(jìn)化類算法的分析中，人們習(xí)慣將每一步進(jìn)化迭代理解為用新個(gè)體( 即 子代) 代替舊個(gè)體( 即父代) 的過(guò)程。這里，如果我們將p s o 算法的進(jìn)化迭代理解 為一個(gè)自適應(yīng)過(guò)程，則微粒的位置x ，( r ) 就不是被新的微粒所代替，而是根據(jù)速度向 量1 ，( f ) 進(jìn)行自適應(yīng)變化。這樣，p s o 算法與其它進(jìn)化類算法的最大不同點(diǎn)在于：p s o 算法在進(jìn)化過(guò)程中同時(shí)保留和利用位置與速度( 即位置的變化程度) 信息，而其它 進(jìn)化類算法僅保留和利用位置的信息。 另外，如果將位置進(jìn)化方程看作一個(gè)變異算子，則p s o 算法與進(jìn)化規(guī)劃很相似。 所不同之處在于：在每一代，p s o 算法中的每個(gè)微粒只朝一些根據(jù)群體的經(jīng)驗(yàn)認(rèn)為 是好的方向飛行，而在進(jìn)化規(guī)劃中可通過(guò)一個(gè)隨機(jī)函數(shù)變異到任何方向。也就是說(shuō)， p s o 算法執(zhí)行一種有“意識(shí)( c o n s c i o u s ) 的變異。從理論上講，進(jìn)化規(guī)劃具有更 多的機(jī)會(huì)在優(yōu)化點(diǎn)附近進(jìn)行開(kāi)發(fā)，而p s o 算法則有更多的機(jī)會(huì)更快地飛到更好解的 區(qū)域。 綜上所述，p s o 算法也呈現(xiàn)出一些其它進(jìn)化類算法所不具有的特性，特別是， 微粒群算法同時(shí)將微粒的位置與速度模型化，給出了一組顯式的進(jìn)化方程，是其不 同于其它進(jìn)化類算法的最顯著之處，也是該算法所呈現(xiàn)出許多優(yōu)良特性的關(guān)鍵點(diǎn)。 1 3 第三章基于人工神經(jīng)網(wǎng)絡(luò)的求解隨機(jī)優(yōu)化問(wèn)題的混合智能算法 第三章基于人工神經(jīng)網(wǎng)絡(luò)的求解隨機(jī)優(yōu)化問(wèn)題的混合智能算法 為了尋找更有效的求解隨機(jī)優(yōu)化問(wèn)題的算法，本章采用廣義回歸神經(jīng)網(wǎng)絡(luò)作為 適應(yīng)值預(yù)測(cè)模型，由預(yù)測(cè)模型與p s o 算法的結(jié)合機(jī)制及預(yù)測(cè)策略選擇部分個(gè)體的適 應(yīng)值進(jìn)行預(yù)測(cè)，其余個(gè)體的適應(yīng)值則用隨機(jī)仿真進(jìn)行估計(jì)，提出一種將廣義回歸神 經(jīng)網(wǎng)絡(luò)與p s o 算法相結(jié)合求解隨機(jī)優(yōu)化問(wèn)題的混合智能算法。 3 1 人工神經(jīng)網(wǎng)絡(luò) 人工神經(jīng)網(wǎng)絡(luò)( a r t i f i c i a ln e u r a ln e t w o r k , a n n ) 6 0 - 6 3 是由大量處理單元( 神經(jīng) 元) 廣泛互連而成的網(wǎng)絡(luò)，其組織能夠模擬生物神經(jīng)系統(tǒng)對(duì)真實(shí)世界所做出的交互 反應(yīng)。它是根植于神經(jīng)科學(xué)、數(shù)學(xué)、統(tǒng)計(jì)學(xué)、物理學(xué)、計(jì)算機(jī)科學(xué)及工程等學(xué)科的 一種技術(shù)。由于人工神經(jīng)網(wǎng)絡(luò)具有較強(qiáng)的自適應(yīng)性、學(xué)習(xí)能力和大規(guī)模并行計(jì)算能 力，目前已被廣泛應(yīng)用于各種研究及實(shí)際工程領(lǐng)域中，如函數(shù)逼近、模式識(shí)別、圖 像處理與計(jì)算機(jī)視覺(jué)、控制與優(yōu)化、預(yù)報(bào)和智能信息管理、通信、空間科學(xué)等領(lǐng)域。 3 1 1 神經(jīng)元模型 一個(gè)神經(jīng)網(wǎng)絡(luò)由多個(gè)互連的神經(jīng)元組成，人工神經(jīng)網(wǎng)絡(luò)的信息處理由神經(jīng)元之 間的相互作用來(lái)實(shí)現(xiàn)，知識(shí)與信息的存貯表現(xiàn)為網(wǎng)絡(luò)元件互連分布式的物理聯(lián)系， 人工神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)和識(shí)別決定于各神經(jīng)元連接權(quán)系數(shù)的動(dòng)態(tài)演化過(guò)程。神經(jīng)元是 神經(jīng)網(wǎng)絡(luò)的基本處理單元，一個(gè)典型的具有聆個(gè)輸入的通用神經(jīng)元模型如圖3 1 所 示。其中j x = ( 而，恐，吒) r 為神經(jīng)元輸入，w = ( m ，w 29 - o - 9 以) r 為可調(diào)的輸入權(quán)值， 8 為偏移信號(hào)，用于建模神經(jīng)元的興奮閡值，銘( ) 和廠( ) 分別表示神經(jīng)元的基函數(shù)和 激活函數(shù)。基函數(shù)z ，( ) 是一個(gè)多輸入單輸出函數(shù)材= u ( x ，w ，a ) ；激活函數(shù)的一般作用 是對(duì)基函數(shù)輸出u 進(jìn)行“擠壓 ：y = f ( u ) ，即通過(guò)非線性函數(shù)( ) 將u 變換到指定 范圍內(nèi)。 常用的基函數(shù)類型有線性函數(shù)、距離函數(shù)和橢圓基函數(shù)。絕大多數(shù)神經(jīng)網(wǎng)絡(luò)都 采用線性函數(shù)作為基函數(shù)，如多層感知器、h o p f i e l d 網(wǎng)絡(luò)等。激活函數(shù)可以是線性的， 也可以是非線性的。常用的激活函數(shù)類型有硬極限函數(shù)、線性函數(shù)、飽和線性函數(shù)、 s i g m o i d a l 函數(shù)和高斯函數(shù)。高斯函數(shù)是極為重要的一類激活函數(shù)，常用于徑向基函 數(shù)神經(jīng)網(wǎng)絡(luò)。高斯函數(shù)的表達(dá)式為 y = 廠( 群) = e x p ( - h 么2 ) ( 3 1 ) 1 5 適合于隨機(jī)優(yōu)化問(wèn)題的微粒群算法研究 式中，參數(shù)6 稱為高斯函數(shù)的寬度或擴(kuò)展常數(shù)。6 越大，函數(shù)曲線就越平坦；反之， 6 越大，函數(shù)曲線就越陡峭。 t 屯 圖3 - 1 神經(jīng)元模型 f i g u r e3 - 1n e u r o nm o d e l 3 1 2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)及工作方式 神經(jīng)網(wǎng)絡(luò)模型是一個(gè)并行和分布式的信息處理網(wǎng)絡(luò)結(jié)構(gòu)，該網(wǎng)絡(luò)結(jié)構(gòu)一般由許 多神經(jīng)元組成，每個(gè)神經(jīng)元有一個(gè)單一的輸出，它可以連接到很多其它的神經(jīng)元上， 其輸入有多個(gè)連接通路，每個(gè)連接通路對(duì)應(yīng)一個(gè)連接權(quán)系數(shù)。 根據(jù)連接方式，神經(jīng)網(wǎng)絡(luò)常分為兩大類：沒(méi)有反饋的前饋神經(jīng)網(wǎng)絡(luò)和相互結(jié)合 型神經(jīng)網(wǎng)絡(luò)。前饋神經(jīng)網(wǎng)絡(luò)由輸入層、一層或多層的隱含層和輸出層組成，每一層 的神經(jīng)元只接受前一層神經(jīng)元的輸出。而相互結(jié)合型神經(jīng)網(wǎng)絡(luò)中任意兩個(gè)神經(jīng)元之 間都有可能連接，因此，輸入信號(hào)要在神經(jīng)元之間反復(fù)傳遞，從某一初始狀態(tài)開(kāi)始， 經(jīng)過(guò)若干次變化，漸漸趨于某一穩(wěn)定狀態(tài)或進(jìn)入周期振蕩等其他狀態(tài)。雖然目前已 有數(shù)十種神經(jīng)網(wǎng)絡(luò)模型，但常見(jiàn)的主要是三大類模型：前向神經(jīng)網(wǎng)絡(luò)、反饋神經(jīng)網(wǎng) 絡(luò)和自組織神經(jīng)網(wǎng)絡(luò)。 神經(jīng)網(wǎng)絡(luò)的工作過(guò)程主要分為兩個(gè)階段，一個(gè)階段是學(xué)習(xí)期，此時(shí)各計(jì)算單元 狀態(tài)不變，各連接上的權(quán)值通過(guò)學(xué)習(xí)來(lái)修改。第二階段是工作期，此時(shí)連接權(quán)固定， 計(jì)算單元狀態(tài)變化，以達(dá)到某種穩(wěn)定狀態(tài)。 3 ，1 3 神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)方法 通過(guò)向環(huán)境學(xué)習(xí)獲取知識(shí)并改進(jìn)自身性能是神經(jīng)網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)。在一般 情況下，性能的改善是按某種預(yù)定的度量通過(guò)調(diào)節(jié)自身參數(shù)( 如權(quán)值) 逐步達(dá)到的。 學(xué)習(xí)方式有三種：監(jiān)督學(xué)習(xí)、非監(jiān)督學(xué)習(xí)、再勵(lì)學(xué)習(xí)。監(jiān)督學(xué)習(xí)方式需要外界存在 一個(gè)“教師”，他可對(duì)給定一組輸入提供應(yīng)有的輸出結(jié)果，這組己知的輸入輸出數(shù)據(jù) 1 6 第三章基于人工神經(jīng)網(wǎng)絡(luò)的求解隨機(jī)優(yōu)化問(wèn)題的混合智能算法 稱為訓(xùn)練樣本集，學(xué)習(xí)系統(tǒng)( 神經(jīng)網(wǎng)絡(luò)) 可根據(jù)已知輸出與實(shí)際輸出之間的差值( 誤 差信號(hào)) 來(lái)調(diào)節(jié)系統(tǒng)參數(shù)。而非監(jiān)督學(xué)習(xí)不存在外部教師，學(xué)習(xí)系統(tǒng)完全按照環(huán)境 提供數(shù)據(jù)的某些統(tǒng)計(jì)規(guī)律來(lái)調(diào)節(jié)自身參數(shù)或結(jié)構(gòu)。再勵(lì)學(xué)習(xí)介于上述兩種情況之間， 外部環(huán)境對(duì)系統(tǒng)輸出結(jié)果只給出評(píng)價(jià)信息( 獎(jiǎng)或懲) 而不是給出正確答案，學(xué)習(xí)系 統(tǒng)通過(guò)強(qiáng)化那些受獎(jiǎng)的動(dòng)作來(lái)改善自身的性能。神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)規(guī)則有：誤差糾正 學(xué)習(xí)、h e b b 學(xué)習(xí)、競(jìng)爭(zhēng)( c o m p e t i t i v e ) 學(xué)習(xí)。 3 1 4 徑向基函數(shù)神經(jīng)網(wǎng)絡(luò) 徑向基函數(shù)網(wǎng)絡(luò)( r a d i a lb a s i sf u n c t i o n n e t w o r k ,