【正文】 題進(jìn)行算法設(shè)計(jì)。利用多目標(biāo)進(jìn)化算法的特點(diǎn)，針對(duì)我們建立的模型，從不同出發(fā)點(diǎn)考慮設(shè)計(jì)算法，得出不同覆蓋水平和網(wǎng)絡(luò)壽命的規(guī)劃方案。依次進(jìn)行分析和學(xué)習(xí)，找到適合的算法設(shè)計(jì)過(guò)程，進(jìn)行仿真環(huán)境和參數(shù)的設(shè)定，對(duì)得到的仿真結(jié)果進(jìn)行分析和比較，得出結(jié)論。本文分為四大章。第一章緒論，闡述了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的研究背景及意義，國(guó)內(nèi)外發(fā)展水平概況，以及本文對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)主要的研究目標(biāo)和工作。第二章進(jìn)行了對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)進(jìn)行了模型分析，分別包括無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的簡(jiǎn)介、無(wú)線(xiàn)傳感器動(dòng)態(tài)覆蓋的評(píng)價(jià)標(biāo)準(zhǔn)和概率模型。第三章先描述了多目標(biāo)進(jìn)化算法的概念和算法過(guò)程，然后依次介紹了四種多目標(biāo)進(jìn)化算法并對(duì)網(wǎng)絡(luò)覆蓋度進(jìn)行建模和算法分析。第四章選取了基于多目標(biāo)遺傳算法的進(jìn)化算法對(duì)WSN進(jìn)行算法設(shè)計(jì)，得出仿真結(jié)果并對(duì)結(jié)果進(jìn)行分析比對(duì)，從而得出結(jié)論。3第2章 WSN網(wǎng)絡(luò)覆蓋模型分析第2章WSN網(wǎng)絡(luò)覆蓋模型分析由傳感器技術(shù)、分布式信息處理、嵌入式計(jì)算技術(shù)、無(wú)線(xiàn)通信技術(shù)以及微機(jī)電系統(tǒng)(MEMS)這五項(xiàng)技術(shù)結(jié)合而形成的一種全新的信息獲取與處理技術(shù)，就叫做無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)。由傳感器節(jié)點(diǎn)、匯聚節(jié)點(diǎn)（Sink）、后臺(tái)管理中心三部分組成了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)，如圖21所示。傳感器節(jié)點(diǎn)收集有關(guān)通過(guò)其他傳感器節(jié)點(diǎn)的多跳傳輸簡(jiǎn)單的數(shù)據(jù)處理環(huán)境的信息，監(jiān)測(cè)數(shù)據(jù)可以在傳輸過(guò)程中被處理的多個(gè)節(jié)點(diǎn)，通過(guò)多跳中繼數(shù)據(jù)到匯聚節(jié)點(diǎn)將最后直接發(fā)送到管理中心或?qū)崿F(xiàn)傳感器網(wǎng)絡(luò)通過(guò)互聯(lián)網(wǎng)背景交通管理中心，如通信衛(wèi)星和GPRS，從整個(gè)區(qū)域?qū)?shù)據(jù)發(fā)送到集中處理的后臺(tái)管理中心。用戶(hù)管理和傳感器網(wǎng)絡(luò)管理中心通過(guò)后臺(tái)，發(fā)布控制任務(wù)的配置和收集監(jiān)測(cè)數(shù)據(jù)，以監(jiān)控整個(gè)網(wǎng)絡(luò)。圖21無(wú)線(xiàn)傳感器網(wǎng)絡(luò)結(jié)構(gòu)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)具有很多鮮明的特點(diǎn)：（1）網(wǎng)絡(luò)傳感器的規(guī)模巨大。無(wú)線(xiàn)傳感器網(wǎng)路由數(shù)千個(gè)微小的傳感器組成，所以通常主要依靠增加的不是單個(gè)設(shè)備的能力，而是但大規(guī)模的、冗余的嵌入式設(shè)備協(xié)同工作，來(lái)提高系統(tǒng)的可靠性和穩(wěn)定性。（2）傳感器節(jié)點(diǎn)工作在無(wú)人值守的環(huán)境。微型傳感器節(jié)點(diǎn)通常密集分布在需要監(jiān)測(cè)的區(qū)域環(huán)境中，由于規(guī)模巨大，這是不可能人工照顧每個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)系統(tǒng)往往在無(wú)人值守的狀態(tài)下工作。每個(gè)節(jié)點(diǎn)只能依靠自己或獨(dú)立獲得能源（電池，太陽(yáng)能電池）和電源。由此產(chǎn)生的能量是最重要的限制瓶頸，阻礙了無(wú)線(xiàn)傳感器網(wǎng)絡(luò)和應(yīng)用的發(fā)展方向之一。（3）無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是一個(gè)以數(shù)據(jù)為中心的網(wǎng)絡(luò)?；谌蝿?wù)網(wǎng)絡(luò)是一個(gè)傳感器網(wǎng)絡(luò)，其核心是感知信息的數(shù)據(jù)，而不是網(wǎng)絡(luò)硬件，這是從傳統(tǒng)互聯(lián)網(wǎng)，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的重要特征不同。由于傳感器節(jié)點(diǎn)隨機(jī)部署的傳感器網(wǎng)絡(luò)是節(jié)點(diǎn)數(shù)目之間完全動(dòng)態(tài)的組成，我們會(huì)問(wèn)一個(gè)具體的方向是什么在一個(gè)角落里的溫度，但溫度不會(huì)。所需的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)以數(shù)據(jù)為中心的功能設(shè)計(jì)必須檢測(cè)數(shù)據(jù)管理和處理中心，它通常說(shuō)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)是一個(gè)以數(shù)據(jù)為中心的網(wǎng)絡(luò)。（4）動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)?。移?dòng)終端可以在任何高速網(wǎng)絡(luò)和任意方式移動(dòng)，可隨時(shí)關(guān)閉；無(wú)線(xiàn)收發(fā)裝置的天線(xiàn)類(lèi)型多種多樣，與發(fā)射功率帶來(lái)的變化中的能量變化；再加上廣播的頻道，地形和氣候的方式和等因素可能會(huì)發(fā)生在由網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化和改變所形成的任何無(wú)線(xiàn)電信道的移動(dòng)終端的沖擊速度的組合之間的相互干擾是難以預(yù)測(cè)的。 WSN的動(dòng)態(tài)覆蓋問(wèn)題覆蓋問(wèn)題是指:在相關(guān)資源受到限制的情況下,采取傳感器節(jié)點(diǎn)布置和路由選擇等方法,優(yōu)化分配各種資源,最終使感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量得到改善。通常情況下，網(wǎng)絡(luò)覆蓋度是評(píng)價(jià)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的探測(cè)質(zhì)量的一個(gè)最重要的標(biāo)準(zhǔn)。從目前的研究看出，評(píng)價(jià)方式有障礙覆蓋度、區(qū)域覆蓋度和點(diǎn)覆蓋度，我們是從這三個(gè)方式來(lái)評(píng)價(jià)一個(gè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的探測(cè)質(zhì)量。本文就礙覆蓋度、區(qū)域覆蓋度和點(diǎn)覆蓋度會(huì)一一給出模型并進(jìn)行分析，最終會(huì)選擇一個(gè)適合的覆蓋度模型來(lái)評(píng)價(jià)無(wú)線(xiàn)傳感網(wǎng)絡(luò)的探測(cè)效果。由于傳感器的電源能量有限，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)研究的核心問(wèn)題就是如何節(jié)省無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的工作過(guò)程中能量，最大化網(wǎng)絡(luò)的運(yùn)行壽命。為傳感器節(jié)點(diǎn)收集有關(guān)通過(guò)其他傳感器節(jié)點(diǎn)的多跳傳輸簡(jiǎn)單的數(shù)據(jù)處理環(huán)境的信息，監(jiān)測(cè)數(shù)據(jù)可以在傳輸過(guò)程中被處理的多個(gè)節(jié)點(diǎn)，通過(guò)多跳中繼數(shù)據(jù)到宿節(jié)點(diǎn)將最后直接發(fā)送到管理中心或?qū)崿F(xiàn)傳感器網(wǎng)絡(luò)通過(guò)互聯(lián)網(wǎng)背景交通管理中心，如通信衛(wèi)星和GPRS，從整個(gè)區(qū)域?qū)?shù)據(jù)發(fā)送到集中處理的后臺(tái)管理中心。用戶(hù)管理和傳感器網(wǎng)絡(luò)管理中心通過(guò)后臺(tái)，發(fā)布控制任務(wù)的配置和收集監(jiān)測(cè)數(shù)據(jù)，以監(jiān)控整個(gè)網(wǎng)絡(luò)。在滿(mǎn)足覆蓋率要求的前提下，科學(xué)合理的規(guī)劃傳感器的激活順序，才能盡量延長(zhǎng)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的使用壽命這就是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的動(dòng)態(tài)覆蓋問(wèn)題。 網(wǎng)絡(luò)覆蓋度的評(píng)價(jià)標(biāo)準(zhǔn)首先，我們來(lái)定義一下網(wǎng)絡(luò)覆蓋度。網(wǎng)絡(luò)覆蓋度可以分為以下三種，即障礙覆蓋度、區(qū)域覆蓋度以及點(diǎn)覆蓋度。我們一一解釋?zhuān)缦拢海?）障礙覆蓋度障礙覆蓋度指的是通過(guò)障礙物而未被發(fā)現(xiàn)的概率，圖22是一個(gè)障礙覆蓋度的示意圖，其中出發(fā)點(diǎn)和終點(diǎn)分別在矩形區(qū)域上下的邊上。圖22障礙覆蓋度圖（2） 區(qū)域覆蓋度圖23區(qū)域覆蓋度圖區(qū)域覆蓋度是可監(jiān)控區(qū)域占整個(gè)網(wǎng)絡(luò)區(qū)域的比重。區(qū)域覆蓋度C=N1/N2，N1為傳感器所覆蓋的目標(biāo)區(qū)域的面積，N2為目標(biāo)區(qū)域的總面積，n各節(jié)點(diǎn)處于工作狀態(tài)。圖23是隨機(jī)部署的傳感器覆蓋整個(gè)矩形區(qū)域的示意圖，黑色圓點(diǎn)是激活的傳感器，空心圓是處于休眠狀態(tài)的傳感器。（3） 點(diǎn)覆蓋度點(diǎn)覆蓋度是指網(wǎng)絡(luò)所能探測(cè)到的點(diǎn)的數(shù)目占整個(gè)需探測(cè)區(qū)域點(diǎn)的數(shù)目的比重。點(diǎn)覆蓋度C=N1/N2，其中N1是可以被探測(cè)到的點(diǎn)數(shù)，N2是總的需要探測(cè)的點(diǎn)數(shù)。下圖是點(diǎn)覆蓋度的示意圖，其中圓點(diǎn)是隨機(jī)布置的傳感器節(jié)點(diǎn)，黑色圓點(diǎn)是處于激活狀態(tài)，空心圓點(diǎn)是處于休眠狀態(tài)，空心方格是需要被覆蓋探測(cè)的點(diǎn)集。圖24點(diǎn)覆蓋度圖由圖中我們可以看出，黑色圓點(diǎn)處于激活狀態(tài)時(shí)三個(gè)圓的面積就把所有的傳感器包含進(jìn)去了，覆蓋度就是100%。我們通常把探測(cè)的目標(biāo)區(qū)域離散化為格點(diǎn)，從而將區(qū)域覆蓋問(wèn)題轉(zhuǎn)化為點(diǎn)覆蓋問(wèn)題。本文的模型采用了格點(diǎn)模型，在考慮點(diǎn)覆蓋時(shí)，把要覆蓋的區(qū)域分成許多小方格用每個(gè)小方格的中心點(diǎn)來(lái)代表這個(gè)方格區(qū)域，若點(diǎn)被覆蓋，則這個(gè)小方格區(qū)域便被覆蓋，因?yàn)闊o(wú)線(xiàn)傳感器網(wǎng)絡(luò)在應(yīng)用中，通常會(huì)布置或撒播大量傳感器節(jié)點(diǎn)在探測(cè)區(qū)域，傳感器密度比較高，同時(shí)若我們劃分的網(wǎng)格很密集的話(huà)，每個(gè)點(diǎn)也能代表這個(gè)小方格的探測(cè)狀況，所以這種假設(shè)是合理的。這種方式同時(shí)也把所監(jiān)測(cè)的區(qū)域離散化，有利于建模，每個(gè)傳感器打開(kāi)會(huì)覆蓋一部分點(diǎn)。圖25是一個(gè)傳感器有效覆蓋范圍示意圖：圖25傳感器有效覆蓋范圍示意圖 傳感器探測(cè)概率模型在二維網(wǎng)格模型中，傳感器在格點(diǎn)的位置，網(wǎng)格給傳感器網(wǎng)絡(luò)的探測(cè)范圍提供了一個(gè)度量標(biāo)準(zhǔn)。每一個(gè)傳感器的探測(cè)范圍用以傳感器為圓心的圓來(lái)表示圓的半徑就是傳感器的探測(cè)半徑。我們把傳感器si放置在格點(diǎn)（x,y）,若覆蓋區(qū)域的點(diǎn)p坐標(biāo)為（i,j）,我們就用s與p之間的歐氏距離d(s,p)=來(lái)表示s和p的距離。我們選擇概率模型來(lái)進(jìn)行研究，概率模型就是傳感器s有效探測(cè)目標(biāo)點(diǎn)P的概率隨著s和p之間的歐氏距離d(s,p)的增大而指數(shù)級(jí)減小。在概率模型下，若存在多個(gè)傳感器同時(shí)工作，則一個(gè)目標(biāo)點(diǎn)p被有效探測(cè)的概率是幾個(gè)傳感器共同作用的結(jié)果。我們用c(s,p)為傳感器s對(duì)格點(diǎn)p的探測(cè)概率，那么我們定義m(s,p)=1c(s,p)，m(s,p)稱(chēng)為丟失概率，設(shè)S={s1,s2…sn}為無(wú)線(xiàn)傳感器集合，傳感器si對(duì)目標(biāo)點(diǎn)p(xp,yp)的檢測(cè)概率為：公式21其中，d（si，p）為傳感器節(jié)點(diǎn)si與目標(biāo)點(diǎn)p的歐氏距離。Re是傳感器節(jié)點(diǎn)測(cè)量可靠性參數(shù)。整個(gè)監(jiān)測(cè)區(qū)域內(nèi)的傳感器節(jié)點(diǎn)對(duì)目標(biāo)節(jié)點(diǎn)p同時(shí)進(jìn)行檢測(cè)的聯(lián)合檢測(cè)概率為： 公式22我們用在每個(gè)打開(kāi)的時(shí)間段，覆蓋的點(diǎn)數(shù)/所有點(diǎn)數(shù)即來(lái)定義為這個(gè)時(shí)間段的網(wǎng)絡(luò)覆蓋度，即。從網(wǎng)絡(luò)覆蓋度的實(shí)際考慮，一個(gè)網(wǎng)絡(luò)工作的過(guò)程是許多個(gè)時(shí)間段之和，為了使網(wǎng)絡(luò)覆蓋度在各個(gè)時(shí)間段盡可能均衡，考察網(wǎng)絡(luò)的覆蓋質(zhì)量就用它在各個(gè)時(shí)間段的覆蓋度的最小值作為整個(gè)網(wǎng)絡(luò)的覆蓋度，即： 公式23其中，covi為每一時(shí)間段網(wǎng)絡(luò)的覆蓋率；為點(diǎn)的總數(shù)目量；為在ti時(shí)間段內(nèi)網(wǎng)絡(luò)被覆蓋的覆蓋度。從實(shí)際出發(fā)，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋度如果太低了，就起不到作用，比如無(wú)線(xiàn)傳感器網(wǎng)絡(luò)覆蓋度太低，就對(duì)整個(gè)覆蓋區(qū)域監(jiān)測(cè)弱到無(wú)法檢測(cè)，這樣就失去了監(jiān)測(cè)的意義。所以我們要設(shè)置一個(gè)覆蓋度門(mén)檻為，使得各個(gè)時(shí)間段的覆蓋度都不能小于。不同的打開(kāi)組合對(duì)各個(gè)時(shí)間段的覆蓋度是有影響的，因此，構(gòu)建無(wú)線(xiàn)傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問(wèn)題模型如下： 公式24其中：T是網(wǎng)絡(luò)能維持的時(shí)間段數(shù)是最小覆蓋度門(mén)檻；為每一時(shí)間段網(wǎng)絡(luò)的覆蓋率；為點(diǎn)的總數(shù)目量；為在ti時(shí)間段內(nèi)網(wǎng)絡(luò)被覆蓋的覆蓋度。當(dāng)網(wǎng)絡(luò)從部署開(kāi)始到網(wǎng)絡(luò)不工作的時(shí)間跨度就被稱(chēng)為無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生存周期。但是我們又考慮到非功能性網(wǎng)絡(luò)的具體應(yīng)用時(shí)，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的壽命可以是死亡的時(shí)間或范圍發(fā)生的損失的第一個(gè)跨度。在某些情況下，延長(zhǎng)的所有節(jié)點(diǎn)的存活是必需的，只要死亡的一個(gè)節(jié)點(diǎn)，該網(wǎng)絡(luò)的質(zhì)量將大大降低。另一方面，在某些情況下，傳感器節(jié)點(diǎn)可以密集地放置。這樣的數(shù)據(jù)可以被記錄相鄰傳感器相關(guān)或相同的。因此，一個(gè)或幾個(gè)節(jié)點(diǎn)不削弱的網(wǎng)絡(luò)服務(wù)質(zhì)量的工作是不會(huì)自動(dòng)。探測(cè)區(qū)域有產(chǎn)生冗余一般由兩個(gè)原因?qū)е拢海?）網(wǎng)絡(luò)規(guī)模過(guò)大；（2）傳感器節(jié)點(diǎn)密集太過(guò)密集，這些原因會(huì)使電池間斷的工作比持續(xù)工作維持時(shí)間提高了一倍不止，由此我們可以得知間斷的打開(kāi)各個(gè)傳感器節(jié)點(diǎn)能延長(zhǎng)網(wǎng)絡(luò)壽命。網(wǎng)絡(luò)壽命的定義就是根據(jù)電量設(shè)定每個(gè)節(jié)點(diǎn)能打開(kāi)N個(gè)時(shí)間段，傳感器在打開(kāi)狀態(tài)下每個(gè)時(shí)間段的耗能相同，如果一部分節(jié)點(diǎn)的打開(kāi)能承擔(dān)整個(gè)區(qū)域的監(jiān)測(cè)任務(wù)，那么我們?cè)谠摃r(shí)間段只讓這一部分節(jié)點(diǎn)打開(kāi)，其他的傳感器節(jié)點(diǎn)休眠，不消耗能量。這樣依次輪流打開(kāi)不同的節(jié)點(diǎn)集合，既能完整的監(jiān)測(cè)需要檢測(cè)的環(huán)境，又能降低能耗。那么網(wǎng)絡(luò)壽命的定義就是無(wú)線(xiàn)傳感器網(wǎng)絡(luò)能維持所要求覆蓋度的時(shí)間段數(shù)。下面我們用一個(gè)例子來(lái)說(shuō)明這個(gè)問(wèn)題，有圖26所示傳感器布局。圖2－6 無(wú)線(xiàn)傳感器網(wǎng)路布局圖先來(lái)說(shuō)明圖中的各個(gè)元素的含義，A、B、C、D、E、F是傳感器節(jié)點(diǎn)，同時(shí)點(diǎn)A、B、C、D、E、F都是要覆蓋的點(diǎn)，要說(shuō)明的是點(diǎn) G不是傳感器但是它要求被傳感器覆蓋到，我們?cè)O(shè)定每個(gè)節(jié)點(diǎn)的能耗相同。假定網(wǎng)絡(luò)覆蓋度為100%，即A、B、C、D、E、F、G都要被節(jié)點(diǎn)覆蓋到。要完成這個(gè)目標(biāo)，從圖中可以看出，最簡(jiǎn)單的方法就是同時(shí)打開(kāi)A和C兩個(gè)傳感器，這個(gè)方案又是打開(kāi)節(jié)點(diǎn)最少的，所以能耗也最低。那么這就是最優(yōu)的方案了嗎？我們繼續(xù)往下分析，當(dāng)A和C兩個(gè)傳感器電量耗盡之后，剩余的節(jié)點(diǎn)B、D、E、F全部打開(kāi)都不能覆蓋到點(diǎn)G，即網(wǎng)絡(luò)覆蓋度達(dá)不到 100%，這個(gè)方案的網(wǎng)絡(luò)壽命就是A和C兩個(gè)節(jié)點(diǎn)的運(yùn)行時(shí)間。顯然網(wǎng)絡(luò)壽命很低，我們采取另一個(gè)方案，現(xiàn)打開(kāi)A、D和F三個(gè)節(jié)點(diǎn)，從圖中可以看出七個(gè)點(diǎn)都被覆蓋了，而在A、D、F三個(gè)節(jié)點(diǎn)能耗耗盡后，我們?cè)俅蜷_(kāi)B、C和E是那個(gè)節(jié)點(diǎn)，這樣同樣能滿(mǎn)足覆蓋度為100%的要求，那么這個(gè)方案的網(wǎng)絡(luò)壽命是兩次打開(kāi)的時(shí)間之和，時(shí)間是上一個(gè)方案的兩倍。把以有限時(shí)間內(nèi)節(jié)能作為目標(biāo)，求出的最優(yōu)解為{A、C}，而若直接以延長(zhǎng)網(wǎng)絡(luò)壽命為目標(biāo)，則求出的最優(yōu)解為{{A、D、F}，{B、C、E}}。在這種情況下的最優(yōu)解，得到為一個(gè)有限的時(shí)間周期來(lái)確定最節(jié)能的解決方案是不能夠維持網(wǎng)絡(luò)的壽命最長(zhǎng)。因此節(jié)省了時(shí)間和最大化網(wǎng)絡(luò)壽命的限定期間內(nèi)是不能完全等同，但網(wǎng)絡(luò)的壽命問(wèn)題是由能量有限，但在某些情況下不延長(zhǎng)網(wǎng)絡(luò)的生命周期轉(zhuǎn)化為節(jié)能考慮。多個(gè)覆蓋網(wǎng)絡(luò)是一種協(xié)同效應(yīng)傳感器節(jié)點(diǎn)的結(jié)果，單一的高能效不一定延長(zhǎng)網(wǎng)絡(luò)的壽命。這個(gè)帶有一個(gè)固定量，例如汽車(chē)用汽油和機(jī)油，只有汽油和機(jī)油共同作用汽車(chē)才能運(yùn)行，能跑最長(zhǎng)時(shí)間的，不一定是剩的油總量最多的，若最后全剩下機(jī)油，沒(méi)有汽油的配合，也不能開(kāi)動(dòng)。我們的本質(zhì)需要就是要網(wǎng)絡(luò)維持時(shí)間最長(zhǎng)，回到問(wèn)題的本質(zhì)上，設(shè)定一個(gè)目標(biāo)就是在滿(mǎn)足覆蓋度的條件下最大化網(wǎng)絡(luò)壽命，這個(gè)目標(biāo)更準(zhǔn)確。39計(jì)算機(jī)信息工程學(xué)院畢業(yè)設(shè)計(jì)說(shuō)明書(shū)第3章 多目標(biāo)進(jìn)化算法分析第3章 多目標(biāo)進(jìn)化算法分析一、多目標(biāo)進(jìn)化算法概念進(jìn)化算法又稱(chēng)為演化算法，是一種模擬自然進(jìn)化過(guò)程的隨機(jī)優(yōu)化算法。和傳統(tǒng)優(yōu)化技術(shù)來(lái)比較，群體搜索策略和群體間個(gè)體之間的信息交換是進(jìn)化算法的兩個(gè)特點(diǎn)。先明確一個(gè)概念：帕累托最優(yōu)解。資源分配的一種理想狀態(tài)就被稱(chēng)為帕累托最優(yōu)，我們假定有可分配的資源分配給固定的一群人，在沒(méi)有是任何一個(gè)人的資源變少的情況下，從改變分配的方式，使得群體中至少有一個(gè)人的資源更多，這就被稱(chēng)為帕累托改進(jìn)或帕累托最優(yōu)化。帕累托最優(yōu)的狀態(tài)就是帕累托改進(jìn)能達(dá)到帕累托最優(yōu)的路徑和方法。進(jìn)化算法中，個(gè)體需要有分辯優(yōu)劣的能力。這能通過(guò)一個(gè)單一的目標(biāo)函數(shù)來(lái)實(shí)現(xiàn)，但在同時(shí)有多個(gè)目標(biāo)，面對(duì)現(xiàn)實(shí)中的多目標(biāo)問(wèn)題，對(duì)個(gè)體的優(yōu)劣評(píng)價(jià)適應(yīng)度的困難程度變得相對(duì)復(fù)雜。根據(jù)帕累托最優(yōu)的概念，對(duì)多目標(biāo)進(jìn)化算法中分配適應(yīng)度時(shí)主要需要考慮兩個(gè)問(wèn)題，一是如何支配越多個(gè)個(gè)體應(yīng)分配更優(yōu)的適應(yīng)度；二是如何在分布在稀少區(qū)域的個(gè)體分配更優(yōu)的適應(yīng)度。我們通過(guò)不同的多目標(biāo)進(jìn)化算法，能獲得在目標(biāo)空間廣泛分布的不同的解，這就使我們有了更多的選擇余地。只有采取了各自的適應(yīng)度分配方式，才能用不同的多目標(biāo)進(jìn)化算法來(lái)進(jìn)行實(shí)現(xiàn)。本文主要研究了四種多目標(biāo)進(jìn)化算法，分別為多目標(biāo)遺傳算法、改進(jìn)的多目標(biāo)差分進(jìn)化算法、多目標(biāo)粒子群優(yōu)化算法、分布式啟發(fā)式算法對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)動(dòng)態(tài)覆蓋問(wèn)題進(jìn)行學(xué)習(xí)與分析，下文會(huì)一一進(jìn)行介紹。 二、多目標(biāo)優(yōu)化問(wèn)題的特點(diǎn)顧名思義，多目標(biāo)問(wèn)題肯定具有多個(gè)目標(biāo)函數(shù)，而且各個(gè)函數(shù)之間在最優(yōu)化方向上存在沖突。最重要的是，目標(biāo)函數(shù)集要么是求極大，要么是求極小值，兩者只能取其一。就拿本文我們研究的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)來(lái)說(shuō)，傳感器網(wǎng)絡(luò)有兩個(gè)重要指標(biāo)，即網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命，我們?cè)O(shè)計(jì)的要求是讓網(wǎng)絡(luò)覆蓋度和網(wǎng)絡(luò)壽命盡可能的大。而網(wǎng)絡(luò)壽命和網(wǎng)絡(luò)覆蓋度又是一對(duì)矛盾的對(duì)象，要讓網(wǎng)絡(luò)覆蓋度大，那么必然要打開(kāi)更多的傳感器節(jié)點(diǎn)。節(jié)點(diǎn)打開(kāi)的越多，那么可以維持的時(shí)間就越短，網(wǎng)絡(luò)壽命就越小，這就是兩者在最優(yōu)化的方向上存在沖突。（1）算法過(guò)程輸入：基于多目標(biāo)算法的通用算法過(guò)程輸出：多目標(biāo)優(yōu)化解集步驟