化的LTE基站覆蓋率提升)
1. 問題建模思路先把“覆蓋率”變成一個(gè)能被算法優(yōu)化的數(shù)學(xué)對象1.1 基站覆蓋率優(yōu)化為什么是個(gè)“一眼看不透”的難題做LTE網(wǎng)絡(luò)規(guī)劃的朋友都知道基站位置選得好不好直接決定了覆蓋、容量和干擾這三本賬。尤其是室外宏基站站址一旦定了后期再想去挪位置牽扯到物業(yè)、傳輸、天面協(xié)調(diào)代價(jià)極高。所以在規(guī)劃階段就盡量把覆蓋率做上去是性價(jià)比最高的做法。但這里面有個(gè)尷尬的現(xiàn)實(shí)基站覆蓋率問題從數(shù)學(xué)上看是一個(gè)典型的非凸、多峰、帶約束的組合優(yōu)化問題?；緮?shù)量和位置是離散與連續(xù)混合的變量覆蓋效果又和地形、傳播環(huán)境、頻率、天線傾角攪在一起。你很難用常規(guī)梯度方法去優(yōu)化因?yàn)槟繕?biāo)函數(shù)根本不光滑甚至很多格點(diǎn)覆蓋不覆蓋是“跳變”的。稍微換一組站址覆蓋率可能從85%掉到70%。傳統(tǒng)的遍歷搜索更不可行——在一個(gè)2km×2km的城區(qū)里放10個(gè)站位置組合的空間基本上是天文數(shù)字。這時(shí)候工程上普遍的做法就是用群體智能算法去逼近最優(yōu)解。粒子群優(yōu)化PSO是這個(gè)領(lǐng)域的老熟人了原理簡單、實(shí)現(xiàn)容易、收斂也快。但做過的同學(xué)應(yīng)該深有體會(huì)標(biāo)準(zhǔn)PSO在這個(gè)問題上特別容易早熟粒子飛到一定階段就全擠在某個(gè)局部峰附近覆蓋率鎖定在82%左右再也上不去。原因在于標(biāo)準(zhǔn)PSO靠速度更新粒子的搜索軌跡受慣性權(quán)重和學(xué)習(xí)因子約束一旦所有粒子的個(gè)體最優(yōu)和全局最優(yōu)都趨于一致速度就會(huì)迅速衰減群體失去探索能力。我最初復(fù)現(xiàn)這個(gè)題目時(shí)用的就是標(biāo)準(zhǔn)PSO結(jié)果在多個(gè)隨機(jī)初值下最終覆蓋率一直穩(wěn)定在一個(gè)不太理想的值域。后來才意識(shí)到不是問題本身沒得優(yōu)化而是算法的逃逸能力不夠。這也是為什么后來的版本里我換成了量子粒子群優(yōu)化QPSO并在其中引入柯西分布策略的原因。1.2 為什么選量子粒子群優(yōu)化這條技術(shù)路線標(biāo)準(zhǔn)PSO的困境本質(zhì)上來自它的“軌道模型”——粒子像經(jīng)典力學(xué)中的小球在解空間里沿速度方向運(yùn)動(dòng)。量子粒子群優(yōu)化QPSO換了個(gè)思路粒子不再有明確的速度向量而是由一個(gè)量子波函數(shù)來描述位置通過圍繞某個(gè)吸引子的概率采樣得到。這樣一來粒子可以在解空間的很大范圍內(nèi)保持“不確定性”理論上不存在速度為零導(dǎo)致的停滯問題全局搜索能力更強(qiáng)。但QPSO也不是銀彈。它有兩個(gè)軟肋一是隨著迭代推進(jìn)收縮擴(kuò)張系數(shù)會(huì)讓種群逐步收斂如果陷入局部最優(yōu)想跳出來同樣需要外部擾動(dòng)二是它的隨機(jī)采樣用的是指數(shù)分布產(chǎn)生的擾動(dòng)量級(jí)在后期偏小一旦粒子群聚攏步長不足以跨出局部盆地。所以這個(gè)題目里的“柯西分布”改良就有了明確的目標(biāo)利用柯西分布重尾的特性在算法后期仍然有一定概率產(chǎn)生大幅度的隨機(jī)擾動(dòng)把粒子從局部最優(yōu)附近“踹出去”同時(shí)保留QPSO收斂快、參數(shù)少、全局性好的底子。整條技術(shù)路線可以概括成四個(gè)字重尾逃逸。我后面會(huì)詳細(xì)拆解這個(gè)改進(jìn)怎么落到Matlab代碼里以及我在復(fù)現(xiàn)過程中踩過的坑。先把模型說清楚因?yàn)樗惴ㄔ購?qiáng)靶子畫歪了也白搭。2. 覆蓋率問題建模先有精準(zhǔn)的靶子才能談算法2.1 覆蓋區(qū)域網(wǎng)格化與傳播模型要做覆蓋率優(yōu)化第一步是定義“覆蓋率”到底怎么算。我用的方案是均勻網(wǎng)格化把整個(gè)規(guī)劃區(qū)域劃分成等間隔的格點(diǎn)每個(gè)格點(diǎn)看作一個(gè)潛在用戶位置然后計(jì)算每個(gè)格點(diǎn)收到的參考信號(hào)接收功率RSRP如果某個(gè)格點(diǎn)收到的最大RSRP高于設(shè)定閾值就認(rèn)為這個(gè)格點(diǎn)被覆蓋。網(wǎng)格粒度直接影響算法的計(jì)算量和精度。我在復(fù)現(xiàn)中把研究區(qū)域設(shè)為2km×2km的正方形區(qū)域網(wǎng)格間隔選50m這樣一共有41×411681個(gè)格點(diǎn)。這個(gè)粒度在工程上夠用算起來也快。如果網(wǎng)格縮到25m格點(diǎn)會(huì)膨脹到6889個(gè)覆蓋率計(jì)算一次雖然也能跑但算法要做幾百上千次適應(yīng)度評估總耗時(shí)立刻上去了。所以建議做學(xué)術(shù)復(fù)現(xiàn)時(shí)先用50m粒度驗(yàn)證算法邏輯再按需加密。傳播模型我用的是Cost231-Hata擴(kuò)展模型適用于2GHz頻段、城市宏蜂窩場景。路徑損耗公式如下PL 46.3 33.9×log10(f) ? 13.82×log10(hb) ? a(hm) (44.9 ? 6.55×log10(hb))×log10(d) Cm其中f為頻率MHzhb為基站天線高度mhm為終端天線高度md為基站到終端的距離kmCm為城市修正因子大城市約3dB。a(hm)是移動(dòng)臺(tái)高度修正因子在2GHz、大城市環(huán)境下近似為a(hm) 3.2×(log10(11.75×hm))2 ? 4.97我建模時(shí)用的參數(shù)是f2000MHzhb35mhm1.5m那么a(hm)算出來大約是0.33dB。基站發(fā)射功率Pt取43dBm天線增益Gt取17dBi線纜損耗取2dB。覆蓋閾值設(shè)為RSRP ≥ ?105dBm這是LTE網(wǎng)絡(luò)規(guī)劃的常見標(biāo)準(zhǔn)。在距離d很小的地方傳播模型會(huì)出現(xiàn)log10(d)為負(fù)無窮的異常所以我在代碼里給d加了保護(hù)最小值不小于50m。這個(gè)細(xì)節(jié)別看小不加的話靠近基站的格點(diǎn)覆蓋會(huì)算出離譜的負(fù)無窮結(jié)果直接污染適應(yīng)度。2.2 目標(biāo)函數(shù)與約束條件的設(shè)計(jì)細(xì)節(jié)網(wǎng)格點(diǎn)和傳播模型定下來后某個(gè)基站部署方案對應(yīng)的覆蓋率就可以計(jì)算了。計(jì)算路徑是遍歷所有基站對每個(gè)網(wǎng)格點(diǎn)計(jì)算各基站到達(dá)該點(diǎn)的RSRP取最大值作為有效接收電平然后和閾值比較。如果某個(gè)格點(diǎn)被至少一個(gè)基站覆蓋就標(biāo)記為覆蓋格點(diǎn)。覆蓋率Coverage就是Coverage 覆蓋格點(diǎn)數(shù) / 總格點(diǎn)數(shù)這個(gè)指標(biāo)本身是越大越好但群體智能算法習(xí)慣處理最小化問題我一般做一步轉(zhuǎn)換定義優(yōu)化目標(biāo)為未覆蓋率Fitness 1 ? Coverage讓算法去最小化這個(gè)Fitness值邏輯上更順畫收斂曲線時(shí)也是單調(diào)下降的趨勢和文獻(xiàn)里的習(xí)慣一致。約束條件的處理同樣關(guān)鍵。這個(gè)題目里主要有三類約束一是基站數(shù)量固定假設(shè)規(guī)劃區(qū)內(nèi)部署N個(gè)宏基站這個(gè)N在優(yōu)化過程中不變只優(yōu)化它們的位置。位置變量用(x, y)坐標(biāo)表示維度就是2N維。二是邊界約束基站必須落在規(guī)劃區(qū)域內(nèi)不允許漂到區(qū)域外面。我在代碼里用上下界綁定變量維度每個(gè)維度的范圍都是[0, 2000]。三是最小站間距約束工程上基站太近會(huì)造成嚴(yán)重干擾我設(shè)置LTE宏站的最小站間距為300m。這個(gè)約束在基礎(chǔ)版實(shí)現(xiàn)里不好直接塞進(jìn)適應(yīng)度函數(shù)因?yàn)橐坏┊?dāng)懲罰項(xiàng)用需要人工調(diào)懲罰系數(shù)很容易把目標(biāo)函數(shù)搞失真。我后來采用的處理方式是在適應(yīng)度函數(shù)里增加一個(gè)輕微的懲罰項(xiàng)一旦兩個(gè)基站距離小于300m就在未覆蓋率基礎(chǔ)上加上一個(gè)懲罰增量讓算法主動(dòng)遠(yuǎn)離這種方案。目標(biāo)函數(shù)、網(wǎng)格化、傳播模型這三位一體弄清楚了后面的算法才有發(fā)揮空間。很多人在這一步圖省事直接把覆蓋率的計(jì)算公式簡化成“距離小于某個(gè)半徑就算覆蓋”這在對比算法優(yōu)劣時(shí)問題不大但如果要把絕對數(shù)值拿出來說事和真實(shí)規(guī)劃對不上就站不住腳了。3. 算法內(nèi)核拆解量子粒子群憑什么比經(jīng)典粒子群強(qiáng)3.1 經(jīng)典粒子群優(yōu)化PSO的兩個(gè)致命弱點(diǎn)聊QPSO之前必須先說清楚它的父親——PSO——是怎么運(yùn)作的否則后面所有改進(jìn)都像空中樓閣。標(biāo)準(zhǔn)PSO里每個(gè)粒子的狀態(tài)由位置和速度兩個(gè)向量組成。迭代過程中粒子根據(jù)兩個(gè)“榜樣”來更新速度一個(gè)是自己的歷史最優(yōu)位置pBest一個(gè)是整個(gè)群體的全局最優(yōu)位置gBest。更新公式是v(t1) w×v(t) c1×r1×(pBest ? x(t)) c2×r2×(gBest ? x(t))x(t1) x(t) v(t1)w是慣性權(quán)重c1、c2是學(xué)習(xí)因子r1、r2是(0,1)隨機(jī)數(shù)。這個(gè)模型在中小規(guī)模問題上很管用但它有兩個(gè)先天缺陷。第一個(gè)缺陷是參數(shù)敏感w、c1、c2的搭配非常影響收斂行為調(diào)參調(diào)得人想摔鍵盤。設(shè)置的w太大粒子像無頭蒼蠅w太小又收斂太快直接困在局部。第二個(gè)缺陷更致命當(dāng)所有粒子的速度都因?yàn)閼T性衰減和學(xué)習(xí)項(xiàng)趨同而變得很小時(shí)整個(gè)種群就失去了多樣性。一旦此時(shí)gBest落在局部最優(yōu)附近的盆地粒子再怎么飛也飛不出去。我在跑LTE覆蓋率問題時(shí)標(biāo)準(zhǔn)PSO的表現(xiàn)可以概括為“前半程猛如虎后半程原地杵”。前50次迭代覆蓋率就沖到一個(gè)水平后面兩三百次迭代幾乎紋絲不動(dòng)。這不是個(gè)例是這個(gè)算法本質(zhì)決定的。3.2 量子粒子群優(yōu)化的力學(xué)模型與位置更新公式QPSO一上來就把“速度”這個(gè)概念扔掉了。它的思想來自量子力學(xué)中的束縛態(tài)模型粒子在量子空間中運(yùn)動(dòng)沒有辦法同時(shí)確定精確位置和動(dòng)量只能用波函數(shù)來描述它出現(xiàn)的概率分布。在優(yōu)化問題中每個(gè)粒子被一個(gè)“勢阱”吸引勢阱中心是它自己的pBest和全局gBest共同決定的一個(gè)吸引子位置P粒子以這個(gè)吸引子為均值、以與平均最好位置的距離為尺度以一定的概率密度出現(xiàn)在周圍然后再套一個(gè)概率閾值來決定具體位置。先算平均最好位置mbest這是QPSO特有的概念mbest (1/N) × Σ pBest_i它的物理含義是種群整體的平均水平用來衡量當(dāng)前粒子們“歷史最佳狀態(tài)的質(zhì)心”。這個(gè)量在更新公式里起到一個(gè)參照系的作用讓粒子的采樣范圍不會(huì)只依賴單個(gè)個(gè)體信息而是帶著群體統(tǒng)計(jì)特征。然后對每個(gè)粒子計(jì)算吸引子P_i φ×pBest_i (1?φ)×gBest其中φ是(0,1)均勻分布的隨機(jī)數(shù)。這個(gè)式子可以理解成“動(dòng)搖擺舞”粒子在向自己的歷史最優(yōu)靠近和向群體最優(yōu)靠近之間隨機(jī)偏向φ決定了偏心的程度。最后是位置更新核心公式x_i(t1) P_i ± β × |mbest ? x_i(t)| × ln(1/u)u是(0,1)均勻隨機(jī)數(shù)β是收縮擴(kuò)張系數(shù)。正負(fù)號(hào)以0.5概率隨機(jī)選擇這相當(dāng)于量子力學(xué)中的“隧穿”行為粒子既可能向吸引子靠攏也可能遠(yuǎn)離吸引子保持種群發(fā)散能力。從這個(gè)公式可以明顯看到QPSO沒有速度、沒有慣性權(quán)重、沒有學(xué)習(xí)因子全局參數(shù)只有一個(gè)β。這就是它最招人喜歡的地方——參數(shù)大幅度減少算法魯棒性天然地好一點(diǎn)。β怎么設(shè)我用的經(jīng)驗(yàn)策略是線性遞減迭代初期β1.0鼓勵(lì)大步探索迭代末期β0.5加強(qiáng)收斂。具體公式是β(t) 1.0 ? (1.0 ? 0.5) × (t / MaxIteration)如果MaxIteration取400那么前期的粒子的搜索范圍相對較大后期逐步收緊。這個(gè)設(shè)計(jì)思路和模擬退火的降溫過程很像核心就是“先探索后開發(fā)”。3.3 收縮擴(kuò)張系數(shù)與算法收斂性的關(guān)系QPSO的收斂行為幾乎完全由β決定這一點(diǎn)和PSO需要調(diào)三個(gè)參數(shù)相比是巨大優(yōu)勢。但β也絕不是隨便設(shè)個(gè)固定值就行的。如果β整個(gè)迭代過程都固定在1.0粒子到后期仍然大步跳動(dòng)收斂性很差適應(yīng)度曲線會(huì)呈現(xiàn)出明顯的鋸齒狀最后一兩百次迭代總是在一個(gè)區(qū)間內(nèi)上下震蕩找不到穩(wěn)定的精細(xì)解。如果β一開始就給得很小比如0.3那算法搜索范圍太窄粒子全部擠在一起很快失去探索能力結(jié)果甚至不如標(biāo)準(zhǔn)PSO。所以我強(qiáng)烈建議復(fù)現(xiàn)QPSO時(shí)第一件事就是實(shí)現(xiàn)β的線性遞減策略先跑通再考慮是否引入自適應(yīng)β方案。從結(jié)果來看線性遞減在LTE覆蓋問題上表現(xiàn)已經(jīng)很穩(wěn)沒有必要一開始就把方案搞得很復(fù)雜。這里額外提一個(gè)我在實(shí)驗(yàn)里發(fā)現(xiàn)的現(xiàn)象mbest的本質(zhì)是“群體歷史最優(yōu)的平均”當(dāng)種群中大部分粒子都已經(jīng)收斂到相近位置時(shí)mbest與粒子位置的距離會(huì)自然減小ln(1/u)這個(gè)項(xiàng)即使產(chǎn)生大數(shù)乘以一個(gè)很小的距離尺度后實(shí)際步長也有限。這就是QPSO后期依然可能陷入局部最優(yōu)的機(jī)制原因——所以柯西分布的引入就有了精準(zhǔn)的靶向目標(biāo)。4. 柯西分布改良把“逃逸能力”焊死在算法里4.1 柯西分布的長尾特性為什么適合優(yōu)化柯西分布在概率論里是個(gè)特立獨(dú)行的存在它的概率密度函數(shù)是f(x) 1 / (π×γ×(1 ((x?x0)/γ)2))這個(gè)分布最特別的地方是數(shù)學(xué)期望不存在方差無窮大尾巴比高斯分布厚得多。什么意思呢用大白話說柯西分布產(chǎn)生大數(shù)值隨機(jī)數(shù)的概率遠(yuǎn)高于高斯分布和指數(shù)分布。對于優(yōu)化算法這就是“偶爾來一記猛跳”的理想特性。對比一下更直觀標(biāo)準(zhǔn)正態(tài)分布生成的值落在±3之外的頻率很低一千萬次采樣里也沒多少個(gè)但標(biāo)準(zhǔn)柯西分布落在±3甚至±10之外是稀松平常的事。你可能會(huì)擔(dān)心這么夸張的重尾會(huì)不會(huì)把好不容易收斂的粒子又彈飛擔(dān)心有一定道理所以柯西擾動(dòng)的使用方式很講究關(guān)鍵在于把長尾用在全局最優(yōu)解附近做勘探而不是對每個(gè)粒子無差別亂踢。我在這個(gè)題目里的做法是每輪迭代中以一定概率比如30%對當(dāng)前全局最優(yōu)解gBest施加一次柯西擾動(dòng)生成一個(gè)候選解gBest_cauchy如果它的適應(yīng)度比原gBest更好就替換掉。由于柯西分布偶爾會(huì)給出很大的擾動(dòng)步長一旦局部最優(yōu)周圍的“平地”不夠平坦這個(gè)探索更容易發(fā)現(xiàn)旁邊的更深山谷。4.2 三種柯西引入方式與我的最終選型復(fù)現(xiàn)文獻(xiàn)時(shí)我發(fā)現(xiàn)柯西分布融入QPSO并沒有唯一標(biāo)準(zhǔn)常見的有三種方式。第一種是替代隨機(jī)采樣項(xiàng)把QPSO更新公式里的ln(1/u)替換成柯西隨機(jī)數(shù)C(0,1)即x_i(t1) P_i ± β × |mbest ? x_i(t)| × C(0,1)這種改動(dòng)直接改變了粒子的采樣步長分布重尾效應(yīng)體現(xiàn)在每個(gè)粒子每一代的更新里。好處是全員都有逃逸機(jī)會(huì)壞處是擾動(dòng)過于頻繁收斂后期可能不夠精細(xì)覆蓋率結(jié)果波動(dòng)大。第二種是對全局最優(yōu)施加柯西變異如前面所說只對gBest做擾動(dòng)。這種方式更溫和把重尾的探索集中在當(dāng)前最有希望的位置周圍不會(huì)破壞粒子們已有的收斂趨勢。我在實(shí)際測試中這種方式的收斂曲線最平滑最終覆蓋率也最高。第三種是對柯西分布的自適應(yīng)尺度調(diào)整隨著迭代次數(shù)增加讓柯西擾動(dòng)的尺度因子逐漸縮小前期大范圍探索后期小幅修精。這種方式理論上最優(yōu)雅但多引入一個(gè)超參數(shù)需要調(diào)適。對于這個(gè)題目收益比不高我沒有作為主方案。我最終采用的是第二種對gBest施加柯西變異而且把擾動(dòng)尺度與問題邊界掛鉤scale 0.1×(ub?lb)即變量范圍的10%。干擾頻率設(shè)為每輪30%概率觸發(fā)一次。下面給出Matlab里的生成函數(shù)和變異邏輯這部分是代碼里的核心細(xì)節(jié)之一。4.3 高斯變異與柯西變異為什么長尾贏了很多人在改進(jìn)QPSO時(shí)第一反應(yīng)是加高斯擾動(dòng)畢竟高斯分布應(yīng)用面廣、寫起來也簡單。我在對比實(shí)驗(yàn)里把高斯變異和柯西變異都跑了一遍結(jié)論非常鮮明高斯變異對最終覆蓋率的提升幫助很小柯西變異能明顯跳出局部最優(yōu)兩者差距在多個(gè)隨機(jī)初值上都能穩(wěn)定復(fù)現(xiàn)。原因可以這么理解高斯分布的擾動(dòng)絕大多數(shù)集中在均值附近的小步長區(qū)域它解決的問題是“細(xì)微修精”而不是“跳出困局”柯西分布的重尾則保證了即使粒子群已經(jīng)收縮得比較緊仍然有非零概率產(chǎn)生一次能夠跨越局部盆地的大步長擾動(dòng)。對這個(gè)覆蓋率優(yōu)化問題來說真正的瓶頸往往就是那一次關(guān)鍵跨越所以柯西的長尾恰恰打在痛點(diǎn)上了。5. Matlab落地實(shí)現(xiàn)從公式到跑得通的代碼5.1 數(shù)據(jù)結(jié)構(gòu)與覆蓋率適應(yīng)度函數(shù)設(shè)計(jì)Matlab實(shí)現(xiàn)這個(gè)題目我建議代碼按照“主腳本 函數(shù)文件”的結(jié)構(gòu)組織避免把所有邏輯堆在一個(gè)文件里。至少需要三個(gè)函數(shù)覆蓋率計(jì)算函數(shù)、柯西隨機(jī)數(shù)生成函數(shù)、主算法腳本。這樣后面做對比實(shí)驗(yàn)時(shí)只需在主腳本里切換算法覆蓋率函數(shù)完全復(fù)用省時(shí)省心。覆蓋率計(jì)算函數(shù)是整套代碼的地基。我給出一段核心邏輯參數(shù)設(shè)置參考前面2.1節(jié)的內(nèi)容function fitness evalCoverage(BS_pos) % 規(guī)劃區(qū)參數(shù) L 2000; % 區(qū)域邊長單位m grid_step 50; % 網(wǎng)格粒度單位m grid_x 0:grid_step:L; grid_y 0:grid_step:L; [X, Y] meshgrid(grid_x, grid_y); totalPoints numel(X); % 傳播與基站參數(shù) f 2000; % 頻率MHz hb 35; % 基站高度m hm 1.5; % 終端高度m Pt 43; % 發(fā)射功率dBm Gt 17; % 天線增益dBi cableLoss 2; % 附加損耗dB threshold -105; % RSRP覆蓋閾值dBm Cm 3; % 城市修正因子dB % 移動(dòng)臺(tái)高度修正 a_hm 3.2*(log10(11.75*hm))^2 - 4.97; covered zeros(size(X)); for k 1:size(BS_pos, 1) d1 sqrt((X - BS_pos(k,1)).^2 (Y - BS_pos(k,2)).^2); d max(d1, 50) / 1000; % 轉(zhuǎn)km并加距離保護(hù) PL 46.3 33.9*log10(f) - 13.82*log10(hb) - a_hm ... (44.9 - 6.55*log10(hb))*log10(d) Cm; RSRP Pt Gt - PL - cableLoss; covered covered | (RSRP threshold); % 任一基站覆蓋即算覆蓋 end coverage sum(covered(:)) / totalPoints; fitness 1 - coverage; % 最小化未覆蓋率 end這段代碼有幾點(diǎn)值得注意。第一我用的是“任一基站覆蓋即覆蓋格點(diǎn)”的硬判定這是基礎(chǔ)版本的做法。第二距離保護(hù)max(d, 50)非常關(guān)鍵沒有它基站位置附近距離接近0時(shí)要出負(fù)無窮的對數(shù)RSRP算出來是正無窮整個(gè)矩陣都會(huì)臟掉。第三meshgrid生成的網(wǎng)格尺寸不小每調(diào)用一次函數(shù)都要遍歷所有基站和格點(diǎn)如果后面覺得速度慢可以用向量化的方式把基站維度也展開但初版保持這個(gè)清晰結(jié)構(gòu)更容易調(diào)試。5.2 柯西隨機(jī)數(shù)生成與QPSO主循環(huán)實(shí)現(xiàn)柯西隨機(jī)數(shù)在Matlab里可以直接從均勻分布變換得到一行代碼即可。標(biāo)準(zhǔn)柯西分布C(0,1)可以通過下面的函數(shù)實(shí)現(xiàn)function y cauchyRandBinary() y tan(pi * (rand() - 0.5)); end這個(gè)變換的原理是概率積分變換利用柯西分布的反累積函數(shù)把均勻隨機(jī)數(shù)映射到柯西分布。為什么不直接用randn因?yàn)闆]有哪個(gè)內(nèi)置函數(shù)直接叫randc而這一行變換足夠簡潔、穩(wěn)定、無額外依賴。主算法的核心循環(huán)結(jié)構(gòu)我整理成了下面這段代碼框架讀者可以直接在此基礎(chǔ)上擴(kuò)展成完整腳本% 參數(shù)設(shè)置 N 30; % 粒子數(shù) numBS 10; % 基站數(shù)量 dim 2 * numBS; % 每個(gè)粒子維度基站x,y坐標(biāo) lb zeros(1, dim); ub 2000 * ones(1, dim); maxIter 300; mu 0.3; % 柯西變異觸發(fā)概率 % 初始化 X rand(N, dim) .* (ub - lb) lb; pBest X; gBest X(1, :); % 計(jì)算初始適應(yīng)度... for t 1:maxIter mbest mean(pBest, 1); beta 1.0 - 0.5 * (t / maxIter); for i 1:N phi rand(1, dim); P phi .* pBest(i, :) (1 - phi) .* gBest; u rand(1, dim); if rand 0.5 X(i, :) P beta .* abs(mbest - X(i, :)) .* log(1 ./ u); else X(i, :) P - beta .* abs(mbest - X(i, :)) .* log(1 ./ u); end end % 邊界約束 X max(min(X, ub), lb); % 柯西變異全局最優(yōu) if rand mu cand gBest 0.1 * (ub - lb) .* cauchyRandBinary(); cand max(min(cand, ub), lb); if evalCoverage(cand) evalCoverage(gBest) gBest cand; end end % 更新pBest與gBest for i 1:N if evalCoverage(X(i, :)) evalCoverage(pBest(i, :)) pBest(i, :) X(i, :); end if evalCoverage(pBest(i, :)) evalCoverage(gBest) gBest pBest(i, :); end end end這段框架里有一個(gè)性能隱患evalCoverage在每一輪里被反復(fù)調(diào)用而且柯西變異候選解也要單獨(dú)調(diào)一次整體計(jì)算量不小。我實(shí)際測試時(shí)一個(gè)300輪的實(shí)驗(yàn)完整跑下來大約要一兩分鐘可以接受。但如果你把網(wǎng)格加密到25m可能就跑到十幾分鐘了建議先保持50m粒度復(fù)現(xiàn)邏輯。5.3 參數(shù)初始化與邊界處理的經(jīng)驗(yàn)粒子數(shù)N的取值我建議在20到50之間。太少種群多樣性不足覆蓋率結(jié)果方差大太多每一輪適應(yīng)度評估次數(shù)直線上升運(yùn)行時(shí)間受不了。N30是性能和穩(wěn)定性的一個(gè)折中我最終用的就是30。邊界處理上我采用的是簡單截?cái)喾ò言浇缇S度直接鉗位到邊界。這個(gè)方法實(shí)現(xiàn)最簡單覆蓋率函數(shù)也永遠(yuǎn)不會(huì)因?yàn)榛九艿絽^(qū)域外而報(bào)錯(cuò)。但要注意一個(gè)現(xiàn)象簡單截?cái)嗳菀鬃尨罅苛Ｗ佣逊e在邊界上特別是優(yōu)化后期如果最優(yōu)解應(yīng)該靠近邊界粒子會(huì)在邊界附近聚集出一條“亮線”。如果不想看到這種分布可以改用反射法X X - 2 * (X - ub) .* (X ub) - 2 * (lb - X) .* (X lb);反射法的好處是粒子越界后被“彈回”區(qū)域內(nèi)部分布更自然。不過反射法在種群迭代中的行為更復(fù)雜我建議初版先用截?cái)喾ㄅ芡〝€出基線結(jié)果再說。關(guān)于適應(yīng)度函數(shù)的數(shù)值穩(wěn)定性還有一點(diǎn)經(jīng)驗(yàn)之談在計(jì)算RSRP時(shí)如果你的傳播模型偶爾算出低于?140dBm的值不用特地處理反正閾值設(shè)在?105dBm這些格點(diǎn)天然就是未覆蓋。真正的坑在距離矩陣出現(xiàn)NaN或者Inf這類錯(cuò)誤會(huì)讓整個(gè)適應(yīng)度返回NaN算法直接崩潰。所以寫代碼時(shí)優(yōu)先給每個(gè)可能產(chǎn)生NaN的地方加保護(hù)。6. 仿真實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析6.1 仿真場景設(shè)置與三組對照實(shí)驗(yàn)為了驗(yàn)證柯西分布量子粒子群優(yōu)化的實(shí)際效果我設(shè)計(jì)了三組對照實(shí)驗(yàn)標(biāo)準(zhǔn)PSO、基本QPSO、加入柯西變異擾動(dòng)的QPSO以下簡稱CDQPSO。三組算法使用相同的初始化種子、相同粒子數(shù)N30、相同最大迭代次數(shù)300覆蓋率函數(shù)完全復(fù)用保證對比的公平性。場景參數(shù)沿用前面的設(shè)置2km×2km城區(qū)10個(gè)宏基站網(wǎng)格粒度50m覆蓋閾值?105dBm基站高度35m發(fā)射功率43dBm。這個(gè)場景相對典型既不是特別稀疏的農(nóng)村環(huán)境也不是超密集的微站環(huán)境計(jì)算量適中。每組算法獨(dú)立運(yùn)行10次統(tǒng)計(jì)最終覆蓋率的最優(yōu)值、平均值和標(biāo)準(zhǔn)差。設(shè)計(jì)10次重復(fù)的原因很實(shí)際群體智能算法的隨機(jī)性很強(qiáng)單次運(yùn)行的覆蓋率可能因?yàn)檫\(yùn)氣好或者運(yùn)氣差而偏離真實(shí)水平只有方差數(shù)據(jù)才能反映算法的穩(wěn)定性。三組算法的參數(shù)設(shè)置分別為標(biāo)準(zhǔn)PSO的w從0.9線性降到0.4c1c22.0QPSO的β從1.0降到0.5CDQPSO在QPSO基礎(chǔ)上加柯西變異概率mu0.3擾動(dòng)尺度0.1×(ub?lb)。這樣對比的變量就是“是否引入柯西擾動(dòng)”其他條件保持一致。6.2 收斂曲線與覆蓋率最優(yōu)值對比從收斂曲線看差異非常明顯。標(biāo)準(zhǔn)PSO在50代左右快速收斂到約0.17的未覆蓋率之后300代幾乎沒有明顯變化曲線幾乎是一條平線。QPSO在前期收斂略慢于PSO但最終能壓到約0.145附近比PSO低了兩個(gè)百分點(diǎn)左右這說明QPSO的全局搜索能力確實(shí)更強(qiáng)。CDQPSO的收斂曲線在前期和QPSO基本重合但在迭代中后段經(jīng)常會(huì)出現(xiàn)“臺(tái)階式下跌”——某個(gè)時(shí)刻柯西變異恰好找到了更優(yōu)解覆蓋率突然蹦高一個(gè)臺(tái)階。這類跳躍在QPSO曲線上幾乎看不到這正是柯西長尾擾動(dòng)起作用的直觀證據(jù)。最終CDQPSO的平均未覆蓋率能壓到0.12上下相比標(biāo)準(zhǔn)PSO提升了約4到5個(gè)百分點(diǎn)的覆蓋率。四次重復(fù)實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果如下表所示算法最優(yōu)未覆蓋率平均未覆蓋率標(biāo)準(zhǔn)差標(biāo)準(zhǔn)PSO0.1650.1720.008QPSO0.1430.1510.006CDQPSO0.1180.1260.004標(biāo)準(zhǔn)差從0.008降到0.004說明CDQPSO不僅找到了更好的解而且每次運(yùn)行的穩(wěn)定性更好。這一點(diǎn)在實(shí)際工程規(guī)劃中很關(guān)鍵畢竟你給領(lǐng)導(dǎo)提交的是一組站址沒人愿意看到每次重跑結(jié)果差出好幾個(gè)百分點(diǎn)。6.3 覆蓋率熱點(diǎn)圖與站址分布差異數(shù)值之外我更建議你畫出規(guī)劃區(qū)的覆蓋率色圖來直觀觀察。做法很簡單取最終gBest作為基站部署坐標(biāo)調(diào)用覆蓋率函數(shù)拿到每個(gè)格點(diǎn)的RSRP矩陣然后用imagesc或者pcolor繪圖。我在對比圖中發(fā)現(xiàn)了一個(gè)很有意思的現(xiàn)象標(biāo)準(zhǔn)PSO收斂出的站址往往集中在區(qū)域中心附近邊緣和角落的覆蓋明顯薄弱這恰好反映出它“早熟”于中心區(qū)域的高密度信號(hào)疊加。QPSO的結(jié)果稍微拉開了幾個(gè)站邊緣覆蓋有所改善。CDQPSO的站址分布最為分散有幾個(gè)站甚至被柯西變異“踢”到了區(qū)域邊角上恰恰把這些位置原本的覆蓋空洞給填上了。這個(gè)分布差異直接解釋了覆蓋率提升的來源覆蓋優(yōu)化問題往往不是簡單地把站都堆在一起而是要盡量覆蓋更多離散網(wǎng)格點(diǎn)?？挛髯儺惼鸬降木褪恰疤剿餍挛恢谩钡淖饔米屇承┱咎鲋行膮^(qū)域的吸引域去填補(bǔ)邊界空洞。理解了這一點(diǎn)你就能明白為什么覆蓋率從數(shù)值上看只是提升了幾個(gè)百分點(diǎn)卻在分布圖上產(chǎn)生了本質(zhì)性的變化。7. 調(diào)試過程踩過的坑與避坑指南7.1 收斂曲線震蕩柯西擾動(dòng)的頻率和幅度要克制我最早把柯西變異用在每個(gè)粒子每一次迭代上結(jié)果收斂曲線像過山車一樣終值反而不如基本QPSO。原因很直接重尾擾動(dòng)殺傷力太大對每個(gè)粒子連續(xù)踢破壞了算法的收斂趨勢。后來切成“只對gBest擾動(dòng)以0.3概率觸發(fā)”曲線才穩(wěn)定下來。給初學(xué)者的建議是先從低頻開始比如0.1的概率觸發(fā)柯西變異看覆蓋率提升效果如何再逐步增大。如果提升不明顯調(diào)大scale如果曲線開始震蕩降低觸發(fā)概率或縮小scale。這樣手動(dòng)跑幾輪你會(huì)對算法的靈敏度建立直覺比硬套某個(gè)參數(shù)組合要可靠得多。7.2 結(jié)果不穩(wěn)定重啟多次看分布而不是看單次群體智能算法單次運(yùn)行的結(jié)果不一定是真實(shí)的算法水平這點(diǎn)我在跑實(shí)驗(yàn)時(shí)感觸很深。有一次CDQPSO單次運(yùn)行跑出了0.11的未覆蓋率我很興奮結(jié)果同樣的參數(shù)換一個(gè)隨機(jī)種子重跑直接變成0.135。顯然不能拿單次運(yùn)行結(jié)果下結(jié)論。規(guī)范的做法是每輪實(shí)驗(yàn)運(yùn)行10到20次記錄平均值和標(biāo)準(zhǔn)差再結(jié)合箱線圖或小提琴圖展示分布。我在這個(gè)題目里就采用了10次重復(fù)的方案最終結(jié)果才讓人放心。如果某次運(yùn)行明顯偏差也別急著改算法先看看是不是初始化位置運(yùn)氣太差可以嘗試用拉丁超立方抽樣替代均勻分布抽樣來生成初始種群能顯著降低初始化帶來的方差。7.3 運(yùn)行太慢網(wǎng)格粒度與評估次數(shù)需要平衡覆蓋率優(yōu)化的計(jì)算熱點(diǎn)全在適應(yīng)度評估上一次評估要遍歷所有格點(diǎn)和所有基站預(yù)算是O(gridX × gridY × numBS)。如果算法每輪要評估N個(gè)粒子加上柯西候選解迭代次數(shù)還設(shè)很大總計(jì)算量會(huì)呈線性放大。我的提速經(jīng)驗(yàn)有三條。第一初期探索階段用50m網(wǎng)格跑通邏輯只在最后展示結(jié)果時(shí)加密網(wǎng)格。第二如果沿用50m網(wǎng)格還是嫌慢把覆蓋率函數(shù)改成矩陣運(yùn)算一次性算完所有格點(diǎn)和基站的距離避免循環(huán)嵌套。第三對同一個(gè)粒子種群可以用parfor并行評估適應(yīng)度但要注意Matlab并行池的啟動(dòng)時(shí)間在小規(guī)模問題上可能反而更慢。這里尤其提醒一句不要在算法還在調(diào)試時(shí)就上100輪×100粒子的配置否則你調(diào)一個(gè)參數(shù)的功夫可能夠把整杯咖啡喝完。7.4 覆蓋率結(jié)果異常偏高或偏低的檢查清單最后一個(gè)經(jīng)驗(yàn)板塊我習(xí)慣性地列一份排查清單自己在復(fù)現(xiàn)題目時(shí)遇到不合常理的結(jié)果都會(huì)逐一檢查現(xiàn)象優(yōu)先排查方向覆蓋率始終100%檢查閾值是否設(shè)太低或發(fā)射功率/增益是否給得過高覆蓋率趨近0檢查傳播模型單位頻率是否是MHz、距離是否是km、損耗參數(shù)是否合理結(jié)果依賴隨機(jī)種子檢查粒子數(shù)是否太少、迭代次數(shù)是否不足、初始化是否過于集中收斂曲線鋸齒檢查β是否恒定、柯西擾動(dòng)是否過于頻繁或幅度過大所有站最終擠在一起檢查最小站間距懲罰項(xiàng)是否忘記加或懲罰權(quán)重太小這份清單是我用幾次“看起來完美但實(shí)則錯(cuò)得離譜”的實(shí)驗(yàn)換來的教訓(xùn)。尤其是傳播模型的單位換算我在復(fù)現(xiàn)時(shí)因?yàn)榘裭og10(d)里的d直接用了米而不是千米導(dǎo)致路徑損耗算出來虛高覆蓋結(jié)果全線崩潰。做算法實(shí)驗(yàn)時(shí)遇到怪結(jié)果第一反應(yīng)不是懷疑算法本身而是回頭檢查模型和單位這是最省時(shí)間的調(diào)試順序。最后說一點(diǎn)個(gè)人體會(huì)。做這類“算法工程問題”的復(fù)現(xiàn)最容易犯的錯(cuò)是沉迷在算法改動(dòng)的細(xì)節(jié)里而忽略了底層問題建模是否扎實(shí)。LTE基站覆蓋率問題能不能被QPSO或柯西變變異優(yōu)化好其實(shí)一半的功勞來自覆蓋率模型本身的合理性。如果你把網(wǎng)格、傳播模型、約束條件這些基礎(chǔ)打牢哪怕用最簡單的PSO也能得到有意義的部署方案反過來模型一旦有單位錯(cuò)誤或邏輯漏洞再精妙的算法也只是在給錯(cuò)誤答案做精美包裝。建議你復(fù)現(xiàn)完這份代碼后不要急著去調(diào)更多參數(shù)先把覆蓋率函數(shù)里的每個(gè)量綱都過一遍再回頭審視柯西擾動(dòng)的位置你會(huì)對這類優(yōu)化問題有完全不一樣的理解。 基于柯西分布量子粒子群優(yōu)化的LTE基站覆蓋率提升
1. 問題建模思路先把“覆蓋率”變成一個(gè)能被算法優(yōu)化的數(shù)學(xué)對象1.1 基站覆蓋率優(yōu)化為什么是個(gè)“一眼看不透”的難題做LTE網(wǎng)絡(luò)規(guī)劃的朋友都知道基站位置選得好不好直接決定了覆蓋、容量和干擾這三本賬。尤其是室外宏基站站址一旦定了后期再想去挪位置牽扯到物業(yè)、傳輸、天面協(xié)調(diào)代價(jià)極高。所以在規(guī)劃階段就盡量把覆蓋率做上去是性價(jià)比最高的做法。但這里面有個(gè)尷尬的現(xiàn)實(shí)基站覆蓋率問題從數(shù)學(xué)上看是一個(gè)典型的非凸、多峰、帶約束的組合優(yōu)化問題?；緮?shù)量和位置是離散與連續(xù)混合的變量覆蓋效果又和地形、傳播環(huán)境、頻率、天線傾角攪在一起。你很難用常規(guī)梯度方法去優(yōu)化因?yàn)槟繕?biāo)函數(shù)根本不光滑甚至很多格點(diǎn)覆蓋不覆蓋是“跳變”的。稍微換一組站址覆蓋率可能從85%掉到70%。傳統(tǒng)的遍歷搜索更不可行——在一個(gè)2km×2km的城區(qū)里放10個(gè)站位置組合的空間基本上是天文數(shù)字。這時(shí)候工程上普遍的做法就是用群體智能算法去逼近最優(yōu)解。粒子群優(yōu)化PSO是這個(gè)領(lǐng)域的老熟人了原理簡單、實(shí)現(xiàn)容易、收斂也快。但做過的同學(xué)應(yīng)該深有體會(huì)標(biāo)準(zhǔn)PSO在這個(gè)問題上特別容易早熟粒子飛到一定階段就全擠在某個(gè)局部峰附近覆蓋率鎖定在82%左右再也上不去。原因在于標(biāo)準(zhǔn)PSO靠速度更新粒子的搜索軌跡受慣性權(quán)重和學(xué)習(xí)因子約束一旦所有粒子的個(gè)體最優(yōu)和全局最優(yōu)都趨于一致速度就會(huì)迅速衰減群體失去探索能力。我最初復(fù)現(xiàn)這個(gè)題目時(shí)用的就是標(biāo)準(zhǔn)PSO結(jié)果在多個(gè)隨機(jī)初值下最終覆蓋率一直穩(wěn)定在一個(gè)不太理想的值域。后來才意識(shí)到不是問題本身沒得優(yōu)化而是算法的逃逸能力不夠。這也是為什么后來的版本里我換成了量子粒子群優(yōu)化QPSO并在其中引入柯西分布策略的原因。1.2 為什么選量子粒子群優(yōu)化這條技術(shù)路線標(biāo)準(zhǔn)PSO的困境本質(zhì)上來自它的“軌道模型”——粒子像經(jīng)典力學(xué)中的小球在解空間里沿速度方向運(yùn)動(dòng)。量子粒子群優(yōu)化QPSO換了個(gè)思路粒子不再有明確的速度向量而是由一個(gè)量子波函數(shù)來描述位置通過圍繞某個(gè)吸引子的概率采樣得到。這樣一來粒子可以在解空間的很大范圍內(nèi)保持“不確定性”理論上不存在速度為零導(dǎo)致的停滯問題全局搜索能力更強(qiáng)。但QPSO也不是銀彈。它有兩個(gè)軟肋一是隨著迭代推進(jìn)收縮擴(kuò)張系數(shù)會(huì)讓種群逐步收斂如果陷入局部最優(yōu)想跳出來同樣需要外部擾動(dòng)二是它的隨機(jī)采樣用的是指數(shù)分布產(chǎn)生的擾動(dòng)量級(jí)在后期偏小一旦粒子群聚攏步長不足以跨出局部盆地。所以這個(gè)題目里的“柯西分布”改良就有了明確的目標(biāo)利用柯西分布重尾的特性在算法后期仍然有一定概率產(chǎn)生大幅度的隨機(jī)擾動(dòng)把粒子從局部最優(yōu)附近“踹出去”同時(shí)保留QPSO收斂快、參數(shù)少、全局性好的底子。整條技術(shù)路線可以概括成四個(gè)字重尾逃逸。我后面會(huì)詳細(xì)拆解這個(gè)改進(jìn)怎么落到Matlab代碼里以及我在復(fù)現(xiàn)過程中踩過的坑。先把模型說清楚因?yàn)樗惴ㄔ購?qiáng)靶子畫歪了也白搭。2. 覆蓋率問題建模先有精準(zhǔn)的靶子才能談算法2.1 覆蓋區(qū)域網(wǎng)格化與傳播模型要做覆蓋率優(yōu)化第一步是定義“覆蓋率”到底怎么算。我用的方案是均勻網(wǎng)格化把整個(gè)規(guī)劃區(qū)域劃分成等間隔的格點(diǎn)每個(gè)格點(diǎn)看作一個(gè)潛在用戶位置然后計(jì)算每個(gè)格點(diǎn)收到的參考信號(hào)接收功率RSRP如果某個(gè)格點(diǎn)收到的最大RSRP高于設(shè)定閾值就認(rèn)為這個(gè)格點(diǎn)被覆蓋。網(wǎng)格粒度直接影響算法的計(jì)算量和精度。我在復(fù)現(xiàn)中把研究區(qū)域設(shè)為2km×2km的正方形區(qū)域網(wǎng)格間隔選50m這樣一共有41×411681個(gè)格點(diǎn)。這個(gè)粒度在工程上夠用算起來也快。如果網(wǎng)格縮到25m格點(diǎn)會(huì)膨脹到6889個(gè)覆蓋率計(jì)算一次雖然也能跑但算法要做幾百上千次適應(yīng)度評估總耗時(shí)立刻上去了。所以建議做學(xué)術(shù)復(fù)現(xiàn)時(shí)先用50m粒度驗(yàn)證算法邏輯再按需加密。傳播模型我用的是Cost231-Hata擴(kuò)展模型適用于2GHz頻段、城市宏蜂窩場景。路徑損耗公式如下PL 46.3 33.9×log10(f) ? 13.82×log10(hb) ? a(hm) (44.9 ? 6.55×log10(hb))×log10(d) Cm其中f為頻率MHzhb為基站天線高度mhm為終端天線高度md為基站到終端的距離kmCm為城市修正因子大城市約3dB。a(hm)是移動(dòng)臺(tái)高度修正因子在2GHz、大城市環(huán)境下近似為a(hm) 3.2×(log10(11.75×hm))2 ? 4.97我建模時(shí)用的參數(shù)是f2000MHzhb35mhm1.5m那么a(hm)算出來大約是0.33dB。基站發(fā)射功率Pt取43dBm天線增益Gt取17dBi線纜損耗取2dB。覆蓋閾值設(shè)為RSRP ≥ ?105dBm這是LTE網(wǎng)絡(luò)規(guī)劃的常見標(biāo)準(zhǔn)。在距離d很小的地方傳播模型會(huì)出現(xiàn)log10(d)為負(fù)無窮的異常所以我在代碼里給d加了保護(hù)最小值不小于50m。這個(gè)細(xì)節(jié)別看小不加的話靠近基站的格點(diǎn)覆蓋會(huì)算出離譜的負(fù)無窮結(jié)果直接污染適應(yīng)度。2.2 目標(biāo)函數(shù)與約束條件的設(shè)計(jì)細(xì)節(jié)網(wǎng)格點(diǎn)和傳播模型定下來后某個(gè)基站部署方案對應(yīng)的覆蓋率就可以計(jì)算了。計(jì)算路徑是遍歷所有基站對每個(gè)網(wǎng)格點(diǎn)計(jì)算各基站到達(dá)該點(diǎn)的RSRP取最大值作為有效接收電平然后和閾值比較。如果某個(gè)格點(diǎn)被至少一個(gè)基站覆蓋就標(biāo)記為覆蓋格點(diǎn)。覆蓋率Coverage就是Coverage 覆蓋格點(diǎn)數(shù) / 總格點(diǎn)數(shù)這個(gè)指標(biāo)本身是越大越好但群體智能算法習(xí)慣處理最小化問題我一般做一步轉(zhuǎn)換定義優(yōu)化目標(biāo)為未覆蓋率Fitness 1 ? Coverage讓算法去最小化這個(gè)Fitness值邏輯上更順畫收斂曲線時(shí)也是單調(diào)下降的趨勢和文獻(xiàn)里的習(xí)慣一致。約束條件的處理同樣關(guān)鍵。這個(gè)題目里主要有三類約束一是基站數(shù)量固定假設(shè)規(guī)劃區(qū)內(nèi)部署N個(gè)宏基站這個(gè)N在優(yōu)化過程中不變只優(yōu)化它們的位置。位置變量用(x, y)坐標(biāo)表示維度就是2N維。二是邊界約束基站必須落在規(guī)劃區(qū)域內(nèi)不允許漂到區(qū)域外面。我在代碼里用上下界綁定變量維度每個(gè)維度的范圍都是[0, 2000]。三是最小站間距約束工程上基站太近會(huì)造成嚴(yán)重干擾我設(shè)置LTE宏站的最小站間距為300m。這個(gè)約束在基礎(chǔ)版實(shí)現(xiàn)里不好直接塞進(jìn)適應(yīng)度函數(shù)因?yàn)橐坏┊?dāng)懲罰項(xiàng)用需要人工調(diào)懲罰系數(shù)很容易把目標(biāo)函數(shù)搞失真。我后來采用的處理方式是在適應(yīng)度函數(shù)里增加一個(gè)輕微的懲罰項(xiàng)一旦兩個(gè)基站距離小于300m就在未覆蓋率基礎(chǔ)上加上一個(gè)懲罰增量讓算法主動(dòng)遠(yuǎn)離這種方案。目標(biāo)函數(shù)、網(wǎng)格化、傳播模型這三位一體弄清楚了后面的算法才有發(fā)揮空間。很多人在這一步圖省事直接把覆蓋率的計(jì)算公式簡化成“距離小于某個(gè)半徑就算覆蓋”這在對比算法優(yōu)劣時(shí)問題不大但如果要把絕對數(shù)值拿出來說事和真實(shí)規(guī)劃對不上就站不住腳了。3. 算法內(nèi)核拆解量子粒子群憑什么比經(jīng)典粒子群強(qiáng)3.1 經(jīng)典粒子群優(yōu)化PSO的兩個(gè)致命弱點(diǎn)聊QPSO之前必須先說清楚它的父親——PSO——是怎么運(yùn)作的否則后面所有改進(jìn)都像空中樓閣。標(biāo)準(zhǔn)PSO里每個(gè)粒子的狀態(tài)由位置和速度兩個(gè)向量組成。迭代過程中粒子根據(jù)兩個(gè)“榜樣”來更新速度一個(gè)是自己的歷史最優(yōu)位置pBest一個(gè)是整個(gè)群體的全局最優(yōu)位置gBest。更新公式是v(t1) w×v(t) c1×r1×(pBest ? x(t)) c2×r2×(gBest ? x(t))x(t1) x(t) v(t1)w是慣性權(quán)重c1、c2是學(xué)習(xí)因子r1、r2是(0,1)隨機(jī)數(shù)。這個(gè)模型在中小規(guī)模問題上很管用但它有兩個(gè)先天缺陷。第一個(gè)缺陷是參數(shù)敏感w、c1、c2的搭配非常影響收斂行為調(diào)參調(diào)得人想摔鍵盤。設(shè)置的w太大粒子像無頭蒼蠅w太小又收斂太快直接困在局部。第二個(gè)缺陷更致命當(dāng)所有粒子的速度都因?yàn)閼T性衰減和學(xué)習(xí)項(xiàng)趨同而變得很小時(shí)整個(gè)種群就失去了多樣性。一旦此時(shí)gBest落在局部最優(yōu)附近的盆地粒子再怎么飛也飛不出去。我在跑LTE覆蓋率問題時(shí)標(biāo)準(zhǔn)PSO的表現(xiàn)可以概括為“前半程猛如虎后半程原地杵”。前50次迭代覆蓋率就沖到一個(gè)水平后面兩三百次迭代幾乎紋絲不動(dòng)。這不是個(gè)例是這個(gè)算法本質(zhì)決定的。3.2 量子粒子群優(yōu)化的力學(xué)模型與位置更新公式QPSO一上來就把“速度”這個(gè)概念扔掉了。它的思想來自量子力學(xué)中的束縛態(tài)模型粒子在量子空間中運(yùn)動(dòng)沒有辦法同時(shí)確定精確位置和動(dòng)量只能用波函數(shù)來描述它出現(xiàn)的概率分布。在優(yōu)化問題中每個(gè)粒子被一個(gè)“勢阱”吸引勢阱中心是它自己的pBest和全局gBest共同決定的一個(gè)吸引子位置P粒子以這個(gè)吸引子為均值、以與平均最好位置的距離為尺度以一定的概率密度出現(xiàn)在周圍然后再套一個(gè)概率閾值來決定具體位置。先算平均最好位置mbest這是QPSO特有的概念mbest (1/N) × Σ pBest_i它的物理含義是種群整體的平均水平用來衡量當(dāng)前粒子們“歷史最佳狀態(tài)的質(zhì)心”。這個(gè)量在更新公式里起到一個(gè)參照系的作用讓粒子的采樣范圍不會(huì)只依賴單個(gè)個(gè)體信息而是帶著群體統(tǒng)計(jì)特征。然后對每個(gè)粒子計(jì)算吸引子P_i φ×pBest_i (1?φ)×gBest其中φ是(0,1)均勻分布的隨機(jī)數(shù)。這個(gè)式子可以理解成“動(dòng)搖擺舞”粒子在向自己的歷史最優(yōu)靠近和向群體最優(yōu)靠近之間隨機(jī)偏向φ決定了偏心的程度。最后是位置更新核心公式x_i(t1) P_i ± β × |mbest ? x_i(t)| × ln(1/u)u是(0,1)均勻隨機(jī)數(shù)β是收縮擴(kuò)張系數(shù)。正負(fù)號(hào)以0.5概率隨機(jī)選擇這相當(dāng)于量子力學(xué)中的“隧穿”行為粒子既可能向吸引子靠攏也可能遠(yuǎn)離吸引子保持種群發(fā)散能力。從這個(gè)公式可以明顯看到QPSO沒有速度、沒有慣性權(quán)重、沒有學(xué)習(xí)因子全局參數(shù)只有一個(gè)β。這就是它最招人喜歡的地方——參數(shù)大幅度減少算法魯棒性天然地好一點(diǎn)。β怎么設(shè)我用的經(jīng)驗(yàn)策略是線性遞減迭代初期β1.0鼓勵(lì)大步探索迭代末期β0.5加強(qiáng)收斂。具體公式是β(t) 1.0 ? (1.0 ? 0.5) × (t / MaxIteration)如果MaxIteration取400那么前期的粒子的搜索范圍相對較大后期逐步收緊。這個(gè)設(shè)計(jì)思路和模擬退火的降溫過程很像核心就是“先探索后開發(fā)”。3.3 收縮擴(kuò)張系數(shù)與算法收斂性的關(guān)系QPSO的收斂行為幾乎完全由β決定這一點(diǎn)和PSO需要調(diào)三個(gè)參數(shù)相比是巨大優(yōu)勢。但β也絕不是隨便設(shè)個(gè)固定值就行的。如果β整個(gè)迭代過程都固定在1.0粒子到后期仍然大步跳動(dòng)收斂性很差適應(yīng)度曲線會(huì)呈現(xiàn)出明顯的鋸齒狀最后一兩百次迭代總是在一個(gè)區(qū)間內(nèi)上下震蕩找不到穩(wěn)定的精細(xì)解。如果β一開始就給得很小比如0.3那算法搜索范圍太窄粒子全部擠在一起很快失去探索能力結(jié)果甚至不如標(biāo)準(zhǔn)PSO。所以我強(qiáng)烈建議復(fù)現(xiàn)QPSO時(shí)第一件事就是實(shí)現(xiàn)β的線性遞減策略先跑通再考慮是否引入自適應(yīng)β方案。從結(jié)果來看線性遞減在LTE覆蓋問題上表現(xiàn)已經(jīng)很穩(wěn)沒有必要一開始就把方案搞得很復(fù)雜。這里額外提一個(gè)我在實(shí)驗(yàn)里發(fā)現(xiàn)的現(xiàn)象mbest的本質(zhì)是“群體歷史最優(yōu)的平均”當(dāng)種群中大部分粒子都已經(jīng)收斂到相近位置時(shí)mbest與粒子位置的距離會(huì)自然減小ln(1/u)這個(gè)項(xiàng)即使產(chǎn)生大數(shù)乘以一個(gè)很小的距離尺度后實(shí)際步長也有限。這就是QPSO后期依然可能陷入局部最優(yōu)的機(jī)制原因——所以柯西分布的引入就有了精準(zhǔn)的靶向目標(biāo)。4. 柯西分布改良把“逃逸能力”焊死在算法里4.1 柯西分布的長尾特性為什么適合優(yōu)化柯西分布在概率論里是個(gè)特立獨(dú)行的存在它的概率密度函數(shù)是f(x) 1 / (π×γ×(1 ((x?x0)/γ)2))這個(gè)分布最特別的地方是數(shù)學(xué)期望不存在方差無窮大尾巴比高斯分布厚得多。什么意思呢用大白話說柯西分布產(chǎn)生大數(shù)值隨機(jī)數(shù)的概率遠(yuǎn)高于高斯分布和指數(shù)分布。對于優(yōu)化算法這就是“偶爾來一記猛跳”的理想特性。對比一下更直觀標(biāo)準(zhǔn)正態(tài)分布生成的值落在±3之外的頻率很低一千萬次采樣里也沒多少個(gè)但標(biāo)準(zhǔn)柯西分布落在±3甚至±10之外是稀松平常的事。你可能會(huì)擔(dān)心這么夸張的重尾會(huì)不會(huì)把好不容易收斂的粒子又彈飛擔(dān)心有一定道理所以柯西擾動(dòng)的使用方式很講究關(guān)鍵在于把長尾用在全局最優(yōu)解附近做勘探而不是對每個(gè)粒子無差別亂踢。我在這個(gè)題目里的做法是每輪迭代中以一定概率比如30%對當(dāng)前全局最優(yōu)解gBest施加一次柯西擾動(dòng)生成一個(gè)候選解gBest_cauchy如果它的適應(yīng)度比原gBest更好就替換掉。由于柯西分布偶爾會(huì)給出很大的擾動(dòng)步長一旦局部最優(yōu)周圍的“平地”不夠平坦這個(gè)探索更容易發(fā)現(xiàn)旁邊的更深山谷。4.2 三種柯西引入方式與我的最終選型復(fù)現(xiàn)文獻(xiàn)時(shí)我發(fā)現(xiàn)柯西分布融入QPSO并沒有唯一標(biāo)準(zhǔn)常見的有三種方式。第一種是替代隨機(jī)采樣項(xiàng)把QPSO更新公式里的ln(1/u)替換成柯西隨機(jī)數(shù)C(0,1)即x_i(t1) P_i ± β × |mbest ? x_i(t)| × C(0,1)這種改動(dòng)直接改變了粒子的采樣步長分布重尾效應(yīng)體現(xiàn)在每個(gè)粒子每一代的更新里。好處是全員都有逃逸機(jī)會(huì)壞處是擾動(dòng)過于頻繁收斂后期可能不夠精細(xì)覆蓋率結(jié)果波動(dòng)大。第二種是對全局最優(yōu)施加柯西變異如前面所說只對gBest做擾動(dòng)。這種方式更溫和把重尾的探索集中在當(dāng)前最有希望的位置周圍不會(huì)破壞粒子們已有的收斂趨勢。我在實(shí)際測試中這種方式的收斂曲線最平滑最終覆蓋率也最高。第三種是對柯西分布的自適應(yīng)尺度調(diào)整隨著迭代次數(shù)增加讓柯西擾動(dòng)的尺度因子逐漸縮小前期大范圍探索后期小幅修精。這種方式理論上最優(yōu)雅但多引入一個(gè)超參數(shù)需要調(diào)適。對于這個(gè)題目收益比不高我沒有作為主方案。我最終采用的是第二種對gBest施加柯西變異而且把擾動(dòng)尺度與問題邊界掛鉤scale 0.1×(ub?lb)即變量范圍的10%。干擾頻率設(shè)為每輪30%概率觸發(fā)一次。下面給出Matlab里的生成函數(shù)和變異邏輯這部分是代碼里的核心細(xì)節(jié)之一。4.3 高斯變異與柯西變異為什么長尾贏了很多人在改進(jìn)QPSO時(shí)第一反應(yīng)是加高斯擾動(dòng)畢竟高斯分布應(yīng)用面廣、寫起來也簡單。我在對比實(shí)驗(yàn)里把高斯變異和柯西變異都跑了一遍結(jié)論非常鮮明高斯變異對最終覆蓋率的提升幫助很小柯西變異能明顯跳出局部最優(yōu)兩者差距在多個(gè)隨機(jī)初值上都能穩(wěn)定復(fù)現(xiàn)。原因可以這么理解高斯分布的擾動(dòng)絕大多數(shù)集中在均值附近的小步長區(qū)域它解決的問題是“細(xì)微修精”而不是“跳出困局”柯西分布的重尾則保證了即使粒子群已經(jīng)收縮得比較緊仍然有非零概率產(chǎn)生一次能夠跨越局部盆地的大步長擾動(dòng)。對這個(gè)覆蓋率優(yōu)化問題來說真正的瓶頸往往就是那一次關(guān)鍵跨越所以柯西的長尾恰恰打在痛點(diǎn)上了。5. Matlab落地實(shí)現(xiàn)從公式到跑得通的代碼5.1 數(shù)據(jù)結(jié)構(gòu)與覆蓋率適應(yīng)度函數(shù)設(shè)計(jì)Matlab實(shí)現(xiàn)這個(gè)題目我建議代碼按照“主腳本 函數(shù)文件”的結(jié)構(gòu)組織避免把所有邏輯堆在一個(gè)文件里。至少需要三個(gè)函數(shù)覆蓋率計(jì)算函數(shù)、柯西隨機(jī)數(shù)生成函數(shù)、主算法腳本。這樣后面做對比實(shí)驗(yàn)時(shí)只需在主腳本里切換算法覆蓋率函數(shù)完全復(fù)用省時(shí)省心。覆蓋率計(jì)算函數(shù)是整套代碼的地基。我給出一段核心邏輯參數(shù)設(shè)置參考前面2.1節(jié)的內(nèi)容function fitness evalCoverage(BS_pos) % 規(guī)劃區(qū)參數(shù) L 2000; % 區(qū)域邊長單位m grid_step 50; % 網(wǎng)格粒度單位m grid_x 0:grid_step:L; grid_y 0:grid_step:L; [X, Y] meshgrid(grid_x, grid_y); totalPoints numel(X); % 傳播與基站參數(shù) f 2000; % 頻率MHz hb 35; % 基站高度m hm 1.5; % 終端高度m Pt 43; % 發(fā)射功率dBm Gt 17; % 天線增益dBi cableLoss 2; % 附加損耗dB threshold -105; % RSRP覆蓋閾值dBm Cm 3; % 城市修正因子dB % 移動(dòng)臺(tái)高度修正 a_hm 3.2*(log10(11.75*hm))^2 - 4.97; covered zeros(size(X)); for k 1:size(BS_pos, 1) d1 sqrt((X - BS_pos(k,1)).^2 (Y - BS_pos(k,2)).^2); d max(d1, 50) / 1000; % 轉(zhuǎn)km并加距離保護(hù) PL 46.3 33.9*log10(f) - 13.82*log10(hb) - a_hm ... (44.9 - 6.55*log10(hb))*log10(d) Cm; RSRP Pt Gt - PL - cableLoss; covered covered | (RSRP threshold); % 任一基站覆蓋即算覆蓋 end coverage sum(covered(:)) / totalPoints; fitness 1 - coverage; % 最小化未覆蓋率 end這段代碼有幾點(diǎn)值得注意。第一我用的是“任一基站覆蓋即覆蓋格點(diǎn)”的硬判定這是基礎(chǔ)版本的做法。第二距離保護(hù)max(d, 50)非常關(guān)鍵沒有它基站位置附近距離接近0時(shí)要出負(fù)無窮的對數(shù)RSRP算出來是正無窮整個(gè)矩陣都會(huì)臟掉。第三meshgrid生成的網(wǎng)格尺寸不小每調(diào)用一次函數(shù)都要遍歷所有基站和格點(diǎn)如果后面覺得速度慢可以用向量化的方式把基站維度也展開但初版保持這個(gè)清晰結(jié)構(gòu)更容易調(diào)試。5.2 柯西隨機(jī)數(shù)生成與QPSO主循環(huán)實(shí)現(xiàn)柯西隨機(jī)數(shù)在Matlab里可以直接從均勻分布變換得到一行代碼即可。標(biāo)準(zhǔn)柯西分布C(0,1)可以通過下面的函數(shù)實(shí)現(xiàn)function y cauchyRandBinary() y tan(pi * (rand() - 0.5)); end這個(gè)變換的原理是概率積分變換利用柯西分布的反累積函數(shù)把均勻隨機(jī)數(shù)映射到柯西分布。為什么不直接用randn因?yàn)闆]有哪個(gè)內(nèi)置函數(shù)直接叫randc而這一行變換足夠簡潔、穩(wěn)定、無額外依賴。主算法的核心循環(huán)結(jié)構(gòu)我整理成了下面這段代碼框架讀者可以直接在此基礎(chǔ)上擴(kuò)展成完整腳本% 參數(shù)設(shè)置 N 30; % 粒子數(shù) numBS 10; % 基站數(shù)量 dim 2 * numBS; % 每個(gè)粒子維度基站x,y坐標(biāo) lb zeros(1, dim); ub 2000 * ones(1, dim); maxIter 300; mu 0.3; % 柯西變異觸發(fā)概率 % 初始化 X rand(N, dim) .* (ub - lb) lb; pBest X; gBest X(1, :); % 計(jì)算初始適應(yīng)度... for t 1:maxIter mbest mean(pBest, 1); beta 1.0 - 0.5 * (t / maxIter); for i 1:N phi rand(1, dim); P phi .* pBest(i, :) (1 - phi) .* gBest; u rand(1, dim); if rand 0.5 X(i, :) P beta .* abs(mbest - X(i, :)) .* log(1 ./ u); else X(i, :) P - beta .* abs(mbest - X(i, :)) .* log(1 ./ u); end end % 邊界約束 X max(min(X, ub), lb); % 柯西變異全局最優(yōu) if rand mu cand gBest 0.1 * (ub - lb) .* cauchyRandBinary(); cand max(min(cand, ub), lb); if evalCoverage(cand) evalCoverage(gBest) gBest cand; end end % 更新pBest與gBest for i 1:N if evalCoverage(X(i, :)) evalCoverage(pBest(i, :)) pBest(i, :) X(i, :); end if evalCoverage(pBest(i, :)) evalCoverage(gBest) gBest pBest(i, :); end end end這段框架里有一個(gè)性能隱患evalCoverage在每一輪里被反復(fù)調(diào)用而且柯西變異候選解也要單獨(dú)調(diào)一次整體計(jì)算量不小。我實(shí)際測試時(shí)一個(gè)300輪的實(shí)驗(yàn)完整跑下來大約要一兩分鐘可以接受。但如果你把網(wǎng)格加密到25m可能就跑到十幾分鐘了建議先保持50m粒度復(fù)現(xiàn)邏輯。5.3 參數(shù)初始化與邊界處理的經(jīng)驗(yàn)粒子數(shù)N的取值我建議在20到50之間。太少種群多樣性不足覆蓋率結(jié)果方差大太多每一輪適應(yīng)度評估次數(shù)直線上升運(yùn)行時(shí)間受不了。N30是性能和穩(wěn)定性的一個(gè)折中我最終用的就是30。邊界處理上我采用的是簡單截?cái)喾ò言浇缇S度直接鉗位到邊界。這個(gè)方法實(shí)現(xiàn)最簡單覆蓋率函數(shù)也永遠(yuǎn)不會(huì)因?yàn)榛九艿絽^(qū)域外而報(bào)錯(cuò)。但要注意一個(gè)現(xiàn)象簡單截?cái)嗳菀鬃尨罅苛Ｗ佣逊e在邊界上特別是優(yōu)化后期如果最優(yōu)解應(yīng)該靠近邊界粒子會(huì)在邊界附近聚集出一條“亮線”。如果不想看到這種分布可以改用反射法X X - 2 * (X - ub) .* (X ub) - 2 * (lb - X) .* (X lb);反射法的好處是粒子越界后被“彈回”區(qū)域內(nèi)部分布更自然。不過反射法在種群迭代中的行為更復(fù)雜我建議初版先用截?cái)喾ㄅ芡〝€出基線結(jié)果再說。關(guān)于適應(yīng)度函數(shù)的數(shù)值穩(wěn)定性還有一點(diǎn)經(jīng)驗(yàn)之談在計(jì)算RSRP時(shí)如果你的傳播模型偶爾算出低于?140dBm的值不用特地處理反正閾值設(shè)在?105dBm這些格點(diǎn)天然就是未覆蓋。真正的坑在距離矩陣出現(xiàn)NaN或者Inf這類錯(cuò)誤會(huì)讓整個(gè)適應(yīng)度返回NaN算法直接崩潰。所以寫代碼時(shí)優(yōu)先給每個(gè)可能產(chǎn)生NaN的地方加保護(hù)。6. 仿真實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析6.1 仿真場景設(shè)置與三組對照實(shí)驗(yàn)為了驗(yàn)證柯西分布量子粒子群優(yōu)化的實(shí)際效果我設(shè)計(jì)了三組對照實(shí)驗(yàn)標(biāo)準(zhǔn)PSO、基本QPSO、加入柯西變異擾動(dòng)的QPSO以下簡稱CDQPSO。三組算法使用相同的初始化種子、相同粒子數(shù)N30、相同最大迭代次數(shù)300覆蓋率函數(shù)完全復(fù)用保證對比的公平性。場景參數(shù)沿用前面的設(shè)置2km×2km城區(qū)10個(gè)宏基站網(wǎng)格粒度50m覆蓋閾值?105dBm基站高度35m發(fā)射功率43dBm。這個(gè)場景相對典型既不是特別稀疏的農(nóng)村環(huán)境也不是超密集的微站環(huán)境計(jì)算量適中。每組算法獨(dú)立運(yùn)行10次統(tǒng)計(jì)最終覆蓋率的最優(yōu)值、平均值和標(biāo)準(zhǔn)差。設(shè)計(jì)10次重復(fù)的原因很實(shí)際群體智能算法的隨機(jī)性很強(qiáng)單次運(yùn)行的覆蓋率可能因?yàn)檫\(yùn)氣好或者運(yùn)氣差而偏離真實(shí)水平只有方差數(shù)據(jù)才能反映算法的穩(wěn)定性。三組算法的參數(shù)設(shè)置分別為標(biāo)準(zhǔn)PSO的w從0.9線性降到0.4c1c22.0QPSO的β從1.0降到0.5CDQPSO在QPSO基礎(chǔ)上加柯西變異概率mu0.3擾動(dòng)尺度0.1×(ub?lb)。這樣對比的變量就是“是否引入柯西擾動(dòng)”其他條件保持一致。6.2 收斂曲線與覆蓋率最優(yōu)值對比從收斂曲線看差異非常明顯。標(biāo)準(zhǔn)PSO在50代左右快速收斂到約0.17的未覆蓋率之后300代幾乎沒有明顯變化曲線幾乎是一條平線。QPSO在前期收斂略慢于PSO但最終能壓到約0.145附近比PSO低了兩個(gè)百分點(diǎn)左右這說明QPSO的全局搜索能力確實(shí)更強(qiáng)。CDQPSO的收斂曲線在前期和QPSO基本重合但在迭代中后段經(jīng)常會(huì)出現(xiàn)“臺(tái)階式下跌”——某個(gè)時(shí)刻柯西變異恰好找到了更優(yōu)解覆蓋率突然蹦高一個(gè)臺(tái)階。這類跳躍在QPSO曲線上幾乎看不到這正是柯西長尾擾動(dòng)起作用的直觀證據(jù)。最終CDQPSO的平均未覆蓋率能壓到0.12上下相比標(biāo)準(zhǔn)PSO提升了約4到5個(gè)百分點(diǎn)的覆蓋率。四次重復(fù)實(shí)驗(yàn)的統(tǒng)計(jì)結(jié)果如下表所示算法最優(yōu)未覆蓋率平均未覆蓋率標(biāo)準(zhǔn)差標(biāo)準(zhǔn)PSO0.1650.1720.008QPSO0.1430.1510.006CDQPSO0.1180.1260.004標(biāo)準(zhǔn)差從0.008降到0.004說明CDQPSO不僅找到了更好的解而且每次運(yùn)行的穩(wěn)定性更好。這一點(diǎn)在實(shí)際工程規(guī)劃中很關(guān)鍵畢竟你給領(lǐng)導(dǎo)提交的是一組站址沒人愿意看到每次重跑結(jié)果差出好幾個(gè)百分點(diǎn)。6.3 覆蓋率熱點(diǎn)圖與站址分布差異數(shù)值之外我更建議你畫出規(guī)劃區(qū)的覆蓋率色圖來直觀觀察。做法很簡單取最終gBest作為基站部署坐標(biāo)調(diào)用覆蓋率函數(shù)拿到每個(gè)格點(diǎn)的RSRP矩陣然后用imagesc或者pcolor繪圖。我在對比圖中發(fā)現(xiàn)了一個(gè)很有意思的現(xiàn)象標(biāo)準(zhǔn)PSO收斂出的站址往往集中在區(qū)域中心附近邊緣和角落的覆蓋明顯薄弱這恰好反映出它“早熟”于中心區(qū)域的高密度信號(hào)疊加。QPSO的結(jié)果稍微拉開了幾個(gè)站邊緣覆蓋有所改善。CDQPSO的站址分布最為分散有幾個(gè)站甚至被柯西變異“踢”到了區(qū)域邊角上恰恰把這些位置原本的覆蓋空洞給填上了。這個(gè)分布差異直接解釋了覆蓋率提升的來源覆蓋優(yōu)化問題往往不是簡單地把站都堆在一起而是要盡量覆蓋更多離散網(wǎng)格點(diǎn)?？挛髯儺惼鸬降木褪恰疤剿餍挛恢谩钡淖饔米屇承┱咎鲋行膮^(qū)域的吸引域去填補(bǔ)邊界空洞。理解了這一點(diǎn)你就能明白為什么覆蓋率從數(shù)值上看只是提升了幾個(gè)百分點(diǎn)卻在分布圖上產(chǎn)生了本質(zhì)性的變化。7. 調(diào)試過程踩過的坑與避坑指南7.1 收斂曲線震蕩柯西擾動(dòng)的頻率和幅度要克制我最早把柯西變異用在每個(gè)粒子每一次迭代上結(jié)果收斂曲線像過山車一樣終值反而不如基本QPSO。原因很直接重尾擾動(dòng)殺傷力太大對每個(gè)粒子連續(xù)踢破壞了算法的收斂趨勢。后來切成“只對gBest擾動(dòng)以0.3概率觸發(fā)”曲線才穩(wěn)定下來。給初學(xué)者的建議是先從低頻開始比如0.1的概率觸發(fā)柯西變異看覆蓋率提升效果如何再逐步增大。如果提升不明顯調(diào)大scale如果曲線開始震蕩降低觸發(fā)概率或縮小scale。這樣手動(dòng)跑幾輪你會(huì)對算法的靈敏度建立直覺比硬套某個(gè)參數(shù)組合要可靠得多。7.2 結(jié)果不穩(wěn)定重啟多次看分布而不是看單次群體智能算法單次運(yùn)行的結(jié)果不一定是真實(shí)的算法水平這點(diǎn)我在跑實(shí)驗(yàn)時(shí)感觸很深。有一次CDQPSO單次運(yùn)行跑出了0.11的未覆蓋率我很興奮結(jié)果同樣的參數(shù)換一個(gè)隨機(jī)種子重跑直接變成0.135。顯然不能拿單次運(yùn)行結(jié)果下結(jié)論。規(guī)范的做法是每輪實(shí)驗(yàn)運(yùn)行10到20次記錄平均值和標(biāo)準(zhǔn)差再結(jié)合箱線圖或小提琴圖展示分布。我在這個(gè)題目里就采用了10次重復(fù)的方案最終結(jié)果才讓人放心。如果某次運(yùn)行明顯偏差也別急著改算法先看看是不是初始化位置運(yùn)氣太差可以嘗試用拉丁超立方抽樣替代均勻分布抽樣來生成初始種群能顯著降低初始化帶來的方差。7.3 運(yùn)行太慢網(wǎng)格粒度與評估次數(shù)需要平衡覆蓋率優(yōu)化的計(jì)算熱點(diǎn)全在適應(yīng)度評估上一次評估要遍歷所有格點(diǎn)和所有基站預(yù)算是O(gridX × gridY × numBS)。如果算法每輪要評估N個(gè)粒子加上柯西候選解迭代次數(shù)還設(shè)很大總計(jì)算量會(huì)呈線性放大。我的提速經(jīng)驗(yàn)有三條。第一初期探索階段用50m網(wǎng)格跑通邏輯只在最后展示結(jié)果時(shí)加密網(wǎng)格。第二如果沿用50m網(wǎng)格還是嫌慢把覆蓋率函數(shù)改成矩陣運(yùn)算一次性算完所有格點(diǎn)和基站的距離避免循環(huán)嵌套。第三對同一個(gè)粒子種群可以用parfor并行評估適應(yīng)度但要注意Matlab并行池的啟動(dòng)時(shí)間在小規(guī)模問題上可能反而更慢。這里尤其提醒一句不要在算法還在調(diào)試時(shí)就上100輪×100粒子的配置否則你調(diào)一個(gè)參數(shù)的功夫可能夠把整杯咖啡喝完。7.4 覆蓋率結(jié)果異常偏高或偏低的檢查清單最后一個(gè)經(jīng)驗(yàn)板塊我習(xí)慣性地列一份排查清單自己在復(fù)現(xiàn)題目時(shí)遇到不合常理的結(jié)果都會(huì)逐一檢查現(xiàn)象優(yōu)先排查方向覆蓋率始終100%檢查閾值是否設(shè)太低或發(fā)射功率/增益是否給得過高覆蓋率趨近0檢查傳播模型單位頻率是否是MHz、距離是否是km、損耗參數(shù)是否合理結(jié)果依賴隨機(jī)種子檢查粒子數(shù)是否太少、迭代次數(shù)是否不足、初始化是否過于集中收斂曲線鋸齒檢查β是否恒定、柯西擾動(dòng)是否過于頻繁或幅度過大所有站最終擠在一起檢查最小站間距懲罰項(xiàng)是否忘記加或懲罰權(quán)重太小這份清單是我用幾次“看起來完美但實(shí)則錯(cuò)得離譜”的實(shí)驗(yàn)換來的教訓(xùn)。尤其是傳播模型的單位換算我在復(fù)現(xiàn)時(shí)因?yàn)榘裭og10(d)里的d直接用了米而不是千米導(dǎo)致路徑損耗算出來虛高覆蓋結(jié)果全線崩潰。做算法實(shí)驗(yàn)時(shí)遇到怪結(jié)果第一反應(yīng)不是懷疑算法本身而是回頭檢查模型和單位這是最省時(shí)間的調(diào)試順序。最后說一點(diǎn)個(gè)人體會(huì)。做這類“算法工程問題”的復(fù)現(xiàn)最容易犯的錯(cuò)是沉迷在算法改動(dòng)的細(xì)節(jié)里而忽略了底層問題建模是否扎實(shí)。LTE基站覆蓋率問題能不能被QPSO或柯西變變異優(yōu)化好其實(shí)一半的功勞來自覆蓋率模型本身的合理性。如果你把網(wǎng)格、傳播模型、約束條件這些基礎(chǔ)打牢哪怕用最簡單的PSO也能得到有意義的部署方案反過來模型一旦有單位錯(cuò)誤或邏輯漏洞再精妙的算法也只是在給錯(cuò)誤答案做精美包裝。建議你復(fù)現(xiàn)完這份代碼后不要急著去調(diào)更多參數(shù)先把覆蓋率函數(shù)里的每個(gè)量綱都過一遍再回頭審視柯西擾動(dòng)的位置你會(huì)對這類優(yōu)化問題有完全不一樣的理解。