计算周期序列k-错线性复杂度的混合遗传算法

牛志华， 苑 璨， 孔得宇

(上海大学 计算机工程与科学学院，上海 200444)

周期序列s的k-错线性复杂度定义为：当改变s的1个周期中至多k位之后，得到的所有序列的线性复杂度中的最小值.一个良好的序列需具有较大的线性复杂度和k-错线性复杂度.具有低线性复杂度的序列在密码学上是弱的，因为通过使用Berlekamp-Massey (BM)算法[1]，获得任何两倍于其线性复杂度的连续比特，就可以有效地恢复整个序列.同样，具有低的k-错线性复杂度的序列也较弱，因为如果找到相应的线性递归关系，该序列就容易受到攻击.

针对序列的线性复杂度及其稳定性，即序列线性复杂度和k-错线性复杂度指标，国内外学者做了大量研究.对于2n-周期的序列， Games等[2]提出了计算序列线性复杂度的快速算法，其时间复杂度远低于通用的BM算法，文献[3-4] 基于Games-Chan算法，研究了序列k-错线性复杂度的分布，而文献[5] 针对固定不变的k-错线性复杂度，研究了周期序列的分布.对于pn-周期的序列，文献[6-7]研究了序列的k-错线性复杂度谱，文献[8]提出了计算错误序列的算法.对于2pn-周期的序列，文献[9]提出了计算序列k-错线性复杂度的算法.更多关于线性复杂度和k-错线性复杂度的研究成果见文献[10-15].目前，有很多算法可以计算周期为2n、pn、2pn的序列的k-错线性复杂度，但没有算法可以计算其他任意周期序列的k-错线性复杂度.因此，设计一个能计算任意周期序列的k-错线性复杂度的通用算法非常关键.

k-错线性复杂度的本质是求线性复杂度最小值的优化问题，而遗传算法很适合求解优化问题.Alecu等[16]首次将遗传算法应用到二元序列复杂度的初步探索中，利用遗传算法来近似计算周期为2n的二元序列的k-错线性复杂度，能够计算周期为32的二元序列的5-错线性复杂度，且实验结果比准确值平均高19.5%.

本文设计了一种混合遗传算法来计算二元有限域GF(2)上给定序列的k-错线性复杂度的近似值.采用二进制编码、轮盘赌选择和最优保留策略、两点交叉、单点随机变异、自适应调整交叉和变异概率，并行计算每代种群个体的适应度，以提高算法效率，并对每代的最佳个体进行模拟退火避免收敛于局部最优解.使用本文改进的遗传算法，计算周期为256的二元序列的8-错线性复杂度，实验值仅比准确值高8%.因此，在k值较小且可以接受微小误差的情况下，即可使用本文的混合遗传算法计算任意周期序列的k-错线性复杂度.

1 可行性分析

本节首先介绍线性复杂度和k-错线性复杂度，然后分析使用遗传算法计算序列的k-错线性复杂度的可行性.

定义1设s={s0,s1,…}为q元有限域GF(q)上的序列，若对任意的i，有si=si+N，则s是周期为N的序列.如果GF(q)上的周期序列s满足sj+c1sj-1+…+cLsj-L=0 (j≥L)，其中L是正整数，c1,c2,…,cL在GF(q)中，则称s是一个L阶线性递归序列，满足上式的最小的正整数L称为该递归序列的线性复杂度，记为LC(s).

周期序列的线性复杂度是序列密码的重要评价指标.然而，线性复杂度很高并不一定能保证序列的安全，即当改变这些序列周期的少数几位时，其线性复杂度大幅下降.因此，学者们提出了线性复杂度稳定性的评价指标，即k-错线性复杂度.

定义2周期为N的序列s的k-错线性复杂度为，当改变s的一个周期中至多k(0≤k

LCk(s)=min{LC(s+e)|wH(e)≤k}

(1)

式中：e为周期为N的序列，常被称为错误序列、错误类型；wH(e)为序列e的1个周期中不为0的元素个数.显然，至少存在1个错误序列e，使得LC(s+e)=LCk(s)，称使得(s+e)的线性复杂度等于k-错线性复杂度的错误序列e为k-错线性复杂度对应的错误序列.

序列的k-错线性复杂度，即所有的错误序列e加上原序列s的线性复杂度LC(s+e)的最小值是1个典型的求最小值的单目标优化问题.而求解优化问题是遗传算法的1个非常重要且擅长的领域，问题的关键为确定“优”的标准.设计相应的适应度函数，使序列(s+e)的线性复杂度越小时，适应度越高，序列越优秀.对于一般序列，可以用BM算法计算序列(s+e)的线性复杂度；对于特殊周期的序列，如果有计算线性复杂度的算法，可以用其定义适应度函数来判断(s+e)的适应性.因此，采用遗传算法近似计算序列的k-错线性复杂度在理论上是可行的.

2 标准遗传算法计算k-错线性复杂度时出现的问题

遗传算法是基于达尔文的进化论和孟德尔的群体遗传学说，模拟自然界的生物进化过程的一种随机搜索和全局优化算法[16].它针对一个种群，按照适者生存的原理，按照适应度大小挑选个体，并进行交叉和变异操作，产生新一代种群，新种群比前代种群更适应环境，如此反复进行直到满足优化准则或者达到最大遗传代数，该过程得到的最优结果即为问题的近似最优解.本节介绍使用的标准遗传算法和其中出现的问题.

算法1标准遗传算法(GA)

(1) 初始化：序列s的第一个周期sN={s0,s1,…,sN-1}，k，PS，MAXGEN，POP(0)，GEN=0；

(2) 计算POP(0)中每个个体的适应度；

(3) 判断GEN >MAXGEN 是否成立，若成立则转(9)；

(4) 使用轮盘赌从POP(GEN)中选择出POP(GEN+1)；

(5) 在POP(GEN+1)中按照交叉概率Pc执行单点交叉；

(6) 在POP(GEN+1)中按照变异概率Pm执行单点随机变异；

(7) 计算POP(GEN+1)中每个个体的适应度；

(8) GEN=GEN+1，转(3)；

(9) 输出序列s的近似k-错线性复杂度 LCk(s)，结束.

其中：PS为种群大小；MAXGEN为最大生成代数；POP(i)为第i代种群；GEN为变量；Pc为[0,1]区间的一个值，表示交叉概率；Pm为[0,1]区间的一个值，表示变异概率. 在上述算法中，PS=400, MAXGEN=500,Pc=0.6,Pm=0.03.

然而，使用算法1来计算k-错线性复杂度时，存在以下几个问题：

(1) 针对不同的优化问题，需要反复实验来确定Pc和Pm，并且很难找到适应于每个问题的最佳值；

(2) 伴随着N的增加，编码长度也在不断增加，导致算法效率急剧下降；

(3) 实验表明，标准遗传算法容易快速收敛于局部最优解.

3 基于遗传算法的计算任意周期二元序列的k-错线性复杂度的改进算法

针对标准遗传算法中出现的如何确定Pc和Pm的最佳值问题，本文采用自适应方法来调整Pc和Pm的值，在保证群体多样性的同时，保证遗传算法的收敛性.对于算法效率的问题，采用并行计算来提高算法的性能，使N、k增加时，能够减少计算时间，提高效率.将遗传算法和模拟退火算法相结合，提高算法的全局和局部搜索能力，加速收敛并避免早熟，解决标准遗传算法常获得局部最优解的问题.

3.1 编码

遗传算法通常采用二进制编码，浮点数编码和符号编码.本文研究的输入序列s在GF(2)上，对染色体使用二进制编码较为方便.二进制编码将问题的可能解映射成有限个二进制符号组成的符号串，即定义1个染色体为任何可能的错误模式：e∈GF(2)n,wH(e)≤k.最佳的染色体是在改变原始序列的最多k位之后，引起线性复杂度下降最大的染色体.

3.2 适应度函数

遗传算法在进化过程中以适应度函数作为依据进行优胜劣汰进行选择，基本不利用外部信息，因此适应度函数的选择直接影响到遗传算法的收敛速度和能否找到最优解.

根据k-错线性复杂度的定义，序列的k-错线性复杂度为其改变至多k位能得到线性复杂度的最小值.因此，将目标序列s与错误序列e相加得到改变后的序列(s+e)，计算其线性复杂度，该值越小，说明e的适应度越高.定义适应度函数为

f(e)=Cmax-LC(s+e)

(2)

式中：Cmax是序列s可能出现的最大线性复杂度的值，用序列s的周期N代替.本节采用BM算法(算法2)计算序列(s+e)的线性复杂度.

BM算法可用于计算任意域上的周期序列的线性复杂度和特征多项式[1].根据BM算法，如果1个序列的线性复杂度为LC(s)，那么只需知道该序列的任意长度为2LC(s)的连续比特即可恢复出全部的序列.

算法2BM算法

(1) 初始化：sN={s0,s1,…,sN-1},P(X)=1,P′(X)=1,LC=0,m=-1,d′=1,t=0；

(2) 判断t>N-1是否成立,若成立，则转(9)；

(4) 判断d≠0是否成立，若成立则转(6)；

(5)t=t+1，转(2)；

(6)T(X)=P(X),P(X)=P(X)-d(d′)-1P′(X)Xt-m；

(7) 判断2LC>t是否成立，若成立则转(5)；

(8) LC=t+1-LC,m=t,P′(X)=T(X),d′=d，转(5)；

(9) 输出LC和P(X)，结束.

其中：sN为序列s的一个周期；LC为s的线性复杂度；P(X)为特征多项式；其他的变量均为辅助的中间变量.

3.3 选择、交叉、变异算子

选择算子模拟自然界中优胜劣汰、适者生存的自然法则，其目的在于为下一代保留适应度高的优秀基因，使得种群进化朝着最优解的方向进行，加速收敛速度，同时也要保证种群的多样性.所以我们使用轮盘赌和最优保存策略相结合的选择算子.

交叉算子模拟了自然界生物体的基因重组，体现了信息交换的思想.通过两个染色体的交叉组合，来产生新的优良个体，从而搜索空间中新的点.本文使用两点交叉，因为在单点交叉中，染色体末端的良好基因总是被交换，不利于保留优良基因.

若只有选择和交叉算子，遗传算法就无法在初始基因组合以外的空间进行搜索，进化过程很容易陷入局部最优解而导致进化过程终止，不能得到全局最优解.而变异算子是模拟生物在自然遗传环境中由各种偶然因素引起基因突变的过程，以一个很小的变异概率随机地改变遗传基因(染色体的符号串的某一位)的值.本文使用基本位变异算子，提高种群的多样性，防止早熟.

3.4 自适应算子

标准遗传算法中，交叉概率Pc和变异概率Pm在进化过程中固定不变，而它们是影响遗传算法性能的关键，直接影响算法的收敛性.如果Pc太大，种群虽然更容易产生新个体，但是优良个体在种群中保留率也会降低；如果Pc太小，搜索效率会下降甚至停滞不前.如果Pm太大，遗传算法成为纯粹的随机搜索算法；如果Pm太小，则不易产生新的个体结构.

为了提高遗传算法的收敛性，达到全局最优解，采用Srinivas等提出的自适应遗传算法[17]，使Pc和Pm的值随着适应度的变化而自动改变.当种群的整体适应度趋于一致或者趋于局部最优时，增大Pc和Pm；当种群的整体适应度比较分散时，降低Pc和Pm.同时，对于适应度高于平均值的个体，降低Pc和Pm，保证其进入下一代；对于适应度低于平均值的个体，提高Pc和Pm，以将其淘汰.此操作使得自适应的Pc和Pm能够提供相对于某个解的最佳Pc和Pm.因此，自适应遗传算法在保持种群多样性的同时，也保证了遗传算法的收敛性.

Pc和Pm按照如下公式进行计算：

Pc=

(3)

Pm=

(4)

式中：Pc1=0.6,Pc2=0.3,Pm1=0.1,Pm2=0.01；f为需要变异个体的适应度；f′为两个需要交叉操作的个体中适应度较大的个体适应度；favg为种群的平均适应度；fmax为种群中的最大适应度.

3.5 并行算子

初步实验说明，当N较大时，标准遗传算法的效率会下降.由于算法的运行时间主要在于个体适应度的计算，而遗传算法的特性在于个体之间相互独立，个体的适应度可并行计算，划分的不同种群之间也可以相互独立的进行演化，所以使用并行遗传算法来加速搜索过程，以减少计算时间.

使用OpenMP实现并行遗传算法[18].程序开始执行时，仅为1个单线程程序，当需要并行计算适应度函数时，会形成1个线程组，多个线程并行执行计算适应度函数的代码.最后，到所有线程都执行完并行代码后，回归主线程继续执行至结束.此操作不仅降低了并行程序设计的难度，还提高了算法的收敛速度.

3.6 模拟退火算子

标准遗传算法通常容易产生早熟现象、局部搜索能力较差等问题，而模拟退火算法具有较强的局部搜索能力，并能使搜索过程避免陷入局部最优解[19].所以在遗传算法中引入模拟退火算子，提高算法的全局和局部搜索能力，加速收敛并避免早熟.

模拟退火(SA)是一种基于Monte Carlo迭代法的启发式随机搜索算法.SA来源于对固体物质的退火降温过程中的热平衡问题的模拟和随机搜索优化问题，以找到全局最优解或近似全局最优解[20].在搜索最优解的过程中，SA除了可以接受最优解外，还有1个随机接受准则(Metropolis准则)，可以有限度地接受恶化解，并且接受恶化解的概率慢慢趋向于0，使得算法有可能从局部最优中跳出，找到全局最优解，保证算法的收敛.

将遗传算法和模拟退火算法相结合，对每一代最优个体执行模拟退火操作.步骤如下：

(1) 初始化遗传算法，初始化退火温度T0=LC(s).

(2) 对种群进行交叉、变异等操作，选出本代最优个体.

(3) 在温度TK下执行操作：产生新的可行解e′(e′是e相应的目标函数值)； 计算新解的评价函数f(e′)和旧解的评价函数f(e)的差值：Δf=f(e′)-f(e)；依照概率 min{1,exp(-Δf/TK)}>random[0,1]接收新解，random[0,1]是1个 [0,1] 区间内的随机数；按一定的方式，缓慢降低温度，定义降温函数为TK+1=αTK，K=K+1(α为降温系数，为1个小于1的正数).

(4) 执行最优保留算子，若满足收敛条件，则结束；否则转(2).

3.7 混合遗传算法

使用轮盘赌和最优保留、两点交叉代替单点交叉、单点随机变异、自适应交叉和变异概率，对每代的最佳个体进行模拟退火以保证不陷入局部最优解，并行编程以提高效率.

算法3混合遗传算法(IGA)

(1) 初始化：sN={s0,s1,s2,…,sN-1}，k，PS，MAXGEN，POP(0)，GEN=0；

(2) 根据式(2)并行计算POP(0)中每个个体的适应度；

(3) 判断 GEN>MAXGEN 是否成立，若成立则转(11)；

(4) 使用轮盘赌从POP(GEN)中选择出POP(GEN+1)；

(5) 在POP(GEN+1)中按照式(3)得到的自适应交叉概率Pc执行两点交叉；

(6) 在POP(GEN+1)中按照式(4)得到的自适应变异概率Pm执行单点随机变异；

(7) 根据式(2)并行计算POP(GEN+1)中每个个体的适应度；

(8) 最优选择；

(9) 对本代最优个体执行模拟退火算子；

(10) GEN=GEN+1，转(3)；

(11) 输出LCk(s)，结束.

4 实验与分析

本节首先使用混合遗传算法(算法3)与标准遗传算法(算法1)对周期为2n的序列进行数值实验，并对两个算法进行重复实验，对比两个算法的结果，说明混合遗传算法比标准遗传算法在误差率和算法效率方面更优秀.然后展示2n周期序列的k-错线性复杂度实验值和准确值的对比图，说明混合遗传算法的误差率较低，并挑选几个任意周期序列的k-错线性复杂度实验图说明本文设计的混合遗传算法可以计算非特殊周期序列的k-错线性复杂度.

实验设定PS=200，MAXGEN=200以及PS=400，MAXGEN=500，使用混合遗传算法IGA(算法3)，针对周期2n的不同取值进行重复实验，分别计算序列的6-错线性复杂度，统计算法的准确率和运行时间，结果如表1所示.表中：A为实验值比准确值高出的百分比，即误差率；T为算法的运行时间.

表1 PS=200，MAXGEN=200和PS=400，MAXGEN=500时，混合遗传算法的结果

Tab.1 Results of IGA at PS=200，MAXGEN=200 and PS=400，MAXGEN=500

NkPSMAXGENAIGA/%TIGA/s6462002000.6816464005000.52612862002000.66312864005000.571625662002000.551025664005000.1250

对于不同周期序列的6-错线性复杂度，当 PS=400，MAXGEN=500时，尽管运行时间长，但误差率均比PS=200，MAXGEN=200时低.在尽量保证算法准确度的情况下，下文实验选取 PS=400，MAXGEN=500的组合参数，针对周期2n和k的不同取值进行重复实验，每组实验随机生成400个序列，统计算法的准确率和运行时间，结果如表2和表3所示.其中IGA为混合遗传算法(算法3)的结果，GA表示标准遗传算法(算法1)的结果.

表2 混合遗传算法计算k=6,7,8的结果

表3 标准遗传算法计算k=6,7,8的结果

标准遗传算法中，Pc和Pm设置为固定值，本文通过多次实验对比，发现Pc=0.6,Pm=0.03时，实验结果更准确，故后文的实验使用此参数组合.

在IGA实验中，采用4个线程并行计算的运行时间均比采用GA所需的时间更短，效率更高.在程序运行中，使用BM算法计算每个个体的适应度占据了大部分时间，而每个个体之间是相互独立的，在计算适应度时能够并行执行，极大地减少了运行时间.在硬件环境支持的情况下，线程数越多，运行时间越短，效率越高.当PS=200,MAXGEN=200时，计算k-错线性复杂度，64位的序列通常只需要1 s，128位的序列需要3 s，256位的序列需要10 s.随着种群规模和迭代代数的增加，PS=400,MAXGEN=500，虽然运行时间在增加，但算法的误差率在不断减小.

当k<8时，IGA有较小的误差率，N=64时，误差率小于8%；N=128时，误差率小于3%；N=256时，误差率小于2%.当k>8时，误差率变大，但经常使用传统算法研究的多是1-错，2-错线性复杂度，而对于8-错及更大的k-错线性复杂度，其研究难度较大，同时当k值很大时，k-错线性复杂度的研究意义不大.实验证明，k值较小时，混合遗传算法的效率更高，误差率更低，实验结果更加接近准确值.

下面分别展示不同的2n周期序列的k-错线性复杂度的实验值和准确值的对比图.图1～3分别为n=6，7，8时，即N=64，128，256时，3个序列s1、s2、s3的k-错线性复杂度情况.可以看出，当k<8时，本文混合遗传算法的误差率较低，实验值与准确值很接近，当k较大时，算法慢慢收敛，实验值与准确值的误差变大.

s1={011000111100110101010011101110011001110 1111000101100011111100000}，N=64

图1 序列s1的k-错线性复杂度实验值和准确值对比

s2={111001001011110001101100000011010110101 11110110110111111011100110101001011100101011 10001100010001010000001110001101000000101001 1}，N=128

图2 序列s2的k-错线性复杂度实验值和准确值对比

s3={01011011011010000010011101010110110010 11010000011101011110010000010110110111011011 10101110011100110101010100100101111011011101 00101000101100000001100000111111010001111110 01100001110011010111010101111001100010010011 001010011111100001000011000101111000011010}，N=256

图3 序列s3的k-错线性复杂度实验值和准确值对比

对比文献[16]的实验结果，周期为32的二元序列的5-错线性复杂度的实验结果比准确值平均高19.5%.而本文算法可以计算周期为256的二元序列的8-错线性复杂度，其实验值仅比准确值高8%.因此，本文算法不仅使可计算的N、k增加，还提高了算法的准确性和效率.

前文的实验之所以采用N=64，128，256，是因为我们可以计算这些周期序列的准确的k-错线性复杂度，从而可以对比实验结果，计算误差率，说明算法准确性的提高.而我们的算法可以计算任意周期的二元序列的k-错线性复杂度，所以下面给出两条任意周期序列的k-错线性复杂度的实验图.图4和5分别为N=200的序列s4和周期N=500的序列s5的k-错线性复杂度的实验图.

s4={01000111110011000010001011011101100000 11100110101111010000001011000110011110001100 10101110011111011011011110011100010100011101 10110001101110101111011100101110100001010101 001100010100011111001000001110}，N=200

图4 序列s4的k-错线性复杂度实验值

s5={10101011001000011110110010100000000010 10110001011001110001010001111001010111000101 01011000000101110100000001111100110011011000 11001000000011001111110000000010100010010111 01110010101010111111011000000011100010000110 11010010010000011001011100010100001000011011 01101101111101011110000010110100110100000100 10111110000000000001101011011001100110110100 11110100010001000101111110110010000101010111 00011110100110111000001101100010111110100100 00101011100010000000111111100100010001011010 1110000111010010101100}，N=500

图5 序列s5的k-错线性复杂度实验值

从图4和5可以看出，非2n周期序列的k-错线性复杂度实验值变化规律和2n周期序列的k-错线性复杂度实验值变化规律类似.即在k值较小且可以接受微小误差的情况下，可以计算任意周期序列的k-错线性复杂度.

5 结语

使用遗传算法计算在有限域上给定周期序列的k-错线性复杂度时，针对标准遗传算法所存在的问题，对其进行改进，设计了一种混合的遗传算法.为了保证遗传算法的收敛性，加速寻优并避免陷入局部最优解，使用轮盘赌和精英选择、自适应调整交叉和变异概率，进行两点交叉和单点随机变异操作，并行计算每代个体的适应度，并对每代的最优个体进行模拟退火操作.结果表明，当k较小时，混合遗传算法的误差率小于8%，同时提高了遗传算法的寻优性能和运行效率.因此，在k值较小且可以接受微小误差的情况下，可以使用本文设计的混合遗传算法来计算任意周期序列的k-错线性复杂度.