一種基于禁忌搜索算法的設(shè)站問題解決方案*

邱 戀，李秦偉

0 引 言

設(shè)站問題是網(wǎng)絡(luò)規(guī)劃過程中的關(guān)鍵問題，不僅影響用戶的通信質(zhì)量，而且影響運(yùn)營商的運(yùn)營利潤。網(wǎng)絡(luò)規(guī)劃過程中的設(shè)站問題，實(shí)質(zhì)是從多個(gè)候選基站中選擇既滿足通信質(zhì)量要求又能使運(yùn)營商設(shè)站成本最低的一組若干個(gè)基站。

1 通信網(wǎng)規(guī)劃簡介

通信網(wǎng)絡(luò)規(guī)劃的目標(biāo)，是在要提供業(yè)務(wù)的區(qū)域里，根據(jù)所要保證的業(yè)務(wù)、所要支持的業(yè)務(wù)量、所需服務(wù)的用戶數(shù)量，通過采用一系列理論分析、工具仿真與預(yù)測(cè)，獲得支持相應(yīng)用戶數(shù)量所需的網(wǎng)絡(luò)設(shè)備的數(shù)量、配置和部屬地點(diǎn)[1]，以供核算網(wǎng)絡(luò)投資，并為未來的工程設(shè)計(jì)提供參考。下面以WCDMA系統(tǒng)的網(wǎng)絡(luò)規(guī)劃為例進(jìn)行說明。

無線網(wǎng)絡(luò)規(guī)劃是WCDMA系統(tǒng)走向商用的關(guān)鍵工作，直接影響網(wǎng)絡(luò)建設(shè)成本、網(wǎng)絡(luò)容量、服務(wù)質(zhì)量以及設(shè)備性能的發(fā)揮。WCDMA無線網(wǎng)絡(luò)規(guī)劃的工作分為初步規(guī)劃和詳細(xì)規(guī)劃兩階段[2]。初步規(guī)劃的結(jié)果通常是對(duì)網(wǎng)絡(luò)規(guī)模有一個(gè)數(shù)量上的認(rèn)識(shí)，而基站站址選擇則是詳細(xì)規(guī)劃的重要內(nèi)容[3]。

通信網(wǎng)規(guī)劃中，設(shè)站問題的關(guān)鍵主要有兩個(gè)：一是所需站的數(shù)量，二是站點(diǎn)設(shè)置的位置。如何確定站點(diǎn)數(shù)量和站點(diǎn)對(duì)應(yīng)設(shè)置位置，可歸類為組合優(yōu)化問題。

組合優(yōu)化問題可以用一個(gè)包含三個(gè)參數(shù)的關(guān)系式表示即(D,F,f)，其中D表示決策變量的定義域，設(shè)站問題中相當(dāng)于需要規(guī)劃的區(qū)域；F表示可行解區(qū)域，設(shè)站問題中相當(dāng)于候選站址集合，F(xiàn)中的任何一個(gè)元素稱為該問題的可行解；f表示目標(biāo)函數(shù)，設(shè)站問題中等同于滿足基站建站成本和滿足通信質(zhì)量要求的代價(jià)函數(shù)。具體地，滿足式（1）的可行解x*稱為該問題的最優(yōu)解。

可以看到，F(xiàn)的數(shù)量有限，只要有充足的時(shí)間對(duì)可行解集F的每一種情況進(jìn)行嘗試，總會(huì)找到滿足f最小的解[4]。

在通信網(wǎng)規(guī)劃過程中，站址選擇的目標(biāo)函數(shù)通常包括基站建站費(fèi)用C、滿足功率覆蓋要求時(shí)基站位置折合成的代價(jià)D、移動(dòng)臺(tái)與基站連接需要的代價(jià)K以及連接基站中繼線的代價(jià)X等，即目標(biāo)函數(shù)L為：

設(shè)第i個(gè)基站的建站成本為fi，將第i個(gè)移動(dòng)臺(tái)與第j個(gè)基站連接的代價(jià)設(shè)為cij，再把D和X折算成每個(gè)基站的權(quán)重wi，則式（2）可寫成式（3）：

式中dij表示第i個(gè)移動(dòng)臺(tái)與第j個(gè)基站的距離測(cè)度。此時(shí)的設(shè)站問題可描述為，在基站候選集F中，找到滿足代價(jià)L最小時(shí)的一組k個(gè)基站和k個(gè)基站對(duì)應(yīng)的位置f(d)。

對(duì)于一個(gè)中等規(guī)模的規(guī)劃場(chǎng)景，假設(shè)有50個(gè)候選站址，則可選的規(guī)劃方案可達(dá)250-1種。顯然，這種問題通過窮舉方法求得最優(yōu)解是不可行的[3]。這類選擇優(yōu)化問題一般可用啟發(fā)式算法求解，從可行解域中尋找一個(gè)在可接受的計(jì)算時(shí)間內(nèi)能找到的可行解作為問題的解。

2 禁忌搜索概述

2.1 啟發(fā)式算法簡介

啟發(fā)式算法是相對(duì)于優(yōu)化算法提出的。它可以這樣定義：一個(gè)基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的花費(fèi)（指計(jì)算時(shí)間、占用空間等）下給出待解決組合優(yōu)化問題每一個(gè)實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度不一定事先可以預(yù)計(jì)[5]。

啟發(fā)式算法包括禁忌搜索算法（Tabu search）、模擬退火算法（Simulated Annealing）、遺傳算法（Genetic Algorithms）、神經(jīng)網(wǎng)絡(luò)算法（Neural Networks）和拉格朗日松弛算法等。這些算法涉及生物進(jìn)化、人工智能、數(shù)學(xué)和物理科學(xué)、神經(jīng)系統(tǒng)和統(tǒng)計(jì)力學(xué)等概念，是以一定的直觀基礎(chǔ)而構(gòu)造的算法，故而稱之為啟發(fā)式算法。

2.2 禁忌搜索簡介

禁忌搜索（Tabu Search或Taboo Search）[6]作為一種常用的優(yōu)化算法，最大的優(yōu)點(diǎn)在于可以跳出局部最優(yōu)解，找到全局最優(yōu)解[7]。一方面，算法通過設(shè)置禁忌表，把已經(jīng)找到的一組準(zhǔn)最優(yōu)解放在禁忌表中保護(hù)。設(shè)置禁忌長度表示保護(hù)進(jìn)行多少步。例如，禁忌長度設(shè)置為3，則接下來的3步被保護(hù)的準(zhǔn)最優(yōu)解將不被考慮。另一方面，算法還設(shè)置了一種特赦原則，即如果找到一組新的解，它的目標(biāo)函數(shù)比之前已找到的所有情況都要好，那么這個(gè)新的最優(yōu)解就作為當(dāng)前為止的最佳解（best_so_far），同時(shí)將該解送入禁忌表進(jìn)行保護(hù)。

禁忌搜索算法的主要過程是在鄰域內(nèi)尋找全局最優(yōu)解[8]，是人工智能與局部鄰域搜索算法的結(jié)合，沿襲了鄰域搜索的鄰域構(gòu)造，并增加了一個(gè)禁忌表。值得關(guān)注的是，鄰域的連通性是禁忌搜索可以達(dá)到全局優(yōu)解的一個(gè)必要條件[9]，其連通與否直接關(guān)系禁忌搜索算法能否得到全局最優(yōu)解。

禁忌搜索涉及到禁忌表（tabu list）、禁忌長度（tabu length）、鄰域（neighborhood）、候選解（candidate）、特赦準(zhǔn)則（free pardon criterion）等概念[10]。

2.3 禁忌搜索算法流程

鄰域。在禁忌搜索算法中，鄰域是一個(gè)相對(duì)于初始解的概念。假設(shè)算法的所有解集為C,給定的初始解為Zs的鄰域?yàn)镹i,則應(yīng)有：

且Z與Ni之間必須連通。

禁忌表。禁忌表用來保存當(dāng)前搜索步數(shù)下被禁止考慮的解集。該解集元素的數(shù)量主要由禁忌長度決定。同時(shí)，若禁忌長度值為n，則也決定了被禁止考慮的某個(gè)解在接下來的n次搜索將不會(huì)被考慮。

候選解。候選解是從前一次搜索所使用的解的鄰域中選出來的一組或若干組解，候選解一定不是禁忌表中的保護(hù)項(xiàng)。

特赦準(zhǔn)則。特赦準(zhǔn)則用于保存當(dāng)前搜索次數(shù)為止得到的最優(yōu)解。

簡單禁忌搜索算法的基本思想：給定一個(gè)當(dāng)前解（初始解）和一種鄰域，在當(dāng)前解的鄰域中確定若干候選解；若候選解對(duì)應(yīng)的目標(biāo)值中有優(yōu)于當(dāng)前為止最佳解“best_so_far”狀態(tài)的，則忽視其禁忌特性，用其替代當(dāng)前解和“best_so_far”狀態(tài)，并將相應(yīng)的對(duì)象加入禁忌表，同時(shí)修改禁忌表中各對(duì)象的任期；若不存在上述候選解，則無視它與“best_so_far”的優(yōu)劣，在候選解中選擇非禁忌的最佳狀態(tài)為新的當(dāng)前解，同時(shí)將相應(yīng)的對(duì)象加入禁忌表，并修改禁忌表中各對(duì)象的任期；如此重復(fù)上述迭代搜索過程，直至滿足停止準(zhǔn)則[11]。

算法步驟可描述如下：

（1）設(shè)置搜索參數(shù)，初始解設(shè)為z，并清空禁忌表。

（2）判斷算法終止條件是否滿足？若是，則結(jié)束算法并輸出優(yōu)化結(jié)果；否則，繼續(xù)以下步驟。

（3）把當(dāng)前解z作為鄰域函數(shù)的輸入?yún)?shù)調(diào)用鄰域函數(shù)，從其所產(chǎn)生的z的鄰域解集中確定若干候選解。

（4）候選解代入目標(biāo)函數(shù)L，所得結(jié)果與特赦準(zhǔn)則進(jìn)行對(duì)比判定。若符合特赦準(zhǔn)則，則用最佳狀態(tài)y替代z成為新的當(dāng)前解即z=y，并用與y對(duì)應(yīng)的禁忌對(duì)象替換早進(jìn)入禁忌表的禁忌對(duì)象，同時(shí)用y替換“best_so_far”狀態(tài)，然后轉(zhuǎn)步驟（2）；否則，進(jìn)行步驟（5）。

圖1 算法流程

（5）判斷候選解對(duì)應(yīng)的各對(duì)象的禁忌屬性，選擇候選解集中非禁忌對(duì)象對(duì)應(yīng)的最佳狀態(tài)為新的當(dāng)前解，同時(shí)用與之對(duì)應(yīng)的禁忌對(duì)象替換早進(jìn)入禁忌表的禁忌對(duì)象元素，轉(zhuǎn)步驟（2）。

上述算法可用流程圖更直觀,描述，如圖1所示[4]。

從算法流程可以看出，禁忌表、禁忌長度、鄰域函數(shù)和特赦準(zhǔn)則是禁忌搜索算法的關(guān)鍵。其中，禁忌表和禁忌長度的設(shè)置能為局部最優(yōu)解提供保護(hù)；鄰域函數(shù)沿用局部鄰域搜索的思想，用于實(shí)現(xiàn)鄰域搜索；特赦準(zhǔn)則用于保護(hù)當(dāng)前最佳解并保存全局最優(yōu)。上述算法僅是一種簡單的禁忌搜索框架，對(duì)各關(guān)鍵環(huán)節(jié)復(fù)雜和多樣化的設(shè)計(jì)，它可構(gòu)造出各種禁忌搜索算法。同時(shí)，算法流程中的禁忌對(duì)象可以是搜索狀態(tài)，也可以是特定搜索操作，甚至是搜索目標(biāo)值等。

3 算法設(shè)計(jì)與實(shí)驗(yàn)分析

3.1 案例與分析

本文假設(shè)在指定區(qū)域內(nèi)，經(jīng)前期預(yù)規(guī)劃，確定30個(gè)候選基站位置，如圖2所示。

30個(gè)候選基站的位置坐標(biāo)表示成矩陣：

一天，宋娟的父親從街上買回一個(gè)西瓜，那個(gè)西瓜的皮非常厚，母親舍不得扔，就把外面的青皮一刨，切成一片片炒出了一盤美味的蔬菜。這給了宋娟一個(gè)大膽的想法：能不能把柚子也當(dāng)成蔬菜賣？

設(shè)它們的相對(duì)建站費(fèi)用分別為：

設(shè)在所規(guī)劃的區(qū)域內(nèi)移動(dòng)臺(tái)均勻分布，要實(shí)現(xiàn)完全覆蓋預(yù)計(jì)需要10個(gè)臺(tái)站。

實(shí)際問題中，為排除候選站址集中分布的不合理情況，需要把候選站址分組，以確保規(guī)劃區(qū)域內(nèi)臺(tái)站的分散性。根據(jù)站點(diǎn)位置關(guān)系和離散程度，將候選站址區(qū)分為10個(gè)小組，通過窮舉的方法，代入式（3）計(jì)算所有的310種組合，得到如圖3所示的各種組合情況對(duì)應(yīng)的規(guī)劃代價(jià)值。

由圖3可知，代價(jià)最小值Lmin=189 277.778 3，其對(duì)應(yīng)的組合即為最優(yōu)組合，同時(shí)也是本實(shí)例的最優(yōu)解。

3.2 算法設(shè)計(jì)

3.2.1 鄰域構(gòu)造

本文設(shè)計(jì)了一種基于隨機(jī)因子的鄰域構(gòu)造方法。鄰域構(gòu)造原理圖如圖4所示。

由初始解（或前一次搜索所使用的解）z和隨機(jī)因子s共同確定初始解（或前一次搜索使用的解）的鄰域。設(shè)解為 z=[z1,z2,…zi]，則對(duì)應(yīng)的鄰域N為：

實(shí)例中候選站址的數(shù)量是有限的。所以，隨著si的多次隨機(jī)跳變，可以遍歷所有的組合情況，保證鄰域的連通性。同時(shí)通過對(duì)si的設(shè)置，可以調(diào)整領(lǐng)域變化的強(qiáng)度。

3.2.2 搜索完成條件

設(shè)置完成搜索的條件有兩個(gè)，一是禁忌搜索次數(shù)達(dá)到100次到達(dá)上限、停止搜索，并認(rèn)可當(dāng)前為止最佳“best_so_far”為最佳解；二是“best_so_far”狀態(tài)保持連續(xù)40次不變且有15次回歸“best_so_far”狀態(tài)。此時(shí)，認(rèn)可“best_so_far”值為最優(yōu)站址方案時(shí)的最佳目標(biāo)函數(shù)值，對(duì)應(yīng)的站址方案為最優(yōu)站址方案，同時(shí)結(jié)束搜索。

3.2.3 算法參數(shù)設(shè)置

本算法中設(shè)置一個(gè)禁忌表，禁忌長度為5。將式（3）作為設(shè)站問題的目標(biāo)函數(shù)，初始解設(shè)置為Z=[2,6,9,12,15,16,20,24,27,30]，即案例中的第2、6、9、12、15、16、20、24、27和第30共10個(gè)基站位置作為初始解。

3.2.4 算法過程描述

由初始解Z出發(fā)，計(jì)算對(duì)應(yīng)的目標(biāo)函數(shù)值L。第一次搜索時(shí)，該L值直接作為“best_so_far”，同時(shí)Z進(jìn)入禁忌表，并在接下來的5次搜索中不再考慮。

通過本文設(shè)計(jì)的鄰域構(gòu)造方法構(gòu)造鄰域，再從鄰域中隨機(jī)選定3組解（每組10個(gè)點(diǎn)）作為下一次搜索的候選解，并計(jì)算對(duì)應(yīng)目標(biāo)函數(shù)值L，取其中最小的L值作為本次搜索結(jié)果，同時(shí)與當(dāng)前為止最佳狀態(tài)“best_so_far”對(duì)比，確定是否更新“best_so_far”值，并更新禁忌表項(xiàng)和各表項(xiàng)對(duì)應(yīng)的禁忌步長。

判斷搜索完成條件是否滿足。不滿足，繼續(xù)搜索；滿足，則跳出搜索，記錄“best_so_far”及對(duì)應(yīng)的最優(yōu)解。

3.3 結(jié)果分析

仿真過程中，共搜索60次，小于最大搜索次數(shù)100次，即滿足搜索完成條件二仿真結(jié)束?！癰est_so_far”狀態(tài)保持連續(xù)40次不變且有15次以上最佳狀態(tài)回歸，則認(rèn)可該“best_so_far”狀態(tài)為全局最優(yōu)解，對(duì)應(yīng)所得最優(yōu)設(shè)站方案即為圖5、圖6，分別為當(dāng)前為止最佳狀態(tài)與各次搜索結(jié)果的對(duì)比關(guān)系圖。

圖5 最優(yōu)站址分布情況

圖5 中，“*”點(diǎn)即為當(dāng)前案例的最優(yōu)解。從圖 5可 知， 選 擇 第 1、4、7、10、13、16、21、22、27和第29個(gè)基站時(shí)，為最佳設(shè)站方案。

圖6 局部最優(yōu)與全局最優(yōu)關(guān)系

圖6 中加“.”的RESULT曲線表示每次搜索時(shí)得到的本次搜索目標(biāo)函數(shù)值（局部最優(yōu)），平滑“best_so_far”曲線則表示到當(dāng)前搜索為止目標(biāo)函數(shù)的最小值（全局最優(yōu)）。從圖6可知，當(dāng)搜索到第12次時(shí)，第一次得到目標(biāo)函數(shù)的最小值L，并一直穩(wěn)定在“best_so_far”狀態(tài)，即最優(yōu)解時(shí)的設(shè)站代價(jià)值被認(rèn)定為L=189 277.778 3。此外，從局部最優(yōu)與全局最優(yōu)的關(guān)系可以看出，搜索結(jié)果具有良好的收斂效果。

對(duì)比本文設(shè)計(jì)算法結(jié)果與3.1節(jié)窮舉結(jié)果，有：

驗(yàn)證了算法的可靠性。

4 結(jié) 語

本文設(shè)計(jì)的基于隨機(jī)因子構(gòu)造鄰域的禁忌搜索算法，能有效解決網(wǎng)絡(luò)規(guī)劃過程中的設(shè)站問題。實(shí)驗(yàn)分析顯示，算法能夠有效規(guī)避搜索陷入局部解，得到全局最優(yōu)解。因此，可以通過少量的搜索次數(shù)，得到設(shè)站問題的最優(yōu)解，減少求解此類問題的計(jì)算量。

[1] 周炯槃.通信網(wǎng)理論基礎(chǔ)(修訂版)[M].北京:人民郵電出版社,2009.ZHOU Jiong-pan.Communication Foundation Theoretical Basis(Revised)[M].Beijing:People's Posts and Telecommunications Press,2009.

[2] 任曉華,田寶玉.無線通信中站址規(guī)劃優(yōu)化的研究[EB/OL].(2013-03-21)[2017-11-21].http://www.doc88.com/p-8099994492323.html.REN Xiao-hua,TIAN Bao-yu.Research on Site Optimization Planning in Wireless Communication[EB/OL].(2013-03-21)[2017-11-21].http://www.doc88.com/p-8099994492323.html.

[3] 陳偉.WCDMA基站站址選擇算法的研究[D].上海:上海交通大學(xué),2006.CHEN Wei.Research on the Algorithm of WCDMA Base Station Site Selection[D].Shanghai:Shanghai Jiao Tong University,2006.

[4] 彭超.禁忌搜索求解排課問題的應(yīng)用研究[D].西安:西安電子科技大學(xué),2007.PENG Chao.The Application of Tabu Search in Solving the Problem of Scheduling[D].Xi'an:Xidian University,2007.

[5] 何漢武.數(shù)控等離子切割機(jī)的路徑優(yōu)化[D].上海:上海交通大學(xué),2008.HE Han-wu.Path Optimization of Numerical Control Plasma Cutting Machine[D].Shanghai:Shanghai Jiao Tong University,2008.

[6] Glover F.Future Paths for Integer Programming and Links to Artificial Intelligence[J].Computers and Operations Research,1986,13(05):533-549.

[7] 賀一,劉光遠(yuǎn),基于變異方法的禁忌搜索[J].計(jì)算機(jī)科學(xué),2002,29(05):115-116.HE Yi,LIU Guang-yuan.Tabu Search Based on Mutation Method[J].Computer Science,2002,29(05):115-116.

[8] 袁慶達(dá),閆昱,周再玲.Tabu Search算法在優(yōu)化配送路線問題中的應(yīng)用[J].計(jì)算機(jī)工程,2001(11):86-89.YUAN Qing-da,YAN Yu,ZHOU Zai-ling.Application of Tabu Search Algorithm in Optimizing Distribution Routing Problem[J].Computer Engineering,2001(11):86-89.

[9] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2001.WANG Ling.Intelligent Optimization Algorithm and Its Application[M].Beijing:Tsinghua University Press,2001.

[10] A Multi-dimensional Tabu Search Algorithm for the Optimization of Process Planning[J].Science China(Technological Sciences),2011(12):3211-3219.

[11] Chen C H,Schonfeld P.Work Zone Optimization for Twolane Highway Maintenance Project[J].Transportation Research Record,2004(1877):95-105.