劉 娟 楊春花

（烏魯木齊職業(yè)大學(xué)信息工程學(xué)院 烏魯木齊832000）

1 引言

在通訊設(shè)備建設(shè)中，基站選址優(yōu)化是一項(xiàng)極其復(fù)雜又非常重要的問(wèn)題［1］。隨著現(xiàn)代通訊事業(yè)的大力發(fā)展，網(wǎng)絡(luò)覆蓋率低導(dǎo)致的用戶(hù)對(duì)網(wǎng)絡(luò)供應(yīng)商的矛盾也日益引發(fā)人們的關(guān)注和重視?；具x址優(yōu)化問(wèn)題的核心是提高網(wǎng)絡(luò)覆蓋率。然而，由于基站選址優(yōu)化時(shí)，具有用戶(hù)量大、計(jì)算復(fù)雜以及大量復(fù)雜因素等特點(diǎn)，使得基站選址模型具有較強(qiáng)的非線(xiàn)性和不確定性，使得傳統(tǒng)的優(yōu)化策略難以精確有效地對(duì)選址模型進(jìn)行求解。

目前，基站選址優(yōu)化的相關(guān)算法改進(jìn)策略已成為相關(guān)科研人員的研究重點(diǎn)。目前，已經(jīng)有大量的研究應(yīng)用于實(shí)際的基站選址優(yōu)化問(wèn)題中。為了降低TD-SCDMA網(wǎng)絡(luò)基站建設(shè)代價(jià)，朱思峰［2］等提出了一種基于免疫計(jì)算的基站選址優(yōu)化方案。石雷［3］等設(shè)計(jì)了基于干擾管理的高吞吐基站選址算法，針對(duì)在傳輸過(guò)程中遇到的并發(fā)傳輸干擾，通過(guò)干擾管理策略進(jìn)行優(yōu)化，提高了數(shù)據(jù)傳輸效率。張英杰［4］等提出了一種基于免疫算法的TD-SCDMA網(wǎng)絡(luò)基站選址優(yōu)化方案。針對(duì)現(xiàn)有3G基站選址方法的不足，閆濤［5］提出了一種基于免疫算法的基站選址優(yōu)化方法。王亞偉［6］等提出一種基于聚類(lèi)遺傳算法的基站選址優(yōu)化方案。晁迎［7］等提出一種加速遺傳算法的基站選址優(yōu)化方案。此外還有基于多目標(biāo)優(yōu)化量子免疫算法的基站選址優(yōu)化方案［8］、基于免疫記憶克隆算法的基站選址優(yōu)化方案［9］和基于WCDMA的基站選址優(yōu)化方案［9］。以上的研究能夠?qū)Σ糠只具x址優(yōu)化問(wèn)題解決有相當(dāng)程度的幫助，但仍然存在著算法尋優(yōu)效果不夠理想的問(wèn)題。

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

2 基站選址優(yōu)化問(wèn)題的數(shù)學(xué)模型

由于網(wǎng)絡(luò)用戶(hù)的激增，目前基站選址優(yōu)化面臨的最突出的問(wèn)題即是在網(wǎng)絡(luò)基站有限的情況下，更好地提升網(wǎng)絡(luò)覆蓋率以解決用戶(hù)信號(hào)不穩(wěn)定的問(wèn)題［11］。因此，基站選址優(yōu)化問(wèn)題中的網(wǎng)絡(luò)覆蓋率優(yōu)化是至關(guān)重要的，網(wǎng)絡(luò)覆蓋率記為fcov。具體的以網(wǎng)絡(luò)覆蓋率優(yōu)化作為優(yōu)化目的的優(yōu)化模型為

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

3 改進(jìn)的粒子群果蠅混合算法

3.1 粒子群算法

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

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

3.2 果蠅優(yōu)化算法

果蠅優(yōu)化算法是一種新的仿生優(yōu)化算法，由潘文超在2011年6月提出［12］。果蠅優(yōu)化算法參數(shù)結(jié)構(gòu)簡(jiǎn)單，易于調(diào)節(jié)。若果蠅數(shù)目為Nf，最優(yōu)果蠅的位置為Xaxis、Yaxis。

基本果蠅優(yōu)化算法更新迭代計(jì)算公式如式（3）所述：

式（3）中，j為果蠅序號(hào)為果蠅 維 度為 隨 機(jī) 數(shù)，為果蠅第tf維的搜索半徑。

由于無(wú)法得知食物位置，需要先計(jì)算序號(hào)為j的當(dāng)前果蠅個(gè)體位置與原點(diǎn)的距離Dj，再計(jì)算味道濃度判斷值Sj，Sj為距離Dj的倒數(shù)，具體的計(jì)算公式如式（4）所述：

果蠅優(yōu)化算法通過(guò)其味道濃度值來(lái)判定優(yōu)劣，具體的味道濃度值計(jì)算公式如式（5）所述：

式（5）中，Smellj為第j個(gè)果蠅個(gè)體的味道濃度函數(shù)值，fs為味道濃度值計(jì)算公式。

3.3 粒子群果蠅混合算法

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

式（6）中，rpso為粒子群算法的更新權(quán)重顯然，1-rpso為果蠅混合算法的更新權(quán)重；Rd為第d維的搜索半徑；rand為隨機(jī)數(shù)為基本粒子群算法得到的個(gè)體更新結(jié)果；為粒子群果蠅混合算法所給出的引導(dǎo)個(gè)體；為粒子群果蠅混合算法最終得到的個(gè)體更新結(jié)果。

3.4 引入遺傳進(jìn)化機(jī)制的混合算法更新流程

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

圖1 改進(jìn)的果蠅粒子群混合算法的更新流程圖

4 仿真實(shí)驗(yàn)

4.1 基于測(cè)試函數(shù)的仿真對(duì)比

本文采用三種不同的測(cè)試函數(shù)（ZDT1、ZDT2、DTLZ1）對(duì)本文提出的改進(jìn)粒子群果蠅混合算法（IHA）、果蠅算法（FOA）和粒子群算法（PSO）分這三種不同的智能優(yōu)化算法進(jìn)行對(duì)比測(cè)試。采用IGD［14］測(cè)試函數(shù)作為評(píng)價(jià)函數(shù)，對(duì)三種算法進(jìn)行數(shù)值仿真實(shí)驗(yàn)，其計(jì)算公式如式（7）所示：

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

表1 各個(gè)尋優(yōu)算法獲得的IGD值

圖2 采用ZDT1函數(shù)的仿真測(cè)試結(jié)果效果圖

圖3 采用ZDT2函數(shù)的仿真測(cè)試結(jié)果效果圖

圖4 采用DTLZ1函數(shù)的仿真測(cè)試結(jié)果效果圖

圖2 ~圖4中，TPF表示測(cè)試函數(shù)的真實(shí)前沿。

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

4.2 基于實(shí)際問(wèn)題測(cè)試算例的仿真對(duì)比

本文采用實(shí)際基站選址優(yōu)化問(wèn)題的測(cè)試算例對(duì)本文提出的改進(jìn)粒子群果蠅混合算法（IHA）、果蠅算法（FOA）和粒子群算法（PSO）這三種不同的粒子群算法進(jìn)行對(duì)比測(cè)試。本文選用的基站選址問(wèn)題的測(cè)試算例的參數(shù)如下：基站數(shù)目為3、基站覆蓋半徑為15km、測(cè)試區(qū)域?yàn)?0×60km2、測(cè)試點(diǎn)總數(shù)目為261個(gè)。

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

圖8 各個(gè)算法迭代曲線(xiàn)效果圖

表2 各個(gè)尋優(yōu)算法獲得的IGD值

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

圖7 果蠅優(yōu)化算法（FOA）得到的基站覆蓋效果圖

圖6 果蠅優(yōu)化算法（FOA）得到的基站覆蓋效果圖

從表2和圖8可知，相較其他兩種算法求解的結(jié)果，本文所提改進(jìn)粒子群果蠅混合算法求解的網(wǎng)絡(luò)覆蓋率更高，求解所需迭代次數(shù)最少，說(shuō)明本文所提改進(jìn)粒子群果蠅混合算法的求解精度跟高，求解速度更快。此外，從圖5~圖7可知，相較其FOA算法和PSO算法的求解結(jié)果，本文所提改進(jìn)粒子群果蠅混合算法對(duì)測(cè)試點(diǎn)密集區(qū)的覆蓋率更高，分布更加廣泛均勻，說(shuō)明本文所提改進(jìn)粒子群果蠅混合算法的求解覆蓋效果更高，求解的結(jié)果更加合理，有效。因此，本文提出的改進(jìn)粒子群果蠅混合算法（IHA）更適合于求解基站選址優(yōu)化問(wèn)題。

5 結(jié)語(yǔ)

本文基于基站選址優(yōu)化問(wèn)題，提出了一種改進(jìn)粒子群果蠅混合算法（IHA）。首先，在粒子群算法和果蠅優(yōu)化算法的個(gè)體更新方式的基礎(chǔ)上，結(jié)合兩種算法的特性，提出了一種復(fù)合的個(gè)體更新方式，從而避免單一更新方式引起的算法陷入局部極小值的問(wèn)題；其次，引入了遺傳進(jìn)化機(jī)制，以便于更好地維持種群多樣性，提高算法的全局搜索能力和局部開(kāi)發(fā)能力。通過(guò)測(cè)試函數(shù)對(duì)比實(shí)驗(yàn)和基站優(yōu)化對(duì)比實(shí)驗(yàn)的實(shí)驗(yàn)結(jié)果可知，本文提出的改進(jìn)的粒子群果蠅混合算法（IHA）的尋優(yōu)性能更佳，能夠更有效地解決基站選址優(yōu)化問(wèn)題。