楊化斌，林中，孫俊

空軍工程大學(xué)電訊工程學(xué)院，西安 710077

頻率指配問題求解的模式分析核方法

楊化斌，林中，孫俊

空軍工程大學(xué)電訊工程學(xué)院，西安 710077

1 引言

頻率指配是無線電網(wǎng)絡(luò)應(yīng)用中一個典型的NP完全問題，頻率指配方案一般采用序列即向量的形式進(jìn)行編碼，在編碼后的解空間中搜索可行解需要耗費(fèi)大量的時間，擁有n個電臺m個頻率的無約束固定頻率指配問題的解空間大小是mn，有約束條件的頻率指配問題的解空間比無約束頻率指配問題小，但是有約束頻率指配問題的求解搜索空間大小與無約束頻率指配問題相同，約束條件的存在使問題求解變得更加復(fù)雜。跳頻電臺異步組網(wǎng)時，為實(shí)現(xiàn)各網(wǎng)之間互不干擾或降低干擾，跳頻序列的選擇成為關(guān)鍵因素，對整個系統(tǒng)性能起到?jīng)Q定性作用，假設(shè)異步組網(wǎng)所有可用頻率數(shù)目為n，電臺跳頻序列長度為m，理論上來講解空間的大小是cmn(m-1)![1]。

根據(jù)其對解空間搜索采用方法的不同，求解頻率指配問題算法通?？梢苑譃榇_定性算法[2-3]和啟發(fā)式算法[4]，其根本上的相似性是通過對已知的一個或多個解進(jìn)行變換[5]以達(dá)成對解空間的遍歷。無論是確定性算法和啟發(fā)式算法在實(shí)際應(yīng)用當(dāng)中收斂速度受到初始解好壞的嚴(yán)重影響，也沒有算法討論如何縮小解的搜索范圍。運(yùn)用模式分析的核方法[6-7]，通過解空間當(dāng)中模式的尋找，發(fā)現(xiàn)看似雜亂的解空間中存在的模式，可以實(shí)現(xiàn)冗余解的剔除，有效縮小大部分頻率指配問題解的搜索范圍?？紤]到算法對所有頻率指配問題的適用性，通過運(yùn)用模式分析核方法，合理定義核函數(shù)，在特征空間中運(yùn)用聚類分析算法將指配方案進(jìn)行歸類。用于處理向量這種結(jié)構(gòu)化數(shù)據(jù)的核函數(shù)，一般包括序列的譜核、所有子序列核和trie樹核等核函數(shù)，但是對于頻率指配問題，以干擾值優(yōu)化為例，兩個結(jié)構(gòu)基本相同的序列應(yīng)用于同一個電臺網(wǎng)絡(luò)獲得的目標(biāo)函數(shù)值可能有較大的區(qū)別，因此本文采用目標(biāo)函數(shù)值構(gòu)建新的核矩陣作為衡量相似性的尺度，定義了絕對平均和加權(quán)平均兩種核函數(shù)來度量頻率指配序列的相似性，使得目標(biāo)評估函數(shù)值差距小的頻率指配序列的特征向量在特征空間中距離也較近。聚類分析完成后，以聚類質(zhì)心對應(yīng)的指配方案為典型方案作為后續(xù)算法的初始解，使得對典型方案的優(yōu)化可以達(dá)成減少解空間搜索量的效果。經(jīng)過模式分析算法找出的指配方案可直接作為頻率指配問題的最終解，如果聚類當(dāng)中沒有可行解，模式分析算法的結(jié)果也可作為其他優(yōu)化算法的初始解，加快其他算法的收斂速度。

2 利用評估函數(shù)值構(gòu)造核函數(shù)

求解頻率指配問題的樣本數(shù)據(jù)隨機(jī)來自解空間，指配序列及其評估函數(shù)值構(gòu)成集合s={(x1，y1)，(x2，y2)，…，(xl，yl)}，其中xi∈Rn，對應(yīng)的yi∈R，利用評估函數(shù)定義核函數(shù)最簡單的方式是將評估函數(shù)值進(jìn)行適當(dāng)組合作為特征空間向量的內(nèi)積。評估函數(shù)值的組合方式可以是絕對平均、加權(quán)平均等，以下通過兩種方式計(jì)算向量的內(nèi)積。

首先構(gòu)建如下的對稱矩陣，矩陣中的元素為特征空間中向量的內(nèi)積，內(nèi)積的計(jì)算由以下矩陣給出。

如果函數(shù)κ:X×X→R是一個對稱函數(shù)，則它滿足有限半正定矩陣的性質(zhì)。通過把矩陣限制在空間X的任何子集而形成的矩陣是半正定的。運(yùn)用目標(biāo)函數(shù)值乘積構(gòu)建的核矩陣是對稱矩陣，并且對于頻率指配問題，該矩陣隱式地定義了一個定義域在頻率指配序列上的對稱函數(shù)。由此可知上面通過絕對平均構(gòu)造的矩陣G是半正定矩陣。

函數(shù)κ:X×X→R或者連續(xù)，或者有一個可數(shù)的域。可以把這個函數(shù)分解為κ(x，z)=〈?(x)，?(z)〉。其中?是作用于該函數(shù)的兩個自變量的希爾伯特空間F內(nèi)的一個特征映射，可以通過求F中的內(nèi)積得到這個映射，當(dāng)且僅當(dāng)該函數(shù)滿足有限半正定性質(zhì)。由以上論證可知絕對平均構(gòu)造的矩陣G是特征空間中的內(nèi)積，它定義了原始數(shù)據(jù)空間s到特征空間F的映射，同時也隱式地確定了原始數(shù)據(jù)空間s到特征空間F的映射的核函數(shù)κ(x，z)。同理運(yùn)用加權(quán)乘積構(gòu)造如下矩陣：

其中a、b為權(quán)值系數(shù)，這個矩陣Gα也是特征空間中的內(nèi)積，它定義了原始數(shù)據(jù)空間s到特征空間F的另一個映射，同時也隱式地確定了原始數(shù)據(jù)空間s到特征空間F的映射的核函數(shù)κα(x，z)。

核函數(shù)的構(gòu)建應(yīng)該能夠獲得特定領(lǐng)域或任務(wù)的相似性衡量尺度。頻率指配序列和普通結(jié)構(gòu)化數(shù)據(jù)有很大的區(qū)別，兩個結(jié)構(gòu)基本相同的序列應(yīng)用于同一個電臺網(wǎng)絡(luò)獲得的目標(biāo)函數(shù)值可能有較大的區(qū)別，比如只有一個頻率指配數(shù)值不一樣的兩個頻率指配序列，其總體干擾值差距可能很大。在特征空間中兩個特征向量的距離等于這兩個向量之差的范數(shù)的開方，該范數(shù)計(jì)算方法如下：

由上式和目標(biāo)函數(shù)值乘積、目標(biāo)函數(shù)值加權(quán)乘積兩種方式構(gòu)建的核矩陣可知，無論兩個頻率指配序列在串、序列這樣的結(jié)構(gòu)化數(shù)據(jù)衡量標(biāo)準(zhǔn)下區(qū)別有多大，只要其產(chǎn)生的目標(biāo)函數(shù)值差距接近，那么在本文構(gòu)造的核矩陣決定的特征空間當(dāng)中，兩個頻率指配序列對應(yīng)的特征向量在特征空間當(dāng)中距離也比較近。

3 模式分析核方法聚類分析

其中?是特征空間F上的投影函數(shù)，核函數(shù)κ計(jì)算內(nèi)積κ(xi，xj)=〈?(xi)，?(xj)〉。

假設(shè)有n組頻率指配方案x1，x2，…，xn，f1，f2，…，fn為對應(yīng)的頻率指配方案干擾值。其中每組頻率指配方案包含頻率個數(shù)為m。應(yīng)用f1，f2，…，fn可以構(gòu)造目標(biāo)函數(shù)值乘積核函數(shù)和目標(biāo)函數(shù)值加權(quán)乘積核函數(shù)尋找解空間局部存在的非線性模式。本文中模式分析的核方法主要以聚類質(zhì)心對應(yīng)的指配方案為典型方案以達(dá)成縮小解的搜索范圍，所以應(yīng)用x1，x2，…，xn構(gòu)建目標(biāo)函數(shù)值乘積核、目標(biāo)函數(shù)值加權(quán)乘積核，在特征空間當(dāng)中運(yùn)行聚類分析算法，達(dá)成對原始指配方案x1，x2，…，xn進(jìn)行歸類是本文關(guān)注的重點(diǎn)。

通過目標(biāo)函數(shù)值乘積、目標(biāo)函數(shù)值加權(quán)乘積核矩陣的計(jì)算，指配方案被映射到特征空間當(dāng)中，運(yùn)行聚類分析算法[8]的目的是通過尋找指配方案以聚類形式存在的結(jié)構(gòu)，同一個聚類內(nèi)部的指配方案具有相似性，指配方案被劃分為若干組。假設(shè)每一個聚類有一個中心，可以利用點(diǎn)到分配給這個點(diǎn)的聚類中心的平方距離來評估點(diǎn)的擬合程度。當(dāng)新的點(diǎn)被分配到距離自己最近的聚類時，這個平均距離被最小化。在本文當(dāng)中采用平方距離標(biāo)準(zhǔn)來評估聚類的質(zhì)量，因?yàn)楹硕x數(shù)據(jù)項(xiàng)之間的兩兩相似性，從而提供評估聚類質(zhì)量的所需信息。給定一組指配方案S={x1，x2，…，xl}，尋找適當(dāng)?shù)姆椒?，把每一個指配方案分配到N個類別中的一個，聚類結(jié)果相當(dāng)于尋找一個映射：

f:s→{1，2，…，N}

根據(jù)以上需求，選擇適當(dāng)?shù)姆峙浞椒?，使以下聚類函?shù)達(dá)到最優(yōu)化。

4 仿真實(shí)驗(yàn)

假設(shè)在一定區(qū)域內(nèi)配置了128部超短波電臺，共有90個頻率點(diǎn)可以進(jìn)行指配，頻率起始點(diǎn)為45 MHz，最小頻率間隔為25 kHz，產(chǎn)生干擾的頻率間隔閾值為5個頻率間隔即125 kHz，在此實(shí)驗(yàn)性配置的基礎(chǔ)上，本文運(yùn)用兩種核函數(shù)對指配方案集合進(jìn)行聚類分析，算法的初始指配方案隨機(jī)產(chǎn)生，目標(biāo)評估函數(shù)系統(tǒng)總體干擾值，運(yùn)用k均值法進(jìn)行干擾值聚類分析，聚類個數(shù)設(shè)置為4。聚類質(zhì)心對應(yīng)的指配方案的干擾值通常不是聚類方案當(dāng)中最小的，但是理論上應(yīng)用聚類質(zhì)心處對應(yīng)的指配方案作為典型解運(yùn)行其他算法最合適。

4.1 目標(biāo)函數(shù)值乘積核聚類分析仿真實(shí)驗(yàn)

隨機(jī)給定100個初始頻率指配方案，并計(jì)算其相應(yīng)的干擾值。應(yīng)用干擾值可以構(gòu)建出如下的目標(biāo)函數(shù)值乘積核矩陣[9]。

應(yīng)用k均值法和核矩陣G對輸入的100個指配方案進(jìn)行聚類分析，并設(shè)置聚類數(shù)量為4，運(yùn)行程序得到聚類矩陣A和距離矩陣D。表1匯總了矩陣A和矩陣D的具體內(nèi)容，表中第一列為隨機(jī)指配方案的編號，第二列代表指配方案在特征空間中距所屬聚類質(zhì)心的距離，第三到第六列標(biāo)識當(dāng)前指配方案屬于哪個聚類，其中1代表屬于該聚類，反之不屬于該聚類。

表1 乘積聚類個數(shù)設(shè)置為4的分析結(jié)果

通過對聚類分析結(jié)果進(jìn)行程序分析，特征空間的聚類基本反映了原始空間中指配方案的相似性，但也出現(xiàn)了個別相似性很低的指配序列被分在同一個聚類當(dāng)中的情況，這可能和問題特殊性相關(guān)?？傮w來講，算法對初始指配序列進(jìn)行了良好的分類，圖1顯示序列分別與4個聚類質(zhì)心距離總和。

圖1 乘積聚類結(jié)果與不同質(zhì)心距離之和對比

從圖1可以看出，4個聚類內(nèi)部的指配方案與質(zhì)心的距離實(shí)現(xiàn)了最小化，同時聚類之間的距離也實(shí)現(xiàn)了最大化，聚類大小也都維持相等，這個聚類分析結(jié)果為了避免聚類距離閾值比較而帶來的運(yùn)行時間的負(fù)擔(dān)，并沒有完全采用聚類分析的策略，因?yàn)樗惴ǖ慕Y(jié)果只是對指配序列進(jìn)行歸類劃分，雖然具有一定的優(yōu)化效果，但獲得可行解的概率較低，需要再次應(yīng)用遺傳算法等其他算法對問題進(jìn)行求解。

4.2 目標(biāo)函數(shù)值加權(quán)乘積核聚類分析仿真實(shí)驗(yàn)

隨機(jī)給定100個初始頻率指配方案，并計(jì)算其相應(yīng)的干擾值。應(yīng)用干擾值可以構(gòu)建出如下的目標(biāo)函數(shù)值加權(quán)乘積核矩陣，其中序列占據(jù)頻帶較窄的指配方案權(quán)值設(shè)置為0.6，反之權(quán)值設(shè)置為0.4，也可以根據(jù)其他標(biāo)準(zhǔn)為任意兩個序列設(shè)置浮動權(quán)值，設(shè)置權(quán)值雖然增加算法的時間復(fù)雜度，但是浮動權(quán)值理論上優(yōu)化效果比固定權(quán)值好。

應(yīng)用k均值法和核矩陣G對輸入的100個指配方案進(jìn)行聚類分析，并設(shè)置聚類數(shù)量為4，運(yùn)行程序得到聚類矩陣A和距離矩陣D。表2匯總了矩陣A和矩陣D的具體內(nèi)容。

表2 加權(quán)乘積聚類個數(shù)設(shè)置為4的分析結(jié)果

通過對聚類分析結(jié)果進(jìn)行程序分析，特征空間的聚類和絕對平均聚類分析一樣基本反映了原始空間中指配方案的相似性，并且聚類劃分也體現(xiàn)了相似性，劃分結(jié)果中同一指配方案劃分給不同聚類的情況出現(xiàn)較少，同樣也出現(xiàn)了個別相似性很低的指配序列被分在同一個聚類當(dāng)中的情況，這同樣與問題相關(guān)。總體來講，算法對初始指配序列進(jìn)行了良好的分類，圖2顯示序列分別與4個聚類質(zhì)心距離總和。

圖2 加權(quán)乘積聚類結(jié)果與不同質(zhì)心距離之和對比

從圖2可以看出，4個聚類內(nèi)部的指配方案與質(zhì)心的距離實(shí)現(xiàn)了最小化，同時聚類之間的距離也實(shí)現(xiàn)了最大化，聚類大小也都維持相等，通過和圖1進(jìn)行對比，加權(quán)乘積聚類內(nèi)部的距離變小，而聚類之間的距離變大，說明加權(quán)乘積聚類的結(jié)果指配序列在特征空間當(dāng)中收緊效果相對較好，不同聚類的相異性也較乘積聚類要好。

5 仿真實(shí)驗(yàn)結(jié)果分析

從以上的仿真實(shí)驗(yàn)可以看出，運(yùn)用本文構(gòu)造的核矩陣較好地完成了特征空間中指配方案的聚類分析，質(zhì)心處對應(yīng)的指配方案可以作為后續(xù)其他算法的初始解。算法對隨機(jī)或者其他算法生成的初始指配方案能夠進(jìn)行快速分類，通過對初始解當(dāng)中的類似解的剔除，達(dá)到了減少解空間搜索量的效果。除了作為初始解篩選工具之外，算法還可以直接應(yīng)用于解決其他類似問題當(dāng)中，將其應(yīng)用于跳頻序列選取當(dāng)中，跳頻序列的碰撞率明顯降低，并且在跳頻序列選取時，構(gòu)造的核矩陣對問題敏感性較低，優(yōu)化效果比較好。

6 結(jié)論

運(yùn)用本文構(gòu)造的核矩陣較好地完成了特征空間中指配方案的聚類分析，通過對初始解當(dāng)中的類似方案的剔除，達(dá)到了壓縮解空間的效果，從而使簡單頻率指配問題能夠?qū)崟r完成，對于大型問題而言，頻率指配的時間復(fù)雜度也大大降低。

[1]楊化斌，孫俊.基于聚類分析的跳頻序列選取[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（27）：113-114.

[2]翟霄飛，張波.防空兵戰(zhàn)場頻譜管理中頻率分配與指配問題研究[J].通信對抗，2010（3）：34-36.

[3]李良辰.帶限制條件的頻率分配的近似算法[J].華中師范大學(xué)學(xué)報(bào)，2010，44（3）：55-57.

[4]徐奇，熊暉，李釗，等.一種針對頻率分配問題的改進(jìn)ANΤS算法[J].無線電工程，2010，40（1）：58-61.

[5]Chert J K，de Veciana G，Rappaport Τ S.Improved measurement-based frequency allocation algorithms for wireless networks[C]//IEEE GLOBECOM 2007，2007.

[6]伍忠東，高新波.基于核方法的模糊聚類算法[J].西安電子科技大學(xué)學(xué)報(bào)，2004（4）：533-537.

[7]劉婷婷，任興民.核獨(dú)立分量分析在機(jī)械振動信號分離中的應(yīng)用[J].西北工業(yè)大學(xué)學(xué)報(bào)，2011，29（1）：108-113.

[8]錢衛(wèi)寧，周傲英.從多角度分析現(xiàn)有聚類算法[J].軟件學(xué)報(bào)，2002，13（8）：1382-1394.

[9]郭崇慧，李芳.基于核矩陣的改進(jìn)支持向量聚類算法[J].情報(bào)學(xué)報(bào)，2010，29（3）：422-427.

YANG Huabin,LIN Zhong,SUN Jun

Τelecommunication Engineering Institute,Air Force Engineering University,Xi’an 710077,China

Τhe kernel methods for pattern analysis are applied to solving the frequency assignment problem.Τhe algorithm takes randomly assigned solutions and their corresponding values of object function to construct kernel matrix.Τhen based on the kernel matrix,this paper uses cluster analysis algorithm in the eigen space to measure similarity of solutions and classify solutions. Optimized results of the cluster analysis algorithm can be directly applied to actual engineering project,and also can be used as the initial input of other optimization algorithms.Using optimized results of the cluster analysis algorithm as the initial solution, algorithms like ant colony algorithm and genetic algorithm reflect high efficiency in the application that has large-scale radio stations. Convergence rate is improved significantly.

frequency assignment;pattern analysis;kernel method;cluster analysis;kernel matrix

為有效解決頻率指配問題，提出了一種解決該問題的模式分析核方法，算法利用頻率指配方案的評估函數(shù)值構(gòu)建核矩陣，以核矩陣為基礎(chǔ)在特征空間中運(yùn)行聚類分析算法，對頻率指配方案相似性進(jìn)行度量，完成頻率指配方案的歸類劃分。優(yōu)化結(jié)果可直接作為跳頻指配結(jié)果，也可作為其他優(yōu)化算法的初始解。該算法在電臺數(shù)量規(guī)模較大的應(yīng)用中體現(xiàn)出良好的性能，算法結(jié)果作為蟻群、遺傳算法的初始解，后繼算法收斂速度明顯提高。

頻率指配；模式分析；核方法；聚類分析；核矩陣

A

ΤP391

10.3778/j.issn.1002-8331.1201-0257

YANG Huabin,LIN Zhong,SUN Jun.Using kernel methods for pattern analysis to solve frequency assignment problem. Computer Engineering and Applications,2013,49（21）：168-171.

國家自然科學(xué)基金（No.61174162，No.61101102）；航空科學(xué)基金（No.20100796004）。

楊化斌（1973—），男，博士研究生，講師，主要從事軍事通信學(xué)戰(zhàn)場頻率指配研究；林中（1972—），男，講師，主要從事軍事通信學(xué)電子對抗研究；孫?。?977—），男，講師，主要從事復(fù)雜電磁環(huán)境中的通信指揮研究。E-mail：lyhb0909@sina.com

2012-01-16

2012-05-28

1002-8331（2013）21-0168-04