◆張思瑤

（北方工業(yè)大學(xué) 北京 100144）

1 引言

信息安全的核心是密碼理論和技術(shù)[1-3]，布爾函數(shù)是研究密碼技術(shù)的重要工具，在流密碼以及分組密碼中都有重要的作用。構(gòu)造滿足對(duì)稱性、平衡性、低自相關(guān)免疫性、高非線性度等特性的布爾函數(shù)是密碼學(xué)的熱門課題[4-6]。啟發(fā)式算法在設(shè)計(jì)出滿足密碼學(xué)特性的布爾函數(shù)上表現(xiàn)出巨大的優(yōu)越性，因此受到研究者們重點(diǎn)關(guān)注。

在運(yùn)用啟發(fā)式算法中的模擬退火算法進(jìn)行最優(yōu)解的搜索時(shí)，雖然算法可以通過設(shè)定概率來接受較差解以此跳出局部最優(yōu)，從而能夠設(shè)計(jì)出滿足密碼學(xué)特性的布爾函數(shù)；但是傳統(tǒng)模擬退火算法受初始參數(shù)設(shè)定的影響較大，不易準(zhǔn)確而快速遍歷可行解空間找到最優(yōu)解，降低算法收斂速度，進(jìn)而影響全局最優(yōu)解的選擇。

因此，為設(shè)計(jì)出貼合布爾函數(shù)特性的模擬退火算法的初始參數(shù)和降溫策略，最有效的方案是結(jié)合多種啟發(fā)式算法的優(yōu)點(diǎn)，使得模擬退火算法中最優(yōu)解的產(chǎn)生受初始參數(shù)設(shè)定和溫度梯度下降的影響最低，進(jìn)而能更快更精確地收斂至全局最優(yōu)解。為了實(shí)現(xiàn)上述目標(biāo)，本文將模擬退火算法與遺傳算法的變異策略、混沌原理[7]相結(jié)合，使初始解分布更加均勻，同時(shí)使算法能更加全面地遍歷布爾函數(shù)的可行解空間，進(jìn)而有利于快速找到全局最優(yōu)解。

2 方法與步驟

下面將詳細(xì)介紹本文改進(jìn)模擬退火算法的三個(gè)具體方面，分別是將傳統(tǒng)模擬退火算法與混沌原理、遺傳算法中的變異策略、“學(xué)習(xí)策略”相結(jié)合，并給出改進(jìn)的算法步驟。

2.1 基于混沌原理的初始溫度的選取

傳統(tǒng)模擬退火算法通常將初始溫度設(shè)定為一個(gè)較高的值，以便充分地對(duì)解空間進(jìn)行隨機(jī)搜索，但是這種做法會(huì)造成高溫下的冗余迭代，進(jìn)而使算法效率降低。因此，需要對(duì)初始溫度T0進(jìn)行貼合布爾函數(shù)設(shè)計(jì)的設(shè)定。本文利用混沌原理進(jìn)行初始溫度的設(shè)定。根據(jù) Metropolis 準(zhǔn)則：接受差解的概率為P0，則：

兩邊取對(duì)數(shù)，則：

按混沌原理首先搜索出N個(gè)可能解，并對(duì)這N個(gè)可能解對(duì)應(yīng)的目標(biāo)函數(shù)值的最大值Nf(fmax)、最小值Nf(fmin)進(jìn)行記錄，計(jì)算ΔC=Nf(fmax)－Nf(fmin)，帶入式（1）得到初始溫度的設(shè)定公式為：

2.2 基于遺傳算法與平衡布爾函數(shù)特點(diǎn)的擾動(dòng)策略

傳統(tǒng)模擬退火算法在搜索最優(yōu)解時(shí)，由于擾動(dòng)規(guī)則的設(shè)定，擾動(dòng)后的解只能與其相鄰解比較，這樣容易陷入局部的最優(yōu)解。因此，為了防止上述現(xiàn)象發(fā)生，本文將遺傳算法中的變異策略根據(jù)平衡布爾函數(shù)的特點(diǎn)進(jìn)行改進(jìn)，并應(yīng)用在模擬退火中的擾動(dòng)方案中。本文方案的搜索空間是具有高非線性度和低自相關(guān)性的平衡布爾函數(shù)，所以需要采用如下策略來保證經(jīng)過擾動(dòng)之后的布爾函數(shù)依然是平衡的：定義一個(gè)平衡的布爾函數(shù)f，設(shè)α為布爾函數(shù)真值交換值的次數(shù)；每次交換時(shí)首先，隨后判斷若（f x1）≠（f x2），則將（f x1）與（f x2）的值進(jìn)行交換，交換次數(shù)加1；重復(fù)進(jìn)行如上交換步驟直到交換次數(shù)等于α?xí)r，擾動(dòng)結(jié)束。

其中α的值進(jìn)行自適應(yīng)選取：最初時(shí)搜索要在較大的解空間范圍內(nèi)進(jìn)行，從而能有更多的選擇，所以此時(shí)α 的取值要較大；當(dāng)算法搜索進(jìn)行到一定程度時(shí)，搜索的解已經(jīng)逐漸向全局最優(yōu)解靠攏，搜索要在最優(yōu)解的鄰域的小范圍進(jìn)行，所以此時(shí)α的取值要較小。因此α的取值與當(dāng)前迭代次數(shù)相關(guān)，公式為：

式（3）中：m為整數(shù)，k為當(dāng)前迭代次數(shù)。

2.3 基于粒子集群智能的學(xué)習(xí)策略

為了解決傳統(tǒng)的模擬退火算法容易陷入局部的最優(yōu)解的問題，本文將集群智能中粒子向當(dāng)前全局最好解靠攏的思想與模擬退火算法結(jié)合，提出一個(gè)新的學(xué)習(xí)策略，使得改進(jìn)的模擬退火算法能夠跳出局部最優(yōu)解。改進(jìn)的學(xué)習(xí)策略為：判斷如果在搜索過程中的一段時(shí)間內(nèi)總是沒有接受解，或者沒有產(chǎn)生好解時(shí)，就將當(dāng)前算法搜索到的最好解E_best設(shè)置為下一次迭代的初始解，使下一次迭代從當(dāng)前最好解開始繼續(xù)進(jìn)行擾動(dòng)。

2.4 改進(jìn)的模擬退火算法步驟

將改進(jìn)的模擬退火算法用于布爾函數(shù)的設(shè)計(jì)，固體退火過程就相當(dāng)于布爾函數(shù)真值表的構(gòu)建過程，粒子狀態(tài)則對(duì)應(yīng)于布爾函數(shù)的真值表，最低能量下的粒子狀態(tài)便是設(shè)計(jì)的高非線性度的布爾函數(shù)的最優(yōu)解，溫度則相當(dāng)于控制參數(shù)，初始溫度即設(shè)定搜索空間能力的大小。因此，改進(jìn)的模擬退火算法具體步驟如圖1 所示。

圖1 改進(jìn)的SA 算法流程圖

綜上所述，改進(jìn)的模擬退火算法能夠高效地搜索出具有良好密碼學(xué)性質(zhì)的布爾函數(shù)。

4 實(shí)驗(yàn)

為了驗(yàn)證本文提出的改進(jìn)算法的有效性，本文分別采用基本的模擬退火方法和改進(jìn)的模擬退火方法來演化8 元布爾函數(shù)，并將結(jié)果做對(duì)比。在試驗(yàn)中，設(shè)定初始接受概率P0=0.6，設(shè)置降溫系數(shù)=0.9，未產(chǎn)生好解的最大次數(shù)N=100，式（2）中：m=4。本文用非線性度Nf與自相關(guān)性ACf來測(cè)評(píng)搜索到的8 元布爾函數(shù)的性質(zhì)。

本文總共進(jìn)行兩次實(shí)驗(yàn)，第一次實(shí)驗(yàn)通過比較傳統(tǒng)模擬退火算法與本文改進(jìn)的模擬退火算法所產(chǎn)生的布爾函數(shù)在不同密碼學(xué)特性下的個(gè)數(shù)，旨在表明改進(jìn)的模擬退火算法的優(yōu)化是有效的。分析表1和表2 可知，采用傳統(tǒng)的模擬退火算法只能搜索到 5 個(gè)非線性度Nf=112 的8 元布爾函數(shù)，而采用本文改進(jìn)的模擬退火方案能夠搜索出94 個(gè)Nf=112 的8 元布爾函數(shù)，并且利用改進(jìn)模擬退火方案生成的布爾函數(shù)自相關(guān)值A(chǔ)Cf也平均小于傳統(tǒng)模擬函數(shù)所生成的布爾函數(shù)的自相關(guān)值A(chǔ)Cf，同時(shí)改進(jìn)的模擬退火算法還成功搜索出7 個(gè)Nf=114 的8 元布爾函數(shù)。這說明在傳統(tǒng)模擬退火算法中增加基于布爾函數(shù)的變異擾動(dòng)可以使算法的全局搜索能力更強(qiáng)，易于跳出局部的最優(yōu)解，并最終得到全局的最優(yōu)解。

表1 傳統(tǒng)模擬退火算法生成8 元布爾函數(shù)結(jié)果

表2 改進(jìn)的模擬退火算法生成8 元布爾函數(shù)結(jié)果

第二次實(shí)驗(yàn)旨在表明改進(jìn)的模擬退火算法性能更優(yōu)。分析圖2可知，使用本文提出的改進(jìn)模擬退火算法產(chǎn)生的布爾函數(shù)的非線性度收斂至最優(yōu)解的迭代次數(shù)遠(yuǎn)遠(yuǎn)小于傳統(tǒng)模擬退火算法的迭代次數(shù)，這說明改進(jìn)后的模擬退火算法中加入學(xué)習(xí)策略有利于提升收斂速度，提高了算法的效率。

圖2 傳統(tǒng)模擬退火推算與改進(jìn)模擬退火算法迭代曲線

綜上所述，使用本文提出的改進(jìn)的模擬退火算法能夠克服算法對(duì)初始參數(shù)設(shè)置的依賴，具有更優(yōu)地跳出局部最優(yōu)解的能力，并且能夠消除算法初期高溫狀態(tài)下的冗余迭代，可以搜索出具有良好密碼學(xué)特性的布爾函數(shù)。

5 總結(jié)

本文首先通過實(shí)驗(yàn)證明將傳統(tǒng)的模擬退火算法應(yīng)用于設(shè)計(jì)布爾函數(shù)時(shí)存在依賴于初始參數(shù)設(shè)置、易于陷入局部最優(yōu)解和冗余迭代次數(shù)過多等問題，進(jìn)而造成算法收斂速度低，且不易得出具有高非線性度、低自相關(guān)性的平衡的布爾函數(shù)。針對(duì)該問題，本文分別從擺脫初始參數(shù)設(shè)置依賴、增強(qiáng)跳出局部最優(yōu)解能力以及減少高溫冗余迭代三方面對(duì)傳統(tǒng)的模擬退火算法進(jìn)行優(yōu)化，將混沌原理以及遺傳算法中的變異策略與模擬退火算法結(jié)合并進(jìn)行符合布爾函數(shù)的改進(jìn)。通過大量實(shí)驗(yàn)證明，改進(jìn)后的模擬退火算法在效率、跳出局部最優(yōu)等方面優(yōu)于傳統(tǒng)的模擬退火算法，并能搜索出具有良好密碼學(xué)性質(zhì)的布爾函數(shù)。