（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）計算智能及其在無線傳感器網(wǎng)絡(luò)優(yōu)化中的應(yīng)用.pdf

1iljjjllijljjilj j1-，lill一 i 授權(quán)說明 獨立進(jìn)行研究工作所取 得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個人或集體已經(jīng)發(fā)表或撰寫 過的作品或成果。對本文的研究做出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。 本聲明的法律結(jié)果由本人承擔(dān)。 論文作者簽名： 也最 日期：少p 年3 - 月瑚e l 學(xué)位論文版權(quán)使用授權(quán)說明 本人完全了解海南大學(xué)關(guān)于收集、保存、使用學(xué)位論文的規(guī)定，即：學(xué)校有權(quán)保留并向 國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。本人授權(quán)海南大 學(xué)可以將本學(xué)位論文的全部或部分內(nèi)容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃 描等復(fù)制手段保存和匯編本學(xué)位論文。本人在導(dǎo)師指導(dǎo)下完成的論文成果，知識產(chǎn)權(quán)歸屬海 南大學(xué)。 保密論義在解密后遵守此規(guī)定。 ：j 9 講最名：乞咿 日期：山如年 甫勻日日期：少口年f 月弼e 1 本人已經(jīng)認(rèn)真閱讀“c a l l s 高校學(xué)位論文全文數(shù)據(jù)庫發(fā)布章程”，同意將本人的學(xué)位論 文提交“c a l l s 高校學(xué)位論文全文數(shù)據(jù)庫”中全文發(fā)布，并可按 權(quán)益。園童途塞握鑾丘澄卮；遂匕生；旦= 生；旦三生蕉盔。 論文作者簽名：一 j 痞乙 日期：如k 鉗月船e l “章程”中規(guī)定享受相關(guān) 導(dǎo)師簽名： 日期：泓舟r 月蟋日 海南大學(xué)碩士學(xué)位論文摘要 摘要 隨著科學(xué)的發(fā)展和時代的進(jìn)步，人們在工業(yè)生產(chǎn)和工程實踐過程中遇到的問 題，越來越多地具有規(guī)模大、復(fù)雜性、約束性、非線性、不確定性等特點，在生 產(chǎn)實踐和科學(xué)研究的諸多領(lǐng)域有大量的問題都急需人們在龐大和復(fù)雜空間尋找 最優(yōu)解或近似最優(yōu)解，常規(guī)的優(yōu)化算法面對這樣的大型問題已無能為力。計算智 能作為一種新興的優(yōu)化技術(shù)，很好地解決了常規(guī)優(yōu)化算法遇到的難點，其算法相 對簡單，易理解，易實現(xiàn)，更為重要的是，計算智能方法大都具有隱含并行性、 自組織、自適應(yīng)等特點，有效地促進(jìn)了其在生產(chǎn)各領(lǐng)域中的優(yōu)化應(yīng)用，對生產(chǎn)效 率的提高、能耗的降低、資源的合理利用等具有重要的作用。 本文從計算智能中的兩種應(yīng)用廣泛的技術(shù)i 掛化計算和群體智能入手，以 進(jìn)化計算中經(jīng)典的遺傳算法和群體智能中具有代表性的蟻群優(yōu)化算法作為研究 基礎(chǔ)，簡單介紹了這兩種算法的相關(guān)理論和特點，然后進(jìn)行一些改進(jìn)，并與其他 算法進(jìn)行了融合，尋找適合于工程實踐需求的智能優(yōu)化應(yīng)用。在具體的優(yōu)化應(yīng)用 中，本文針對無線傳感器網(wǎng)絡(luò)( w i r e l e s ss e n s o rn e t w o r k , w s n ) 必須有很強(qiáng)的自組 織性、自適應(yīng)性和魯棒性且傳感器節(jié)點的能量資源都非常有限等不同于其他傳統(tǒng) 網(wǎng)絡(luò)的特點，充分利用計算智能特性，有機(jī)地將兩個研究熱點結(jié)合起來，為應(yīng)用 計算智能方法解決w s n 優(yōu)化問題，提供了方法與思路。 本文主要在三個方面做了一些工作：一，對w s n 分簇問題進(jìn)行了描述和 研究，并將遺傳算法應(yīng)用于w s n 分簇過程，綜合考慮簇內(nèi)鄰居節(jié)點的距離和能 量信息，優(yōu)化簇頭節(jié)點的選擇，使得w s n 簇內(nèi)節(jié)點的能量消耗得以均衡，避免 了節(jié)點因能量快速耗盡而過早死亡，能有效提高大規(guī)模無線傳感器網(wǎng)絡(luò)的生存周 期；二，對w s n 覆蓋問題進(jìn)行了描述，針對其具有多目標(biāo)優(yōu)化的特點，在基于 g a f 的拓?fù)淇刂葡?，?yīng)用基于p a r e t o 排序的遺傳算法來求解此問題，并考慮群 體多樣性和p a r e t o 最優(yōu)解的性能，采取一些措施對算法進(jìn)行改進(jìn)，最終實現(xiàn)使用 盡可能少數(shù)目的傳感器節(jié)點以達(dá)到盡可能大的覆蓋度的目標(biāo)，均衡了w s n 能量 消耗，減少了無線信道中潛在的訪問沖突；三，針對w s n 路由問題，結(jié)合w s n 層次型路由算法特點，充分考慮傳感器節(jié)點剩余能量和傳輸能耗，設(shè)計了一種基 于蟻群優(yōu)化的分層路由算法，使得w s n 簇頭多跳路由性能得以改善，網(wǎng)絡(luò)節(jié)點 能量消耗得以均衡。 關(guān)鍵詞g計算智能遺傳算法蟻群優(yōu)化算法無線傳感器網(wǎng)絡(luò)優(yōu)化 r 。- 。1 。1 。 海南大學(xué)碩士學(xué)位論文 a b s 仃a c t f 。1 。- _ _ _ - _ - - - - - - - - _ - _ - _ _ - _ _ - - _ _ _ - 一 a b s t r a c t a ss c i e n c ed e v e l o p sa n dt e c h n o l o g yp r o g r e s s e s ，m o r ea n dm o r e p r o b l e m sh a v e t h ef e a t u r eo fl a r g e - s c a l e ，c o m p l e x i t y , c o n s t r a i n t ，n o n l i n e a r i t ya n dn o n d e t e r m i n a c y o p t i m i z i n go f a uk i n d so fp r o c e s si np r o d u c t i o na n ds c i e n c ei sa l lu r g e n tp r o b l e mt h a t n e e d st ob es o l v e d ，h o w e v e r , t r a d i t i o n a lo p t i m i z a t i o nm e t h o d sa r ed i f f i c u l tt os o l v e t h e s ec o m p l i c a t e d l a r g e s c a l ep r o b l e m s a sar i s i n gt e c h n o l o g yo fo p t i m i z a t i o n ， c o m p u t a t i o n a li n t e l l i g e n c ep r o v i d ei n n o v a t i v et h o u g h ta n dm e a n st os o l v e t h e s e c o m p l i c a t e dp r o b l e m s t h ea l g o r i t h m sb a s e do nc o m p u t a t i o n a li n t e l l i g e n c ea r ee a s y t ou n d e r s t a n da n dr e a l i z e ，e s p e c i a l l y , m o s to fc o m p u t a t i o n a li n t e l l i g e n c em e t h o d s p o s s e s si n n e rp a r a l l e la n dd i s t r i b u t i o n ，a u t o o r g a n i z a t i o n ，a u t o a d a p t a t i o n ，w h i c h e f f e c t i v e l yp r o m o t et h ea p p l i c a t i o no fc o m p u t a t i o n a li n t e l l i g e n c ei nt h ed o m a i no f o p t i m i z a t i o n c o m p u t a t i o n a li n t e l l i g e n c ep l a ym o r ea n dm o r ei m p o r t a n tr o l e si n i m p r o v i n gt h ep r o d u c t i o ne f f i c i e n c y , r e d u c i n gc o n s u m i n ge n e r g ya n ds a v i n gr e s o u r c e t h i s p a p e r s t a r t sw i t ht w om e t h o d s a p p l i e dw i d e l y o fc o m p u t a t i o n a l i n t e l l i g e n c e ：e v o l u t i o n a r yc o m p u t i n ga n ds w a r mi n t e l l i g e n c e i tm a k e st h eg e n e t i c a l g o r i t h m s ( g a ) t h a ti s c l a s s i ci n e v o l u t i o n a r yc o m p u t i n ga n da n tc o l o n y o p t i m i z a t i o n ( a c o ) a l g o r i t h m st h a ti sr e p r e s e n t a t i v ei ns w a r mi n t e l l i g e n c ea si t s s t u d yf o u n d a t i o n i tp r e s e n t st h e o r ya n dc h a r a c t e r i s t i co ft h et w om e t h o d ss i m p l y , t h e n g i v e ss o m ei m p r o v e m e n t sa n dm a k e ss o m ec o m b i n a t i o n sw i t ho t h e rm e t h o d st os e e k t h ea p p l i c a t i o no fi n t e l l i g e n to p t i m i z a t i o n v i e wo ft h ef e a t u r et h a tw i r e l e s s i ne n g i n e e r i n gp r a c t i c e i na p p l i c a t i o n ，i n s e n s o r n e t w o r k s ( w s n ) m u s tp o s s e s s a u t o - o r g a n i z a t i o n , a u t o 。a d a p t a t i o na n dr o b u s t n e s s ，e s p e c i a l l y , e n e r g yo fw s ni sv e r y l i m i t e d ，t h i sp a p e rf u l l yu t i l i z e st h ea d v a n t a g e so fc o m p u t a t i o n a li n t e l l i g e n c e ，m a r r i e s t o g e t h e rb o t ht h er e s e a r c hf o c u s e s i tp r o p o s e ss o m em e t h o d sa n di d e a sf o ra p p l y i n g c o m p u t a t i o n a li n t e l l i g e n c et os o l v eo p t i m i z a t i o np r o b l e m so fw s n t h em a j o r c o n t e n t so ft h i sp a p e rc o u l db es u m m a r i z e da sf o l l o w s ： 1 t h ep r o b l e mo fc l u s t e r i n gi nw s ni sd e s c r i b e da n ds t u d i e di nt h i sp a p e r s y n t h e t i c a l l yc o n s i d e r i n gi n f o r m a t i o no fp o s i t i o na n de n e r g yo fn e i g h b o rn o d e si n c l u s t e r , g ai sa p p l i e dt oo p t i m i z et h e s e l e c t i o no fc l u s t e rh e a dt ob a l a n c et h e c o n s u m i n ge n e r g yo fn o d e si nc l u s t e r , a v o i dn o d e sd y i n ge a r l y , a n dp r o l o n gt h e n e t w o r kl i 危- t i m e u - ah i e r a r c h i c a lr o u t i n ga l g o r i t h mb a s e do na c o f i n a l l y , t h ea l g o r i t h mi m p r o v e s p e r f o r m a n c eo fm u l t i h o pr o u t i n go f c l u s t e rh e a d ，a n db a l a n c e st h ec o n s u m i n ge n e r g y o f n o d e si nw s n k e yw o r d s ：c o m p u t a t i o n a li n t e l l i g e n c e g e n e t i ca l g o r i t h m sa n tc o l o n y o p t i m i z a t i o n w i r e l e s ss e n s o rn e t w o r k s i i i 一 目錄 1 1 2 2 3 4 5 2 1 遺傳算法5 2 1 1 遺傳算法的基本原理一5 2 1 2 遺傳算法的構(gòu)成要素6 2 1 3 遺傳算法的數(shù)學(xué)機(jī)理9 2 1 4 遺傳算法的特點1 l 2 2 蟻群優(yōu)化算法12 2 2 1 基本蟻群優(yōu)化算法的原理12 2 2 2 蟻群系統(tǒng)1 4 2 2 3 蟻群優(yōu)化算法的特點l5 2 3 本章小結(jié)1 5 3 無線傳感器網(wǎng)絡(luò)簡介1 6 3 1 無線傳感器網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)1 6 3 2 無線傳感器網(wǎng)絡(luò)的特征1 7 3 3 無線傳感器網(wǎng)絡(luò)的一些關(guān)鍵技術(shù)1 8 3 4 本章小結(jié)2 0 4 基于遺傳算法的無線傳感器網(wǎng)絡(luò)分簇優(yōu)化2 1 4 1 無線傳感器網(wǎng)絡(luò)分簇問題描述2 l 4 2 遺傳算法優(yōu)化分簇設(shè)計2 2 4 2 1 適應(yīng)度函數(shù)設(shè)計2 2 4 2 2 編碼與算子設(shè)計。2 3 4 2 3 算法實現(xiàn)過程2 3 4 3 算法仿真與結(jié)果分析2 4 4 4 本章小結(jié)2 6 5 基于多目標(biāo)遺傳算法的無線傳感器網(wǎng)絡(luò)覆蓋問題優(yōu)化2 7 5 1 無線傳感器網(wǎng)絡(luò)覆蓋問題描述2 7 5 2 多目標(biāo)優(yōu)化的基本概念2 9 5 3 多目標(biāo)遺傳算法設(shè)計2 9 5 3 1 適應(yīng)度值分配機(jī)制3 0 海南人學(xué)碩士學(xué)位論文目錄 5 3 2 編碼與選擇算子的改進(jìn)3 0 5 3 3 最優(yōu)保存策略31 5 3 4 群體多樣性3l 5 3 5 算法實現(xiàn)過程3 2 5 4 算法仿真與結(jié)果分析3 3 5 5 本章小結(jié)3 4 6 蟻群優(yōu)化算法在無線傳感器網(wǎng)絡(luò)路由中的應(yīng)用3 5 6 1 無線傳感器網(wǎng)絡(luò)路由問題描述3 5 6 2 基于蟻群優(yōu)化的路由算法設(shè)計。3 6 6 3 算法仿真與結(jié)果分析3 9 6 4 本章小結(jié)4 0 7 總結(jié)與展望4 1 參考文獻(xiàn)4 3 碩士期間發(fā)表的論文4 6 后記4 7 1 隨著科學(xué)的發(fā)展和時代的進(jìn)步，人們在工業(yè)生產(chǎn)和工程實踐過程中遇到的問 題，越來越多地具有規(guī)模大、復(fù)雜性、約束性、非線性、不確定性等特點，在生 產(chǎn)實踐、經(jīng)濟(jì)管理和科學(xué)研究的諸多領(lǐng)域有大量的問題都急需人們在龐大和復(fù)雜 空間尋找最優(yōu)解或近似最優(yōu)解。然而，鑒于實際工程優(yōu)化問題復(fù)雜程度和規(guī)模的 不斷提高，常規(guī)的優(yōu)化算法面對這樣的大型問題已無能為力，尋找適合于工程實 踐需求的各種新型優(yōu)化方法，一直是人們研究的熱點和重要方向。計算智能作為 一種新興的優(yōu)化技術(shù)，很好地解決了常規(guī)優(yōu)化算法遇到的難點，其算法相對簡單， 易理解，易實現(xiàn)，更為重要的是，計算智能方法大都具有隱含并行性、自組織、 自適應(yīng)等特點，有效地促進(jìn)了其在生產(chǎn)各領(lǐng)域中的優(yōu)化應(yīng)用，對系統(tǒng)效率的提高、 能耗的降低、資源的合理利用及經(jīng)濟(jì)效益的提高具有重要的作用和研究意義。 隨著當(dāng)今信息技術(shù)的飛速發(fā)展，無線傳感器網(wǎng)絡(luò)( w i r e l e s ss e n s o rn e t w o r k , w s n ) 以其高度的學(xué)科交叉性和廣泛的應(yīng)用前景而成為新興前沿?zé)狳c研究領(lǐng)域， w s n 是由眾多具有通信和計算能力的傳感器節(jié)點，以多跳通信、自組織方式形 成的網(wǎng)絡(luò)，在軍事和民用方面都有廣闊的應(yīng)用領(lǐng)域?，F(xiàn)在，互聯(lián)網(wǎng)為人們?nèi)粘Ｉ?活提供了快捷的通信平臺，極大地方便了人們的信息交流；而w s n 拓展了人們 的信息獲取能力，將客觀的物理世界同互聯(lián)網(wǎng)虛擬的信息世界融合在一起，使人 們直接感知客觀物理世界，極大地擴(kuò)展現(xiàn)有網(wǎng)絡(luò)功能和人類認(rèn)識世界的能力。 遺傳算法是進(jìn)化計算方法的代表，蟻群優(yōu)化算法是近幾年來發(fā)展起來的群體 智能計算方法的代表，本文對這兩種算法進(jìn)行研究和一些改進(jìn)，并與其他算法進(jìn) 行融合，尋找適合于工程實踐需求的智能優(yōu)化應(yīng)用。同時，針對w s n 不同于其 他傳統(tǒng)網(wǎng)絡(luò)的特點w s n 必須有很強(qiáng)的自組織性、自適應(yīng)性和魯棒性且傳感 器節(jié)點的能量資源都非常有限，充分利用計算智能方法特性，對w s n 中分簇優(yōu) 化、覆蓋問題和路由選擇進(jìn)行研究與探索，為以較小代價實現(xiàn)w s n 分簇、覆蓋 及路由功能，提高系統(tǒng)整體能量效率，提供了新的方法與思路。 海南大學(xué)碩士學(xué)位論文 1 序言 1 2 計算智能的發(fā)展和現(xiàn)狀 1 2 1 計算智能發(fā)展及現(xiàn)狀 傳統(tǒng)的人工智能是基于符號處理的，通常也稱為符號智能，它以知識為基礎(chǔ)， 偏重于邏輯推理，以順序離散符號推理為特征，強(qiáng)調(diào)知識表示和推理及規(guī)則的形 成和表示。而隨著科學(xué)的發(fā)展和時代的進(jìn)步，人們在工業(yè)生產(chǎn)和工程實踐中遇到 的問題，越來越多地具有規(guī)模大、復(fù)雜性、約束性、非線性、不確定性等特點， 傳統(tǒng)的人工智能在感知、理解、學(xué)習(xí)、聯(lián)想及形象思維等方面遇到了嚴(yán)重的困難。 人們逐漸認(rèn)識到探索新方法來解決更加靈活、魯棒性較強(qiáng)問題的必要性，智能模 擬算法開始興起，并越來越多地得到研究者的重視。隨著計算機(jī)容量和計算速度 的不斷提高、大規(guī)模并行處理技術(shù)的產(chǎn)生和逐步成熟，使得智能模擬方法進(jìn)入了 一個全新的發(fā)展階段。由智能模擬方法組成的計算智能技術(shù)，更是引起了諸多領(lǐng) 域?qū)＜覍W(xué)者的關(guān)注。計算智能的興起與發(fā)展，擺脫了傳統(tǒng)人工智能所面臨的困境， 已成為該領(lǐng)域的一個新的發(fā)展方向。 計算智臺g ( c o m p u t a t i o n a li n t e l l i g e n c e ) 是一種借鑒和利用自然界中自然現(xiàn)象或 生物體的各種原理和機(jī)理而開發(fā)的并具有自適應(yīng)環(huán)境能力的計算方法。計算智能 的方法是人們從生物進(jìn)化的機(jī)理和一些自然現(xiàn)象中受到啟發(fā)，提出的許多用以解 決復(fù)雜優(yōu)化問題的新方法，具有分布、并行、仿生、自學(xué)習(xí)、自組織、自適應(yīng)等 特性【l 羽，因其高效的優(yōu)化性能、無需問題特殊信息等優(yōu)點，在諸多領(lǐng)域得到了 成功應(yīng)用。研究較多的計算智能技術(shù)主要包括進(jìn)化計算( e v o l u t i o n a r y c o m p u t i n d 、人工神經(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 ) 、模糊計算( f u z z y c o m p u t i n g ) 、人工免疫系統(tǒng)( a r t i f i c i a li m m u n es y s t e m ) 和群體智能( s w a r m i n t e l l i g e n c e ) 等。 目前計算智能算法的研究呈現(xiàn)出三大趨勢 4 1 ：一是對經(jīng)典智能算法的改進(jìn)和 廣泛應(yīng)用，以及對其理論的深入、廣泛研究；二是現(xiàn)代智能算法的發(fā)展，即不斷 從生物智能和自然界中得到啟示，探索思想更先進(jìn)、功能更強(qiáng)大的新型智能算法， 拓寬其應(yīng)用領(lǐng)域，并對其尋求理論基礎(chǔ)；三是各種智能算法的相互融合，相互補 充，增強(qiáng)彼此的能力，從而獲得更有力的表示和解決實際問題的能力。至今新的 智能算法不斷涌現(xiàn)，計算智能應(yīng)用領(lǐng)域越來越廣，從工程優(yōu)化、模式識別、智能 控制、經(jīng)濟(jì)管理到網(wǎng)絡(luò)智能自動化等領(lǐng)域都取得了顯著的研究成果與應(yīng)用。 本文主要就進(jìn)化計算中的遺傳算法和群體智能中的蟻群優(yōu)化算法進(jìn)行研究 與應(yīng)用。 海南大學(xué)碩士學(xué)位論文1 序言 1 2 2 進(jìn)化計算與群體智能 ( 1 ) 進(jìn)化計算 進(jìn)化計算( e v o l u t i o n a r yc o m p u t i n g ) 是基于自然選擇和自然遺傳等生物進(jìn)化 機(jī)制的一種模擬生物進(jìn)化過程的智能搜索算法。它以生物界的“優(yōu)勝劣態(tài)、適者 生存 作為算法的進(jìn)化規(guī)則，結(jié)合達(dá)爾文的自然選擇與孟德爾的遺傳變異理論， 將生物進(jìn)化中的四個基本形式：繁殖、變異、競爭和選擇引入到算法過程中。進(jìn) 化計算采用簡單的編碼技術(shù)，并對一組編碼進(jìn)行遺傳操作和優(yōu)勝劣汰的自然選 擇，從而達(dá)到指導(dǎo)學(xué)習(xí)和確定搜索方向的目的。由于它采用基于種群的方式組織 啟發(fā)式搜索，從而具有自學(xué)習(xí)、自組織、自適應(yīng)等智能特征。 2 0 世紀(jì)6 0 _ _ 7 0 年代，進(jìn)化計算作為一個新興的交叉學(xué)科并未受到普遍的重 視。自從8 0 年代以來，人們逐漸認(rèn)識到傳統(tǒng)優(yōu)化方法的困境，并且隨著計算機(jī) 處理速度的提高和并行技術(shù)的發(fā)展以及進(jìn)化算法本身的不斷發(fā)展和成功應(yīng)用，進(jìn) 化計算在理論和實踐兩個方面都取得了長足的發(fā)展，現(xiàn)在已經(jīng)成為人工智能領(lǐng)域 中的一個重要分支，在工程技術(shù)、社會經(jīng)濟(jì)和科學(xué)計算等諸多領(lǐng)域表現(xiàn)出了良好 的應(yīng)用前景。 目前研究的進(jìn)化計算技術(shù)主要有四種算法：遺傳算法( g e n e t i ca l g o r i t h m ) 、 進(jìn)化規(guī)劃( e v o l u t i o n a r yp r o g r a m m i n g ) 、進(jìn)化策略( e v o l u t i o n a r ys t r a t e g y ) 和遺傳規(guī)劃 ( g e n e t i cp r o g r a m m i n g ) 。前三種算法是彼此獨立發(fā)展起來的，最后一種是在遺傳 算法的基礎(chǔ)上發(fā)展起來的一個分支【5 1 。遺傳算法及其在優(yōu)化問題中的應(yīng)用是本文 的研究重點之一。 ( 2 ) 群體智能 自然界存在著很多讓人嘆為觀止的生物群體智能現(xiàn)象，如蟻群、魚群和鳥群 等。這些群居生物所體現(xiàn)的社會性和分布式智能實現(xiàn)模式給了人類很大的啟發(fā)。 群體智能( s w a r mi n t e l l i g e n c e ) 是受社會性昆蟲的啟發(fā)，通過對其行為的模擬 形成一系列用于解決復(fù)雜問題的新方法。由單個復(fù)雜個體完成的任務(wù)可由大量簡 單的個體組成的群體合作完成，而后者往往更具有靈活性、魯棒性和經(jīng)濟(jì)上的優(yōu) 勢。群體智能利用群體優(yōu)勢，在沒有集中控制和全局模型的前提下，依靠群體中 眾多智能個體相互之間的簡單合作進(jìn)行分布式的問題求解，為尋找復(fù)雜問題解決 方案提供了新的思路。群體智能是指群體中眾多簡單個體通過相互之間的簡單合 作表現(xiàn)出來的智能行為，“簡單個體”是只具有簡單能力或智能的單個個體，而 “簡單合作”是指個體與其鄰近個體進(jìn)行某種簡單的直接通訊或通過改變環(huán)境因 素間接與其他個體通訊，從而實現(xiàn)相互影響和協(xié)同合作 6 1 。 群體智能方法作為一種新興的具有并行性、分布式和自適應(yīng)性的隨機(jī)啟發(fā)式 搜索算法，自從2 0 世紀(jì)8 0 年代出現(xiàn)以來，引起了多個學(xué)科領(lǐng)域研究人員的關(guān)注， 海南大學(xué)碩士學(xué)位論文1 序言 已經(jīng)成為人工智能以及經(jīng)濟(jì)、社會、生物等交叉學(xué)科的熱點和前沿領(lǐng)域。目前群 體智能主要有兩種算法模式，分別是蟻群優(yōu)化( a n tc o l o n yo p t i m i z a t i o 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 ) 。其中，蟻群優(yōu)化算法及其在優(yōu)化問題中的應(yīng) 用是本文的研究重點之一。 1 3 論文主要研究內(nèi)容和結(jié)構(gòu)安排 本文主要內(nèi)容是研究進(jìn)化計算和群體智能中具有代表性的算法一遺傳算法 和蟻群優(yōu)化算法的原理、特點及其實現(xiàn)，對算法進(jìn)行改進(jìn)，并與其他算法進(jìn)行融 合，然后應(yīng)用于求解w s n 中一些優(yōu)化問題，并通過算法仿真進(jìn)行結(jié)果分析。本 文余下章節(jié)的內(nèi)容和結(jié)構(gòu)安排如下： 第2 章，簡單介紹了兩種在以后章節(jié)涉及到的計算智能方法：遺傳算法和蟻 群優(yōu)化算法。 第3 章，簡單介紹了w s n 的結(jié)構(gòu)、特征和一些關(guān)鍵技術(shù)，為后面章節(jié)應(yīng)用 計算智能方法求解w s n 具體優(yōu)化問題作基礎(chǔ)。 第4 章，針對現(xiàn)有w s n 分簇算法存在的問題，充分考慮簇內(nèi)鄰居節(jié)點的能 量和距離分布信息，應(yīng)用遺傳算法優(yōu)化分簇過程，從而改善分簇算法性能，以均 衡簇內(nèi)能量消耗，提高系統(tǒng)能量效率，最后給出算法仿真，并分析結(jié)果。 第5 章，對w s n 節(jié)點覆蓋問題進(jìn)行了描述，針對其具有多目標(biāo)優(yōu)化的特點， 應(yīng)用基于p a r e t o 排序的遺傳算法來求解此問題，并考慮群體多樣性和p a r e t o 最 優(yōu)解的性能，采取一些措施對算法進(jìn)行改進(jìn)，最后給出算法仿真，并分析結(jié)果。 第6 章，針對w s n 路由問題，結(jié)合w s n 層次型路由算法特點，充分考慮 傳感器節(jié)點剩余能量和傳輸能耗，設(shè)計了一種基于蟻群優(yōu)化的分層路由算法，改 善w s n 簇頭多跳路由性能，均衡網(wǎng)絡(luò)節(jié)點能量消耗，最后給出算法仿真，并分 析結(jié)果。 總結(jié)與展望部分，對本文所做的工作進(jìn)行了總結(jié)，并給出了還需進(jìn)一步完善 的工作和設(shè)想。 4 海南大學(xué)碩士學(xué)位論文 2 計算智能方法概述 2 計算智能方法概述 計算智能作為新興的智能處理技術(shù)，是一種借鑒、模擬自然現(xiàn)象或生物體各 種原理及機(jī)理而開發(fā)的并具有自適應(yīng)環(huán)境能力的計算方法，具有分布、并行、仿 生、自學(xué)習(xí)、自組織、自適應(yīng)等優(yōu)點，其在諸多領(lǐng)域都受到越來越多的關(guān)注。下 面，本章將本文所要研究與應(yīng)用的兩種計算智能方法作為代表，對遺傳算法和蟻 群優(yōu)化算法的相關(guān)理論及特點進(jìn)行簡要概括。 2 1 遺傳算法 遺傳算法起源于2 0 世紀(jì)6 0 年代，密歇根大學(xué)教授h o l l a n d 在研究自然和人 工系統(tǒng)的自適應(yīng)行為的過程中，意識到用群體方法搜索以及選擇、交換等操作策 略的重要性，并開創(chuàng)了基因操作，提出了重要的模式理論和二進(jìn)制編碼。7 0 年 代d ej o n g 基于遺傳算法的思想在計算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化的實 驗。8 0 年代g o l d b e r g 在一系列研究工作基礎(chǔ)上進(jìn)行歸納總結(jié)，形成了遺傳算法 的基本框架。遺傳算法是模擬生物在自然環(huán)境中遺傳和進(jìn)化過程而形成的一種自 適應(yīng)全局優(yōu)化概率搜索算法，進(jìn)入9 0 年以來，以不確定性、非線性、時間不可 逆為內(nèi)涵，遺傳算法在許多領(lǐng)域得到了廣泛應(yīng)用。 2 1 1 遺傳算法的基本原理 遺傳算法是以自然選擇和遺傳變異理論為基礎(chǔ)，將生物進(jìn)化過程中適者生存 規(guī)則與群體內(nèi)部染色體的隨機(jī)信息交換機(jī)制相結(jié)合的搜索算法。在利用遺傳算法 求解問題時，問題的每個可能解都被編碼成一個染色體，即個體，若干個個體構(gòu) 成了群體。遺傳算法總是從一組隨機(jī)產(chǎn)生的初始解( 群體) 開始搜索過程，根據(jù) 預(yù)定的目標(biāo)函數(shù)對每個個體進(jìn)行評價，給出一個適應(yīng)度值。根據(jù)每個個體適應(yīng)度 值，選擇個體用來復(fù)制下一代。選擇操作體現(xiàn)了適者生存理論，適應(yīng)度值高的個 體被選擇用來復(fù)制，而適應(yīng)度值低的個體則被淘汰。被選擇出來的個體經(jīng)過交叉 和變異操作重組為新的一代，這一新群體由于繼承了上一代的一些優(yōu)良性狀，因 而在性能上優(yōu)于上一代，這樣逐步朝著更優(yōu)解的方向進(jìn)化。因此遺傳算法可以看 作是一個由初始解組成的群體逐步向最優(yōu)解或近似最優(yōu)解群體搜索的迭代過程。 圖2 1 描述了遺傳算法的流程。 海南大學(xué)碩士學(xué)位論文2 計算智能方法概述 2 1 2 遺傳算法的構(gòu)成要素 圖2 1 遺傳算法流程圖 1 染色體編碼方法 遺傳算法操作的對象是表示個體的染色體，因此編碼是設(shè)計遺傳算法的一 個關(guān)鍵步驟，它是把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜 索空間的轉(zhuǎn)換方法，它不僅決定個體染色體的排列方式，還決定個體從搜索空間 的基因型變換到解空間的表現(xiàn)型時的解碼方法。對于一個具體的應(yīng)用問題，如何 設(shè)計一種好的編碼方案，不僅影響到具體的遺傳算子運算方法，而且在很大程度 上影響著遺傳進(jìn)化操作的效率。d ej o n g 曾提出了兩條操作性較強(qiáng)的實用編碼原 則川。 原則一：應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階、短定義長度模 式的編碼方式。 原n - ：應(yīng)使用能使問題得到自然表示或描述的具有最小編碼字符集的編 碼方案。 海南大學(xué)碩士學(xué)位論文2 計算智能方法概述 這兩條原則只是給出了設(shè)計編碼方法時的指導(dǎo)性意見，而在實際應(yīng)用中， 還須對編碼方法、遺傳操作和解碼方法等統(tǒng)一考慮。目前人們已經(jīng)提出的多種不 同的編碼方法可以分為三大類：二進(jìn)制編碼方法、浮點數(shù)編碼方法、符號編碼方 法。 ( 1 ) 二進(jìn)制編碼 二進(jìn)制編碼是最常見的編碼方式，它所使用的編碼符號集是由二進(jìn)制符號 0 和l 組成的二值符號集 o ，1 ) ，它所構(gòu)成的個體基因型是一個二進(jìn)制編碼符號 串。一般來說，二進(jìn)制編碼、解碼操作簡單易行，符合最小字符集編碼原則，也 使得交叉、變異等遺傳操作便于實現(xiàn)。 ( 2 ) 浮點數(shù)編碼 對于高維、高精度要求的連續(xù)優(yōu)化問題，使用二進(jìn)制編碼常常是不方便的。 二進(jìn)制編碼存在著連續(xù)函數(shù)離散化的映射誤差，個體編碼串長度較短時，可能達(dá) 不到精度要求，而個體編碼串的長度較長是，雖能提高編碼精度，但會使遺傳算 法的搜索空間急劇擴(kuò)大。同時，二進(jìn)制編碼不便于反映所求問題的特定知識，這 樣也就不便于開發(fā)針對專門問題的遺傳算子。針對二進(jìn)制編碼的這些缺點，人們 提出了浮點數(shù)編碼方法。采用浮點數(shù)編碼時，個體的每個基因值用某一范圍內(nèi)的 一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。 ( 3 ) 符號編碼 符號編碼是指個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有 代碼含義的符號集。這個符號集可以是一個字母表，也可以是一個數(shù)字符號表， 還可以是一個代碼表。 2 個體適應(yīng)度 遺傳算法求解問題時，首先要確定問題的目標(biāo)函數(shù)和決策變量，然后使用 所求問題的目標(biāo)函數(shù)就可得到下一步的有關(guān)搜索信息。確定一個適應(yīng)度函數(shù)，將 個體目標(biāo)函數(shù)值轉(zhuǎn)換為個體適應(yīng)度值，就是使用目標(biāo)函數(shù)值的體現(xiàn)。遺傳算法采 用適應(yīng)度來度量群體中各個個體在迭代過程中有可能達(dá)到或接近于找到最優(yōu)解 的優(yōu)良程度。適應(yīng)度值高的個體以較高的概率遺傳到下一代，而適應(yīng)度值較低的 個體遺傳到下一代的概率就相對小一些。 個體適應(yīng)度的確定通常反映了應(yīng)用者對個體的評價標(biāo)準(zhǔn)和搜索原則，在進(jìn) 化的不同階段可以根據(jù)實際情況作出一些調(diào)整。例如，在算法初期，由于個體差 異比較明顯，某些優(yōu)秀個體會迅速在后代中積累起來，導(dǎo)致群體多樣性的喪失， 這時就應(yīng)壓縮優(yōu)秀個體的適應(yīng)度，縮小差異；相反，到了后期，由于群體中個體 適應(yīng)度差異不大，就要擴(kuò)大差異。 3 遺傳操作 海南大學(xué)碩士學(xué)位論文 2 計算智能方法概述 遺傳操作是模擬生物基因的操作，它根據(jù)個體的適應(yīng)度對其施加一定的操 作，從而實現(xiàn)優(yōu)勝劣汰的進(jìn)化過程。遺傳操作包括三個基本遺傳算子：選擇、交 海南大學(xué)碩士學(xué)位論文2 計算智能方法概述 因座的其他等位基因來替換，從而產(chǎn)生一個新個體。 變異算子本身是一種局部隨機(jī)搜索，能夠避免由于選擇和交叉算子而引起 的某些信息的永久性丟失，保證了遺傳算法的有效性，同時使得算法能保持群體 的多樣性，防止出現(xiàn)早熟現(xiàn)象。交叉算子與變異算子互相配合、共同完成對搜索 空間的全局搜索和局部搜索，從而使得遺傳算法能夠以良好的搜索性能完成最優(yōu) 化問題的尋優(yōu)過程。 最簡單的變異算子是基本位變異，是指對個體編碼串中以變異概率p m 隨機(jī) 指定的某一位或某幾位基因座上的基因值作變異運算。此外，還有均勻變異、邊 界變異、高斯變異等變異算子。在變異算子中，變異概率p m 通常較小，一般取 值為0 0 0 1 4 ) 0 1 。 4 遺傳算法的運行參數(shù) 在遺傳算法運行過程中，存在著對其性能產(chǎn)生重大影響的一些參數(shù)，這些 參數(shù)在初始階段或群體進(jìn)化過程中需要合理的選擇和控制，以使遺傳算法以最佳 的搜索性能達(dá)到最優(yōu)解。運行參數(shù)主要有個體編碼串長度l 、群體大小m 、交叉 概率p c 、變異概率p m 、終止代數(shù)t 等。這些參數(shù)的選擇對算法運行性能影響較 大，需要認(rèn)真衡量【9 】。 ( 1 ) 編碼串長度l ：l 的選擇取決于特定問題解的精度和決策變量的個數(shù) 等。編碼串越長，算法計算時間就會越多，為了提高計算效率，也可以使用可變 長度的編碼或在當(dāng)前所達(dá)到的較小可行域內(nèi)重新編碼。 ( 2 ) 群體大小m ：即群體中所含個體的數(shù)量。當(dāng)m 取值較小時，可提高 遺傳算法的運算速度，但卻降低了群體的多樣性，可能會引起算法的早熟現(xiàn)象； 而當(dāng)m 取值較大時，又會降低遺傳算法的運行效率，一般取為2 0 1 0 0 。 ( 3 ) 交叉概率p 。：交叉概率越高，群體中新結(jié)構(gòu)的引入越快，但已獲得的 優(yōu)良基因結(jié)構(gòu)的丟失速度也相應(yīng)升高；交叉概率太低又會使新個體的產(chǎn)生速度過 慢。一般p 。取值為0 鯽9 。 ( 4 ) 變異概率p m ：變異操作是保持群體多樣性的有效手段，然而變異概 率不能過高，如果p m 0 5 ，遺傳算法就退化為隨機(jī)搜索了。p m 通常取值為 0 0 0 1 - - 4 ) o l 。 ( 5 ) 終止代數(shù)t ：終止代數(shù)表示遺傳算法運行到指定的進(jìn)化代數(shù)t 之后就 停止運行，并將當(dāng)前群體中的最佳個體作為所求問題的最優(yōu)解輸出。t 通常取值 為1 0 0 - - - 5 0 0 。 2 1 3 遺傳算法的數(shù)學(xué)機(jī)理 雖然遺傳算法的計算過程和形式簡單，但是其運行機(jī)理非常復(fù)雜。隨著遺傳 海南大學(xué)碩士學(xué)位論文 2 計算智能方法概述 算法在復(fù)雜優(yōu)化問題和實際工程設(shè)計中的應(yīng)用，人們?yōu)榱烁玫胤治鏊惴ǖ男?質(zhì)，對算法的工作機(jī)理、數(shù)學(xué)基礎(chǔ)等進(jìn)行了深入的研究和認(rèn)識。 1 模式定理【1 0 l 模式是在某些確定位置上取相同字符的字符串集合。例如，在二進(jìn)制編碼串 中，模式是基于三個字符集( 0 ，1 ，) 的字符串，符號葉七表任意字符，可為0 ， 也可為l ，模式幸幸0 0 描述了一個后兩個位置都為0 的子集 o o o o ，0 1 0 0 ，1 0 0 0 ，1 1 0 0 。 因此，可以把模板看成一個相似性模板，而遺傳算法的搜素過程實際上就是對相 似模板的搜索過程。在某個模式中，確定字符的個數(shù)稱為模式的階，其最左端確 定字符到最右端確定字符間的距離稱為模式的定義距。例如模式0 1 1 0 0 * 的階 是5 ，定義距是5 。引入下列符號： 脅某個模式； z ：第價字符串( 解) 的適應(yīng)度； ( f ) ：第f 代群體的平均適應(yīng)度； f ( h ，f ) ：模式臃第玳群體的平均適應(yīng)度； ( 日，+ 1 ) ：由第f 代模式硼勺某個解往第f + l 代生成的后代數(shù)的期望值； n ( h ，t ) - 第玳屬于模式肭解的個數(shù)； 6 ( 日) ：腳勺定義距； d ( 日) ：肭階。 首先考慮選擇算子的作用。在基本遺傳算法中，選擇是采用按適應(yīng)度值大小 比例的原則，第i 個個體經(jīng)選擇算子的作用在下一代繼續(xù)存在的個數(shù)的期望值為 刀( z 藝力，因 f ( h , t ) 2 高n1 - 1t ，一 i 一。 貝i j n ( h ，+ 1 ) = 以( 日，r ) 廠( 日，) ( ，) ( 2 1 ) ( 2 2 ) 上述等式表明，選擇算子的作用將使適應(yīng)度高于( 低于) 平均水平的模式在 代代相傳時增大( 減小) 其容量。 接著考慮交叉算子的作用。若不進(jìn)行交叉或雖交叉但交叉點落在模式最左、 右兩端確定字符所處位置之外，該模式在下一代顯然能保存下來。因此，模式日 在下一代得以繼續(xù)存在的概率應(yīng)滿足： 只l p c 8 ( h ) ( l 1 ) ( 2 3 ) 于是，綜合考慮選擇和交叉的作用，有 一|一 n ( h ，r + 1 ) n ( h ，f ) f ( h ，f ) 【1 一只8 ( h ) ( l - 1 ) 廠o ) ( 2 4 ) 最后，考慮變異算子。當(dāng)模式日中0 ( 日) 個確定位都存活時，模式日被保存 海南大學(xué)碩士學(xué)位論文2 計算智能方法概述 下來，其存活概率為： ( 1 一己) 伙片1 - o ( h ) 巴( 己 ，( f ，j = 0 l ，2 ，一， 一1 ) 表示城市間的邊，d = 4 ，) 表示兩城市 f ，j 間的歐氏距離，構(gòu)造解的過程即搜索權(quán)重最小的h a m i l t o n i a n 圈。匆( f ) 表示t 時刻位于城市f 的螞蟻個數(shù)，m = 6 f ( f ) 為螞蟻的總數(shù)。乃( f ) 表示f 時刻邊f(xié) ，歹上 的信息素量，r u ( o ) = ( 為常數(shù)) 。隨著時間的推移，新的信息素加進(jìn)來，舊的 信息素要揮發(fā)，夕【0 , 1 】表示信息素?fù)]發(fā)系數(shù)。當(dāng)所有螞蟻完成一次周游后，各 邊上的信息素調(diào)整規(guī)則如下： r u ( t + 刀) = ( 1 一, o ) r o ( t ) + ( 2 9 ) 一 肼 一 乃= 勺七 k = l ( 2 1 0 ) 其中，乃( ，) 表示本次周游中路徑f ，上的信息素增量，初始時刻，( f ) = 0 。 0 表示第k 只螞蟻在周游過程中釋放在邊i