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

關(guān)鍵詞：信道分配；遺傳算法；模擬退火算法；尋優(yōu)式爬山法；大規(guī)?；蛲蛔?/p>

中圖分類號：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 引 言

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

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

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

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

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

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

2 問題建模

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

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

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

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

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

從文獻[3]中我們知道采用最小間隔編碼可以避免CSC違約，縮小頻率搜索空間，從而代價函數(shù)可以變?yōu)椋?/p>

3 算法實現(xiàn)

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

(1) 適應(yīng)度函數(shù)定義

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

(2) 產(chǎn)生初始種群

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

(3) 選擇

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

(4) 交叉算子

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

(5) 變異算子

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

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

從后面的仿真結(jié)果可以看到混合算法的收斂速度較一般遺傳算法有明顯提高，且有很好的穩(wěn)定性，但混合算法極易陷入局部最優(yōu)解。為了進一步提高算法性能我們加入了“尋優(yōu)式爬山”與大規(guī)?；蛲蛔儍煞N優(yōu)化方法對混合算法進行改進。

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

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

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

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

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

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

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

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

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

當(dāng)算法運行很多代，適應(yīng)度仍保持不變時，可能已陷入局部極小值，這時采取突然提高變異率的方法使大量個體進行變異，同時適當(dāng)提高退火溫度，并使用排序選擇法進行選擇操作，使新個體容易存活，幫助種群快速跳出局部極小值，這就是大規(guī)?；蛲蛔兊幕舅枷?。經(jīng)過以上改進的算法被稱作改進混合算法。下面對3種算法進行仿真比較。

4 程序仿真及結(jié)果比較

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

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

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

我們針對6號問題，取G為40 000代，其他參數(shù)保持不變，進行仿真，一般遺傳算法仿真結(jié)束時間為22 209 s，混合算法結(jié)束時間為8 868 s，結(jié)果如圖4所示?？梢钥吹揭话氵z傳算法保持平穩(wěn)收斂，但收斂速度慢，結(jié)束時最小違約數(shù)為12；混合算法收斂速度相對較快，但在13 000代后陷入局部極小值無法跳出，結(jié)束時最小違約數(shù)仍為16。

5 結(jié) 語

改進混合算法通過將遺傳算法與模擬退火算法的優(yōu)[CM(21*2]點結(jié)合，并加入“尋優(yōu)式爬山”與大規(guī)模基因突變兩種改進，既克服了一般遺傳算法收斂速度慢的缺點，又解決了遺傳退火混合算法易于陷入局部最小的問題，從算法效率與穩(wěn)定性兩方面提高了算法的性能。目前該算法已應(yīng)用到我們自己開發(fā)的頻率管理軟件中，并取得很好的效果，對其進行深入的研究，并應(yīng)用于信道分配及管理領(lǐng)域?qū)鸬礁蟮淖饔谩?/p>

參考文獻

［1］張業(yè)榮，竺南直，程勇.蜂窩移動通信網(wǎng)絡(luò)規(guī)劃與優(yōu)化[M].北京:電子工業(yè)出版社，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］王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實現(xiàn)[M].西安:西安交通大學(xué)出版社，2004.

［5］王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社，2004.

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

作者簡介

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

熊 輝 副教授。

魏急波 教授，博士生導(dǎo)師。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>