基于微分進(jìn)化算法的無線傳感器網(wǎng)絡(luò)若干優(yōu)化問題研究.pdf

1、物聯(lián)網(wǎng)、大數(shù)據(jù)、云計(jì)算是未來科技的發(fā)展趨勢(shì)和研究熱點(diǎn)，無線傳感器網(wǎng)絡(luò)（WSN）是物聯(lián)網(wǎng)和大數(shù)據(jù)的基礎(chǔ)設(shè)施，也稱為物聯(lián)網(wǎng)的雛形，它由大量具有無線通信與計(jì)算能力的無線傳感器節(jié)點(diǎn)組成，具備信息采集、傳送、處理于一體的分布式網(wǎng)絡(luò)系統(tǒng)，并具有靈活性、自組織、動(dòng)態(tài)性、以數(shù)據(jù)為中心的特點(diǎn)。WSN的這些特點(diǎn)與物聯(lián)網(wǎng)、大數(shù)據(jù)的特點(diǎn)非常相似，因此對(duì)WSN的研究具有較強(qiáng)的實(shí)際意義和廣闊的發(fā)展前景。無線傳感器網(wǎng)絡(luò)的部署實(shí)施需要考慮節(jié)能性和覆蓋性，這些需求使得W

2、SN中存在諸多復(fù)雜優(yōu)化問題，例如WSN最長(zhǎng)生存時(shí)間問題、覆蓋問題、最優(yōu)路徑問題等。
　　這些優(yōu)化問題多數(shù)為NP難題，為解決此類復(fù)雜優(yōu)化問題，研究人員發(fā)現(xiàn)用大自然為藍(lán)本的模型和象征，以達(dá)爾文進(jìn)化論為基礎(chǔ)的進(jìn)化算法在求解此類問題時(shí)表現(xiàn)出較好的效果。微分進(jìn)化屬于進(jìn)化算法的新興分支，是一種基于種群的并行迭代優(yōu)化算法，其性能主要由變異因子，交叉概率因子和種群規(guī)模等決定，具有結(jié)構(gòu)簡(jiǎn)單、收斂迅速、魯棒性強(qiáng)等優(yōu)點(diǎn)而受到了廣泛的關(guān)注和研究，并已應(yīng)用

3、于模式識(shí)別、生物信息、工程優(yōu)化、組合優(yōu)化等問題。但是，標(biāo)準(zhǔn)微分進(jìn)化存在早熟收斂和搜索停滯的缺陷，因此需要對(duì)其研究和改進(jìn)。
　　本文主要研究基于微分進(jìn)化的無線傳感器網(wǎng)絡(luò)的若干優(yōu)化問題。首先，為解決WSN中的最優(yōu)路徑問題，研究了微分進(jìn)化算法中的交叉策略，使用基于優(yōu)劣個(gè)體的交叉策略（SI）對(duì)原始算法進(jìn)行改進(jìn)。其次，針對(duì)WSN中的兩目標(biāo)覆蓋問題，對(duì)多目標(biāo)微分進(jìn)化中的非支配排序、擁擠距離計(jì)算進(jìn)行研究，改進(jìn)了非支配解排序和擁擠距離計(jì)算方法，提

4、出了快速的多目標(biāo)微分進(jìn)化算法（FMODE）。然后，基于上述研究成果對(duì)WSN的若干優(yōu)化問題進(jìn)行研究，包括使用標(biāo)準(zhǔn)微分進(jìn)化算法研究WSN中的最大生存時(shí)間問題；基于優(yōu)劣交叉策略的微分進(jìn)化研究WSN中最優(yōu)路徑問題；利用提出的快速多目標(biāo)微分進(jìn)化研究WSN中兩目標(biāo)覆蓋問題。
　　本文主要研究工作如下：
　?。?）微分進(jìn)化算法中優(yōu)劣交叉策略的研究
　　為解決無線傳感器網(wǎng)絡(luò)中最優(yōu)路徑問題，對(duì)微分進(jìn)化的交叉策略進(jìn)行研究。針對(duì)算法進(jìn)化中后

5、期，種群多樣性降低，過度聚集的個(gè)體無法產(chǎn)生更優(yōu)解的現(xiàn)象。從提高種群多樣性，增大搜索空間考慮，本章介紹一種基于微分進(jìn)化的優(yōu)劣交叉策略（SI）。具體而言，種群多樣性非常小時(shí)，使用優(yōu)秀與劣質(zhì)個(gè)體之間的交叉，提高種群多樣性，增大搜索空間。反之，采用優(yōu)秀與優(yōu)秀個(gè)體間交叉，提高開發(fā)能力，產(chǎn)生更優(yōu)解。提出的策略在交叉操作之前執(zhí)行，它只是調(diào)整部分目標(biāo)個(gè)體和變異個(gè)體的位置。此外，還給出了優(yōu)劣交叉策略提高種群多樣性的理論基礎(chǔ)，同時(shí)考慮參數(shù)選擇對(duì)性能的敏感性

6、，嘗試提出一種自適應(yīng)的優(yōu)劣交叉策略。實(shí)驗(yàn)結(jié)果表明，在24個(gè)數(shù)值優(yōu)化問題上，提出的交叉策略在傳統(tǒng)微分進(jìn)化算法和其變體的性能上都有所改善。
　?。?）多目標(biāo)微分進(jìn)化中非支配解排序及擁擠距離的研究
　　為解決無線傳感器網(wǎng)絡(luò)中的兩目標(biāo)覆蓋優(yōu)化問題，對(duì)多目標(biāo)微分進(jìn)化進(jìn)行研究。首先分析多目標(biāo)進(jìn)化算法NSGAII，發(fā)現(xiàn)在非支配解等級(jí)排序時(shí)存在冗余。經(jīng)典NSGAII的非支配解排序需要對(duì)所有個(gè)體計(jì)算，且是在所有個(gè)體分配等級(jí)之后，排序操作才完成

7、。而后，再根據(jù)所有等級(jí)中的個(gè)體，按等級(jí)由高到低依次選取個(gè)體進(jìn)入下一代。為解決這個(gè)不足，介紹一種快速的非支配解排序方法，方法每次只處理當(dāng)前種群中最高等級(jí)個(gè)體，且在分配等級(jí)的同時(shí)，可選擇個(gè)體進(jìn)入下一代，下一代個(gè)體被選足時(shí)，即結(jié)束程序，進(jìn)入下一輪進(jìn)化。該方法減少了非支配解排序時(shí)處理個(gè)體數(shù)量，較大降低時(shí)間復(fù)雜度。另外，引入一種均勻的擁擠距離計(jì)算方法，最后將快速非支配解排序、均勻擁擠距離計(jì)算和微分進(jìn)化結(jié)合，提出基于非支配解排序的快速多目標(biāo)微分進(jìn)化

8、算法（FMODE）。采用標(biāo)準(zhǔn)最小化兩目標(biāo)優(yōu)化問題ZDTl-ZDT4和ZDT6進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，提出算法能夠降低計(jì)算等級(jí)時(shí)的處理時(shí)間，并在收斂性和多樣性指標(biāo)上明顯優(yōu)于對(duì)比算法，實(shí)驗(yàn)也確定了FMODE算法的參數(shù)。
　　（3）基于單目標(biāo)微分進(jìn)化研究無線傳感器網(wǎng)絡(luò)中最大生存時(shí)間問題
　　研究使用微分進(jìn)化算法求解無線傳感器網(wǎng)絡(luò)中的最大生存時(shí)間問題。首先介紹一種WSN中覆蓋問題部署生成方法，為此類研究提供測(cè)試集數(shù)據(jù)和環(huán)境。以找出W

9、SN中最多完全覆蓋子集的角度來實(shí)現(xiàn)其生存時(shí)間最長(zhǎng)，提出基于微分進(jìn)化的滿覆蓋子集計(jì)算算法，算法兩個(gè)重要特點(diǎn)是重組操作和適應(yīng)度計(jì)算。重組操作保證至少一個(gè)關(guān)鍵目標(biāo)點(diǎn)所對(duì)應(yīng)的傳感器被分配到不同的子集中，它能較大提高初始種群解的質(zhì)量。適應(yīng)度計(jì)算方法，不但考慮完全覆蓋子集的個(gè)數(shù)，也考慮了未完全覆蓋子集覆蓋的百分率。實(shí)驗(yàn)結(jié)果表明，提出的算法不差于兩個(gè)經(jīng)典的對(duì)比算法，特別在收斂速度上，提出的算法明顯優(yōu)于兩個(gè)對(duì)比算法，需要最少的進(jìn)化代數(shù)即可找到理論最優(yōu)解

10、。
　?。?）基于單目標(biāo)微分進(jìn)化研究無線傳感器網(wǎng)絡(luò)中最優(yōu)路徑問題
　　研究基于優(yōu)劣交叉策略的微分進(jìn)化解決無線傳感器網(wǎng)絡(luò)中最優(yōu)路徑問題。首先分析無線傳感器網(wǎng)絡(luò)中的路徑優(yōu)化問題，并建立優(yōu)化模型。然后使用微分進(jìn)化算法作為搜索工具，求解路徑優(yōu)化模型中的最小能量消耗，即最優(yōu)路徑問題。染色體表示采用十進(jìn)制編碼方式，由于信息傳遞路徑長(zhǎng)度不統(tǒng)一，每個(gè)染色體的長(zhǎng)度可變。在變異時(shí)采用集合的差、并運(yùn)算，類似于微分進(jìn)化中的差分、求和運(yùn)算，使用二項(xiàng)式

11、交叉策略。變異交叉后需執(zhí)行修正操作，將存在環(huán)路和非法路徑的染色體修正成合法染色體，從而保證種群中所有個(gè)體都是從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的合法路徑。最后，與此類經(jīng)典算法GA、PSO和標(biāo)準(zhǔn)DE進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果顯示，使用基于優(yōu)劣交叉策略微分進(jìn)化算法，在求解該問題的性能優(yōu)于或不差于幾個(gè)對(duì)比算法，驗(yàn)證了提出方法的有效性。
　　（5）基于多目標(biāo)微分進(jìn)化研究無線傳感器網(wǎng)絡(luò)中兩目標(biāo)覆蓋問題
　　研究使用提出的快速多目標(biāo)微分進(jìn)化（FMODE）求解無

12、線傳感器網(wǎng)絡(luò)中的兩目標(biāo)覆蓋問題。首先介紹該兩目標(biāo)覆蓋問題的背景并建立數(shù)學(xué)模型，使用標(biāo)準(zhǔn)多目標(biāo)微分進(jìn)化和提出的FMODE算法來解決該問題。然后，針對(duì)該問題建立染色體的編碼方式，同時(shí)給出適應(yīng)度函數(shù)的設(shè)計(jì)、非支配解排序、算法總體框架。在求解該問題時(shí)，使用重組操作保證了至少一個(gè)關(guān)鍵目標(biāo)所對(duì)應(yīng)的傳感器被分配到不同的子集中，從而提高找到滿覆蓋子集上限的概率。為驗(yàn)證提出方法的有效性，對(duì)比實(shí)驗(yàn)在6個(gè)給定的測(cè)試集中完成。從最優(yōu)解集中最高等級(jí)解的個(gè)數(shù)和質(zhì)量