基于慣性擾動與自適應(yīng)調(diào)節(jié)的量子粒子群軌跡覆蓋算法

宋凡

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006）

0 引言

無線傳感器覆蓋問題起源于卡內(nèi)基·梅隆大學(xué)的分布式傳感器網(wǎng)絡(luò)研究組。近些年來，隨著技術(shù)水平的大規(guī)模提高，對無線傳感器網(wǎng)絡(luò)的研究、開發(fā)成為計(jì)算機(jī)領(lǐng)域一個(gè)熱點(diǎn)，在美國移動計(jì)算和網(wǎng)絡(luò)會議上，無線傳感器是下一個(gè)世紀(jì)面臨的發(fā)展機(jī)遇[1-2]被提出，越來越多的研究機(jī)構(gòu)和公司正加入到這方面的研究工作來。

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

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

隨著20 世紀(jì)80 年代，智能進(jìn)化算法的出現(xiàn)引起了許多學(xué)科領(lǐng)域研究人員的關(guān)注，已經(jīng)成為人工智能、生物、能源等交叉學(xué)科的前沿及熱點(diǎn)領(lǐng)域。智能進(jìn)化算法主要分為以蟻群算法[6]、粒子群算法[7]、遺傳算法等。文獻(xiàn)[8]利用遺傳算法實(shí)現(xiàn)覆蓋優(yōu)化，雖然遺傳算法全局尋優(yōu)能力強(qiáng)，但收斂速度慢，難以滿足實(shí)時(shí)性要求。文獻(xiàn)[9]基于粒子群算法實(shí)現(xiàn)覆蓋優(yōu)化，但是標(biāo)準(zhǔn)粒子群算法易早熟，難以滿足覆蓋率的要求。

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

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

1 背景

1.1 粒子群優(yōu)化算法

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

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

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

1.2 量子粒子群算法和全局粒子群優(yōu)化算法

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

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

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

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

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

2.1 問題定義

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

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

2.2 問題建模

（1）軌跡表示

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

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

圖1 離散前的原路徑和離散后近似表達(dá)的路徑

圖1 的（b）中，每個(gè)空心點(diǎn)代表一個(gè)路徑點(diǎn)，用一系列路徑點(diǎn)近似表達(dá)了原始路徑。

（2）優(yōu)化目標(biāo)

本文的優(yōu)化目標(biāo)為在有限節(jié)點(diǎn)下盡可能達(dá)到更高的覆蓋率以及在全覆蓋條件下，盡可能減少節(jié)點(diǎn)數(shù)目。路徑離散后，覆蓋率coverRatio 可以近似的表達(dá)為：

其中，Ncover為被節(jié)點(diǎn)覆蓋一次或一次以上的路徑點(diǎn)個(gè)數(shù)，Nsum 表達(dá)了原始路徑離散化后總的路徑點(diǎn)個(gè)數(shù)，由累加求得。當(dāng)某一路徑點(diǎn)被節(jié)點(diǎn)覆蓋一次或多次即numcover∈N+時(shí)，對應(yīng)的為1，否則為0。

圖2 判斷路徑是否被覆蓋

由公式（16）可以判斷某一路徑點(diǎn)是否被節(jié)點(diǎn)覆蓋。

當(dāng)路徑點(diǎn) j 到節(jié)點(diǎn) i 的歐氏距離distancenode-i,path-point-j大于節(jié)點(diǎn)的探測半徑rnode時(shí)，節(jié)點(diǎn)i未能覆蓋路徑點(diǎn)j，否則節(jié)點(diǎn)i 覆蓋了路徑點(diǎn)j。

2.3 QPSO和GPSO實(shí)現(xiàn)軌跡覆蓋問題的比較

（1）個(gè)體編碼

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

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

圖3 粒子個(gè)體編碼

xi和yi分別為第i 個(gè)節(jié)點(diǎn)的x 維度坐標(biāo)和y 維度坐標(biāo)，rand1和rand2是[0，1]間的隨機(jī)數(shù)。對于GPSO 則有公式（18）所示的粒子速度初始化：

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

（2）算法流程

算法流程如圖4 所示。

圖4 QPSO和GPSO的流程圖

（3）結(jié)果比較

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

3 帶聚合度因子的自適應(yīng)全局量子粒子群算法

3.1 QPSO與GPSO存在的問題

根據(jù)圖7 的結(jié)果可知，QPSO 全局尋優(yōu)能力比較強(qiáng)，能達(dá)到比較好的覆蓋率，但是收斂速度比較慢、而GPSO 收斂速度很快但是容易陷入早熟。

圖5 測試GPSO與QPSO的地圖a

3.2 帶GPSO慣性權(quán)重更新的GQPSO

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

圖6 GQPSO算法流程

圖7 9 至14 個(gè)探測器數(shù)量下GQPSO、GPSO、QPSO相應(yīng)覆蓋率的比較

3.3 分析GQPSO的結(jié)果并提出改進(jìn)算法AGQPSO

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

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

3.4 進(jìn)一步改進(jìn)AGQPSO

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

聚合度因子d 定義如下：

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

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

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

圖9 9 至14 個(gè)探測器數(shù)量下AGQPSO、GQPSO、QPSO相應(yīng)覆蓋率的比較

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

3.5 完整算法流程

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

步驟2）按預(yù)設(shè)的迭代次數(shù)進(jìn)行循環(huán)

2.1）對群體中每個(gè)粒子：

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

1）否，執(zhí)行公式（5）的慣性權(quán)重更新規(guī)則

2）是，改變慣性權(quán)重更新規(guī)則

根據(jù)公式（22）結(jié)果分別采用（8）和公式（21）所示的慣性權(quán)重更新規(guī)則計(jì)算每個(gè)粒子的適應(yīng)值，更新粒子的pbest，gbest計(jì)算群體的收斂速度和聚合度，并以此計(jì)算慣性因子

根據(jù)公式（2）計(jì)算粒子下一代位置

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

算法中的學(xué)習(xí)系數(shù)c1和c2與標(biāo)準(zhǔn)中的設(shè)置相同，c1=c2=1.0。

4 實(shí)驗(yàn)設(shè)計(jì)及數(shù)據(jù)分析

4.1 數(shù)據(jù)集與參數(shù)設(shè)置

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

表1 AGQPSO 中的參數(shù)值

4.2 實(shí)驗(yàn)結(jié)果

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

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

圖10 AGQPSO、GPSO和QPSO在探測器個(gè)數(shù)為14時(shí)在地圖6上的結(jié)果

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

5 結(jié)語

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