基于慣性擾動與自適應調節的量子粒子群軌跡覆蓋算法

宋凡

（廣東工業大學計算機學院，廣州510006）

0 引言

無線傳感器覆蓋問題起源于卡內基·梅隆大學的分布式傳感器網絡研究組。近些年來，隨著技術水平的大規模提高，對無線傳感器網絡的研究、開發成為計算機領域一個熱點，在美國移動計算和網絡會議上，無線傳感器是下一個世紀面臨的發展機遇[1-2]被提出，越來越多的研究機構和公司正加入到這方面的研究工作來。

我們研究的軌跡覆蓋問題則是屬于無線傳感器覆蓋問題中的一個子問題，其目的就是設置傳感器覆蓋路徑并監測其物理環境。因此覆蓋率是軌跡覆蓋問題中的一個重要指標，它反映了無線傳感器是否能提供滿意的服務。近年來，覆蓋控制方面的研究工作有一定進展[3]。

根據覆蓋方式的分類，分為區域覆蓋、點覆蓋和柵欄覆蓋幾種覆蓋算法。對于區域覆蓋，多重k 級覆蓋控制算法[4]被提出。對于點覆蓋基于不交叉優勢集的覆蓋控制算法被提出。針對柵欄覆蓋提出了基于暴露模型的覆蓋控制算法。文獻[5]提出一個啟發性的算法：分布式探測算法PEAS。在PEAS 中，一部分傳感器處于工作狀態，其他傳感器則處于休眠狀態。傳感器輪流分配工作時間，可以提高傳感器的使用時間。

隨著20 世紀80 年代，智能進化算法的出現引起了許多學科領域研究人員的關注，已經成為人工智能、生物、能源等交叉學科的前沿及熱點領域。智能進化算法主要分為以蟻群算法[6]、粒子群算法[7]、遺傳算法等。文獻[8]利用遺傳算法實現覆蓋優化，雖然遺傳算法全局尋優能力強，但收斂速度慢，難以滿足實時性要求。文獻[9]基于粒子群算法實現覆蓋優化，但是標準粒子群算法易早熟，難以滿足覆蓋率的要求。

基于上述文獻的研究成果，證明智能進化算法能一定程度實現覆蓋優化。本文的研究工作是以基本粒子群算法為基礎，通過改進和結合其他優化算法來設計軌跡覆蓋優化算法。在兼顧全局搜索能力和局部搜索能力的平衡的基礎上有效解決早熟及收斂過慢等問題，以實現傳感器的優化配置，獲得有限節點情況下的網絡最大覆蓋率。

本文提出一種改進的量子粒子群算法用來解決軌跡覆蓋問題。首先將經典的PSO 改進型算法例如，量子粒子群算法（QPSO）[10]和全局粒子群算法（GPSO）[11]應用到軌跡覆蓋問題中，并比較兩者的優劣，在綜合GPSO和QPSO 的基礎上提出改進的算法GQPSO，再對GQPSO 的結果進行分析后，進一步提出了收斂速度和聚集程度兩個因子，最終得到改進后的算法AGQPSO。

1 背景

1.1 粒子群優化算法

粒子群優化算法（Particle Swarm Optimization，PSO）由Kennedy 和Eberhart 在1995 年提出，該算法對于Hepper 的模擬鳥群（魚群）的模型進行修正，以使粒子能夠飛向解空間，并在最好解處降落，從而得到了粒子群優化算法。

PSO 從這種模型中得到啟示并用于解決優化問題。PSO 中，每個優化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。所有的粒子都有一個由被優化的函數決定的適值（fitness value），每個粒子還有一個速度決定它們飛翔的方向和距離。然后粒子們就追隨當前的最優粒子在解空間中搜索。

PSO 初始化為一群隨機粒子（隨機解），然后通過迭代找到最優解。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優解，這個極值是全局極值。

1.2 量子粒子群算法和全局粒子群優化算法

量子粒子群算法（QPSO）和全局粒子群算法（GPSO）屬于標準粒子群算法（PSO）的兩個分支。PSO 算法在復雜問題和非線性變化問題下容易早熟，QPSO 算法采用波函數表示粒子位置，通過蒙特卡羅方法求出粒子位置，在解空間中粒子都有相應的概率到達[12-13]。而GPSO 采用一種擾動式的動態慣性權重來更新粒子速度，使得權重雖然整體呈減少趨勢但是在一定范圍內波動。QPSO 和GPSO 所采取的策略都使得其全局搜索能力增強。

公式（1-5）為QPSO 主要公式，公式（1）中mbest 為當前代種群所有個體最佳位置的平均值，公式（5）β為慣性權重，公式（4）L 為粒子i 到mbest 的距離，由公式（3）求得種群的吸引點pi后，可根據公式（2）求得下一代粒子的位xi（t），其中M 為種群粒子個數，D 為粒子維數，pbesti為第i 個粒子歷史最優，gbest 為粒子群全局最優，u、rand 為（0，1）間的隨機數。

公式（6-9）為GPSO 的主要公式，t+1 代粒子i 的位置由t 代粒子i 的位置和t+1代粒子i 的速度決定。GPSO 的速度更新方式如公式（6）所示，其中βt表示第t 代的慣性權重，rand 為（0，1）之間的隨機數，βmax和βmin為慣性權重的上下限分別取值0.9 和0.4。根據文獻[9]的研究，GPSO 的慣性權重呈現總體下降但局部震蕩的趨勢，其中φ 為擾動因子，該因子增強了在全局最優解附近搜索的隨機性，取值為0.01 可以得到較好的效果。

量子粒子群算法簡單且全局搜索能力強[14]，具有相應概率到達解空間內所有位置，在許多情況下，都可以針對所選問題進行改進從而生成性能更優的算法[15-16]。

2 面向覆蓋問題的粒子群算法

2.1 問題定義

軌跡覆蓋是指從一個擁有數條軌跡的空間中設置傳感器覆蓋軌跡的過程。但由于傳感器數量有限，軌跡之間的組合數量過多，無法將每條軌跡都進行全部覆蓋，因此軌跡覆蓋需要選用可行的算法進行優化。軌跡覆蓋的困難在于達到較好的覆蓋效率，一條軌跡，在其轉折處覆蓋比在平滑處覆蓋具有更高的相對覆蓋率，但是容易造成傳感器之間的重復覆蓋。與其他軌跡組合到一起時，可能會變成多條，匯聚的復雜路線。理想的覆蓋方法應該是整體路徑的覆蓋率高，傳感器之間重復覆蓋率低。

目前，雖然許多針對覆蓋的算法被提出，大部分算法的目標只是提高覆蓋率。傳感器數量的增加雖然可以提高覆蓋率，但是過多的傳感器數量將導致成本高昂，也不利于后續的傳感器網絡維護。如何在提高可接受的覆蓋率的同時，降低傳感器數量，這是兩個沖突的目標，可以折中選擇傳感器數量較少，但覆蓋率相對較高的組合，用于實際的覆蓋應用中。

2.2 問題建模

（1）軌跡表示

第一步生成路徑，本文中，二維空間中有x，y 兩個維度，沿x 維度每隔一定距離k 取一個采樣點的維度值x，每個采樣點根據路徑生成函數生成對應的維度值y。最終生成的路徑如公式（11）所示：

其中waypointi,i ∈[0,p]為在二維空間中生成的路徑點，p 的取值如公式（12）所示，其中xMax 為路徑在x維度上的最大值，k 為兩個取樣點之間x 維度上的距離。

圖1 離散前的原路徑和離散后近似表達的路徑

圖1 的（b）中，每個空心點代表一個路徑點，用一系列路徑點近似表達了原始路徑。

（2）優化目標

本文的優化目標為在有限節點下盡可能達到更高的覆蓋率以及在全覆蓋條件下，盡可能減少節點數目。路徑離散后，覆蓋率coverRatio 可以近似的表達為：

其中，Ncover為被節點覆蓋一次或一次以上的路徑點個數，Nsum 表達了原始路徑離散化后總的路徑點個數，由累加求得。當某一路徑點被節點覆蓋一次或多次即numcover∈N+時，對應的為1，否則為0。

圖2 判斷路徑是否被覆蓋

由公式（16）可以判斷某一路徑點是否被節點覆蓋。

當路徑點 j 到節點 i 的歐氏距離distancenode-i,path-point-j大于節點的探測半徑rnode時，節點i未能覆蓋路徑點j，否則節點i 覆蓋了路徑點j。

2.3 QPSO和GPSO實現軌跡覆蓋問題的比較

（1）個體編碼

粒子群算法首先初始化種群，在本文中，每個個體被編碼成坐標點的矩陣。坐標點矩陣的第j 列代表了傳感器網絡中第j 個傳感器的位置（xj，yj）。向量X，Y分別代表了矩陣的第一行（x0，x1，…，xp）和第二行（y0，y1，…，yp）（如圖3）。一個粒子由一對坐標點組成（xi，yi）。一個個體由p 個粒子組成（X，Y）。坐標點矩陣的行數j 由空間維數決定，列數i 則由傳感器網絡中節點的個數p 決定。

假設x 維度空間大小為[xMin，xMax]，y 維度空間大小為[yMin，yMax]，則按照如下公式對每個粒子進行初始化：

圖3 粒子個體編碼

xi和yi分別為第i 個節點的x 維度坐標和y 維度坐標，rand1和rand2是[0，1]間的隨機數。對于GPSO 則有公式（18）所示的粒子速度初始化：

其中vMin、Vmax 分別為速度下限和上限，rand 為[0，1]間隨機數。

（2）算法流程

算法流程如圖4 所示。

圖4 QPSO和GPSO的流程圖

（3）結果比較

根據本文的編碼方式，將QPSO 和GPSO 應用到測試地圖a 的軌跡覆蓋（圖5），結果如圖7 所示。

3 帶聚合度因子的自適應全局量子粒子群算法

3.1 QPSO與GPSO存在的問題

根據圖7 的結果可知，QPSO 全局尋優能力比較強，能達到比較好的覆蓋率，但是收斂速度比較慢、而GPSO 收斂速度很快但是容易陷入早熟。

圖5 測試GPSO與QPSO的地圖a

3.2 帶GPSO慣性權重更新的GQPSO

綜合比較GPSO 與QPSO 的結果，由于QPSO 優秀的全局尋優能力，本文在QPSO 的基礎上進行改進。原始的QPSO 的慣性權重β 依據公式（5）線性遞減，本文將GPSO 的慣性權重更新方式應用到QPSO 中，依據公式（8）可得到改進后的GQPSO 粒子更新方式，式中參數的取值與前面介紹QPSO、GPSO 的參數取值一致。

圖6 GQPSO算法流程

圖7 9 至14 個探測器數量下GQPSO、GPSO、QPSO相應覆蓋率的比較

3.3 分析GQPSO的結果并提出改進算法AGQPSO

觀察GQPSO 的結果發現，雖然算法收斂速度有所提高，但是最終得到的覆蓋率不理想，與原始QPSO 相比并反而更差。綜上，本文提出收斂速度因子s，定義為：

其中ct為第t 次迭代的全局最優粒子覆蓋率ct-1為第t-1 次迭代的全局最優粒子覆蓋率，s ∈[0,1]，s 越小說明收斂速度越快。定義收斂速度因子后，AGQPSO的慣性權重先采用公式（8）中的慣性權重計算方式達到快速收斂目的，如果收斂速度趨近0，則改變慣性權重的計算方式，依據公式（5）計算慣性權重。AGQPSO在前期使用GPSO 慣性權重計算方式快速迭代，當種群迭代一定代數后無法找到更好的解就使用QPSO 慣性權重計算方式，種群具有更高的全局尋優能力。

3.4 進一步改進AGQPSO

雖然AGQPSO 與QPSO 相比收斂速度更快，與GPSO 相比覆蓋率更高，但是AGQPSO 的提升都只是在一方面，對此本文提出聚合度因子，進一步改進AGQPSO。

聚合度因子d 定義如下：

mbest 為第t 代粒子最好位置的平均適應度，顯然，0 ＜d ≤1，d 代表了群體最優粒子的適應度到群體粒子平均適應度的比值，一定程度反映了粒子的聚集程度，當d=1 時，算法收斂。有了粒子聚集度因子，我們可以知道群體當前的聚集狀態，當粒子都聚集到一起時，可以增大慣性權重β，當粒子太分散時，可以減小β 以達到控制粒子的全局搜索能力和局部搜索能力達到平衡。

其中，w1和w2分別為控制收斂速度和聚集度的權重，b=1。由圖7 可知，QPSO 采取的線性慣性權重遞減雖然收斂速度較慢，但是其收斂曲線穩定遞進，具有較好的探索能力，而GPSO 采取的權重更新方式具有一定的不確定性，有利于跳出局部最優。從而我們采取兩種方式改進AGQPSO，第一種為：完全根據公式（21）進行權重更新，第二種為在原始QPSO 權重更新方式上融合GPSO 和公式（21）中的方式更新權重。采用第二種方式，具體為：先對慣性權重β 線性減少，使得粒子穩定搜索解空間，每迭代k 代，如果收斂速度小于γ，β 就改變更新方式，每次迭代根據公式（22）計算權重概率rw，其中rand 為[0，1]間的隨機數，t 為當前迭代次數，MaxIteration 為最大迭代次數。當rw小于閾值0.7時采用GPSO 的更新方式，當rw大于或者等于0.7 時采用公式（21）所示的更新方式。GPSO 的更新方式具有一定的隨機性，有助于跳出局部最優，每當進行一次隨機性較大的慣性權重更新以后，采用收斂速度因子和聚集度因子來評估群體當前狀態，并依據公式（21）根據評估結果對權重進行計算，調整粒子位置。這樣隨著迭代次數增加rw小于0.7 的可能性降低，種群隨機性降低收斂趨于穩定，使群體能夠最終找到較好的結果。所得的結果如圖8，在分析rw時，我們選取了0.5、0.6、0.7、0.8 和0.9 共5 個閾值，根據實驗結果選擇0.7作為最終取值。

圖8 AGQPSO 在地圖6 取不同閾值時的覆蓋率

圖9 9 至14 個探測器數量下AGQPSO、GQPSO、QPSO相應覆蓋率的比較

由圖9 可知：最終改進的AGQPSO 與GQPSO 相比在9、10、11、12 個探測器個數時都能取得更高的覆蓋率，在13、14 個探測器個數時都能達到全覆蓋。AGQPSO 與QPSO 相比在所有情況下，收斂速度和覆蓋率都更好。

3.5 完整算法流程

步驟1）對群體中的每個粒子的位置初始化

步驟2）按預設的迭代次數進行循環

2.1）對群體中每個粒子：

根據收斂速度判斷群體是否停滯不前，無法快速找到更好的結果

1）否，執行公式（5）的慣性權重更新規則

2）是，改變慣性權重更新規則

根據公式（22）結果分別采用（8）和公式（21）所示的慣性權重更新規則計算每個粒子的適應值，更新粒子的pbest，gbest計算群體的收斂速度和聚合度，并以此計算慣性因子

根據公式（2）計算粒子下一代位置

步驟3）找到取得gbest 的粒子，并將其所在位置作為結果返回

算法中的學習系數c1和c2與標準中的設置相同，c1=c2=1.0。

4 實驗設計及數據分析

4.1 數據集與參數設置

在比較試驗中，每種算法的粒子個數都為100 個，最大迭代次數為3000 代。實驗分別采用QPSO（量子粒子群算法）、GPSO（全局粒子群算法）和AGQPSO（本文提出的算法），在6 種不同的地圖上分別測試30 次所得的平均覆蓋率作為最終結果來比較（如表2 所示）。參數取值如表1 所示。

表1 AGQPSO 中的參數值

4.2 實驗結果

如表1 和圖7 所示，比較QPSO 與GPSO 我們發現QPSO 的迭代速度通常慢于GPSO，但是覆蓋率優于GPSO，特別的在實驗1 下探測器個數為10 個時，GPSO的迭代次數相比QPSO 少了1000 代，結果僅僅差了2.4%，說明GPSO 雖然覆蓋率不如QPSO 但是結果相差不大，且收斂速度很快。如圖9 所示，結合了QPSO和GPSO 優點的GQPSO 在收斂速度上優于QPSO，在覆蓋率上優于GPSO，GQPSO 在QPSO 和GPSO 的優勢上有所折中，但是補充了各自的缺點。如表2 及圖9所示，在GQPSO 上進一步改進的AGQPSO 在引入了聚合度和收斂速度這兩個因子后，收斂速度及覆蓋率相比于QPSO 和GPSO 都有不錯的提升，不僅在覆蓋率上超過了QPS O，在收斂速度上也不差于GPSO。

表2 比較QPSO、GPSO 和AGQPSO 在不同地圖和不同探測特個數下的覆蓋率

圖10 AGQPSO、GPSO和QPSO在探測器個數為14時在地圖6上的結果

在較復雜的地圖中（實驗6），GPSO 覆蓋率停滯不前，算法陷入早熟，QPSO 雖然沒有陷入早熟，但是搜索能力大大降低，只有AGQPSO 仍能找到一個較好的結果。

5 結語

AGQPSO 是基于QPSO 與GPSO 算法提出的優化算法，繼承了QPSO 優秀的全局尋優能力，且能在一定程度上提高算法的收斂速度。在引入收斂速度及聚合度因子后，粒子的表現得到了量化，使得算法可以更好地引導粒子尋優。在簡單和復雜地圖中相比QPSO 和GPSO 算法都有更好的表現。