基于微分進化算法的無線傳感器網絡若干優(yōu)化問題研究.pdf

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

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

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

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

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

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

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

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

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

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

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

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