基于遺傳-禁忌混合算法的低相關(guān)區(qū)序列集搜索方法

李明陽(yáng)，柏 鵬，彭衛(wèi)東，李淑婧

(1.空軍工程大學(xué)裝備管理與安全工程學(xué)院，陜西西安710051;2.空軍工程大學(xué)綜合電子信息系統(tǒng)與電子對(duì)抗技術(shù)研究中心，陜西西安710051)

0 引言

具有較好相關(guān)特性的序列集在擴(kuò)頻通信［1］、多輸入多輸出(multiple input multiple output，MIMO)雷達(dá)［2］等系統(tǒng)中具有重要應(yīng)用價(jià)值。文獻(xiàn)［3］基于進(jìn)化機(jī)制生成了具有較低副峰的非周期二相序列，文獻(xiàn)［4-5］分別利用遺傳算法、粒子群算法、蜂群算法和模擬退火算法等生成適用于MIMO雷達(dá)的多相碼。研究表明，在整個(gè)移位周期范圍內(nèi)，自相關(guān)副峰(autocorrelation sidelobe peak，ASP)和互相關(guān)峰(cross-correlation peak，CP)不能同時(shí)得到有效抑制［6］。文獻(xiàn)［7］提出的零相關(guān)區(qū)(zero correlation zone，ZCZ)序列不要求在整個(gè)移位周期范圍內(nèi)具有理想的ASP和CP，相對(duì)于完全正交序列具有更加靈活的參數(shù)。文獻(xiàn)［8］將零相關(guān)區(qū)序列應(yīng)用于MIMO雷達(dá)系統(tǒng)，獲得較高的距離分辨率和探測(cè)性能。類似地，低相關(guān)區(qū)序列集要求在一定范圍內(nèi)具有較低的ASP和CP。LCZ和ZCZ序列的構(gòu)造方法通常包括最優(yōu)化搜索方法［9-11］、交織方法［12，13］、代數(shù)方法［14］等。交織方法和代數(shù)方法依然受到較為嚴(yán)格的參數(shù)限制，無(wú)法生成任意長(zhǎng)度的LCZ/ZCZ序列，最優(yōu)化搜索方法雖然不能生成理論最優(yōu)或次優(yōu)的序列，但可選參數(shù)更靈活。

本文將遺傳算法和禁忌算法相結(jié)合，提出一種低相關(guān)區(qū)序列集的智能搜索方法。該方法將禁忌算法嵌入到遺傳算法的變異操作中，設(shè)置變異位為禁忌對(duì)象，防止某位頻繁變異。進(jìn)化過(guò)程中，根據(jù)當(dāng)前全局最小的最大ASP和最大CP動(dòng)態(tài)調(diào)節(jié)交叉點(diǎn)，使交叉點(diǎn)數(shù)隨全局ASP和CP的逐漸縮小而減少，從而在進(jìn)化前期保證進(jìn)化速度，在進(jìn)化后期保證收斂。每一輪進(jìn)化前檢驗(yàn)序列的移位等價(jià)性，剔除移位等價(jià)序列，從而提高種群多樣性，防止早熟。最后，通過(guò)數(shù)值仿真證明了本文方法的有效性。

1 基本定義和定理

(1)式中，*表示對(duì)復(fù)數(shù)共軛運(yùn)算。

類似地，序列集的周期相關(guān)函數(shù)定義為

如果i=j，(1)式和(2)式稱為序列xi的非周期/周期自相關(guān)函數(shù)，否則(1)式和(2)式稱為序列xi和xj的非周期/周期互相關(guān)函數(shù)。

定義2 對(duì)于定義1中的序列集X，如果X中任意2個(gè)序列相關(guān)函數(shù)滿足如下條件

則稱X為低相關(guān)區(qū)長(zhǎng)度為ZLC的LCZ(P，L，M，ZLC，σa，σc)序列集。

(3)式中:P表示序列集的進(jìn)制;σa和σc分別表示序列集的最大ASP和最大CP。

2 基于遺傳-禁忌算法的LCZ序列集搜索方法

2.1 問(wèn)題的優(yōu)化模型

在LCZ序列集參數(shù)P，L，M和ZLC固定的條件下，σa和σc的絕對(duì)值越小，LCZ序列集的相關(guān)特性越好。以上參數(shù)固定條件下，搜索σa和σc的絕對(duì)值較小的問(wèn)題可以歸結(jié)為求使(4)式中目標(biāo)函數(shù)E最小的序列集X。

(4)式中，ωa，ωc為加權(quán)系數(shù)。如果 σa≠ σc，且σc/σa=λ，則取系數(shù)ωa=λ，ωc=1。

2.2 遺傳-禁忌混合算法搜索步驟

使(4)式最小化的序列集的求解是一個(gè)多元非線性NP問(wèn)題，如果采用窮舉法，其計(jì)算量為2MLP。對(duì)于NP問(wèn)題，一種可行的方法是利用智能算法獲得近似最優(yōu)解，遺傳算法和禁忌算法都是求解NP問(wèn)題的啟發(fā)式算法。其中，遺傳算法具有較好的全局搜索能力，禁忌算法對(duì)初值的依賴較大，但是局部“爬坡”能力很強(qiáng)，將二者結(jié)合可以利用遺傳算法實(shí)現(xiàn)粗搜索，利用禁忌算法獲得更精確搜索。文獻(xiàn)［15］利用遺傳－禁忌混合算法獲得了相對(duì)于單純遺傳算法［10］更優(yōu)的搜索性能，但是該方法只是將遺傳算法和禁忌算法進(jìn)行簡(jiǎn)單的級(jí)聯(lián)，不能充分發(fā)揮2種算法的優(yōu)點(diǎn)。因?yàn)檫z傳算法的局部搜索能力主要源自變異操作，所以本文中將禁忌算法嵌入到遺傳的變異操作中，將所有一點(diǎn)變異作為鄰域，在該鄰域內(nèi)用禁忌算法搜索，從而提高變異的局部搜索能力?；谶z傳-禁忌混合算法LCZ序列集搜索方法的實(shí)現(xiàn)流程如圖1所示。

圖1 基于遺傳-禁忌算法搜索LCZ序列集的流程圖Fig.1 Flow chart of searching method of LCZ sequence set based on genetic-taboo algorithm

基于遺傳-禁忌混合算法LCZ序列集搜索方法實(shí)現(xiàn)步驟和關(guān)鍵技術(shù)如下。

1)編碼。采用P進(jìn)制級(jí)聯(lián)編碼，用一個(gè)長(zhǎng)度為ML的P進(jìn)制序列表示一個(gè)序列集X。

2)初始化。假設(shè)種群數(shù)量為pop_size，則隨機(jī)產(chǎn)生pop_size個(gè)編碼序列，預(yù)先設(shè)定交叉概率pc和變異概率pm。

3)遺傳操作。

①選擇。假設(shè)第l個(gè)編碼序列的目標(biāo)函數(shù)為El，按照輪盤(pán)賭選擇法，第l個(gè)編碼序列依概率遺傳到下一代。

②交叉。從種群中任意選擇2個(gè)編碼序列，假設(shè)2個(gè)相關(guān)序列對(duì)應(yīng)位相等的位數(shù)為n+，對(duì)應(yīng)位不等的位數(shù)為n－，對(duì)于P元序列最多需要變化(n+－n－)/(2lb P)位則有可能獲得最小的相關(guān)值。所以，從種群中任意選擇2個(gè)編碼序列，隨機(jī)選擇n個(gè)交叉點(diǎn)進(jìn)行多點(diǎn)交叉。其中

③禁忌搜索。將種群中每個(gè)子序列的所有一點(diǎn)變異作為該序列的鄰域，利用禁忌算法進(jìn)行搜索。設(shè)置變異點(diǎn)為禁忌對(duì)象，禁忌長(zhǎng)度為L(zhǎng)T。如果變異不被禁忌，則根據(jù)當(dāng)前序列目標(biāo)函數(shù)和變異序列目標(biāo)函數(shù)的大小判斷是否變異。當(dāng)且僅當(dāng)禁忌表中對(duì)象的目標(biāo)函數(shù)小于當(dāng)前全局最優(yōu)解時(shí)，對(duì)當(dāng)前禁忌解禁，更新禁忌表。

4)評(píng)估種群。利用(4)式評(píng)估種群。

5)結(jié)束判斷。智能算法收斂后目標(biāo)函數(shù)將不再變化，所以可以假定目標(biāo)函數(shù)保持不變后算法收斂。定義(4)式中目標(biāo)函數(shù)跳變間隔為目標(biāo)函數(shù)2個(gè)不相等值間隔的進(jìn)化代數(shù)，設(shè)定跳變間隔的最大值，當(dāng)超過(guò)該最大值仍不跳變則認(rèn)為已經(jīng)收斂到最優(yōu)解。根據(jù)經(jīng)驗(yàn)，本文中設(shè)定最大跳變間隔為進(jìn)化代數(shù)的1/10。

6)剔除移位等價(jià)序列。為了消除移位等價(jià)序列［16］對(duì)種群多樣性的破壞，本文設(shè)計(jì)了快速剔除移位等價(jià)序列的方法。根據(jù)FFT變換的性質(zhì)，序列及其循環(huán)移位序列具有相同的FFT包絡(luò)，所以對(duì)種群矩陣進(jìn)行一維FFT變換，對(duì)相同包絡(luò)的序列只保留其中一個(gè)，然后將保留編碼序列組成新種群。

3 數(shù)值仿真及分析

選擇參數(shù)，設(shè)定M=4，L=40，P=4，低相關(guān)區(qū)Z=40，搜索非周期序列集，種群大小設(shè)為pop_size=200，進(jìn)化代數(shù)為50，交叉概率為pc=0.3和變異概率為pm=0.03，禁忌長(zhǎng)度為L(zhǎng)T=5。所得到的序列集X={xii∈(0，1，2，3)}為

(5)式中，0—3分別表示相位{0，π/2，π，3π/2}。

表1 序列集的最大ASP和最大CPTab.1 Maximum ASP and CP of the sequence set

圖2 非周期自相關(guān)函數(shù)Fig.2 Aperiodic auto correlation function

序列集的相關(guān)副峰和互相關(guān)峰值最大值為0.175，相比文獻(xiàn)［15］中序列集的相關(guān)副峰和互相關(guān)峰值最大值為0.215 1，多址干擾更小。

設(shè)定M=1，其余參數(shù)不變，進(jìn)化所得到的序列為x=(2，2，1，3，1，1，2，1，1，2，3，2，2，2，3，1，1，3，3，0，3，1，0，1，3，1，2，1，2，3，0，0，0，2，3，0，0，0，2，1)。

序列x自相關(guān)函數(shù)的最大副峰為0.05，可以在通信、定位系統(tǒng)中作為多相測(cè)距、同步碼使用。圖4為序列x的自相關(guān)函數(shù)曲線。

設(shè)定P=2，L=40，Z=40，搜索周期低相關(guān)區(qū)序列集，其余參數(shù)不變。進(jìn)化所得到的序列集，按照16進(jìn)制表示為

圖3 非周期互相關(guān)函數(shù)Fig.3 Aperiodic cross correlation function

圖4 非周期自相關(guān)函數(shù)Fig.4 Aperiodic auto correlation function

序列集X的周期最大ASP和最大CP如表2所示。

表2 序列集的最大ASP和最大CPTab.2 Maximum ASP and CP of the sequence set

在低相關(guān)區(qū)內(nèi)，序列集Y的周期最大ASP和最大CP都為0.2。序列集X和Y的部分相關(guān)函數(shù)曲線如圖5所示。

圖5 不同低相關(guān)區(qū)序列的相關(guān)值對(duì)比Fig.5 Correlation comparison of different LCZ sequences

對(duì)比Z=40和Z=20時(shí)序列集的相關(guān)函數(shù)值，可以發(fā)現(xiàn)低相關(guān)區(qū)縮小后，最大ASP和最大CP由0.3降為0.2。所以適當(dāng)?shù)亟档偷拖嚓P(guān)區(qū)，可以一定程度上抑制序列自身和序列間干擾。

4 結(jié)束語(yǔ)

本文提出基于一種遺傳－禁忌混合算法的多相低相關(guān)區(qū)周期序列集的搜索方法。遺傳算法具有全局搜索能力，但是局部搜索性能相對(duì)較差;禁忌算法局部搜索能力很強(qiáng)，但是對(duì)初始解依賴較大。將二者結(jié)合可以取長(zhǎng)補(bǔ)短，有效提高序列集搜索性能。

文中利用該方法對(duì)周期、非周期，二元以及多元序列集進(jìn)行搜索，獲得了較好的效果。該方法具有一定的通用性，只需要相應(yīng)改變目標(biāo)函數(shù)即可滿足不同序列集的搜索需求。該方法對(duì)于QS－CDMA通信系統(tǒng)、MIMO雷達(dá)系統(tǒng)和測(cè)距系統(tǒng)中擴(kuò)頻序列的設(shè)計(jì)具有一定理論意義和實(shí)用價(jià)值。

［1］曾凡鑫.適用于AS-CDMA系統(tǒng)的具有零(低)相關(guān)區(qū)的二元序列的數(shù)量擴(kuò)張［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，2004，16(4):14-16.

ZENG Fanxin.Extension of family size of binary sequences with zero or low correlation zone for AS-CDMA system［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2004，16(4):14-16.

［2］FISHLER E，HAIMOVICH A，BLUM R，et al.Spatial diversity in radars-models and detection performance［J］.IEEE Transactions on Signal Processing，2006，54(3):823-838.

［3］SUKRU E K，ABDULLAH A.Binary Sequences With Low Aperiodic Autocorrelation for Synchronization Purposes［J］.IEEE Communications Letters，2003，7(1):36-37.

［4］LIU B，HE Z，ZENG J，et al.Polyphase orthogonal code design for MIMO radar systems［C］//IEEE.Processing of the International Conference on Radar.Shanghai:IEEE Press，2006:1-4.

［5］SUKRU E K，ABDULLAH A.Optimization of Orthogonal Polyphase Coding Waveform for MIMO Radar based on Evolutionary Algorithms［J］.Journal of Mathematics and Computer Science，2013，6(2):146-153.

［6］TANG X H，F(xiàn)AN P Z.Bounds on aperiodic and odd correlations of spreading sequences with low and zero correlation zone［J］.Electronics Letters，2001，37(19):1201-1203.

［7］FAN P Z，HAO L.Generalized orthogonal sequences their applications in synchronous CDMA systems［J］.IEICE Trans Fundamentals，2000，E83-A(11):1-16.

［8］XU L，LIANG Q.Zero Correlation Zone Sequence Pair Sets for MIMO Radar［J］.IEEE Transactions on Aerospace and Electronic Systems，2012，48(3):2100-2113.

［9］朱志華，葉飛，辛明軍，等.基于貓群優(yōu)化算法的2n周期優(yōu)秀二元序列的研究與分析［J］.電子與信息學(xué)報(bào)，2013，35(6):1365-1370.

ZHU Zhihua，YE Fei，XIN Mingjun，et al.The Research and Analysis of the Excellent 2nPeriodic Binary Sequence Based on Cat Swarm optimization［J］.Journal of Electronics＆Information Technology，2013，35(6):1365-1370.

［10］金明，廖桂生，李軍.基于遺傳算法的類零相關(guān)多相碼設(shè)計(jì)［J］.系統(tǒng)工程與電子技術(shù)，2010，32(1):14-17.

JIN Ming，LIAO Guisheng，LI Jun.Zero correlation zone like polyphase code design based on genetic algorithm［J］.System Engineering and Electronics，2010，32(1):14-17.

［11］YE L，LI C，QU L.A New Construction of Low-Correlation Zone Sequence Sets［C］//IEEE.8th International Conference on Wireless Communications，Networking and Mobile Computing(WiCOM).Shanghai:IEEE Press，2012:1-5.

［12］TANG X，F(xiàn)AN P Z，LINDNER J.Multiple binary ZCZ sequence sets with good cross-correlation property based on complementary sequence sets［J］.IEEE Transaction on Information Theory，2010，56(8):4038-4045.

［13］TU Y F，F(xiàn)AN P Z，LI H，et al.Construction of Binary Array Set with Zero Correlation Zone Based on Interleaving Technique［J］.IEICE Transaction on Fundamentals of Electronics，Communications and Computer Sciences，2011，94(2):766-772.

［14］JANG J W，KIM S H，NO J S.New Construction of Quaternary Low Correlation Zone Sequence Sets from Binary Low Correlation Zone Sequence Sets［J］.Journal of Communications and Networks，2010，12(4):330-333.

［15］王偉，趙俊杰，王輝.基于混合算法的MIMO雷達(dá)正交多相碼設(shè)計(jì)［J］.系統(tǒng)工程與電子技術(shù)，2013，35(2):294-298.

WANG Wei，ZHAO Junjie，WANG Hui.Design of orthogonal polyphase code for MIMO radar based on hybrid algorithm［J］.System Engineering and Electronics，2013，35(2):294-298.

［16］ZHOU Z C，PAN Z，TANG X H.A new family of optimal zero correlation zone sequences from perfect sequences based on interleaved technique［C］//IEEE.3rd International Workshop on Signal Design and its Applications in Communications(IWSDA).Chengdu:IEEE Press，2007:195-199.