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

趙敏 佘磊 陳炳橋 樊思琪

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

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

引言

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

1.模擬退火算法

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

2.蟻群算法

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

信息素更新的表達式為：

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

3.混合算法

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

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

參考文獻：

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

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

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

[4]張弛，涂立.新型蟻群算法在TSP 問題中的應用 [J].中南大學學報（自然科學版）， 2015，46（8）

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