馮志強(qiáng)，賈振紅，許國(guó)軍

（1.新疆大學(xué) 信息科學(xué)與工程學(xué)院，新疆 烏魯木齊830046；2.中國(guó)移動(dòng)通信集團(tuán)新疆有限公司，新疆烏魯木齊830063）

0 引 言

在蜂窩移動(dòng)通信網(wǎng)絡(luò)中，隨著用戶的急劇增長(zhǎng)，可用的頻率資源變得極為稀少，為了提高頻譜的利用率必須要引入較優(yōu)的頻率分配策略。頻率分配，又稱為信道分配問題 （channel assignment problem），屬于組合優(yōu)化中的 NP（nondeterministic polynomial）完備問題。針對(duì)信道分配問題國(guó)內(nèi)外提出的優(yōu)化算法有：蟻群算法、神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、遺傳算法和進(jìn)化策略等［1－7］，這些優(yōu)化算法已經(jīng)被證明可以用來解決信道分配問題，但這些算法在搜索最優(yōu)解的過程中，依然存在算法復(fù)雜、收斂率較低、容易陷入局部最優(yōu)解等缺點(diǎn)。粒子群算法是新興的群智能算法，參數(shù)簡(jiǎn)單和收斂迅速使其得到了廣泛的關(guān)注和應(yīng)用。粒子群算法極易早熟，如何增加算法的全局搜索能力，已經(jīng)成為研究的熱點(diǎn)。針對(duì)上述問題，本文提出了一種改進(jìn)的離散粒子群優(yōu)化算法 （IDPSO）。該算法根據(jù)文化算法的思想設(shè)計(jì)了最優(yōu)漸進(jìn)式變異算子，使一個(gè)最優(yōu)粒子向著全局最優(yōu)解變異，其它最優(yōu)粒子進(jìn)行隨機(jī)變異，增加了粒子的多樣性，提高了算法的收斂率。又因采用了最小間距編碼，壓縮了求解空間，使得算法的收斂速度得到提高。

1 信道分配問題模型

在蜂窩小區(qū)制中，CAP要考慮的電磁兼容 （EMC）限制有：①同信道約束 （CCC）；②鄰信道約束 （ACC）；③同小區(qū)約束 （CSC）［8］。數(shù)學(xué)上建立的信道分配問題模型詳見文獻(xiàn) ［8］，代價(jià)函數(shù)為

其中F是一個(gè)n×m的矩陣，表示一種信道分配方案，若f（i，a）＝1，表示信道a分配給小區(qū)i，若f （i，a）＝0，表示信道a未分配給任何小區(qū)。當(dāng)所有的限制都滿足時(shí)，代價(jià)函數(shù)C（F）＝0，表示找到了一種最優(yōu)的分配方案。CAP問題的目的就是找到一個(gè)解F使得C （P）＝0。

2 離散粒子群算法

粒子群優(yōu)化算法是一種新興的智能優(yōu)化算法，算法結(jié)構(gòu)簡(jiǎn)單，求解速度快。離散粒子群算法在粒子群算法的基礎(chǔ)上被提出，用來解決工程中的離散問題。離散粒子群算法根據(jù)如下公式更新粒子的速度和位置［9］

其中c1、c2和c3是取值在0到1之間的常數(shù)，vi（t）表示t時(shí)刻粒子i的速度，xi（t）表示t時(shí)刻粒子i的位置，pi（t）表示t時(shí)刻粒子i的局部最優(yōu)位置，pg（t）表示t時(shí)刻粒子i的全局最優(yōu)位置。

3 改進(jìn)的離散粒子群算法

3.1 個(gè)體編碼

本文采用了文獻(xiàn) ［10］的最小間距編碼方案，編碼前的二進(jìn)制串長(zhǎng)度n，編碼后二進(jìn)制串的長(zhǎng)度是：n－ （d－1）（dmin－1）。n表示可用的信道數(shù)，d表示小區(qū)的信道需求，dmin表示同小區(qū)的最小信道間隔。對(duì)于固定的信道數(shù)，小區(qū)需求d越大，編碼后的長(zhǎng)度越小，解空間的壓縮比越大。編碼后的粒子滿足CSC約束條件，代價(jià)函數(shù)可以簡(jiǎn)化為［10］

在工程實(shí)際應(yīng)用中，在滿足用戶需求的情況下，必須使已用頻點(diǎn)數(shù)越小越好。為了求得最小頻點(diǎn)數(shù)，采用如下代價(jià)函數(shù)

其中α和 （是取值介于0和1之間的系數(shù)，M表示當(dāng)前分配方案中所需的頻點(diǎn)數(shù)。當(dāng)O （F）求得最小值時(shí)，C （F）和M也必然求得最小值。

3.2 粒子的位置和速度

粒子的位置P表示為分配給一個(gè)小區(qū)的頻率組成的m維向量，m表示小區(qū)的頻率需求。P的第i維表示小區(qū)的第i個(gè)需求所分配的頻率號(hào)，其公式表示如下

其中ci∈ ｛1，2，3，…，C｝，C表示最大的頻率數(shù)目，m表示小區(qū)的頻率需求。

本文使用交換算子 （i，j）表示小區(qū)的當(dāng)前信道i和即將要切換到的信道j，m個(gè)交換算子就構(gòu)成了粒子的速度

如果令V1＝ （i1，i2，i3，…，im），V2＝ （j1，j2，j3，…，jm），V1就是粒子的當(dāng)前位置，V2就是粒子要移動(dòng)到的目的位置。粒子的位置減法運(yùn)算公式［9］變?yōu)椋篤＝V1ΘV2，V1＝P1，V2＝P2。因此，可以由粒子位置P1和P2直接得到粒子的速度。P1和P2中可能存在相同的信道，直接由P1和P2得到的速度交換算子，使粒子在移動(dòng)后可能就不再滿足小區(qū)的信道需求了。因此，將得到的V2限定如下

這樣就由粒子位置P1和P2形成了粒子速度V，粒子按速度V移動(dòng)后仍滿足小區(qū)的頻點(diǎn)需求。式 （3）和式 （4）中的其他運(yùn)算規(guī)則詳見文獻(xiàn) ［9］。

3.3 最優(yōu)漸進(jìn)式變異算子

在粒子的位置更新過程中，隨著粒子向最優(yōu)粒子的靠攏，會(huì)出現(xiàn)多個(gè)最優(yōu)粒子，從而降低了粒子的多樣性，使算法陷入局部最優(yōu)解而無法獲得全局最優(yōu)解。為了提高算法的局部搜索能力，保證算法的收斂速度和收斂率，本文設(shè)計(jì)了最優(yōu)漸進(jìn)式變異算子：①統(tǒng)計(jì)當(dāng)前粒子群中的最優(yōu)粒子個(gè)數(shù)，并從最優(yōu)粒子中隨機(jī)選擇一個(gè)做為全局最優(yōu)粒子。②對(duì)這個(gè)全局最優(yōu)粒子，將小區(qū)i的第n個(gè)已分配信道隨機(jī)替換為未分配的信道 （i表示小區(qū)號(hào)，n表示小區(qū)i中的第n個(gè)需求）。③計(jì)算已替換后粒子的適應(yīng)度，如果該適應(yīng)度優(yōu)于替換前粒子的適應(yīng)度，則用變異后的粒子替代之前的粒子，否則，恢復(fù)已變異的元素。④反復(fù)執(zhí)行②和③直到所有小區(qū)的所有信道需求元素都經(jīng)過替換。⑤當(dāng)所有的需求信道都替換后仍無較優(yōu)粒子出現(xiàn)，則保留這個(gè)最優(yōu)粒子，對(duì)剩下的最優(yōu)粒子進(jìn)行隨機(jī)變異。這種變異方式使最優(yōu)粒子總是朝著問題的最優(yōu)解方向變異，防止了退化的出現(xiàn)，減少了最優(yōu)粒子的個(gè)數(shù)，提高了粒子的多樣性，使粒子跳出局部最優(yōu)值，增強(qiáng)了算法的全局搜索能力。最優(yōu)漸進(jìn)式變異算子可以表示為

式中：F——最優(yōu)漸進(jìn)式變異操作，fi——粒子i的適應(yīng)度，fb——最優(yōu)粒子的適應(yīng)度。粒子按式 （3）更新位置后，按式 （10）更新位置。最優(yōu)漸進(jìn)式變異算子是以增加算法的運(yùn)算時(shí)間來提高進(jìn)化過程中的種群多樣性的，從而使算法的收斂率得到提高。

3.4 變異概率的確定

粒子位置的不同而表現(xiàn)出的多樣性稱為種群多樣性，它是評(píng)價(jià)粒子群搜索可能解的重要尺度［11］。當(dāng)粒子的多樣性降低時(shí)，粒子開始出現(xiàn)聚集現(xiàn)象。只有粒子出現(xiàn)聚集的時(shí)候才需要對(duì)粒子進(jìn)行變異，而且每個(gè)粒子的變異概率應(yīng)該是不一樣的。本文引入文獻(xiàn) ［11］中的方法來判斷粒子的聚集程度。定義

式中：fi——第i個(gè)粒子的適應(yīng)度，favg——全體粒子的平均適應(yīng)度。從式 （11）可以看出：α2反映了粒子的聚集程度，其值越小，說明粒子的聚集程度越高，可以將這個(gè)值作為變異發(fā)生的條件。當(dāng)α2＝0時(shí)算法要么陷入局部最優(yōu)，要么已經(jīng)找到全局最優(yōu)。

為了保證進(jìn)化的平穩(wěn)性，在粒子沒有聚集或聚集較小的時(shí)候，應(yīng)以較小的概率對(duì)粒子進(jìn)行變異甚至不變異，而粒子聚集比較嚴(yán)重時(shí)，應(yīng)該以較大的概率對(duì)粒子進(jìn)行變異。因此，在迭代的過程中，變異概率應(yīng)該是動(dòng)態(tài)變化的，不同粒子的變異概率也是不同的。本文修改正態(tài)分布函數(shù)為變異概率公式

當(dāng)個(gè)體適應(yīng)度接近平均適應(yīng)度時(shí)取得較大的變異概率，相反，變異概率會(huì)很小。變異概率在0和1之間，只有當(dāng)粒子聚集嚴(yán)重時(shí)才會(huì)以概率1進(jìn)行變異。綜上，當(dāng)α2＜C時(shí)，按照式 （12）的變異概率執(zhí)行最優(yōu)漸進(jìn)式變異算子。

3.5 算法復(fù)雜度分析

粒子群算法的時(shí)間復(fù)雜度主要依賴于迭代次數(shù)t、粒子維數(shù)m和粒子的適應(yīng)度計(jì)算，這里認(rèn)為粒子數(shù)是一個(gè)常數(shù)。在本文中一個(gè)m×n的二維矩陣代表了一個(gè)粒子，則適應(yīng)度函數(shù)執(zhí)行一次的時(shí)間復(fù)雜度是O （m2×n），在求解的過程中的時(shí)間復(fù)雜度是O （m2×n×t）。本文引入了最優(yōu)漸進(jìn)式變異算子，根據(jù)上文表述可知其時(shí)間復(fù)雜度是O （m2×n×p），其中p是最優(yōu)粒子的個(gè)數(shù)，在每次迭代中，最優(yōu)粒子數(shù)目都是在變化的，則在求解過程中的時(shí)間復(fù)雜度是O（m2×n×p×t）。綜上，本文算法的時(shí)間復(fù)雜度是O （m2×n×p×t）。

3.6 粒子位置初始化

實(shí)踐表明：根據(jù)先驗(yàn)知識(shí)對(duì)粒子位置進(jìn)行初始化，能夠生成適應(yīng)度較高的初始粒子群，能夠提高算法的收斂速度和收斂率。本文根據(jù)最大需求最小沖突的思想，對(duì)文獻(xiàn)［11］的初始化方法進(jìn)行了簡(jiǎn)化：對(duì)一個(gè)小區(qū)，在可用的頻率中找到一個(gè)不與其它小區(qū)沖突的頻率，從這個(gè)頻率開始按照頻率號(hào)遞增和遞減交替形成頻率分配表，再按照小區(qū)的需求進(jìn)行分配。此方法可有效的提高初始種群的質(zhì)量，和其它初始化方法相比，此方法更易實(shí)現(xiàn)。

3.7 本文算法步驟

（1）設(shè)置算法的參數(shù)，設(shè)置粒子數(shù)目、最大迭代次數(shù)、以及c1，c2，c3的初始值，根據(jù)本文的方法初始化粒子的位置。

（2）根據(jù)式 （5）或式 （6）計(jì)算粒子的適應(yīng)度，更新粒子的局部最優(yōu)值和全局最優(yōu)值。

（3）根據(jù)式 （11）判斷當(dāng)前粒子是否出現(xiàn)聚集，若出現(xiàn)聚集按式 （12）的變異概率對(duì)最優(yōu)粒子執(zhí)行最優(yōu)漸進(jìn)式變異；若未出現(xiàn)聚集執(zhí)行步驟 （4）。

（4）根據(jù)式 （3）形成粒子的新速度。

（5）根據(jù)式 （4）得到粒子的新位置。

（6）終止條件判斷，若已尋找到最優(yōu)個(gè)體或者達(dá)到最大迭代次數(shù)，則算法結(jié)束，否則執(zhí)行步驟 （2）。

4 仿 真

本文算法采用MATLAB語言編寫，21小區(qū)問題的兼容矩陣和需求向量見文獻(xiàn) ［5］。本文先設(shè)置最大迭代次數(shù)為500，粒子個(gè)數(shù)為50，c1＝0.9，c2＝0.5，c2＝0.7，α＝0.6，β＝0.4，C＝25，粒子的適應(yīng)度評(píng)價(jià)函數(shù)是式 （6），進(jìn)行迭代計(jì)算尋找到最小的可用頻點(diǎn)數(shù)。尋找到最小可用頻點(diǎn)數(shù)后，粒子的適應(yīng)度評(píng)價(jià)函數(shù)是式 （5），按照頻點(diǎn)數(shù)為80、70、52、51、45、42、40進(jìn)行了100次實(shí)驗(yàn)，其他參數(shù)不變。

圖1給出了以式 （6）為個(gè)體的適應(yīng)度評(píng)價(jià)函數(shù)的仿真圖，從圖中可見：當(dāng)?shù)M(jìn)行到第11代時(shí)C（P）為0，即出現(xiàn)了滿足EMC需求的頻率分配方案，此時(shí)需要的頻點(diǎn)數(shù)為57。隨著迭代的繼續(xù)進(jìn)行，系統(tǒng)所需的最小頻點(diǎn)數(shù)仍然在降低，最終收斂于42。因此，系統(tǒng)所需要的最小頻數(shù)應(yīng)該在42左右。

圖1 尋找最小可用頻點(diǎn)數(shù)的進(jìn)化曲線

圖2給出了可用頻點(diǎn)數(shù)為51的仿真圖，采用DPSO算法時(shí)，經(jīng)過13次迭代，歷時(shí)4.3秒求得一個(gè)最優(yōu)解。采用本文算法時(shí)，經(jīng)過6次迭代，歷時(shí)3.9秒求得一個(gè)最優(yōu)解。本文采用的最優(yōu)漸進(jìn)式變異算子增加了算法每次迭代的時(shí)間，但是減少了算法的迭代次數(shù)。綜合來說本文算法耗時(shí)略小于DPSO算法。由圖2可見，在2秒之前，DPSO算法和本文算法均未收斂，這是由于本文采用的粒子位置初始化方法增加了粒子初始化時(shí)的時(shí)間。

由表1可見，在頻點(diǎn)數(shù)為40時(shí)，本文算法仍能達(dá)到100%的收斂，即由本文算法求得的最小頻點(diǎn)數(shù)為40，遠(yuǎn)遠(yuǎn)優(yōu)于文獻(xiàn) ［12］中求得的51個(gè)頻點(diǎn)。表1中，采用DPSO算法時(shí)，隨著可用頻點(diǎn)數(shù)的降低，算法的收斂率在逐漸降低，而算法的平均收斂代數(shù)并沒有明顯的變差，和其它算法相比，粒子群算法能夠迅速收斂。當(dāng)頻點(diǎn)數(shù)為51時(shí)，文獻(xiàn) ［12］的平均收斂代數(shù)為54.5，DPSO算法的平均收斂代數(shù)為10.2，而本文算法的平均收斂代數(shù)為僅為5.5。采用了本文的IDPSO算法后，收斂率得到了顯著的提升，收斂代數(shù)也略有提高。本文中參數(shù)C需要合理的設(shè)置，C設(shè)置的過大在每一代進(jìn)化中都要對(duì)最優(yōu)個(gè)體進(jìn)行變異操作，必然會(huì)增加算法的運(yùn)算時(shí)間，C設(shè)置的過小就不能使粒子跳出局部最優(yōu)值。

圖2 可用頻點(diǎn)數(shù)為51的仿真

表1 算法仿真結(jié)果比較

5 結(jié)束語

本文對(duì)離散粒子群算法做了改進(jìn)，在每代最優(yōu)粒子中引入最優(yōu)漸進(jìn)式變異算子，增加了粒子的多樣性，提高了算法的抗早熟能力。采用了最小間距編碼，壓縮了求解空間，加快了算法收斂。將改進(jìn)的離散粒子群算法用于頻率分配問題上，仿真結(jié)果表明此算法能夠較好的解決該問題，在收斂率和收斂速度上優(yōu)于離散粒子群算法和混洗蛙跳算法。

文中參數(shù)C需要合理的設(shè)置，C設(shè)置過大會(huì)增加算法的運(yùn)行時(shí)間，C設(shè)置的過小會(huì)降低算法的抗早熟能力。簡(jiǎn)單合理的設(shè)置參數(shù)C是一項(xiàng)值得進(jìn)一步研究的問題。

［1］ZHANG Chunfang，CHEN Juan.Solving frequency assignment problem using an adaptive multi colony ant algorithm ［J］.Mini－Micro Systems，2006，27 （5）：837－741 （in Chinese）.［章春芳，陳娟.求解頻率分配問題的自適應(yīng)的多種群蟻群算法 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2006，27 （5）：837－741.］

［2］ZHU Xiaojin，CHEN Yanchun，SHAO Yong，et al.Stepped annealing chaotic neural network model for the channel assignment problem ［J］.Journal on Communications，2008，29（5）：122－127 （in Chinese）. ［朱曉錦，陳艷春，邵勇，等.面向信道分配的分段退火混沌神經(jīng)網(wǎng)絡(luò)模型 ［J］.通信學(xué)報(bào)，2008，29 （5）：122－127.］

［3］SAN Joserevuelta L M.A new adaptive genetic algorithm for fixed channel assignment ［J］.Information Sciences，2007（177）：2655－2678.

［4］KIM Visale，LIU Wei，CHEN Xiaohui，et al.Distributed constraint satisfaction of an improved channel assignment approach in cellular network ［J］.Computer Science，2012，39（6）：81－83 （in Chinese）. ［韋沙，劉威，陳小惠，等.蜂窩網(wǎng)中基于分布式約束滿足算法的改進(jìn)信道分配 ［J］.計(jì)算機(jī)科學(xué)，2012，39 （6）：81－83.］

［5］XU Junjie，XIN Zhanhong.A frequency assignment approach based on microcanonical annealing algorithm ［J］.Journal of Beijing University of Posts and Telecommunications，2007，30 （2）：67－70（in Chinese）.［徐俊杰，忻展紅.基于微正則退火的頻率分配方法 ［J］.北京郵電大學(xué)學(xué)報(bào)，2007，30 （2）：67－70.］

［6］YU Shicai，WEI Xingang.Channel assignment strategy combining guard channel with queuing ［J］.Computer Engineering and Applications，2012，48 （1）：112－113 （in Chinese）. ［於時(shí)才，魏鑫剛.保護(hù)信道和排隊(duì)相結(jié)合的信道分配策略 ［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48 （1）：112－113.］

［7］JIANG Fu，PENG Jun.Dynamic channel assignment based on swarm intelligence in emergency communication ［J］.Application Research of Computers，2012，29 （6）：2293－2296 （in Chinese）.［蔣富，彭軍.應(yīng)急通信系統(tǒng)中基于集群智能的動(dòng)態(tài) 信 道 分 配 ［J］. 計(jì) 算 機(jī) 應(yīng) 用 研 究，2012，29 （6）：2293－2296.］

［8］Benameur L，Alami J，El Imrani A.A new discrete particle swarm model for the frequency assignment problem ［C］／／IEEE International Conference on Computer Systems and Applications，2009：139－144.

［9］GAO Guang’en，LIU Quanli，WANG Wei.Multi－channel assignment algorithm of industrial wireless networks based on discrete particle swarming optimization ［J］.Control and Decision，2012，27 （5）：697－702 （in Chinese）. ［高廣恩，劉全利，王偉.基于離散粒子群優(yōu)化的工業(yè)無線網(wǎng)多信道分配算法 ［J］.控制與決策，2012，27 （5）：697－702.］

［10］ZHONG Xiangyuan，JIN Min，ZHONG Xiangqian，et al.Channel assignment in cellular network based on self－adaptive genetic algorithm ［J］.Computer Enginee－ring，2010，36（17）：189－191 （in Chinese）.［仲向遠(yuǎn)，金敏，仲向前，等.基于自適應(yīng)遺傳算法的蜂窩網(wǎng)絡(luò)信道分配 ［J］.計(jì)算機(jī)工程，2010，36 （17）：189－191.］

［11］LIU Hongbo，WANG Xiukun，TAN Guozhen.Convergence analysis of particle swarm optimization and its improved algorithm based on chaos ［J］.Control and Decision，2006，21（6）：636－640 （in Chinese）.［劉洪波，王秀坤，譚國(guó)真.粒子群優(yōu)化算法的收斂性分析及其混沌改進(jìn)算法 ［J］.控制與決策，2006，21 （6）：636－640.］

［12］HE Di，JIA Zhenhong.Frequency allocation approach based on shuffled frog－leaping algorithm ［J］.Computer Engineering，2011，37 （21）：133－135 （in Chinese）. ［何迪，賈振紅.基于混洗蛙跳算法的頻率分配方法 ［J］.計(jì)算機(jī)工程，2011，37 （21）：133－135.］