馮思堯，張程瀟，柳 毅

（杭州電子科技大學(xué) 管理學(xué)院，浙江 杭州 310018）

0 引言

伴隨著物聯(lián)網(wǎng)的快速發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Network）在生活中的應(yīng)用也越來(lái)越廣泛[1]。無(wú)線傳感器網(wǎng)絡(luò)包含著若干傳感器（Sensors）以及一個(gè)數(shù)據(jù)中心（Data Center），信息通過(guò)傳感器傳送到數(shù)據(jù)中心。在傳感器無(wú)法利用自然條件（太陽(yáng)能）獲取能量的情況下，則需要安排移動(dòng)充電設(shè)備給傳感器電池供電，這時(shí)網(wǎng)絡(luò)稱(chēng)為無(wú)線可充電傳感器網(wǎng)絡(luò) （Wireless Rechargeable Sensor Network，WRSN）。因此，為維持WRSN正常工作，合理規(guī)劃移動(dòng)充電設(shè)備的路徑為傳感器提供能量成為重要的研究問(wèn)題。

梁曉輝等（2020）對(duì)常見(jiàn)的路徑規(guī)劃求解算法進(jìn)行綜述并從不同方面比較各種算法的優(yōu)劣[2]。姚明海等（2013）將模擬退火算法和遺傳算法融合求解TSP（Traveling Salesman Problem）問(wèn)題，利用遺傳算法的全局搜索能力彌補(bǔ)了模擬退火算法容易陷入局部最優(yōu)的問(wèn)題[3]。謝艷麗等（2014）根據(jù)交叉算子和變異算子的特點(diǎn)，針對(duì)交叉算子引入拉普拉斯算子進(jìn)行改進(jìn)，并結(jié)合黃金分割法針對(duì)變異算子進(jìn)行優(yōu)化，提高收斂速度，同時(shí)避免過(guò)早陷入局部最優(yōu)解[4]。于瑩瑩等（2014）在傳統(tǒng)遺傳算法中引入貪婪算法進(jìn)行種群初始化，采用精英個(gè)體保留的選擇方法調(diào)節(jié)個(gè)體適應(yīng)，使其在種群較小的時(shí)候具有較強(qiáng)的尋優(yōu)能力[5]。孫文彬等（2016）改進(jìn)遺傳算法初始解的構(gòu)造方法，引入并行交叉和局部?jī)?yōu)化策略，明顯提升了大規(guī)模TSP問(wèn)題的求解效率[6]。徐練淞等（2017）在蟻群算法的基礎(chǔ)上針對(duì)TSP問(wèn)題提出了一種新型的改進(jìn)蟻群算法，即變參數(shù)選擇城市策略，并且在交叉策略中選擇PMX（Partially Matched Crossover）交叉策略，實(shí)驗(yàn)結(jié)果表明與基本蟻群算法和遺傳算法相比，該方法能夠較快找到最優(yōu)解，求解質(zhì)量也較好[7]。何慶等（2018）根據(jù)舊種群和新種群每個(gè)對(duì)應(yīng)個(gè)體的進(jìn)化程度提出一種改進(jìn)自適應(yīng)的Metropolis準(zhǔn)則，使IGSAA（Improved Genetic Simulated Annealing Algorithm）算法能夠有效地避免陷入局部最優(yōu)，但其對(duì)參數(shù)的設(shè)置具有較大的依賴(lài)[8]。包強(qiáng)（2021）引入并行計(jì)算思想，先用遺傳算法獲得較優(yōu)的初始解，再通過(guò)模擬退火算法進(jìn)行求解，提高了計(jì)算速度以及穩(wěn)定性[9]。許煥等（2021）針對(duì)小車(chē)充電路徑規(guī)劃問(wèn)題，使用變步長(zhǎng)優(yōu)化算法和模擬退火算法組合求解，并由此推廣到了n個(gè)小車(chē)及其對(duì)應(yīng)的電池容量[10]。

本文在研究無(wú)線可充電傳感器網(wǎng)絡(luò)中充電小車(chē)的路徑規(guī)劃問(wèn)題時(shí)，將其視為一個(gè)旅行商路徑優(yōu)化問(wèn)題（Traveling Salesman Problem，TSP）進(jìn)行求解，從圖論的角度建立旅行商問(wèn)題的0-1規(guī)劃數(shù)學(xué)模型，針對(duì)旅行商優(yōu)化問(wèn)題中模擬退火算法（Simulated Annealing，SA）收斂速度慢的問(wèn)題提出一種基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法，使模擬退火算法部分的溫度控制變得更具有自適應(yīng)性，利于該算法實(shí)現(xiàn)通過(guò)充電站尋找到從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路線。

1 單車(chē)充電的路徑規(guī)劃數(shù)學(xué)模型

以2020年“深圳杯”數(shù)學(xué)建模挑戰(zhàn)賽C題為例，從圖論的角度考慮，將充電網(wǎng)絡(luò)模型描述為由n個(gè)節(jié)點(diǎn)構(gòu)成的一個(gè)無(wú)向帶權(quán)圖，記做G=（V，E），V表示移動(dòng)充電器以及傳感器的點(diǎn)集，V={0，1，2，…，29}，其中0表示數(shù)據(jù)中心。E={（i，j）|i，j∈v，i≠j}是n（n-1）/2條邊構(gòu)成的集合，移動(dòng)充電器從數(shù)據(jù)中心0出發(fā)，依次經(jīng)過(guò)29個(gè)傳感器進(jìn)行充電，完成后再次返回?cái)?shù)據(jù)中心。此問(wèn)題即求在圖G中找到由起點(diǎn)出發(fā)的一條經(jīng)過(guò)所有點(diǎn)再回到起點(diǎn)的最短路徑，建立以最短路徑長(zhǎng)度為目標(biāo)函數(shù)的0-1規(guī)劃模型：

其中，xij表示連接節(jié)點(diǎn)i和j邊，當(dāng)取值為1時(shí)，此條邊在最短路徑上；當(dāng)取值為0時(shí)，表示不在最短路徑上。dij為邊xij的權(quán)重大小，即是節(jié)點(diǎn)i和節(jié)點(diǎn)j根據(jù)經(jīng)緯度求解兩點(diǎn)球面距離半正矢公式（Haversine公式）計(jì)算得到的兩點(diǎn)間歐氏直線距離。約束式表示任意一個(gè)節(jié)點(diǎn)都只有一個(gè)出邊和入邊，并保證沒(méi)有任何子回路解產(chǎn)生，即所產(chǎn)生的路徑是包括所有節(jié)點(diǎn)的單一哈密頓回路。

2 求解單車(chē)充電路徑規(guī)劃的改進(jìn)模擬退火算法

2.1 標(biāo)準(zhǔn)的模擬退火算法

傳統(tǒng)的模擬退火算法（SA）通過(guò)給當(dāng)前算法提供一個(gè)初始值作為當(dāng)前解，這個(gè)解包含的部分元素通過(guò)變換產(chǎn)生大量新解，SA算法選擇其中的最優(yōu)解作為當(dāng)前解。SA算法具體步驟[3]及流程如圖1所示。

圖1 模擬退火算法流程圖Figure 1 Flowchart of the simulated annealing algorithm

步驟1：選擇初始路徑S1，確定初始溫度T1，設(shè)置當(dāng)前路徑Si=S1，當(dāng)前溫度T=Tr，確定每個(gè)迭代次數(shù)對(duì)應(yīng)的鏈長(zhǎng)L；

步驟2：從Si的鄰域中隨機(jī)選擇Sj，計(jì)算ΔS=Sj-Si，判斷ΔS是否小于等于0，是則令Si=Sj，否則進(jìn)行第3步；

步驟3：計(jì)算Sj的接受概率＞random（0，1），即判斷接受概率是否大于（0，1）區(qū)間上的隨機(jī)數(shù)，若大于則確定Sj為新的當(dāng)前路徑，否則保留原路徑Si；

步驟4：如果滿足在若干個(gè)Metropolis鏈中新解Sj都沒(méi)有被接受時(shí)終止算法，或設(shè)定結(jié)束溫度，否則按衰減函數(shù)衰減T后回到步驟2。

2.2 動(dòng)態(tài)概率

當(dāng)M0＞M1時(shí)，當(dāng)前解M0與新解M1越接近，需要考慮接受新解的概率P，概率P越大，我們更加傾向于接受M1。因?yàn)镻越大意味著在解空間搜索范圍更廣，為了使得搜索工作更加高效，前期搜索范圍廣，后期更加傾向于局部搜索。定義初始溫度T0=1000，溫度下降后Tt（t為迭代次數(shù)）為：

基于此，構(gòu)造出概率關(guān)于溫度和目標(biāo)值差的關(guān)系表達(dá)式：

2.3 基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法

本文在傳統(tǒng)模擬退火算法的基礎(chǔ)上提出基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法。首先，通過(guò)蒙特卡洛模擬算法隨機(jī)生成多個(gè)初始值，并選擇其中的最優(yōu)解作為當(dāng)前解；其次，同時(shí)采用交換法、移位法、倒序法三種方法來(lái)產(chǎn)生新解（算法中每種方法采用的概率相同，均為1/3，如圖2所示），根據(jù)每次產(chǎn)生的新解對(duì)應(yīng)的目標(biāo)函數(shù)M的值計(jì)算出動(dòng)態(tài)概率P，并在此基礎(chǔ)上判斷對(duì)該解是否接受；最后，在迭代次數(shù)終止后，輸出當(dāng)前最優(yōu)解作為結(jié)果?；趧?dòng)態(tài)概率的改進(jìn)模擬退火算法如表1所示。

表1 基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法Table 1 An improved simulated annealing algorithm based on dynamic probability

圖2 交換法、移位法、倒序法求解過(guò)程圖Figure 2 Solution diagram of exchange method，shift method and reverse order method

3 仿真實(shí)驗(yàn)與數(shù)據(jù)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理

本文研究的問(wèn)題引自2020年“深圳杯”數(shù)學(xué)建模挑戰(zhàn)賽C題[11]，仿真實(shí)驗(yàn)中共給出30個(gè)節(jié)點(diǎn)（包含基站數(shù)據(jù)中心），并在給出每個(gè)節(jié)點(diǎn)經(jīng)緯度且只派出一個(gè)移動(dòng)充電器的前提下規(guī)劃出最優(yōu)充電路線。如圖3所示為WSN的網(wǎng)絡(luò)數(shù)據(jù)中心及傳感器的經(jīng)緯度位置信息圖。在一個(gè)充電周期內(nèi)，使得移動(dòng)充電器在路程上的能量消耗最小，其本質(zhì)為一個(gè)TSP問(wèn)題，因此我們采用了TSP問(wèn)題下的最短哈密頓回路，將一個(gè)充電周期內(nèi)最少能量消耗問(wèn)題轉(zhuǎn)換為求解充電回路最短問(wèn)題?；诖耍⒁宰疃搪窂介L(zhǎng)度為目標(biāo)函數(shù)的0-1規(guī)劃模型，通過(guò)貪婪算法對(duì)模型進(jìn)行求解，同時(shí)使用基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法求解模型，并將得到的結(jié)果進(jìn)行對(duì)比以驗(yàn)證算法的可行性。

圖3 WSN網(wǎng)絡(luò)的數(shù)據(jù)中心及傳感器的經(jīng)緯度位置信息圖Figure 3 The latitude and longitude location information map of the data center and sensors in the WSN network

3.2 實(shí)驗(yàn)過(guò)程

利用貪婪算法求解移動(dòng)充電器充電的最短路徑，首先計(jì)算各個(gè)傳感器與數(shù)據(jù)中心的距離，以當(dāng)前移動(dòng)充電器所在位置為基礎(chǔ)做出路徑最短的最優(yōu)選擇，選取每一次移動(dòng)的局部最優(yōu)解即每一次移動(dòng)的最短路徑，通過(guò)一系列局部最優(yōu)解的選擇，累加得到最終路徑的規(guī)劃路線。通過(guò)上述貪婪算法，得到的最優(yōu)路徑為：（V0表示數(shù)據(jù)中心）V0-V2-V1-V9-V7-V6-V11-V14-V15-V12-V8-V10-V5-V3-V4-V22-V23-V21-V17-V20-V19-V18-V25-V26-V29-V24-V28-V13-V16-V27-V0；對(duì)應(yīng)的最短路徑長(zhǎng)度為：13.817km。如圖4所示為基于路徑最短原則的貪婪算法最優(yōu)路徑規(guī)劃圖。

圖4 基于路徑最短原則的貪婪算法的最優(yōu)路徑規(guī)劃圖Figure 4 The optimal path planning diagram of the greedy algorithm based on the path minimum principle

基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法求解模型得到的最優(yōu)路徑為：（V0表示數(shù)據(jù)中心）V0-V2-V1-V9-V7-V6-V14-V11-V8-V12-V15-V27-V16-V13-V10-V5-V3-V4-V22-V28-V24-V23-V21-V29-V26-V25-V18-V19-V20-V17-V0；本實(shí)驗(yàn)用Python語(yǔ)言編程求解[12]，獲得單充車(chē)充電路線總行程對(duì)應(yīng)的最短路徑長(zhǎng)度為：11.485km。如圖5所示為基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法的近似最優(yōu)規(guī)劃路徑。

圖5 基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法的近似最優(yōu)規(guī)劃路徑Figure 5 Approximate optimal planning path of improved simulated annealing algorithm based on dynamic probability

3.3 實(shí)驗(yàn)結(jié)果分析

對(duì)于一個(gè)可移動(dòng)充電器充電網(wǎng)絡(luò)路徑規(guī)劃模型，采用基于最短路徑的貪婪算法與改進(jìn)的模擬退火算法進(jìn)行求解，得到兩種移動(dòng)充電器的充電路徑對(duì)比結(jié)果如表2所示?；趧?dòng)態(tài)概率的改進(jìn)模擬退火算法迭代過(guò)程如圖6所示。

表2 貪婪算法與改進(jìn)的模擬退火算法的充電路徑優(yōu)化結(jié)果對(duì)比Table 2 Comparison of charging path optimization results between greedy algorithm and improved simulated annealing algorithm

通過(guò)圖6可以看出：基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法在迭代50次之前，能夠快速下降使得規(guī)劃路徑長(zhǎng)度快速縮短；在迭代50次之后，路徑長(zhǎng)度曲線下降減緩并在300次之前達(dá)到收斂，因此該算法在大于50次的迭代次數(shù)下均能夠獲得較好的結(jié)果。對(duì)比文獻(xiàn)[10]的優(yōu)化結(jié)果，本文提出的改進(jìn)算法獲得的最優(yōu)路徑為11.485km，且在迭代300次后算法進(jìn)入收斂趨勢(shì)。對(duì)相同數(shù)據(jù)，兩種算法所得的最優(yōu)結(jié)果相似，但本算法的迭代次數(shù)與運(yùn)行時(shí)間均得到了較大的優(yōu)化。

4 結(jié)語(yǔ)

本文將無(wú)線傳感器網(wǎng)絡(luò)中單車(chē)充電路徑規(guī)劃問(wèn)題抽象為NP-hard經(jīng)典旅行商問(wèn)題（TSP），建立數(shù)學(xué)模型，并提出基于動(dòng)態(tài)概率的改進(jìn)模擬退火算法。改進(jìn)算法通過(guò)動(dòng)態(tài)概率和交換法、移位法、倒序法調(diào)節(jié)模擬退火算法的參數(shù)來(lái)優(yōu)化局部尋優(yōu)能力和全局尋優(yōu)能力。仿真實(shí)驗(yàn)結(jié)果表明，與路徑最短的貪婪算法和傳統(tǒng)模擬退火算法求解結(jié)果相比，本文的改進(jìn)模擬退火算法在求解無(wú)線傳感器網(wǎng)絡(luò)中單車(chē)充電路徑規(guī)劃問(wèn)題時(shí)具有收斂精度高、全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)。