基於改進雙係統協同進化算法的無線傳感器網絡節點定位
網絡與通信
作者：尚俊娜 劉春菊 嶽克強 李林
摘要：為進一步提高無線傳感器網絡（WSN）中節點的定位精度，提出了一種雙係統協同進化（BCO）算法。改進算法利用粒子群優化（PSO）算法快速收斂的特性和混合蛙跳算法（SFLA）較高的尋優精度的特性，在較少的迭代次數內快速收斂且實現深度搜索達到較高的精度。仿真實驗結果表明：在應用雙係統協同進化算法對測試目標函數進行求解時，能非常接近最優解；同時將該算法應用到基於接收信號強度值（RSSI）測距的節點定位中，預測位置與實際位置的絕對誤差在0.05m範圍內；相比基於RSSI的分步粒子群算法（IPSORSSI），其定位精度至少提高了10倍。
關鍵詞：節點定位；粒子群算法；蛙跳算法；並行係統；協同進化；定位精度
中圖分類號： TP393 文獻標誌碼：A
英文摘要
Abstract：In order to improve the locating accuracy in Wireless Senor Network （WSN） _disibledevent=（pi1， pi2，…， piD）表示。該算法將可行域中蛙群個體按照適應度值的大小降序排列，按照一定的規則分組。SFLA的核心部分主要在於蛙群的局部搜索，設最大跳躍距離為dmax， 全局的最優蛙的位置記為pg與初始化群體中Pi有何關係，是否對應，是否也為向量？該處pg是所有初始個體pi中最優個體，也屬於pi中的一個個體，是向量。，每個團體局部最優位置記為pb，最差蛙記為pw。
2 BCO算法
雙係統協同進化思想是指利用A、B兩個並行係統分別演化同一個目標函數，但是從整個係統來看A、B係統並不是完全孤立的進化，二者個體間進行信息交流共享來實現協同進化，並利用兩個係統中的最優個體引導進化尋優方向。該算法結合了粒子群算法快速收斂和蛙跳算法深度搜索的優點，並且具有較強的魯棒性。
2.1 算法改進思路
BOC算法利用PSO算法和SFLA對同一目標函數進行優化，二者的最小適應度值在不同進化時期具有不同的特點：蛙跳算法在迭代進化前期比粒子群算法擁有更小的適應度值，說明SFLA中個體位置更接近於最優解，用該最優解指導PSO算法的進化方向會提高算法的收斂速度；在迭代進化中期，PSO算法比SFLA有更小的最小適應度值，此時用對應位置的最優解去指導蛙跳算法進化，就會大大減少其迭代次數而找到最優解，提高收斂速度；在進化的後期，SFLA具有深度搜索的能力，其全局最優解的位置更接近於真實解，用此最優解指導PSO算法的進化方向，使其具有較高的精度。利用雙係統協同進化的思想，將PSO算法與SFLA分別獨立複製給A、B兩個子係統並分別演化同一個目標函數，兩個算法在整個係統中相輔相成，相互指導進化，加速了收斂且提高了優化精度。此外，整個係統中，每個子係統除了利用兩者中的最優解位置指導進化方向以外，係統之間又進行了個體交流實現信息共享，蛙跳算法進行個體交流以後可以將每組中最差蛙進行替換從而更快地尋找到最優解。在算法複雜度方麵，通過融入PSO算法的個體來替代基本SFLA中部分個體，所以該算法中的個體總數相比於SFLA並沒有增多，標準 PSO算法具有參數少、模型簡單、快速收斂等優點且算法複雜度並不是很高，從整體上來看，所提算法的複雜度並沒有增加很多，但是算法的優化精度和收斂速度卻得到了提高。
2.2 算法步驟流程
本文所提的雙係統協同進化算法中，A係統采用混合蛙跳算法，B係統采用粒子群算法，其實現步驟如下：
1）設定粒子群算法和混合蛙跳算法的參數、各自總個體數、最大迭代次數，以及隨機產生初始群體的位置和速度。
2）計算B係統中每一個個體的自適應度值，尋找出粒子群算法的全局最優個體記錄其位置是否黑斜紅線標注的globe，pg，均為矢量，需要用黑斜體表示。凡""所涉及的到globe，pg均為矢量，用黑斜體表示，globe及其對應的最小適應度函數值fb。
3）計算A係統中每個個體的適應度函數值，標記全局最優蛙位置pg以及對應的最小適應度函數值fa。
4）比較A、B係統中fa與fb的大小，如果fa小於fb，說明A係統的最優解pg更接近於真實解，則pg來替換B係統全局最優解globe；反之用B係統的最優解globe替換A係統的最優解pg。
5）將A係統按照適應度值大小進行降序排列，按照第1個個體分在第1組、第2個個體分在第2組、…、第m個個體分在第m組、第m+1個個體分在第1組、第m+2個個體分在第2組的分組原則分為m個組，組內個體按照蛙跳算法的更新機製和步驟4）中得到的全局最優解進行個體更新進化，直到m個族群中個體更新完全，計算個體適應度值，並分別記錄A係統的全局最優解是否黑斜pg和相應的最小適應度值fa。
6）將 B係統按照粒子群算法的進化規則依據步驟4）中得到的最優解指導個體的更新進化，並記錄B係統的全局最優解globe和最小適應度值fb。
7）將A、B係統進化更新後的所有個體混合，並重新為A係統隨機挑選個體，B係統保持不變，實現了個體間交流信息共享。
8）重複以上步驟4）～7）直到達到迭代終止條件或者最大迭代次數，輸出係統最小適應度值對應的最優解。
2.3 性能仿真
為了驗證改進雙係統協同進化算法的性能，采用標準測試函數進行優化尋找最優解。下麵對比各種算法對6個標準函數的尋優能力。對於仿真所用的標準函數可分為兩類[11]：1）Sphere、Quadric、Rosenbrock是典型的單模函數，其中Rosenbrock函數是單峰連續函數，其極小點所在的山穀易於找到，但取值區間走勢平坦，極難收斂到全局最優點，是測試算法全局收斂性能的經典函數。2）Griewank、Rastrigin、Schatter F6是具有較多局部極值的多模函數，可以有效檢驗算法的群體多樣性、全局搜索性能、逃離局部極值並避免早熟的收斂能力。其中：Griewank 函數是多峰多極值函數，有眾多局部極值，種群極易陷入局部極值中，主要用來評價算法的探索、開發能力；Rastrigrin 函數為多極值函數，在解空間內存在大約10D 個（D為解空間維數）局部極小點；Schaffer F6 函數是具有強烈振蕩的多峰函數。