李 鹤，李 琦，高军萍，雷明然

（河北工业大学 信息工程学院，天津 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—)，女，河北辛集人，硕士。研究方向：信息与编码理论。