基于遗传-禁忌混合算法的低相关区序列集搜索方法

李明阳，柏 鹏，彭卫东，李淑婧

(1.空军工程大学装备管理与安全工程学院，陕西西安710051;2.空军工程大学综合电子信息系统与电子对抗技术研究中心，陕西西安710051)

0 引言

具有较好相关特性的序列集在扩频通信［1］、多输入多输出(multiple input multiple output，MIMO)雷达［2］等系统中具有重要应用价值。文献［3］基于进化机制生成了具有较低副峰的非周期二相序列，文献［4-5］分别利用遗传算法、粒子群算法、蜂群算法和模拟退火算法等生成适用于MIMO雷达的多相码。研究表明，在整个移位周期范围内，自相关副峰(autocorrelation sidelobe peak，ASP)和互相关峰(cross-correlation peak，CP)不能同时得到有效抑制［6］。文献［7］提出的零相关区(zero correlation zone，ZCZ)序列不要求在整个移位周期范围内具有理想的ASP和CP，相对于完全正交序列具有更加灵活的参数。文献［8］将零相关区序列应用于MIMO雷达系统，获得较高的距离分辨率和探测性能。类似地，低相关区序列集要求在一定范围内具有较低的ASP和CP。LCZ和ZCZ序列的构造方法通常包括最优化搜索方法［9-11］、交织方法［12，13］、代数方法［14］等。交织方法和代数方法依然受到较为严格的参数限制，无法生成任意长度的LCZ/ZCZ序列，最优化搜索方法虽然不能生成理论最优或次优的序列，但可选参数更灵活。

本文将遗传算法和禁忌算法相结合，提出一种低相关区序列集的智能搜索方法。该方法将禁忌算法嵌入到遗传算法的变异操作中，设置变异位为禁忌对象，防止某位频繁变异。进化过程中，根据当前全局最小的最大ASP和最大CP动态调节交叉点，使交叉点数随全局ASP和CP的逐渐缩小而减少，从而在进化前期保证进化速度，在进化后期保证收敛。每一轮进化前检验序列的移位等价性，剔除移位等价序列，从而提高种群多样性，防止早熟。最后，通过数值仿真证明了本文方法的有效性。

1 基本定义和定理

(1)式中，*表示对复数共轭运算。

类似地，序列集的周期相关函数定义为

如果i=j，(1)式和(2)式称为序列xi的非周期/周期自相关函数，否则(1)式和(2)式称为序列xi和xj的非周期/周期互相关函数。

定义2 对于定义1中的序列集X，如果X中任意2个序列相关函数满足如下条件

则称X为低相关区长度为ZLC的LCZ(P，L，M，ZLC，σa，σc)序列集。

(3)式中:P表示序列集的进制;σa和σc分别表示序列集的最大ASP和最大CP。

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

2.1 问题的优化模型

在LCZ序列集参数P，L，M和ZLC固定的条件下，σa和σc的绝对值越小，LCZ序列集的相关特性越好。以上参数固定条件下，搜索σa和σc的绝对值较小的问题可以归结为求使(4)式中目标函数E最小的序列集X。

(4)式中，ωa，ωc为加权系数。如果 σa≠ σc，且σc/σa=λ，则取系数ωa=λ，ωc=1。

2.2 遗传-禁忌混合算法搜索步骤

使(4)式最小化的序列集的求解是一个多元非线性NP问题，如果采用穷举法，其计算量为2MLP。对于NP问题，一种可行的方法是利用智能算法获得近似最优解，遗传算法和禁忌算法都是求解NP问题的启发式算法。其中，遗传算法具有较好的全局搜索能力，禁忌算法对初值的依赖较大，但是局部“爬坡”能力很强，将二者结合可以利用遗传算法实现粗搜索，利用禁忌算法获得更精确搜索。文献［15］利用遗传－禁忌混合算法获得了相对于单纯遗传算法［10］更优的搜索性能，但是该方法只是将遗传算法和禁忌算法进行简单的级联，不能充分发挥2种算法的优点。因为遗传算法的局部搜索能力主要源自变异操作，所以本文中将禁忌算法嵌入到遗传的变异操作中，将所有一点变异作为邻域，在该邻域内用禁忌算法搜索，从而提高变异的局部搜索能力。基于遗传-禁忌混合算法LCZ序列集搜索方法的实现流程如图1所示。

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

基于遗传-禁忌混合算法LCZ序列集搜索方法实现步骤和关键技术如下。

1)编码。采用P进制级联编码，用一个长度为ML的P进制序列表示一个序列集X。

2)初始化。假设种群数量为pop_size，则随机产生pop_size个编码序列，预先设定交叉概率pc和变异概率pm。

3)遗传操作。

①选择。假设第l个编码序列的目标函数为El，按照轮盘赌选择法，第l个编码序列依概率遗传到下一代。

②交叉。从种群中任意选择2个编码序列，假设2个相关序列对应位相等的位数为n+，对应位不等的位数为n－，对于P元序列最多需要变化(n+－n－)/(2lb P)位则有可能获得最小的相关值。所以，从种群中任意选择2个编码序列，随机选择n个交叉点进行多点交叉。其中

③禁忌搜索。将种群中每个子序列的所有一点变异作为该序列的邻域，利用禁忌算法进行搜索。设置变异点为禁忌对象，禁忌长度为LT。如果变异不被禁忌，则根据当前序列目标函数和变异序列目标函数的大小判断是否变异。当且仅当禁忌表中对象的目标函数小于当前全局最优解时，对当前禁忌解禁，更新禁忌表。

4)评估种群。利用(4)式评估种群。

5)结束判断。智能算法收敛后目标函数将不再变化，所以可以假定目标函数保持不变后算法收敛。定义(4)式中目标函数跳变间隔为目标函数2个不相等值间隔的进化代数，设定跳变间隔的最大值，当超过该最大值仍不跳变则认为已经收敛到最优解。根据经验，本文中设定最大跳变间隔为进化代数的1/10。

6)剔除移位等价序列。为了消除移位等价序列［16］对种群多样性的破坏，本文设计了快速剔除移位等价序列的方法。根据FFT变换的性质，序列及其循环移位序列具有相同的FFT包络，所以对种群矩阵进行一维FFT变换，对相同包络的序列只保留其中一个，然后将保留编码序列组成新种群。

3 数值仿真及分析

选择参数，设定M=4，L=40，P=4，低相关区Z=40，搜索非周期序列集，种群大小设为pop_size=200，进化代数为50，交叉概率为pc=0.3和变异概率为pm=0.03，禁忌长度为LT=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 非周期自相关函数Fig.2 Aperiodic auto correlation function

序列集的相关副峰和互相关峰值最大值为0.175，相比文献［15］中序列集的相关副峰和互相关峰值最大值为0.215 1，多址干扰更小。

设定M=1，其余参数不变，进化所得到的序列为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自相关函数的最大副峰为0.05，可以在通信、定位系统中作为多相测距、同步码使用。图4为序列x的自相关函数曲线。

设定P=2，L=40，Z=40，搜索周期低相关区序列集，其余参数不变。进化所得到的序列集，按照16进制表示为

图3 非周期互相关函数Fig.3 Aperiodic cross correlation function

图4 非周期自相关函数Fig.4 Aperiodic auto correlation function

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

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

在低相关区内，序列集Y的周期最大ASP和最大CP都为0.2。序列集X和Y的部分相关函数曲线如图5所示。

图5 不同低相关区序列的相关值对比Fig.5 Correlation comparison of different LCZ sequences

对比Z=40和Z=20时序列集的相关函数值，可以发现低相关区缩小后，最大ASP和最大CP由0.3降为0.2。所以适当地降低低相关区，可以一定程度上抑制序列自身和序列间干扰。

4 结束语

本文提出基于一种遗传－禁忌混合算法的多相低相关区周期序列集的搜索方法。遗传算法具有全局搜索能力，但是局部搜索性能相对较差;禁忌算法局部搜索能力很强，但是对初始解依赖较大。将二者结合可以取长补短，有效提高序列集搜索性能。

文中利用该方法对周期、非周期，二元以及多元序列集进行搜索，获得了较好的效果。该方法具有一定的通用性，只需要相应改变目标函数即可满足不同序列集的搜索需求。该方法对于QS－CDMA通信系统、MIMO雷达系统和测距系统中扩频序列的设计具有一定理论意义和实用价值。

［1］曾凡鑫.适用于AS-CDMA系统的具有零(低)相关区的二元序列的数量扩张［J］.重庆邮电大学学报:自然科学版，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，FAN 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］朱志华，叶飞，辛明军，等.基于猫群优化算法的2n周期优秀二元序列的研究与分析［J］.电子与信息学报，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］金明，廖桂生，李军.基于遗传算法的类零相关多相码设计［J］.系统工程与电子技术，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，FAN 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，FAN 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雷达正交多相码设计［J］.系统工程与电子技术，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.