唐麗晴,應(yīng)忠于,羅 云

(武警海警學(xué)院計算機教研室,浙江 寧波 315801)

0 引 言

基站選址的優(yōu)化是網(wǎng)絡(luò)通訊建設(shè)中的一個重要問題，具有極大的復(fù)雜性[1]。當(dāng)前，人們對網(wǎng)絡(luò)通訊質(zhì)量的需求日益提高，同時，由于網(wǎng)絡(luò)覆蓋率低而導(dǎo)致的用戶與網(wǎng)絡(luò)服務(wù)提供商之間的矛盾亟待有效解決。事實上，基站選址優(yōu)化即是在測試區(qū)域中選擇幾處合適的位置用于架設(shè)基站，從而最大程度地提升網(wǎng)絡(luò)覆蓋率，以提高通訊質(zhì)量。然而，由于基站選址優(yōu)化是一個十分復(fù)雜的問題，且實際優(yōu)化中又涉及諸多復(fù)雜的因素，因此，基站選址優(yōu)化問題不易求得最佳的優(yōu)化解。

通常地，求解基站選址優(yōu)化問題應(yīng)當(dāng)建立其問題的優(yōu)化模型，并采用遺傳算法、免疫算法一類的優(yōu)化算法予以尋優(yōu)，從而求得某一優(yōu)化解。目前，已經(jīng)有大量的研究應(yīng)用于實際的基站選址優(yōu)化問題中。Yang等[2]提出了WCDMA網(wǎng)絡(luò)基站選址優(yōu)化的數(shù)學(xué)模型及啟發(fā)式優(yōu)化算法。朱思峰等[3-4]提出了一種基于免疫計算的基站選址優(yōu)化方案，能以較小的網(wǎng)絡(luò)建設(shè)代價滿足覆蓋要求，在此基礎(chǔ)上又提出了一種基于多目標(biāo)優(yōu)化量子免疫算法的基站選址優(yōu)化方案。針對已有3G基站選址優(yōu)化算法的不足和TD-SCDMA網(wǎng)絡(luò)的特點,張英杰等[5]提出了一種基于免疫算法的TD-SCDMA網(wǎng)絡(luò)基站選址優(yōu)化方案,閆濤[6]提出了一種基于免疫算法的基站選址優(yōu)化方法。趙海濤等[7]闡述了移動通信基站選址的思路、原則以及建站過程中對防雷接地、電磁環(huán)境保護等方面的要求。覃和仁等[8]提出了一種改進(jìn)的遺傳算法，以解決無線網(wǎng)絡(luò)規(guī)劃中的基站選址問題,實現(xiàn)了用最少的基站數(shù)量實現(xiàn)最大覆蓋的優(yōu)化目標(biāo)。這些研究有助于解決基站選址優(yōu)化問題，但由于基站選址問題存在著測試點的數(shù)目繁多且測試區(qū)域的子區(qū)域具有不同的測試點密集程度的問題，此外，現(xiàn)有智能優(yōu)化算法及其改進(jìn)算法存在易于陷入局部收斂的問題，從而導(dǎo)致極難求得選址優(yōu)化的滿意優(yōu)化解。

針對現(xiàn)有智能優(yōu)化算法及其改進(jìn)算法存在的易于陷入局部收斂的問題，本文提出一種鯨魚優(yōu)化改進(jìn)算法。鯨魚優(yōu)化算法(WOA)是模擬鯨魚覓食的一種具有極強全局尋優(yōu)性能的新型仿生優(yōu)化算法，但在算法迭代的后期，其仍然存在著易于陷入局部極值的缺點[9]?；贚évy飛行軌跡，Ling等[10]提出了一種鯨魚優(yōu)化改進(jìn)算法，其Lévy飛行軌跡旨在提升算法的種群多樣性維護能力，以更好地避免其陷入局部最優(yōu)。結(jié)合Elman神經(jīng)網(wǎng)絡(luò)和混沌理論，Sun等[11]提出了一種鯨魚優(yōu)化改進(jìn)算法，基于混沌特性和強大的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)能力，其優(yōu)化改進(jìn)算法具有更佳的全局優(yōu)化性能。針對鯨魚優(yōu)化算法存在探索和開發(fā)能力難以協(xié)調(diào)、易陷入局部最優(yōu)等缺陷，王堅浩等[12]提出了一種基于混沌搜索策略的鯨魚優(yōu)化算法，黃清寶等[13]提出了一種基于余弦控制因子和多項式變異的鯨魚優(yōu)化算法，何慶等[14]提出了一種基于混合策略改進(jìn)的鯨魚優(yōu)化算法，還提出了一種基于自適應(yīng)策略和差分進(jìn)化思想的改進(jìn)鯨魚優(yōu)化算法。龍文等[15]提出了一種基于非線性收斂因子的改進(jìn)鯨魚優(yōu)化算法用于求解大規(guī)模復(fù)雜優(yōu)化問題。范祥等[16]設(shè)計了基于混沌序列搜索算子的混沌鯨魚群算法。鐘明輝等[17]提出了一種隨機調(diào)整控制參數(shù)的改進(jìn)鯨魚優(yōu)化算法。郭振洲等[18]提出了基于自適應(yīng)權(quán)重和柯西變異的鯨魚算法。然而，上述研究，并沒有充分考慮收斂因子非線性遞減以及正態(tài)分布的變異擾動的共同作用以提升鯨魚優(yōu)化算法的全局尋優(yōu)性能，并將其鯨魚優(yōu)化改進(jìn)算法應(yīng)用于求解基站選址優(yōu)化問題中來。在此基礎(chǔ)上，為提高鯨魚優(yōu)化算法的全局尋優(yōu)能力以便于更好地解決基站選址優(yōu)化問題，本文提出一種鯨魚優(yōu)化的改進(jìn)算法，其引入了收斂因子隨著迭代次數(shù)非線性遞減的自適應(yīng)改變策略，同時給出了一種基于Sigmoid函數(shù)的自適應(yīng)變異策略，并對部分個體施加服從正態(tài)分布的變異擾動，以增強其全局優(yōu)化性能，從而求得基站選址優(yōu)化問題的測試算例，相比現(xiàn)有的優(yōu)化改進(jìn)算法具有更理想的優(yōu)化解。

為驗證改進(jìn)算法的有效性，本文基于2種測試函數(shù)和1種基站選址優(yōu)化問題的測試算例，采用不同算法仿真對比。仿真結(jié)果表明，本文提出的鯨魚優(yōu)化改進(jìn)算法具有更佳的全局尋優(yōu)能力。

1 基站選址優(yōu)化模型

通常，基站選址優(yōu)化旨在基站有限的情況下，最大程度地提升網(wǎng)絡(luò)覆蓋率以增強網(wǎng)絡(luò)的通訊質(zhì)量[19]。因此，網(wǎng)絡(luò)覆蓋率優(yōu)化應(yīng)當(dāng)作為其優(yōu)化指標(biāo)，將網(wǎng)絡(luò)覆蓋率記為fcov。與此同時，基站選址優(yōu)化問題又存在著一些約束，諸如基站數(shù)目有限，且其覆蓋范圍也是有限的，基站數(shù)目記為nS。

可假定存在一個含有一定數(shù)量nTP的測試點的測試空間Ω，該測試空間擬建立有限數(shù)量nS的基站，且每個基站的覆蓋范圍是有限的。針對以上描述的基站選址優(yōu)化的約束條件，應(yīng)當(dāng)建立一個普適性的基站選址優(yōu)化模型，其決策變量即為各個基站的選址位置。具體的以網(wǎng)絡(luò)覆蓋率優(yōu)化作為優(yōu)化目的，基站覆蓋范圍有限的優(yōu)化模型為：

(1)

其中，TPS為測試點集合，含nTP個不同的測試點，分別記為1,2,…,i,…,nTP；NS為基站集合，含nS個不同的基站，分別記為1,2,…,j,…,ns；Ω為測試空間；Ωs(j)為第j個基站的覆蓋范圍與測試范圍的集合，因此，任意Ωs(j)都包含于Ω；PTP(i)為第i個測試點的位置，顯然，任意PTP(i)都屬于Ω；TPS(i)為第i個測試點是否能夠被某個基站覆蓋的標(biāo)志，若能，也即存在至少一個序號為k的基站，使得PTP(i)∈Ωk，則TPS(i)=1，否則，TPS(i)=0；網(wǎng)絡(luò)覆蓋率fcov為基站優(yōu)化選址問題的評價指標(biāo)。

2 基本鯨魚優(yōu)化算法

鯨魚優(yōu)化算法(Whale Optimization Algorithm, WOA)是仿照座頭鯨的狩獵行為提出的一種新型啟發(fā)式優(yōu)化算法[20]。該算法主要包括3個階段：包圍獵物、氣泡狩獵、搜索食物。在WOA算法中，每只座頭鯨的位置代表一個決策變量。在海洋活動中，座頭鯨有一種特殊的捕食策略，即沿著圓形或者“9”型路徑產(chǎn)生獨特的氣泡從而不斷靠近獵物進(jìn)行狩獵。

此外，鯨魚采用隨機個體位置的方式尋找獵物，其數(shù)學(xué)模型如下所示：

D=|CXrand-X(t)|

(2)

X(t+1)=Xrand-A·D

(3)

其中，A和C為相關(guān)矩陣系數(shù)，A=2a×r1-a，C=2×r2；r1和r2是(0,1)中的隨機數(shù)；a為收斂因子，其值從2到0線性下降，a=2-2×t/Tmax；D為CXrand與X(t)之間差值的絕對值。Xrand是隨機選擇的鯨魚位置向量，算法設(shè)定A≥1時，隨機選擇一個搜索領(lǐng)導(dǎo)個體，根據(jù)領(lǐng)導(dǎo)個體的鯨魚位置來更新其他鯨魚的位置，引導(dǎo)鯨魚離開獵物，借此找到一個更合適的獵物，其目的在于增強算法的全局搜索能力[21]。

座頭鯨在狩獵的時候，除了包圍獵物，還要以螺旋運動軌跡游向獵物，同時還要收縮包圍圈。其基本鯨魚優(yōu)化算法的位置更新公式描述為：

(4)

其中，Dp=|X*(t)-X(t)|，為座頭鯨與獵物之間的距離；X*(t)為當(dāng)前尋優(yōu)得到的最優(yōu)位置向量；p為座頭鯨的行為選擇概率，p∈[0,1]；Ps為座頭鯨的包圍獵物的概率，Ps∈[0,1]，顯然，其螺旋狩獵的概率為1-Ps；b為常數(shù)，用來定義螺線的形狀；l是(-1,1)中的隨機數(shù)；t為當(dāng)前的迭代次數(shù)。

3 鯨魚優(yōu)化算法的改進(jìn)策略

3.1 收斂因子非線性遞減

在鯨魚優(yōu)化算法迭代計算的前期，收斂因子a應(yīng)取較大的值以增強全局勘探能力，從而提升收斂速度；相反地，在算法迭代計算的后期，收斂因子a應(yīng)取較小的值以增強局部尋優(yōu)能力，從而提高收斂精度。但若收斂因子a線性遞減，會使得整個算法在迭代過程中總是具有相同的遞減速率[22]。這種相對固定的規(guī)律會降低鯨魚種群的多樣性維護能力，不利于其全局收斂。為此，本文采用了余弦遞減結(jié)合混沌隨機的收斂因子非線性遞減的策略，具體的計算公式如下：

(5)

其中，Tmax為最大迭代次數(shù)；Pa為收斂因子余弦遞減的概率，Pa∈[0,1]，顯然，收斂因子混沌擾動的概率為1-Pa；pa(t)為收斂因子在當(dāng)前迭代次數(shù)t下的行為選擇概率。

基于上述計算公式(5)，可使收斂因子在整個迭代周期非線性的遞減，且存在著一定程度的不確定性。其收斂因子a和進(jìn)化代數(shù)t的關(guān)系曲線如圖1所示。

圖1 收斂因子a和進(jìn)化代數(shù)t的關(guān)系曲線

由圖1可知，在整個計算迭代的周期，收斂因子余弦遞減是主要趨勢，但也存在著一定程度的混沌隨機。相比于盲目隨機，這種基于混沌映射的混沌隨機具有一定的規(guī)律，因而，能夠避免盲目隨機造成的算法收斂速度慢、過度搜索無效區(qū)域等問題[23]。相比于線性遞減的策略，這種收斂因子非線性遞減的策略使得收斂因子在整個迭代周期的遞減速度差異性明顯，且具有一定程度的混沌不確定性，因而能夠更好地維護鯨魚種群的多樣性，從而有利于算法全局收斂。

3.2 服從正態(tài)分布的變異擾動

鯨魚算法令全部個體向最優(yōu)個體靠攏，容易使算法陷入局部極值。本文為使算法具有更強的全局收斂能力，在鯨魚個體隨機狩獵以前，對部分鯨魚個體施加一種服從正態(tài)分布的變異擾動，以避免局部收斂，具體的變異擾動更新公式如下：

X′=X+Δmax·rand(0,1,-1,1)，pd

(6)

其中，X為未施加變異擾動前的鯨魚個體；X′為施加變異擾動后的鯨魚個體；rand(0,1,-1,1)為(-1,1)區(qū)間的均值為0標(biāo)準(zhǔn)差為1的服從正態(tài)分布的隨機數(shù)；Δmax為變異擾動的最大值，Δmax=0.1·min (X-Xmin,Xmax-X)，Xmin為鯨魚個體的邊界下限，Xmax為鯨魚個體的邊界上限；pd為變異擾動的行為選擇概率，pd∈[0,1]；Pd為變異擾動概率，Pd∈[0,1]。

正態(tài)分布具有靠近均值的中間部分密集而兩邊稀疏的特點。相比于平均分布隨機數(shù)，正態(tài)分布隨機數(shù)有更多的幾率獲得靠近均值的隨機數(shù)值。對于變異擾動而言，過多劇烈的擾動會破壞算法的尋優(yōu)模式，但擾動強度太小，又無法起到增強全局尋優(yōu)能力的效果[24]。由計算公式(6)可知，本文給出的變異擾動策略令擾動強度足夠大，又不過度地不斷擾動，從而達(dá)到在不破壞算法尋優(yōu)能力的前提下，避免算法早熟收斂。

4 仿真實驗

4.1 鯨魚優(yōu)化改進(jìn)算法的參數(shù)設(shè)置

本文提出一種鯨魚優(yōu)化改進(jìn)算法，其鯨魚優(yōu)化改進(jìn)算法的參數(shù)設(shè)置如下：包圍獵物的概率P為0.6，收斂因子余弦遞減的概率Pa為0.9，變異擾動的概率Pd為0.15，最大迭代次數(shù)Tmax為100。本文在同時兼顧收斂速度和尋優(yōu)效果的基礎(chǔ)上，通過多次試驗的仿真效果給出了上述的優(yōu)化參數(shù)。

4.2 基于測試函數(shù)的仿真對比

為驗證本文提出的鯨魚優(yōu)化改進(jìn)算法具有一定的優(yōu)化改善效果，本文采用2種單目標(biāo)的測試函數(shù)(De jong、Schaffer)和一種雙目標(biāo)測試函數(shù)(ZDT1)對本文提出的鯨魚優(yōu)化改進(jìn)算法、基本鯨魚優(yōu)化算法和基本粒子群優(yōu)化算法這3種不同的優(yōu)化算法進(jìn)行仿真對比。以下是具體的仿真對比結(jié)果：

1)De jong函數(shù)(最優(yōu)解為0.0)。

其具體的解析式為:

F(x1,x2)=100×(x1-x2)2+(1-x1)2

具體的De jong函數(shù)的仿真測試結(jié)果如圖2和表1所示。

圖2 采用De jong函數(shù)的仿真測試收斂曲線

表1 采用De jong函數(shù)的仿真測試結(jié)果

由圖2和表1可知，相比其他算法，本文提出的鯨魚優(yōu)化改進(jìn)算法最優(yōu)，其最優(yōu)解為(x1,x2)=(0.9958,0.9943)，最優(yōu)解函數(shù)值為F(x1,x2)=2.4×10-4。

2) Schaffer函數(shù)(最優(yōu)解為0.0)。

其具體的解析式為：

具體的Schaffer函數(shù)的仿真測試結(jié)果如圖3和表2所示。

圖3 采用Schaffer函數(shù)的仿真測試收斂曲線

表2 采用Schaffer函數(shù)的仿真測試結(jié)果

由圖3和表2可知，相比其他算法，本文提出的鯨魚優(yōu)化改進(jìn)算法最優(yōu)，其最優(yōu)解為(x1,x2)=(3.8×10-4,4.1×10-4)，最優(yōu)解函數(shù)值為F(x1,x2)=5.6×10-4。

3)ZDT1函數(shù)。

具體的解析式為：

f1(x)=x1

x=(x1,x2,…,xn)T∈[0,1]n

具體的ZDT1函數(shù)的仿真測試結(jié)果如圖4和表3所示。

(a) 本文提出的鯨魚優(yōu)化改進(jìn)算法得到的優(yōu)化結(jié)果

(b) 基本鯨魚優(yōu)化算法得到的優(yōu)化結(jié)果

(c) 基本粒子群優(yōu)化算法得到的優(yōu)化結(jié)果

表3 采用ZDT1函數(shù)的仿真測試結(jié)果

表3中，反向世代距離被作為評價指標(biāo)，記為IGD值。IGD值越低，說明算法得到的Pareto解集的收斂性和多樣性越好，越接近真實的Pareto front。其計算公式如式(7)所示：

(7)

其中，P為真實Pareto front的均勻采樣點集合，P′為待測試算法得到的近似Pareto解集，|P|為集合P的規(guī)模，d(Pip,P′)為第ip個Pareto采樣點Pi與Pareto解集P′之間的最小距離。

由圖4和表3可知，相比其他算法，本文提出的鯨魚優(yōu)化改進(jìn)算法最優(yōu)，其尋優(yōu)得到的最優(yōu)IGD值為7.34×10-4。

4.3 基于基站選址優(yōu)化問題的測試算例的仿真對比

本文采用基站選址優(yōu)化問題的測試算例，對本文提出的鯨魚優(yōu)化改進(jìn)算法、基本鯨魚優(yōu)化算法和基本粒子群優(yōu)化算法這3種不同的優(yōu)化算法進(jìn)行仿真對比。本文選用的基站選址問題的測試算例的參數(shù)如下：基站數(shù)目為3，其網(wǎng)絡(luò)覆蓋半徑分別為15 km、15 km和10 km，測試區(qū)域為60×60 km2，測試點總數(shù)目為200個。上述基站選址問題的測試算例來源于某一實際地理區(qū)域的某時刻的虛擬通訊示意圖，該地域既包含通訊密集的地域(居民區(qū)及商業(yè)區(qū))，又包含通訊稀疏的地域(河灘、山地及自留開發(fā)區(qū))，按照各個區(qū)域的不同測試點密度隨機地散布測試點。

以下是具體的測試結(jié)果。本文選用的基站選址問題的測試算例的虛擬通訊示意圖如圖5所示。采用本文提出的鯨魚優(yōu)化改進(jìn)算法、基本鯨魚優(yōu)化算法和基本粒子群優(yōu)化算法求解得到的各個優(yōu)化算法的基站選址位置及最終優(yōu)化結(jié)果如表4和表5所示，基站選址網(wǎng)絡(luò)覆蓋效果如圖6～圖8所示，各個優(yōu)化算法的迭代收斂曲線如圖9所示。

圖5 選用的基站選址問題的測試算例的虛擬通訊示意圖

表4 各個優(yōu)化算法得到的最終優(yōu)化結(jié)果

表5 各個優(yōu)化算法得到的基站選址中心點位置

圖6 本文提出的鯨魚優(yōu)化改進(jìn)算法得到的基站選址網(wǎng)絡(luò)覆蓋效果圖

圖7 基本鯨魚優(yōu)化算法得到的基站選址網(wǎng)絡(luò)覆蓋效果圖

圖8 基本粒子群優(yōu)化算法得到的基站選址網(wǎng)絡(luò)覆蓋效果圖

圖9 各個優(yōu)化算法的迭代曲線

由表5和圖9可知，相較于基本鯨魚優(yōu)化算法和基本粒子群優(yōu)化算法，采用本文提出的鯨魚優(yōu)化改進(jìn)算法求解得到的基站選址位置建設(shè)基站，可以獲得明顯較優(yōu)的網(wǎng)絡(luò)覆蓋效果，且具有更快的收斂速度。由圖6～圖8可知，相較于基本鯨魚優(yōu)化算法和基本粒子群優(yōu)化算法，本文提出的鯨魚優(yōu)化改進(jìn)算法求解得到的基站選址位置的網(wǎng)絡(luò)覆蓋區(qū)域?qū)y試點密集區(qū)有著更好的覆蓋效果。因此，本文提出的鯨魚優(yōu)化改進(jìn)算法更適合于解決復(fù)雜的基站選址優(yōu)化問題。

5 結(jié)束語

本文基于基站選址優(yōu)化問題的約束條件，以網(wǎng)絡(luò)覆蓋率作為優(yōu)化指標(biāo)，構(gòu)建了一種基站選址優(yōu)化模型。在此基礎(chǔ)上，本文提出了一種鯨魚優(yōu)化改進(jìn)算法以更好地解決基站選址優(yōu)化問題。具體的改進(jìn)策略如下：1)設(shè)計了一種收斂因子隨著迭代次數(shù)非線性遞減的自適應(yīng)改變策略以提升優(yōu)化算法的全局尋優(yōu)能力；2)采用了一種對部分個體施加服從正態(tài)分布的變異擾動策略，以避免優(yōu)化算法早熟收斂。

為驗證本文提出的鯨魚優(yōu)化改進(jìn)算法的有效性，采用2種測試函數(shù)和1種基站選址優(yōu)化問題的測試算例對3種不同的優(yōu)化算法進(jìn)行仿真驗證。其仿真結(jié)果都表明，本文提出的鯨魚優(yōu)化改進(jìn)算法的全局優(yōu)化性能更佳，能夠獲得更優(yōu)的最終優(yōu)化結(jié)果，且收斂速度更快。