基于改進(jìn)混合遺傳算法的信道分配研究

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

關(guān)鍵詞：信道分配；遺傳算法；模擬退火算法；尋優(yōu)式爬山法；大規(guī)模基因突變

中圖分類號(hào)：TN914 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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 引 言

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

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

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

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

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

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

2 問(wèn)題建模

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

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

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

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

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

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

3 算法實(shí)現(xiàn)

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

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

針對(duì)此信道分配問(wèn)題，適應(yīng)度函數(shù)與代價(jià)函數(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)生最基本也是最常用的方法是隨機(jī)生成法，用這種方法生成初始種群簡(jiǎn)單快捷但平均適應(yīng)度與最佳個(gè)體適應(yīng)度都較差，需要較長(zhǎng)時(shí)間與較多代數(shù)完成收斂。為了解決這個(gè)問(wèn)題，在保證搜索空間完備性的基礎(chǔ)上產(chǎn)生高適應(yīng)度的初始群體，我們?cè)O(shè)計(jì)一種“尋優(yōu)式爬山”算法。尋優(yōu)式爬山算法的具體實(shí)現(xiàn)過(guò)程將在下面的章節(jié)中進(jìn)行介紹。

(3) 選擇

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

(4) 交叉算子

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

(5) 變異算子

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

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

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

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

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

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

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

(4) 對(duì)新個(gè)體進(jìn)行適應(yīng)度估計(jì)；

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

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

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

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

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

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

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

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

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

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

5 結(jié) 語(yǔ)

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

參考文獻(xiàn)

［1］張業(yè)榮，竺南直，程勇.蜂窩移動(dòng)通信網(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)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社，2004.

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

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

作者簡(jiǎn)介

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

熊 輝 副教授。

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。”