基于蟻群-模擬退火算法的基站選址研究

趙敏 佘磊 陳炳橋 樊思琪

摘 要：蟻群算法雖然在螞蟻算法的基礎(chǔ)上已經(jīng)有了改進(jìn)但仍然會(huì)有缺陷，最大的缺點(diǎn)就是會(huì)陷入局部最優(yōu)解。模擬退火算法最大的特點(diǎn)就是有一個(gè)蒙地卡洛判斷準(zhǔn)則，允許其接受一個(gè)較差解，不過算法卻恰恰因?yàn)檫@點(diǎn)而會(huì)非常的耗時(shí)。通過理論的研究發(fā)現(xiàn)可以將這兩種算法融合在一起，兩種算法可以實(shí)現(xiàn)互補(bǔ)。最終便選擇基站選址這個(gè)實(shí)際應(yīng)用問題去用matlab仿真看是否真的可以減少基站的建設(shè)數(shù)量。

關(guān)鍵詞：模擬退火;蟻群;基站選址

引言

基站的作用就是來覆蓋用戶，目前對(duì)于被覆蓋用戶，會(huì)根據(jù)不同的用戶特性分為不同的等級(jí)，一般分為高級(jí)用戶和低級(jí)用戶。對(duì)于覆蓋要求是：高級(jí)用戶全覆蓋，普通用戶盡可能覆蓋但不低于70%。對(duì)于基站的選擇問題，可以看作是一個(gè)多目標(biāo)智能優(yōu)化的選擇，這樣便可以將一些傳統(tǒng)算法加在選址中，可以有效地減少基站的建設(shè)數(shù)量。

1.模擬退火算法

模擬退火實(shí)際上算是一種貪心算法的改進(jìn)，就是為了避免尋找到局部最優(yōu)解。模擬退火算法是模仿固體降溫的一種概率算法。在熱力學(xué)中溫度越高固體內(nèi)部的狀態(tài)越無序，而當(dāng)溫度慢慢降低時(shí)固體內(nèi)部的狀態(tài)變逐漸趨于穩(wěn)定，在每一個(gè)溫度下都會(huì)有一個(gè)平衡狀態(tài)直到最后在常溫下達(dá)到平衡狀態(tài)即最佳狀態(tài)。需要注意的是降溫是一個(gè)緩慢的過程不能快速降，否則會(huì)破壞物體內(nèi)部的晶體狀態(tài)從而導(dǎo)致找不到合適的位置。模擬退火最大的特點(diǎn)就是在于Metropolis的判斷準(zhǔn)則，在t溫度下的平衡概率為 ? ? ? ? ? ? ? ? ? ? ，其中k為Boltzmann常數(shù)，△E為固體內(nèi)部能量的變化大小，將E變成目標(biāo)函數(shù)，溫度T變成控制參數(shù)。整個(gè)算法是由初始解和參數(shù)t開始，其過程為初始解->得到新解->計(jì)算目標(biāo)差->判斷是否接受，在滿足該溫度下的迭代次數(shù)后不斷降低參數(shù)t的值直到t降為常溫。因?yàn)槠浣邮茌^差解的特性可以發(fā)現(xiàn)模擬退火算法有全局的優(yōu)化功能。

2.蟻群算法

蟻群算法就是模仿現(xiàn)實(shí)中螞蟻覓食的過程。現(xiàn)實(shí)中的螞蟻都是通過嗅覺來完成食物的尋找任務(wù)，路徑上的信息素越多則該路徑被選擇的概率越大。t時(shí)刻第i只螞蟻由位置i轉(zhuǎn)移到位置j的概率為：

信息素更新的表達(dá)式為：

于是可以看出信息素的大小對(duì)路徑的選擇至關(guān)重要，所以對(duì)信息素的更新蟻群算法還分成了三個(gè)不同的模型分別是：蟻密模型，蟻量模型，蟻周模型。蟻密模型和蟻量模型都是在螞蟻經(jīng)過兩個(gè)點(diǎn)后開始更新信息素。區(qū)別在于后者的信息素更新會(huì)考慮到路徑的長(zhǎng)度。本文采用的是第三種模型-蟻周模型，因?yàn)橄啾容^于其它兩種模型的實(shí)時(shí)更新，蟻周模型的全局更新顯得更加的高效，畢竟是從全局出發(fā)而前兩種只是從局部出發(fā)。

3.混合算法

模擬退火算法可以在全局中找到最優(yōu)解但耗時(shí)過長(zhǎng)，特別是在處理大規(guī)模數(shù)據(jù)的時(shí)候這一點(diǎn)會(huì)顯得更外得明顯，這就是為了找到全局最優(yōu)解所付出的代價(jià)。蟻群算法的耗時(shí)短是因?yàn)槲浵佋谶x擇路徑時(shí)根據(jù)信息素的強(qiáng)度來做出判斷所以極其容易陷入局部最優(yōu)解。最開始的時(shí)候每條路徑上的信息素都一樣，如果在蟻群中有一只螞蟻在第前幾輪的迭代過程中便發(fā)現(xiàn)了一條較優(yōu)秀的路徑，那么便會(huì)對(duì)后面螞蟻的選擇產(chǎn)生干擾。隨后越來越多的螞蟻選擇這條路徑，最終被確定為最優(yōu)路徑，然而從全局來看這并不是一條最優(yōu)路徑。蟻群-模擬退火混合算法正好將這兩個(gè)算法相融合，用Metropolis判斷準(zhǔn)則去消除蟻群算法中的陷入局部最優(yōu)解的情況，在蟻群算法的框架下使用模擬退火算法可以解決模擬退火算法耗時(shí)長(zhǎng)的缺點(diǎn)。為了證明自己的理論是正確的，這里選用matlab在基站選址這實(shí)際問題中進(jìn)行仿真，來驗(yàn)證混合算法在實(shí)際應(yīng)用的過程中是否會(huì)真的像理論上分析的那樣可以減少基站的建設(shè)數(shù)量。

三張仿真圖依次是蟻群算法，模擬退火算法，蟻群-模擬退火算法。從仿真圖上的運(yùn)行效果來看，蟻群-模擬退火混合算法所需要的基站數(shù)量最少是7個(gè)而蟻群算法需要10個(gè)，模擬退火算法需要8個(gè)。從建設(shè)數(shù)量上來看，蟻群-模擬退火算法無疑是具有實(shí)際效益的，所需要的建設(shè)數(shù)量均比其它兩種算法小，這樣便可以減少資金放大投入，很好的達(dá)到了我們所需要的預(yù)期效果。這恰好證明了本文所提出的蟻群-模擬退火算法不僅僅具有理論上的可行性，而且還具有實(shí)際的應(yīng)用意義。

參考文獻(xiàn)：

[1]姜曉濤.基于模擬退火的蟻群算法求解網(wǎng)格任務(wù)調(diào)度問題 [D] . 安徽大學(xué) 2012

[2]周巖，王學(xué)瑞.基于模擬退火與蟻群算法的圖像邊緣檢測(cè) [J].蘭州工業(yè)學(xué)院學(xué)報(bào)， 2016，23（3）

[3]王琛.基于TSP的蟻群退火混合算法研究 [J].山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版，2014，28（3）

[4]張弛，涂立.新型蟻群算法在TSP 問題中的應(yīng)用 [J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版）， 2015，46（8）

[5]秦軍，董倩倩.基于蟻群模擬退火的云任務(wù)調(diào)度算法改進(jìn) [J].計(jì)算機(jī)技術(shù)與發(fā)展， 2017，27（3）