基于進(jìn)化計算的二元序列優(yōu)化算法研究

李 鶴，李 琦，高軍萍，雷明然

（河北工業(yè)大學(xué) 信息工程學(xué)院，天津 300401）

基于進(jìn)化計算的二元序列優(yōu)化算法研究

李 鶴，李 琦，高軍萍，雷明然

（河北工業(yè)大學(xué) 信息工程學(xué)院，天津 300401）

具有良好非周期自相關(guān)特性二元序列在通信同步、雷達(dá)等領(lǐng)域具有廣泛的應(yīng)用。通過對遺傳算法、粒子群算法與量子粒子群算法三種進(jìn)化算法進(jìn)行對比分析，設(shè)計了具有良好非周期自相關(guān)特性的二元序列的搜索算法。研究結(jié)果表明，粒子群算法的搜索能力優(yōu)于遺傳算法，而量子粒子群算法具有參數(shù)少，易于控制的優(yōu)點，取得了較好的優(yōu)化結(jié)果。

二元序列；非周期自相關(guān)；遺傳算法；粒子群算法；量子粒子群算法

具有良好非周期自相關(guān)性的二元序列廣泛應(yīng)用于雷達(dá)、通信系統(tǒng)和遙測遙控技術(shù)領(lǐng)域中。其中，迄今為止發(fā)現(xiàn)的具有最低幅峰值的二元序列是由Barker提出的Barker序列[1]。但是，Barker序列的長度有限，目前發(fā)現(xiàn)的最長Barker序列的長度僅為13，雖然不少專家學(xué)者進(jìn)行了探索。其中，Storer與Turyn[2]證明不存在長度大于13的奇數(shù)長Barker序列而偶數(shù)長度的Barker序列只能以完全平方數(shù)的形式存在。文獻(xiàn)[3]中將Barker序列擴(kuò)展到 相，但是長度仍然有限，大大限制了其應(yīng)用。因此，尋找其他具有次優(yōu)非周期相關(guān)特性的二元序列是一個重要問題。

在序列的傳統(tǒng)搜索方法中，常利用計算機(jī)窮舉搜索方法，但是窮舉法耗時長、搜索效率低。我們發(fā)現(xiàn)利用組合優(yōu)化的方法可以搜索到更長的序列。其中，遺傳算法（Genetic Algorithms, GA）在20年代60年代末被提出，在人工適應(yīng)系統(tǒng)中設(shè)計了一種基于自然演化原理的搜索機(jī)制，并已經(jīng)應(yīng)用到序列的搜索中。文獻(xiàn)[4]中利用遺傳算法搜索低旁瓣最大長度序列，取得了很好的效果。粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）是由Kennedy和Eberha在1995年提出的一種進(jìn)化算法，已經(jīng)被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、NP問題近似求解、模糊系統(tǒng)控制等眾多不同的領(lǐng)域[5]。隨后，Sun等人將量子算法與粒子群算法結(jié)合起來，提出了性能更優(yōu)越的量子粒子群算法(Quantum-behaved Particle Swarm Optimization ，QPSO)[6]。

本文通過對3種進(jìn)化算法進(jìn)行對比分析，應(yīng)用遺傳算法、粒子群優(yōu)化算法和量子粒子群算法來獲取具有良好非周期自相關(guān)性的二元序列，最后對三種算法的搜索結(jié)果進(jìn)行比較分析，結(jié)果證明采用QPSO算法可以搜索得到具有較好非周期自相關(guān)特性的的二元序列。

1 二元序列及其相關(guān)概念

1.1 二元序列及其非周期自相關(guān)函數(shù)

設(shè)二元序列 的長度為 ，其非周期自相關(guān)函數(shù)表示如下（其中τ≥ 0）：

在通信、雷達(dá)系統(tǒng)中常用序列的旁瓣電平峰值（Peak Sidelobe Level，PSL）作為評價因子來衡量該序列的非周期自相關(guān)特性，表示如下：

PSL的值越小，則說明該序列的非周期自相關(guān)特性越好。

1.2 巴克碼簡介

巴克碼是一種二元偽隨機(jī)序列。設(shè)一 N長的巴克碼 ｛aN｝，(aN∈{+1,-1}),其非周期自相關(guān)函數(shù)為：

顯然，Barker序列的PSL=1，故又稱Barker序列為最佳有限二元序列。但是目前存在的Barker序列不多，僅有9個經(jīng)典的Barker序列，如表1所示，最大長度為13長。

表1 經(jīng)典 Barker序列Tab.1 Classic Barker sequence

由于Barker序列的長度和存在數(shù)量的局限，大大限制了它的應(yīng)用。因此需要尋找其他長度下具有最低副峰值的二元序列。

2 基于PSO和QPSO的二元序列優(yōu)化

進(jìn)化算法中主要包括遺傳算法、粒子群優(yōu)化算法及其改進(jìn)算法等。進(jìn)化算法模擬生物群體的生存過程，并已經(jīng)廣泛運(yùn)用于復(fù)雜的優(yōu)化問題中。在序列優(yōu)化的領(lǐng)域中，遺傳算法（GA）因其良好的全局搜索能力被應(yīng)用到序列搜索工作中。但是由于遺傳算法在群體的進(jìn)化過程中會產(chǎn)生越來越多的優(yōu)良個體，經(jīng)過選擇、交叉、變異的遺傳操作過程中產(chǎn)生的隨機(jī)性，可能會破壞當(dāng)前群體中適應(yīng)度較好的優(yōu)良個體，降低群體的平均適應(yīng)度，從而影響遺傳算法的運(yùn)行效率及收斂性。而粒子群算法很好的改善了這種隨機(jī)性的影響。

粒子群優(yōu)化算法（PSO）源于對人工生命和鳥群捕食行為的研究，和遺傳算法比較省去了選擇、交叉、變異等操作，實現(xiàn)方法簡便，實現(xiàn)過程簡單、代碼效率高。

在PSO算法中，每個優(yōu)化問題的潛在解都可以想象成 維搜索空間的一個點，也就是“粒子”。粒子在搜索空間內(nèi)以一定的速度飛行，這個速度根據(jù)它本身的飛行經(jīng)驗和同伴的飛行經(jīng)驗來動態(tài)調(diào)整[7]。

利用PSO算法優(yōu)化二元序列的具體過程如下：

1 ) 對待解決的問題進(jìn)行編碼：包括序列的長度N、迭代的次數(shù)MaxDT、種群的大小M、搜索空間維數(shù)D、慣性權(quán)重和學(xué)習(xí)因子等。

2 ) 隨機(jī)初始化種群：包括初始化種群個體的位置向量

Xi= ( Xi1,Xi2,…,XiD)和速度向量 Vi= ( Vi1, Vi2, … ViD) 。

3 ) 根據(jù)評價函數(shù)計算種群個體最優(yōu)位置pbesti= ( pbesti1,pbesti2,…,…pbestid)和群體的最優(yōu)位置gbest=(gbest1,gbest2…gbestd,。其中評價函數(shù)為：

4 )粒子更新位置。在每一次迭代中，每個粒子使用下列公式改變自己當(dāng)前的位置：

其中,i=1,2…n, d==1,2…D，ω為慣性權(quán)重，加速PSO的收斂速度，C1、C2學(xué)習(xí)因子為正常數(shù)，r1,r2為 [0,1]之間符合正態(tài)分布的一個偽隨機(jī)數(shù)。

由于二元序列屬于離散序列，所以在粒子更新自己的位置后，還要通過以下函數(shù)對各個粒子的速度向量離散化：

5 ) 達(dá)到最大迭代次數(shù)后，停止迭代，輸出結(jié)果。否則轉(zhuǎn)到步驟2）。

本文利用PSO算法對二元序列進(jìn)行了搜索，序列的長度由49逐漸增大到100，并將搜索結(jié)果與遺傳算法進(jìn)行比較，取其中的10組結(jié)果如表2 所示。

表2 GA算法與PSO算法搜索結(jié)果比較Tab.2 The GA algorithm is compared with PSO algorithm search results

從表2中可以看出，利用GA算法和PSO算法搜索出的序列PSL值都隨著序列長度的增加而增大，PSO算法較GA算法搜索能力略有改善。但是出現(xiàn)了不穩(wěn)定的情況，如序列長增至92時，PSL值突變?yōu)?，破壞了持續(xù)增大的規(guī)律，這就要求對PSO算法進(jìn)行改進(jìn)，得到結(jié)果更穩(wěn)定、性能更優(yōu)化的二元序列。

QPSO算法與PSO算法相比更能保證粒子的全局收斂性，因其在進(jìn)化方程中不需要速度向量，沒有了樣本空間的限制，使得進(jìn)化方程的形式更為簡單、參數(shù)更少，也更容易控制。

在QPSO中[7]，為了保證算法的收斂性，每一個粒子必須收斂到各自的p點，第i個粒子 點的第 維坐標(biāo)為：

在粒子群中引入了一個全局點 來計算粒子的下一步迭代的變量，它定義為所有粒子的局部最好位置的平均值。公式如下：

因此，粒子的進(jìn)化方程為：

其中，u表示 [0,1]之間符合正態(tài)分布的一個偽隨機(jī)數(shù)；a表示收縮擴(kuò)張系數(shù)，能夠控制算法的收斂速度。

由上可知，QPSO算法中，粒子的狀態(tài)只需要用位置向量來描述，并且通過設(shè)置收縮擴(kuò)張系數(shù)就能保證算法的收斂速度，對比PSO算法，減少了對粒子速度的限制，搜索能力更強(qiáng)。

本文利用QPSO算法進(jìn)行了二元序列的優(yōu)化，序列長度由49逐漸增大到100，搜索結(jié)果與PSO算法的對比如下，其中，取10組結(jié)果如表3 所示。

表3 PSO算法與QPSO算法搜索結(jié)果比較Tab.3 The PSO algorithm is compared with QPSO algorithm search results

根據(jù)表3的結(jié)果可以得出，利用QPSO算法得到的PSL值隨著序列長度的增加而增大，對比PSO算法有了明顯的改變，并且算法更為穩(wěn)定。

3 結(jié) 論

文中利用進(jìn)化算法對二元序列進(jìn)行優(yōu)化研究。其中，遺傳算法因其操作中的隨機(jī)性不能保證算法具有良好的收斂性。因此，文中首先采用PSO算法對具有良好非周期自相關(guān)特性的二元序列進(jìn)行了搜索。搜索結(jié)果表明，雖然PSO算法省略了遺傳算法中的交叉、變異等操作，使操作簡單，得到序列的PSL值略有改善，但是出現(xiàn)了PSL值突變的情況。為取得更為優(yōu)化的二元序列，文中結(jié)合量子算法與PSO算法，使搜索只受一個參數(shù)的控制，大大提升了搜索能力。因此，在具有良好非周期自相關(guān)二元序列的優(yōu)化問題中，QPSO算法搜索能力最強(qiáng)、更穩(wěn)定，具有較好效果。因此，在后期的研究工作中準(zhǔn)備將其應(yīng)用于其他類型的序列如光碼分多址系統(tǒng)地址碼的搜索工作中。

[1] Barker R H. Group Synchronizing of Binary Digital Systems.Communication Theory,Jackson W,ed. [M].New York: Academic Press,Inc,1953.

[2] Turyn R J, Storer J. Onbinary sequences [J]. Proc.of Amer.Math.,1961(12):394-399.

[3]王慶海,袁運(yùn)能,毛士藝.泛Barker序列設(shè)計[J].系統(tǒng)工程與電子技術(shù),2006,6(28):798-852.

WANG Qing-hai, YUAN Yun-neng, MAO Shi-yi. PAN barker sequence design[J]. Systems engineering and electronics,2006,6(28):798-852.

[4]何飛,劉肅,張立軍,等. 基于遺傳算法搜索低旁瓣最大長度序列[J].計算機(jī)應(yīng)用研究,2012,29(10):3629-3631.

HE Fei, LIU Su, ZHANG Li-jun,et al. Based on the genetic algorithm to searchthe low sidelobe maximum length sequence[J].Computer Application Research, 2012,29(10):3629-3631.

[5]徐宗本.計算智能—模擬進(jìn)化計算 [M].北京:高等教育出版社, 2005.

[6] Sun J,Feng B,Xu W B. Particle swarm optimization with particles having quantum behavior[C]//Proc of the IEEE Congress on Evolutionary Computation,2004:325-331.

[7]賀毅朝,王彥祺,劉建芹. 一種適于求解離散問題的二進(jìn)制粒子群優(yōu)化算法[J].計算機(jī)應(yīng)用與軟件,2007,24(1):157-159.

HE Yi-chao, WANG Yan-qi, LIU Jian-qin. A kind of suitable for solving the problem of discrete binary particle swarm optimization algorithm[J]. Computer Applications and software, 2007,24(1):157-159.

[8]康燕,孫俊,須文波. 具有量子行為的粒子群優(yōu)化算法的參數(shù)選擇[J].計算機(jī)工程與應(yīng)用,2007,43(23):40-42.

KANG Yan, SUN Jun, XU Wen-bo. With the behavior of quantum particle swarm optimization algorithm of parameter selection[J].Computer Engineering and Application, 2007,43(23):40-42.

Optimization of binary sequences based on evolutionary algorithm

LI He, LI Qi, GAO Jun-ping, LEI Ming-ran
（School of Information Engineering, Hebei University of Technology, Tianjin 300401, China）

Binary sequences with good aperiodic autocorrelation features are widely used in the field of radar,communication synchronization. Genetic algorithm, particle swarm optimization and quantum particle swarm optimization algorithm are compared and analyzed in this paper. The new search algorithm of binary sequences with good aperiodic autocorrelation properties are designed based on three evolutionary algorithms. Research results show that the search ability of particle swarm algorithm is better than genetic algorithm. Quantum particle swarm optimization algorithm has less parameters, easy to control, and the better good optimization results were obtained.

binary sequence; aperiodic autocorrelation; genetic algorithm; particle swarm optimization algorithm; quantum particle swarm algorithm

TP301.6

A

1674-6236(2014)14-0159-03

2013–09–23 稿件編號：201309170

河北省自然科學(xué)基金資助項目（F2012 202 116）

李 鶴(1988—)，女，河北辛集人，碩士。研究方向：信息與編碼理論。