基于進化計算的二元序列優化算法研究

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

（河北工業大學 信息工程學院，天津 300401）

基于進化計算的二元序列優化算法研究

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

（河北工業大學 信息工程學院，天津 300401）

具有良好非周期自相關特性二元序列在通信同步、雷達等領域具有廣泛的應用。通過對遺傳算法、粒子群算法與量子粒子群算法三種進化算法進行對比分析，設計了具有良好非周期自相關特性的二元序列的搜索算法。研究結果表明，粒子群算法的搜索能力優于遺傳算法，而量子粒子群算法具有參數少，易于控制的優點，取得了較好的優化結果。

二元序列；非周期自相關；遺傳算法；粒子群算法；量子粒子群算法

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

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

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

1 二元序列及其相關概念

1.1 二元序列及其非周期自相關函數

設二元序列 的長度為 ，其非周期自相關函數表示如下（其中τ≥ 0）：

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

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

1.2 巴克碼簡介

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

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

表1 經典 Barker序列Tab.1 Classic Barker sequence

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

2 基于PSO和QPSO的二元序列優化

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

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

在PSO算法中，每個優化問題的潛在解都可以想象成 維搜索空間的一個點，也就是“粒子”。粒子在搜索空間內以一定的速度飛行，這個速度根據它本身的飛行經驗和同伴的飛行經驗來動態調整[7]。

利用PSO算法優化二元序列的具體過程如下：

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

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

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

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

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

其中,i=1,2…n, d==1,2…D，ω為慣性權重，加速PSO的收斂速度，C1、C2學習因子為正常數，r1,r2為 [0,1]之間符合正態分布的一個偽隨機數。

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

5 ) 達到最大迭代次數后，停止迭代，輸出結果。否則轉到步驟2）。

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

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

從表2中可以看出，利用GA算法和PSO算法搜索出的序列PSL值都隨著序列長度的增加而增大，PSO算法較GA算法搜索能力略有改善。但是出現了不穩定的情況，如序列長增至92時，PSL值突變為8，破壞了持續增大的規律，這就要求對PSO算法進行改進，得到結果更穩定、性能更優化的二元序列。

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

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

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

因此，粒子的進化方程為：

其中，u表示 [0,1]之間符合正態分布的一個偽隨機數；a表示收縮擴張系數，能夠控制算法的收斂速度。

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

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

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

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

3 結 論

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

[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]王慶海,袁運能,毛士藝.泛Barker序列設計[J].系統工程與電子技術,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].計算機應用研究,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]徐宗本.計算智能—模擬進化計算 [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].計算機應用與軟件,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]康燕,孫俊,須文波. 具有量子行為的粒子群優化算法的參數選擇[J].計算機工程與應用,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

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

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