粒子群果蠅混合改進算法在基站選址優化問題中的應用

劉 娟 楊春花

（烏魯木齊職業大學信息工程學院 烏魯木齊832000）

1 引言

在通訊設備建設中，基站選址優化是一項極其復雜又非常重要的問題［1］。隨著現代通訊事業的大力發展，網絡覆蓋率低導致的用戶對網絡供應商的矛盾也日益引發人們的關注和重視。基站選址優化問題的核心是提高網絡覆蓋率。然而，由于基站選址優化時，具有用戶量大、計算復雜以及大量復雜因素等特點，使得基站選址模型具有較強的非線性和不確定性，使得傳統的優化策略難以精確有效地對選址模型進行求解。

目前，基站選址優化的相關算法改進策略已成為相關科研人員的研究重點。目前，已經有大量的研究應用于實際的基站選址優化問題中。為了降低TD-SCDMA網絡基站建設代價，朱思峰［2］等提出了一種基于免疫計算的基站選址優化方案。石雷［3］等設計了基于干擾管理的高吞吐基站選址算法，針對在傳輸過程中遇到的并發傳輸干擾，通過干擾管理策略進行優化，提高了數據傳輸效率。張英杰［4］等提出了一種基于免疫算法的TD-SCDMA網絡基站選址優化方案。針對現有3G基站選址方法的不足，閆濤［5］提出了一種基于免疫算法的基站選址優化方法。王亞偉［6］等提出一種基于聚類遺傳算法的基站選址優化方案。晁迎［7］等提出一種加速遺傳算法的基站選址優化方案。此外還有基于多目標優化量子免疫算法的基站選址優化方案［8］、基于免疫記憶克隆算法的基站選址優化方案［9］和基于WCDMA的基站選址優化方案［9］。以上的研究能夠對部分基站選址優化問題解決有相當程度的幫助，但仍然存在著算法尋優效果不夠理想的問題。

基站選址優化是一類NP-Hard問題，其在實際工程的應用中，很難具有較高的求解精度和求解效率，因此眾多學者通過人工智能優化算法對基站選址模型進行求解。但人工智能算法具有在迭代后期易早熟收斂，陷入局部最優的問題，很難直接應用于基站選址的優化問題中。針對上述問題，本文基于兼顧網絡覆蓋率，提出一種粒子群與果蠅算法相結合的粒子群果蠅混合優化算法，為驗證改進算法的有效性，本文基于三種測試函數和一種基站選址優化問題的實際測試算例，采用不同算法進行仿真試驗。試驗結果表明，本文提出的改進算法具有更佳的算法性能。

2 基站選址優化問題的數學模型

由于網絡用戶的激增，目前基站選址優化面臨的最突出的問題即是在網絡基站有限的情況下，更好地提升網絡覆蓋率以解決用戶信號不穩定的問題［11］。因此，基站選址優化問題中的網絡覆蓋率優化是至關重要的，網絡覆蓋率記為fcov。具體的以網絡覆蓋率優化作為優化目的的優化模型為

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

3 改進的粒子群果蠅混合算法

3.1 粒子群算法

在粒子群算法［12］中，設種群規模為N，維度為D，則第i的粒子的初始位置為，初始速度為

基本粒子群算法更新迭代計算公式如式（2）所述：

3.2 果蠅優化算法

果蠅優化算法是一種新的仿生優化算法，由潘文超在2011年6月提出［12］。果蠅優化算法參數結構簡單，易于調節。若果蠅數目為Nf，最優果蠅的位置為Xaxis、Yaxis。

基本果蠅優化算法更新迭代計算公式如式（3）所述：

式（3）中，j為果蠅序號為果蠅 維 度為 隨 機 數，為果蠅第tf維的搜索半徑。

由于無法得知食物位置，需要先計算序號為j的當前果蠅個體位置與原點的距離Dj，再計算味道濃度判斷值Sj，Sj為距離Dj的倒數，具體的計算公式如式（4）所述：

果蠅優化算法通過其味道濃度值來判定優劣，具體的味道濃度值計算公式如式（5）所述：

式（5）中，Smellj為第j個果蠅個體的味道濃度函數值，fs為味道濃度值計算公式。

3.3 粒子群果蠅混合算法

粒子群算法和果蠅優化算法都具有極強的全局優化搜索能力，然而，由粒子群算法和果蠅算法的迭代計算公式可知，粒子群算法總使得全部個體都向最優個體進行學習，這導致最優個體對種群進化起著決定性的作用，使得種群難以維持其多樣性，而總是趨于相同。為此，本文基于粒子群算法和果蠅優化算法的個體公式給出了一種新的個體更新規則。具體的粒子群果蠅混合算法的個體更新迭代計算公式如式（6）所述：

式（6）中，rpso為粒子群算法的更新權重顯然，1-rpso為果蠅混合算法的更新權重；Rd為第d維的搜索半徑；rand為隨機數為基本粒子群算法得到的個體更新結果；為粒子群果蠅混合算法所給出的引導個體；為粒子群果蠅混合算法最終得到的個體更新結果。

3.4 引入遺傳進化機制的混合算法更新流程

盡管粒子群果蠅混合算法采用的個體更新公式考慮了粒子群算法和果蠅算法的更新方式，但由于引導個體仍然是基于最優個體進行改變的。所以，本質上沒有改變粒子群算法和果蠅優化算法的更新模式，其個體趨同抑制效果是有限的。為了更好地抑制類似粒子群算法和果蠅優化算法這種特別依賴于最優個體的尋優模式導致的算法容易陷入局部最優的缺點，將遺傳進化機制［13］引入其更新流程是一種很好的改進策略選擇。具體的引入遺傳進化機制的改進的果蠅粒子群混合算法的更新流程如圖1所示。

圖1 改進的果蠅粒子群混合算法的更新流程圖

4 仿真實驗

4.1 基于測試函數的仿真對比

本文采用三種不同的測試函數（ZDT1、ZDT2、DTLZ1）對本文提出的改進粒子群果蠅混合算法（IHA）、果蠅算法（FOA）和粒子群算法（PSO）分這三種不同的智能優化算法進行對比測試。采用IGD［14］測試函數作為評價函數，對三種算法進行數值仿真實驗，其計算公式如式（7）所示：

式（7）中，P為均勻采用點真實值，P′為算法求解所得Pareto近似解集。為采樣點到近似解集之間的最小距離。以下是具體的測試結果。采用ZDT1、ZDT2、DTLZ1等函數的仿真測試結果效果圖如圖2~圖4所示，各個算法獲得的IGD值如 表1所示。

表1 各個尋優算法獲得的IGD值

圖2 采用ZDT1函數的仿真測試結果效果圖

圖3 采用ZDT2函數的仿真測試結果效果圖

圖4 采用DTLZ1函數的仿真測試結果效果圖

圖2 ~圖4中，TPF表示測試函數的真實前沿。

由表1可知，相較于對比算法果蠅優化算法（FOA）和粒子群算法（PSO），本文提出的改進粒子群果蠅混合算法（IHA）取得了明顯較優的IGD值。由圖2~圖4可知，本文提出的改進粒子群果蠅混合算法（IHA）得到的優化結果更加靠近ZDT1、ZDT2、DTLZ1的真實前沿，并且分布的更加均勻。因此，本文提出的改進粒子群果蠅混合算法（IHA）在一般的測試函數上具有比其它優化算法更佳的優化性能。

4.2 基于實際問題測試算例的仿真對比

本文采用實際基站選址優化問題的測試算例對本文提出的改進粒子群果蠅混合算法（IHA）、果蠅算法（FOA）和粒子群算法（PSO）這三種不同的粒子群算法進行對比測試。本文選用的基站選址問題的測試算例的參數如下：基站數目為3、基站覆蓋半徑為15km、測試區域為80×60km2、測試點總數目為261個。

以下是具體的測試結果。采用本文提出的改進粒子群果蠅混合算法（IHA）、果蠅算法（FOA）和粒子群算法（PSO）求解得到的基站覆蓋效果圖如圖5~圖7所示，各個算法迭代收斂曲線如圖8所示，各個算法得到最終優化結果如表2所示。

圖8 各個算法迭代曲線效果圖

表2 各個尋優算法獲得的IGD值

圖5 改進粒子群果蠅混合算法（IHA）得到的基站覆蓋效果圖

圖7 果蠅優化算法（FOA）得到的基站覆蓋效果圖

圖6 果蠅優化算法（FOA）得到的基站覆蓋效果圖

從表2和圖8可知，相較其他兩種算法求解的結果，本文所提改進粒子群果蠅混合算法求解的網絡覆蓋率更高，求解所需迭代次數最少，說明本文所提改進粒子群果蠅混合算法的求解精度跟高，求解速度更快。此外，從圖5~圖7可知，相較其FOA算法和PSO算法的求解結果，本文所提改進粒子群果蠅混合算法對測試點密集區的覆蓋率更高，分布更加廣泛均勻，說明本文所提改進粒子群果蠅混合算法的求解覆蓋效果更高，求解的結果更加合理，有效。因此，本文提出的改進粒子群果蠅混合算法（IHA）更適合于求解基站選址優化問題。

5 結語

本文基于基站選址優化問題，提出了一種改進粒子群果蠅混合算法（IHA）。首先，在粒子群算法和果蠅優化算法的個體更新方式的基礎上，結合兩種算法的特性，提出了一種復合的個體更新方式，從而避免單一更新方式引起的算法陷入局部極小值的問題；其次，引入了遺傳進化機制，以便于更好地維持種群多樣性，提高算法的全局搜索能力和局部開發能力。通過測試函數對比實驗和基站優化對比實驗的實驗結果可知，本文提出的改進的粒子群果蠅混合算法（IHA）的尋優性能更佳，能夠更有效地解決基站選址優化問題。