牛志華， 苑 璨， 孔得宇

(上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院，上海 200444)

周期序列s的k-錯線性復(fù)雜度定義為：當(dāng)改變s的1個周期中至多k位之后，得到的所有序列的線性復(fù)雜度中的最小值.一個良好的序列需具有較大的線性復(fù)雜度和k-錯線性復(fù)雜度.具有低線性復(fù)雜度的序列在密碼學(xué)上是弱的，因?yàn)橥ㄟ^使用Berlekamp-Massey (BM)算法[1]，獲得任何兩倍于其線性復(fù)雜度的連續(xù)比特，就可以有效地恢復(fù)整個序列.同樣，具有低的k-錯線性復(fù)雜度的序列也較弱，因?yàn)槿绻业较鄳?yīng)的線性遞歸關(guān)系，該序列就容易受到攻擊.

針對序列的線性復(fù)雜度及其穩(wěn)定性，即序列線性復(fù)雜度和k-錯線性復(fù)雜度指標(biāo)，國內(nèi)外學(xué)者做了大量研究.對于2n-周期的序列， Games等[2]提出了計(jì)算序列線性復(fù)雜度的快速算法，其時間復(fù)雜度遠(yuǎn)低于通用的BM算法，文獻(xiàn)[3-4] 基于Games-Chan算法，研究了序列k-錯線性復(fù)雜度的分布，而文獻(xiàn)[5] 針對固定不變的k-錯線性復(fù)雜度，研究了周期序列的分布.對于pn-周期的序列，文獻(xiàn)[6-7]研究了序列的k-錯線性復(fù)雜度譜，文獻(xiàn)[8]提出了計(jì)算錯誤序列的算法.對于2pn-周期的序列，文獻(xiàn)[9]提出了計(jì)算序列k-錯線性復(fù)雜度的算法.更多關(guān)于線性復(fù)雜度和k-錯線性復(fù)雜度的研究成果見文獻(xiàn)[10-15].目前，有很多算法可以計(jì)算周期為2n、pn、2pn的序列的k-錯線性復(fù)雜度，但沒有算法可以計(jì)算其他任意周期序列的k-錯線性復(fù)雜度.因此，設(shè)計(jì)一個能計(jì)算任意周期序列的k-錯線性復(fù)雜度的通用算法非常關(guān)鍵.

k-錯線性復(fù)雜度的本質(zhì)是求線性復(fù)雜度最小值的優(yōu)化問題，而遺傳算法很適合求解優(yōu)化問題.Alecu等[16]首次將遺傳算法應(yīng)用到二元序列復(fù)雜度的初步探索中，利用遺傳算法來近似計(jì)算周期為2n的二元序列的k-錯線性復(fù)雜度，能夠計(jì)算周期為32的二元序列的5-錯線性復(fù)雜度，且實(shí)驗(yàn)結(jié)果比準(zhǔn)確值平均高19.5%.

本文設(shè)計(jì)了一種混合遺傳算法來計(jì)算二元有限域GF(2)上給定序列的k-錯線性復(fù)雜度的近似值.采用二進(jìn)制編碼、輪盤賭選擇和最優(yōu)保留策略、兩點(diǎn)交叉、單點(diǎn)隨機(jī)變異、自適應(yīng)調(diào)整交叉和變異概率，并行計(jì)算每代種群個體的適應(yīng)度，以提高算法效率，并對每代的最佳個體進(jìn)行模擬退火避免收斂于局部最優(yōu)解.使用本文改進(jìn)的遺傳算法，計(jì)算周期為256的二元序列的8-錯線性復(fù)雜度，實(shí)驗(yàn)值僅比準(zhǔn)確值高8%.因此，在k值較小且可以接受微小誤差的情況下，即可使用本文的混合遺傳算法計(jì)算任意周期序列的k-錯線性復(fù)雜度.

1 可行性分析

本節(jié)首先介紹線性復(fù)雜度和k-錯線性復(fù)雜度，然后分析使用遺傳算法計(jì)算序列的k-錯線性復(fù)雜度的可行性.

定義1設(shè)s={s0,s1,…}為q元有限域GF(q)上的序列，若對任意的i，有si=si+N，則s是周期為N的序列.如果GF(q)上的周期序列s滿足sj+c1sj-1+…+cLsj-L=0 (j≥L)，其中L是正整數(shù)，c1,c2,…,cL在GF(q)中，則稱s是一個L階線性遞歸序列，滿足上式的最小的正整數(shù)L稱為該遞歸序列的線性復(fù)雜度，記為LC(s).

周期序列的線性復(fù)雜度是序列密碼的重要評價(jià)指標(biāo).然而，線性復(fù)雜度很高并不一定能保證序列的安全，即當(dāng)改變這些序列周期的少數(shù)幾位時，其線性復(fù)雜度大幅下降.因此，學(xué)者們提出了線性復(fù)雜度穩(wěn)定性的評價(jià)指標(biāo)，即k-錯線性復(fù)雜度.

定義2周期為N的序列s的k-錯線性復(fù)雜度為，當(dāng)改變s的一個周期中至多k(0≤k

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

(1)

式中：e為周期為N的序列，常被稱為錯誤序列、錯誤類型；wH(e)為序列e的1個周期中不為0的元素個數(shù).顯然，至少存在1個錯誤序列e，使得LC(s+e)=LCk(s)，稱使得(s+e)的線性復(fù)雜度等于k-錯線性復(fù)雜度的錯誤序列e為k-錯線性復(fù)雜度對應(yīng)的錯誤序列.

序列的k-錯線性復(fù)雜度，即所有的錯誤序列e加上原序列s的線性復(fù)雜度LC(s+e)的最小值是1個典型的求最小值的單目標(biāo)優(yōu)化問題.而求解優(yōu)化問題是遺傳算法的1個非常重要且擅長的領(lǐng)域，問題的關(guān)鍵為確定“優(yōu)”的標(biāo)準(zhǔn).設(shè)計(jì)相應(yīng)的適應(yīng)度函數(shù)，使序列(s+e)的線性復(fù)雜度越小時，適應(yīng)度越高，序列越優(yōu)秀.對于一般序列，可以用BM算法計(jì)算序列(s+e)的線性復(fù)雜度；對于特殊周期的序列，如果有計(jì)算線性復(fù)雜度的算法，可以用其定義適應(yīng)度函數(shù)來判斷(s+e)的適應(yīng)性.因此，采用遺傳算法近似計(jì)算序列的k-錯線性復(fù)雜度在理論上是可行的.

2 標(biāo)準(zhǔn)遺傳算法計(jì)算k-錯線性復(fù)雜度時出現(xiàn)的問題

遺傳算法是基于達(dá)爾文的進(jìn)化論和孟德爾的群體遺傳學(xué)說，模擬自然界的生物進(jìn)化過程的一種隨機(jī)搜索和全局優(yōu)化算法[16].它針對一個種群，按照適者生存的原理，按照適應(yīng)度大小挑選個體，并進(jìn)行交叉和變異操作，產(chǎn)生新一代種群，新種群比前代種群更適應(yīng)環(huán)境，如此反復(fù)進(jìn)行直到滿足優(yōu)化準(zhǔn)則或者達(dá)到最大遺傳代數(shù)，該過程得到的最優(yōu)結(jié)果即為問題的近似最優(yōu)解.本節(jié)介紹使用的標(biāo)準(zhǔn)遺傳算法和其中出現(xiàn)的問題.

算法1標(biāo)準(zhǔn)遺傳算法(GA)

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

(2) 計(jì)算POP(0)中每個個體的適應(yīng)度；

(3) 判斷GEN >MAXGEN 是否成立，若成立則轉(zhuǎn)(9)；

(4) 使用輪盤賭從POP(GEN)中選擇出POP(GEN+1)；

(5) 在POP(GEN+1)中按照交叉概率Pc執(zhí)行單點(diǎn)交叉；

(6) 在POP(GEN+1)中按照變異概率Pm執(zhí)行單點(diǎn)隨機(jī)變異；

(7) 計(jì)算POP(GEN+1)中每個個體的適應(yīng)度；

(8) GEN=GEN+1，轉(zhuǎn)(3)；

(9) 輸出序列s的近似k-錯線性復(fù)雜度 LCk(s)，結(jié)束.

其中：PS為種群大小；MAXGEN為最大生成代數(shù)；POP(i)為第i代種群；GEN為變量；Pc為[0,1]區(qū)間的一個值，表示交叉概率；Pm為[0,1]區(qū)間的一個值，表示變異概率. 在上述算法中，PS=400, MAXGEN=500,Pc=0.6,Pm=0.03.

然而，使用算法1來計(jì)算k-錯線性復(fù)雜度時，存在以下幾個問題：

(1) 針對不同的優(yōu)化問題，需要反復(fù)實(shí)驗(yàn)來確定Pc和Pm，并且很難找到適應(yīng)于每個問題的最佳值；

(2) 伴隨著N的增加，編碼長度也在不斷增加，導(dǎo)致算法效率急劇下降；

(3) 實(shí)驗(yàn)表明，標(biāo)準(zhǔn)遺傳算法容易快速收斂于局部最優(yōu)解.

3 基于遺傳算法的計(jì)算任意周期二元序列的k-錯線性復(fù)雜度的改進(jìn)算法

針對標(biāo)準(zhǔn)遺傳算法中出現(xiàn)的如何確定Pc和Pm的最佳值問題，本文采用自適應(yīng)方法來調(diào)整Pc和Pm的值，在保證群體多樣性的同時，保證遺傳算法的收斂性.對于算法效率的問題，采用并行計(jì)算來提高算法的性能，使N、k增加時，能夠減少計(jì)算時間，提高效率.將遺傳算法和模擬退火算法相結(jié)合，提高算法的全局和局部搜索能力，加速收斂并避免早熟，解決標(biāo)準(zhǔn)遺傳算法常獲得局部最優(yōu)解的問題.

3.1 編碼

遺傳算法通常采用二進(jìn)制編碼，浮點(diǎn)數(shù)編碼和符號編碼.本文研究的輸入序列s在GF(2)上，對染色體使用二進(jìn)制編碼較為方便.二進(jìn)制編碼將問題的可能解映射成有限個二進(jìn)制符號組成的符號串，即定義1個染色體為任何可能的錯誤模式：e∈GF(2)n,wH(e)≤k.最佳的染色體是在改變原始序列的最多k位之后，引起線性復(fù)雜度下降最大的染色體.

3.2 適應(yīng)度函數(shù)

遺傳算法在進(jìn)化過程中以適應(yīng)度函數(shù)作為依據(jù)進(jìn)行優(yōu)勝劣汰進(jìn)行選擇，基本不利用外部信息，因此適應(yīng)度函數(shù)的選擇直接影響到遺傳算法的收斂速度和能否找到最優(yōu)解.

根據(jù)k-錯線性復(fù)雜度的定義，序列的k-錯線性復(fù)雜度為其改變至多k位能得到線性復(fù)雜度的最小值.因此，將目標(biāo)序列s與錯誤序列e相加得到改變后的序列(s+e)，計(jì)算其線性復(fù)雜度，該值越小，說明e的適應(yīng)度越高.定義適應(yīng)度函數(shù)為

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

(2)

式中：Cmax是序列s可能出現(xiàn)的最大線性復(fù)雜度的值，用序列s的周期N代替.本節(jié)采用BM算法(算法2)計(jì)算序列(s+e)的線性復(fù)雜度.

BM算法可用于計(jì)算任意域上的周期序列的線性復(fù)雜度和特征多項(xiàng)式[1].根據(jù)BM算法，如果1個序列的線性復(fù)雜度為LC(s)，那么只需知道該序列的任意長度為2LC(s)的連續(xù)比特即可恢復(fù)出全部的序列.

算法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是否成立,若成立，則轉(zhuǎn)(9)；

(4) 判斷d≠0是否成立，若成立則轉(zhuǎn)(6)；

(5)t=t+1，轉(zhuǎn)(2)；

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

(7) 判斷2LC>t是否成立，若成立則轉(zhuǎn)(5)；

(8) LC=t+1-LC,m=t,P′(X)=T(X),d′=d，轉(zhuǎn)(5)；

(9) 輸出LC和P(X)，結(jié)束.

其中：sN為序列s的一個周期；LC為s的線性復(fù)雜度；P(X)為特征多項(xiàng)式；其他的變量均為輔助的中間變量.

3.3 選擇、交叉、變異算子

選擇算子模擬自然界中優(yōu)勝劣汰、適者生存的自然法則，其目的在于為下一代保留適應(yīng)度高的優(yōu)秀基因，使得種群進(jìn)化朝著最優(yōu)解的方向進(jìn)行，加速收斂速度，同時也要保證種群的多樣性.所以我們使用輪盤賭和最優(yōu)保存策略相結(jié)合的選擇算子.

交叉算子模擬了自然界生物體的基因重組，體現(xiàn)了信息交換的思想.通過兩個染色體的交叉組合，來產(chǎn)生新的優(yōu)良個體，從而搜索空間中新的點(diǎn).本文使用兩點(diǎn)交叉，因?yàn)樵趩吸c(diǎn)交叉中，染色體末端的良好基因總是被交換，不利于保留優(yōu)良基因.

若只有選擇和交叉算子，遺傳算法就無法在初始基因組合以外的空間進(jìn)行搜索，進(jìn)化過程很容易陷入局部最優(yōu)解而導(dǎo)致進(jìn)化過程終止，不能得到全局最優(yōu)解.而變異算子是模擬生物在自然遺傳環(huán)境中由各種偶然因素引起基因突變的過程，以一個很小的變異概率隨機(jī)地改變遺傳基因(染色體的符號串的某一位)的值.本文使用基本位變異算子，提高種群的多樣性，防止早熟.

3.4 自適應(yīng)算子

標(biāo)準(zhǔn)遺傳算法中，交叉概率Pc和變異概率Pm在進(jìn)化過程中固定不變，而它們是影響遺傳算法性能的關(guān)鍵，直接影響算法的收斂性.如果Pc太大，種群雖然更容易產(chǎn)生新個體，但是優(yōu)良個體在種群中保留率也會降低；如果Pc太小，搜索效率會下降甚至停滯不前.如果Pm太大，遺傳算法成為純粹的隨機(jī)搜索算法；如果Pm太小，則不易產(chǎn)生新的個體結(jié)構(gòu).

為了提高遺傳算法的收斂性，達(dá)到全局最優(yōu)解，采用Srinivas等提出的自適應(yīng)遺傳算法[17]，使Pc和Pm的值隨著適應(yīng)度的變化而自動改變.當(dāng)種群的整體適應(yīng)度趨于一致或者趨于局部最優(yōu)時，增大Pc和Pm；當(dāng)種群的整體適應(yīng)度比較分散時，降低Pc和Pm.同時，對于適應(yīng)度高于平均值的個體，降低Pc和Pm，保證其進(jìn)入下一代；對于適應(yīng)度低于平均值的個體，提高Pc和Pm，以將其淘汰.此操作使得自適應(yīng)的Pc和Pm能夠提供相對于某個解的最佳Pc和Pm.因此，自適應(yīng)遺傳算法在保持種群多樣性的同時，也保證了遺傳算法的收斂性.

Pc和Pm按照如下公式進(jìn)行計(jì)算：

Pc=

(3)

Pm=

(4)

式中：Pc1=0.6,Pc2=0.3,Pm1=0.1,Pm2=0.01；f為需要變異個體的適應(yīng)度；f′為兩個需要交叉操作的個體中適應(yīng)度較大的個體適應(yīng)度；favg為種群的平均適應(yīng)度；fmax為種群中的最大適應(yīng)度.

3.5 并行算子

初步實(shí)驗(yàn)說明，當(dāng)N較大時，標(biāo)準(zhǔn)遺傳算法的效率會下降.由于算法的運(yùn)行時間主要在于個體適應(yīng)度的計(jì)算，而遺傳算法的特性在于個體之間相互獨(dú)立，個體的適應(yīng)度可并行計(jì)算，劃分的不同種群之間也可以相互獨(dú)立的進(jìn)行演化，所以使用并行遺傳算法來加速搜索過程，以減少計(jì)算時間.

使用OpenMP實(shí)現(xiàn)并行遺傳算法[18].程序開始執(zhí)行時，僅為1個單線程程序，當(dāng)需要并行計(jì)算適應(yīng)度函數(shù)時，會形成1個線程組，多個線程并行執(zhí)行計(jì)算適應(yīng)度函數(shù)的代碼.最后，到所有線程都執(zhí)行完并行代碼后，回歸主線程繼續(xù)執(zhí)行至結(jié)束.此操作不僅降低了并行程序設(shè)計(jì)的難度，還提高了算法的收斂速度.

3.6 模擬退火算子

標(biāo)準(zhǔn)遺傳算法通常容易產(chǎn)生早熟現(xiàn)象、局部搜索能力較差等問題，而模擬退火算法具有較強(qiáng)的局部搜索能力，并能使搜索過程避免陷入局部最優(yōu)解[19].所以在遺傳算法中引入模擬退火算子，提高算法的全局和局部搜索能力，加速收斂并避免早熟.

模擬退火(SA)是一種基于Monte Carlo迭代法的啟發(fā)式隨機(jī)搜索算法.SA來源于對固體物質(zhì)的退火降溫過程中的熱平衡問題的模擬和隨機(jī)搜索優(yōu)化問題，以找到全局最優(yōu)解或近似全局最優(yōu)解[20].在搜索最優(yōu)解的過程中，SA除了可以接受最優(yōu)解外，還有1個隨機(jī)接受準(zhǔn)則(Metropolis準(zhǔn)則)，可以有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于0，使得算法有可能從局部最優(yōu)中跳出，找到全局最優(yōu)解，保證算法的收斂.

將遺傳算法和模擬退火算法相結(jié)合，對每一代最優(yōu)個體執(zhí)行模擬退火操作.步驟如下：

(1) 初始化遺傳算法，初始化退火溫度T0=LC(s).

(2) 對種群進(jìn)行交叉、變異等操作，選出本代最優(yōu)個體.

(3) 在溫度TK下執(zhí)行操作：產(chǎn)生新的可行解e′(e′是e相應(yīng)的目標(biāo)函數(shù)值)； 計(jì)算新解的評價(jià)函數(shù)f(e′)和舊解的評價(jià)函數(shù)f(e)的差值：Δf=f(e′)-f(e)；依照概率 min{1,exp(-Δf/TK)}>random[0,1]接收新解，random[0,1]是1個 [0,1] 區(qū)間內(nèi)的隨機(jī)數(shù)；按一定的方式，緩慢降低溫度，定義降溫函數(shù)為TK+1=αTK，K=K+1(α為降溫系數(shù)，為1個小于1的正數(shù)).

(4) 執(zhí)行最優(yōu)保留算子，若滿足收斂條件，則結(jié)束；否則轉(zhuǎn)(2).

3.7 混合遺傳算法

使用輪盤賭和最優(yōu)保留、兩點(diǎn)交叉代替單點(diǎn)交叉、單點(diǎn)隨機(jī)變異、自適應(yīng)交叉和變異概率，對每代的最佳個體進(jìn)行模擬退火以保證不陷入局部最優(yōu)解，并行編程以提高效率.

算法3混合遺傳算法(IGA)

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

(2) 根據(jù)式(2)并行計(jì)算POP(0)中每個個體的適應(yīng)度；

(3) 判斷 GEN>MAXGEN 是否成立，若成立則轉(zhuǎn)(11)；

(4) 使用輪盤賭從POP(GEN)中選擇出POP(GEN+1)；

(5) 在POP(GEN+1)中按照式(3)得到的自適應(yīng)交叉概率Pc執(zhí)行兩點(diǎn)交叉；

(6) 在POP(GEN+1)中按照式(4)得到的自適應(yīng)變異概率Pm執(zhí)行單點(diǎn)隨機(jī)變異；

(7) 根據(jù)式(2)并行計(jì)算POP(GEN+1)中每個個體的適應(yīng)度；

(8) 最優(yōu)選擇；

(9) 對本代最優(yōu)個體執(zhí)行模擬退火算子；

(10) GEN=GEN+1，轉(zhuǎn)(3)；

(11) 輸出LCk(s)，結(jié)束.

4 實(shí)驗(yàn)與分析

本節(jié)首先使用混合遺傳算法(算法3)與標(biāo)準(zhǔn)遺傳算法(算法1)對周期為2n的序列進(jìn)行數(shù)值實(shí)驗(yàn)，并對兩個算法進(jìn)行重復(fù)實(shí)驗(yàn)，對比兩個算法的結(jié)果，說明混合遺傳算法比標(biāo)準(zhǔn)遺傳算法在誤差率和算法效率方面更優(yōu)秀.然后展示2n周期序列的k-錯線性復(fù)雜度實(shí)驗(yàn)值和準(zhǔn)確值的對比圖，說明混合遺傳算法的誤差率較低，并挑選幾個任意周期序列的k-錯線性復(fù)雜度實(shí)驗(yàn)圖說明本文設(shè)計(jì)的混合遺傳算法可以計(jì)算非特殊周期序列的k-錯線性復(fù)雜度.

實(shí)驗(yàn)設(shè)定PS=200，MAXGEN=200以及PS=400，MAXGEN=500，使用混合遺傳算法IGA(算法3)，針對周期2n的不同取值進(jìn)行重復(fù)實(shí)驗(yàn)，分別計(jì)算序列的6-錯線性復(fù)雜度，統(tǒng)計(jì)算法的準(zhǔn)確率和運(yùn)行時間，結(jié)果如表1所示.表中：A為實(shí)驗(yàn)值比準(zhǔn)確值高出的百分比，即誤差率；T為算法的運(yùn)行時間.

表1 PS=200，MAXGEN=200和PS=400，MAXGEN=500時，混合遺傳算法的結(jié)果

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-錯線性復(fù)雜度，當(dāng) PS=400，MAXGEN=500時，盡管運(yùn)行時間長，但誤差率均比PS=200，MAXGEN=200時低.在盡量保證算法準(zhǔn)確度的情況下，下文實(shí)驗(yàn)選取 PS=400，MAXGEN=500的組合參數(shù)，針對周期2n和k的不同取值進(jìn)行重復(fù)實(shí)驗(yàn)，每組實(shí)驗(yàn)隨機(jī)生成400個序列，統(tǒng)計(jì)算法的準(zhǔn)確率和運(yùn)行時間，結(jié)果如表2和表3所示.其中IGA為混合遺傳算法(算法3)的結(jié)果，GA表示標(biāo)準(zhǔn)遺傳算法(算法1)的結(jié)果.

表2 混合遺傳算法計(jì)算k=6,7,8的結(jié)果

表3 標(biāo)準(zhǔn)遺傳算法計(jì)算k=6,7,8的結(jié)果

標(biāo)準(zhǔn)遺傳算法中，Pc和Pm設(shè)置為固定值，本文通過多次實(shí)驗(yàn)對比，發(fā)現(xiàn)Pc=0.6,Pm=0.03時，實(shí)驗(yàn)結(jié)果更準(zhǔn)確，故后文的實(shí)驗(yàn)使用此參數(shù)組合.

在IGA實(shí)驗(yàn)中，采用4個線程并行計(jì)算的運(yùn)行時間均比采用GA所需的時間更短，效率更高.在程序運(yùn)行中，使用BM算法計(jì)算每個個體的適應(yīng)度占據(jù)了大部分時間，而每個個體之間是相互獨(dú)立的，在計(jì)算適應(yīng)度時能夠并行執(zhí)行，極大地減少了運(yùn)行時間.在硬件環(huán)境支持的情況下，線程數(shù)越多，運(yùn)行時間越短，效率越高.當(dāng)PS=200,MAXGEN=200時，計(jì)算k-錯線性復(fù)雜度，64位的序列通常只需要1 s，128位的序列需要3 s，256位的序列需要10 s.隨著種群規(guī)模和迭代代數(shù)的增加，PS=400,MAXGEN=500，雖然運(yùn)行時間在增加，但算法的誤差率在不斷減小.

當(dāng)k<8時，IGA有較小的誤差率，N=64時，誤差率小于8%；N=128時，誤差率小于3%；N=256時，誤差率小于2%.當(dāng)k>8時，誤差率變大，但經(jīng)常使用傳統(tǒng)算法研究的多是1-錯，2-錯線性復(fù)雜度，而對于8-錯及更大的k-錯線性復(fù)雜度，其研究難度較大，同時當(dāng)k值很大時，k-錯線性復(fù)雜度的研究意義不大.實(shí)驗(yàn)證明，k值較小時，混合遺傳算法的效率更高，誤差率更低，實(shí)驗(yàn)結(jié)果更加接近準(zhǔn)確值.

下面分別展示不同的2n周期序列的k-錯線性復(fù)雜度的實(shí)驗(yàn)值和準(zhǔn)確值的對比圖.圖1～3分別為n=6，7，8時，即N=64，128，256時，3個序列s1、s2、s3的k-錯線性復(fù)雜度情況.可以看出，當(dāng)k<8時，本文混合遺傳算法的誤差率較低，實(shí)驗(yàn)值與準(zhǔn)確值很接近，當(dāng)k較大時，算法慢慢收斂，實(shí)驗(yàn)值與準(zhǔn)確值的誤差變大.

s1={011000111100110101010011101110011001110 1111000101100011111100000}，N=64

圖1 序列s1的k-錯線性復(fù)雜度實(shí)驗(yàn)值和準(zhǔn)確值對比

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

圖2 序列s2的k-錯線性復(fù)雜度實(shí)驗(yàn)值和準(zhǔn)確值對比

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

圖3 序列s3的k-錯線性復(fù)雜度實(shí)驗(yàn)值和準(zhǔn)確值對比

對比文獻(xiàn)[16]的實(shí)驗(yàn)結(jié)果，周期為32的二元序列的5-錯線性復(fù)雜度的實(shí)驗(yàn)結(jié)果比準(zhǔn)確值平均高19.5%.而本文算法可以計(jì)算周期為256的二元序列的8-錯線性復(fù)雜度，其實(shí)驗(yàn)值僅比準(zhǔn)確值高8%.因此，本文算法不僅使可計(jì)算的N、k增加，還提高了算法的準(zhǔn)確性和效率.

前文的實(shí)驗(yàn)之所以采用N=64，128，256，是因?yàn)槲覀兛梢杂?jì)算這些周期序列的準(zhǔn)確的k-錯線性復(fù)雜度，從而可以對比實(shí)驗(yàn)結(jié)果，計(jì)算誤差率，說明算法準(zhǔn)確性的提高.而我們的算法可以計(jì)算任意周期的二元序列的k-錯線性復(fù)雜度，所以下面給出兩條任意周期序列的k-錯線性復(fù)雜度的實(shí)驗(yàn)圖.圖4和5分別為N=200的序列s4和周期N=500的序列s5的k-錯線性復(fù)雜度的實(shí)驗(yàn)圖.

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

圖4 序列s4的k-錯線性復(fù)雜度實(shí)驗(yàn)值

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

圖5 序列s5的k-錯線性復(fù)雜度實(shí)驗(yàn)值

從圖4和5可以看出，非2n周期序列的k-錯線性復(fù)雜度實(shí)驗(yàn)值變化規(guī)律和2n周期序列的k-錯線性復(fù)雜度實(shí)驗(yàn)值變化規(guī)律類似.即在k值較小且可以接受微小誤差的情況下，可以計(jì)算任意周期序列的k-錯線性復(fù)雜度.

5 結(jié)語

使用遺傳算法計(jì)算在有限域上給定周期序列的k-錯線性復(fù)雜度時，針對標(biāo)準(zhǔn)遺傳算法所存在的問題，對其進(jìn)行改進(jìn)，設(shè)計(jì)了一種混合的遺傳算法.為了保證遺傳算法的收斂性，加速尋優(yōu)并避免陷入局部最優(yōu)解，使用輪盤賭和精英選擇、自適應(yīng)調(diào)整交叉和變異概率，進(jìn)行兩點(diǎn)交叉和單點(diǎn)隨機(jī)變異操作，并行計(jì)算每代個體的適應(yīng)度，并對每代的最優(yōu)個體進(jìn)行模擬退火操作.結(jié)果表明，當(dāng)k較小時，混合遺傳算法的誤差率小于8%，同時提高了遺傳算法的尋優(yōu)性能和運(yùn)行效率.因此，在k值較小且可以接受微小誤差的情況下，可以使用本文設(shè)計(jì)的混合遺傳算法來計(jì)算任意周期序列的k-錯線性復(fù)雜度.