基于改進混合遺傳算法的信道分配研究

摘 要：用遺傳與模擬退火相結合的混合算法對信道分配問題進行研究，并通過加入“尋優式爬山”與大規模基因突變兩種優化方法對混合算法進行改進，克服了一般遺傳算法收斂速度慢以及易于陷入局部最優解的缺點。給出了算法的實現流程，并針對幾個典型信道分配問題對一般遺傳算法、遺傳與退火混合算法、改進后的混合算法進行仿真。仿真結果證明改進算法較其他2種算法至少節省80%的時間，并具有更好的穩定性，是解決信道分配問題的一種很好的算法。

關鍵詞：信道分配；遺傳算法；模擬退火算法；尋優式爬山法；大規模基因突變

中圖分類號：TN914 文獻標識碼：A

文章編號：1004373X(2008)0505704

Study on Channel Assignment Problem with Hybrid Genetic Algorithm

MENG Xianglong，XIONG Hui，WEI Jibo

(School of Electronic Science and Engineering，National University of Defense Technology，Changsha，410073，China)

Abstract：In this paper，an improved hybrid genetic algorithm based on genetic and simulated annealing is presented.Two strategies，optimizing hill-climbing and large-scale gene mutation，are used to overcome the disadvantages of the primary hybrid algorithm，which easily converg to local optima.We give the details of the algorithm and simulate several benchmark channel-assignment problems using the three algorithms.The result shows that the new approach saves at least 80% of the time and is more stable.It is a good method for solving the channel-assignment problem.

Keywords：channel assignment;genetic algorithm;simulated annealing algorithm;optimizing hill-climbing;large scale gene mutation

1 引 言

隨著移動通信的迅速發展，飛速增長的用戶數量與有限的頻率資源這二者之間的矛盾越來越突出，提高現有資源利用率已成為移動通信領域關注的重要課題。所謂“信道分配”，也稱頻率分配，即在采用信道利用技術的蜂窩移動通信系統中，在多信道共用的情況下，使通信過程中的相互干擾減到最小，以最有效的頻譜利用方式，為每個小區的移動通信設備提供盡可能多的可用信道^[1]。

在本文中我們針對蜂窩網絡中的固定信道分配進行研究，考慮移動通信中主要的幾種干擾對信道分配附加一些約束條件：

(1) 同頻約束(cochannel constraint，CCC)：兩小區除非在距離上足夠遠，否則不能分配相同的頻率；

(2) 鄰頻約束(adjacent channel constraint，ACC)：當相鄰小區使用相近頻率時，仍然存在干擾的可能性；

(3) 同小區頻率間隔約束(cosite constraint，CSC)：分配給同一小區的頻率之間應有一定的間隔，比如250 kHz或5個頻點的間隔。

目前已有多種算法被應用到信道分配中，早期主要是用著色算法進行信道分配，近些年用神經網絡算法，模擬退火算法和遺傳算法也被廣泛應用到信道分配中。本文用一種改進的混合遺傳算法對信道分配問題進行研究。常規的遺傳算法存在搜索空間太大，收斂速度慢以及易于陷入局部最優解的缺點，針對這些缺點通過模擬退火與遺傳算法的結合引入父代與子代之間的競爭，既加快了算法的收斂速度又能適當避免算法陷入局部最優解。同時加入了“尋優式爬山”與大規模基因突變兩種優化方法，前者在加快算法收斂速度方面具有明顯的效果，而后者則可以很好地防止算法陷入局部最優解情況的發生。

2 問題建模

為了在數學上構建信道分配問題的模型，引入兼容矩陣[WTHX]C[WTBX]與需求向量D的概念^[2]：對于擁有n個小區的蜂窩網絡，我們用n×n的對稱矩陣[WTHX]C[WTBX]來描述小區之間的頻率兼容性，矩陣[WTHX]C[WTBX]中非對角線上的元素cij表示分配給小區i與小區j之間的頻率的最小間隔，代表小區之間同頻與鄰頻限制。對角線上的元素cii表示分配給小區i的任意兩個頻率之間的最小間隔，代表同小區的頻率間隔限制。用n×1的向量來描述小區的頻率需求關系，n為蜂窩系統中小區的總數，D中的元素di(1≤i≤n)表示第i個小區所需的頻率數。兼容矩陣用數學表達式描述如下：

式中fik是分配給第i個小區的第k個頻點，文中的頻率用正整數表示。

問題編碼：根據問題中分配給小區的頻率為固定范圍正整數的特點，在本文中采用整數編碼與最小間隔編碼^[3]兩種編碼方法。整數編碼用n×dmax大小矩陣表示個體，其中dmax為需求向量D中最大值，fij=y(1≤y≤p，1≤j≤di)表示頻點y分配給第i個小區，fij=0(di＜j≤dmax)。一般情況下，dmax遠小于p，所以這種編碼方式可以節省大量空間且易于理解。最小間隔編碼的詳細內容請參考文獻[3]。采用兩種編碼的個體始終保持對應關系，并滿足分配給第i個小區的頻點個數p等于di。下面對信道分配問題中的限制條件進行描述與建模分析。

如果頻率p已分配給小區i，則與p之間的距離小于cii的頻率q不能分配給小區i，否則將產生CSC，用數學表達式描述如下：

從公式可以看出，違背約束的頻點越少則代價函數越小，當所有分配的頻點都滿足約束條件時，代價函數取到最小值為零。因此我們要做的就是找到一種分配方案F使C(F)達到一定的標準，如果要求違約數為零則要找到一種分配方案使C(F)=0。

從文獻[3]中我們知道采用最小間隔編碼可以避免CSC違約，縮小頻率搜索空間，從而代價函數可以變為：

3 算法實現

一般遺傳算法主要包含初始化、選擇、交叉、變異等算子，下面對適應度函數與各遺傳算子進行設計。

(1) 適應度函數定義

針對此信道分配問題，適應度函數與代價函數密切相關，一般可取f(F)=1/C(F)作為分配方案F的適應度。在本文中采用f(F)=1/C(F)g作為分配方案F適應度函數，其中g為跟代數相關的變量。

(2) 產生初始種群

遺傳算法初始種群的產生最基本也是最常用的方法是隨機生成法，用這種方法生成初始種群簡單快捷但平均適應度與最佳個體適應度都較差，需要較長時間與較多代數完成收斂。為了解決這個問題，在保證搜索空間完備性的基礎上產生高適應度的初始群體，我們設計一種“尋優式爬山”算法。尋優式爬山算法的具體實現過程將在下面的章節中進行介紹。

(3) 選擇

在本文中我們采用常用的輪盤賭選擇法，其基本原理是根據個體適應度大小進行選擇，適應度大的個體被選中的概率大，反之則小，輪盤賭的詳細實現方法可參見文獻[4]。為了防止在選擇以及其后的交叉、變異過程中最佳個體意外丟失，我們在每代遺傳操作前將最佳個體保留，操作結束后將其直接復制，替換子代種群中的最差個體。另外，為了防止優秀個體迅速繁殖，陷入局部最優解，在選擇時要控制最優個體的數量。

(4) 交叉算子

交叉操作在最小間隔編碼的種群中執行，為了保證在交叉的過程中，分配給第i個小區的頻點個數始終等于di，我們采用文獻[3]中的固定交叉算子。在本文中采用一種全新的交叉思想：個體交叉與小區交叉相結合。其基本方法如下：對個體進行交叉部分(將進行交叉的小區)選取，選取過程采用單點與兩點相結合的選取方法，具體過程為生成兩個隨機點a，b(1≤a＜b≤n)，隨機選擇進行交叉的小區為1-a，a-b或b-n，小區選好后，對所有選中的小區進行交叉處理。對具體小區i的交叉方法為生成一個隨機點z，以50%的概率進行前向交叉(從小區第一個元素到點z)或后向交叉(從點z到小區最后一個元素)。此種交叉方法的優點在于可以對個體的所有元素進行幾乎等概率的交叉處理，使交叉操作覆蓋全部處理空間。

(5) 變異算子

交叉算子只是對原有的基因進行重組來產生新的個體，通過交叉并不能產生初始種群以外的基因，而必須靠變異算子來生成新的基因，使遺傳算法能夠在整個解空間上進行全局搜索。在本文中基本的變異方式采用文獻[3]中的對應變異。在此種變異方式的基礎上，我們采用個體變異與小區變異相結合的變異思想。

通過以上算子的實現與組合即可完成一般遺傳算法，但一般遺傳算法存在收斂速度慢的缺點。通過將模擬退火算法與遺傳算法結合可以適當克服遺傳算法的缺點，具體的結合方法為在交叉與變異操作完成之后，由退火算法來決定是否用新產生的個體來代替父代個體。設父代個體的適應度為f1，子代個體的適應度為f2，則適應度改變量Δf=f2–f1如果滿足exp{Δf/T}>rand(1)，則用新個體代替父代個體，否則保持父代個體不變，這樣引入了父代與子代的競爭，有利于加快算法的收斂速度。從判斷條件exp{Δf /T}>rand(1)?可以看出，當新個體適應度大于父個體時，新個體必然被保留，而當新個體適應度小于父個體時仍以一定的概率被保留，這樣可以適當避免種群迅速陷入局部極小值。關于退火算法的知識可參考文獻[5]。

從后面的仿真結果可以看到混合算法的收斂速度較一般遺傳算法有明顯提高，且有很好的穩定性，但混合算法極易陷入局部最優解。為了進一步提高算法性能我們加入了“尋優式爬山”與大規模基因突變兩種優化方法對混合算法進行改進。

尋優式爬山的基本思想很簡單，就是找到一種分配方案中所有不滿足條件的小區及小區中違背約束條件的頻點，用可用的頻點來代替違約頻點，形成新分配方案。如果新分配方案適應度優于原分配方案，則保留，否則放棄。繼續替換過程，直到所有的違約頻點替換結束或無可用頻點，則搜索過程結束。該過程可以描述如下:

(1) 找到一種分配方案中所有不滿足條件的小區(設個數為r)；

(2) 找出第i個小區中違背約束條件的頻點和可以選擇的頻點(1≤i≤r)；

(3) 隨機選擇違約頻點a、可用頻點b，將a用b代替；

(4) 對新個體進行適應度估計；

(5) 如果新生成個體適應度大于原個體，保留新個體，更新違約頻點與可用頻點；

(6) 如果小區中違約頻點與可以選擇的頻點都不為零，重復步驟(3)~(5)；

(7) 取下一個不滿足條件的小區，重復步驟(2)~(6)。

基于以上原理我們進行初始種群生成，首先用隨機生成方式產生適當規模的種群P0，然后對P0中所有的個體進行尋優式爬山處理，生成初始種群P。用這種方法生成的初始種群不僅滿足上述的要求，且具有廣泛的適用性。尋優式爬山算法在程序中的另一處應用為當遺傳操作連續運行一定代數Ng(根據具體情況選取)，仍未找到更高適應度的個體時，選取部分個體進行“尋優式爬山”搜索。但要注意Ng值不可以太小，否則容易造成過早收斂到局部極小值，不利于遺傳算法搜索空間的展開，并且由于尋優式爬山算法需要較長時間，造成程序時間開銷過大。

當算法運行很多代，適應度仍保持不變時，可能已陷入局部極小值，這時采取突然提高變異率的方法使大量個體進行變異，同時適當提高退火溫度，并使用排序選擇法進行選擇操作，使新個體容易存活，幫助種群快速跳出局部極小值，這就是大規模基因突變的基本思想。經過以上改進的算法被稱作改進混合算法。下面對3種算法進行仿真比較。

4 程序仿真及結果比較

我們選取文獻[2]中有代表性的2，3，6三個問題對三種算法分別進行50代仿真，仿真參數如表1所示。表中G為程序運行的最大代數，N為種群大小，pc為交叉概率，pm為個體變異概率，pe為小區中元素的變異概率，K為觸發“尋優式爬山”的計數器，T0為退火初始溫度，k為退火系數，Te為終止溫度，σ為初始種群中個體違約數的標準差。仿真結果見表2。仿真結束后，取每種算法的最佳收斂結果進行繪圖比較，見圖1~圖3。

從圖中可以看出，一般遺傳算法的收斂速度最慢，收斂過程相對平穩，算法運行到最大代數時未完成收斂；混合遺傳算法收斂速度快一些，但仍未完成收斂，這主要是由于常規退火方式后期的溫度降到比較低，新產生的個體不易存活，所以算法很容易陷入局部極小值無法跳出。優化后的混合遺傳算法收斂速度最快，且具有很好的穩定性，除問題6有一次陷入局部最優解，其余全部收斂。

由新初始化方式生成的初始種群的適應度明顯提高，平均違約數只有一般初始化生成種群的25%~45%，這大大減小了算法的搜索空間，加快了算法的收斂速度。從表2可以看出，改進混合算法平均每代的運行時間大于前兩種算法，這主要是由于執行“尋優式爬山”需要較長時間，但從完成收斂總體時間上看，改進算法較其他兩種算法至少節省80%的時間。

我們針對6號問題，取G為40 000代，其他參數保持不變，進行仿真，一般遺傳算法仿真結束時間為22 209 s，混合算法結束時間為8 868 s，結果如圖4所示。可以看到一般遺傳算法保持平穩收斂，但收斂速度慢，結束時最小違約數為12；混合算法收斂速度相對較快，但在13 000代后陷入局部極小值無法跳出，結束時最小違約數仍為16。

5 結 語

改進混合算法通過將遺傳算法與模擬退火算法的優[CM(21*2]點結合，并加入“尋優式爬山”與大規模基因突變兩種改進，既克服了一般遺傳算法收斂速度慢的缺點，又解決了遺傳退火混合算法易于陷入局部最小的問題，從算法效率與穩定性兩方面提高了算法的性能。目前該算法已應用到我們自己開發的頻率管理軟件中，并取得很好的效果，對其進行深入的研究，并應用于信道分配及管理領域將會起到更大的作用。

參考文獻

［1］張業榮，竺南直，程勇.蜂窩移動通信網絡規劃與優化[M].北京:電子工業出版社，2003.

［2］Funabikin，Takefuji.A Neural Network Parallel Algorithm for Channel Assignment Problems in Cellular Radio Networks[J].IEEE Transactions on Vehicular Technology，1992，41(4):430-437.

［3］Chiu Y，NGO，Victor Li O K.Fixed Channel Assignment in Cellular Radio Networks Using a Modified Genetic Algorithm[J].IEEE Transactions on Vehicular Technology，1998 47(1):163-172.

［4］王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安:西安交通大學出版社，2004.

［5］王凌.智能優化算法及其應用[M].北京:清華大學出版社，2004.

［6］楊樂，薛謙.最優子種群實數編碼的遺傳算法[J].現代電子技術，2007，30(15):119-121.

作者簡介

孟祥龍 男，1983年出生，國防科技大學碩士研究生。主要從事頻率分配與優化算法方面研究。

熊 輝 副教授。

魏急波 教授，博士生導師。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”