基于改進模擬退火的布爾函數生成算法

◆張思瑤

（北方工業大學 北京 100144）

1 引言

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

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

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

2 方法與步驟

下面將詳細介紹本文改進模擬退火算法的三個具體方面，分別是將傳統模擬退火算法與混沌原理、遺傳算法中的變異策略、“學習策略”相結合，并給出改進的算法步驟。

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

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

兩邊取對數，則：

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

2.2 基于遺傳算法與平衡布爾函數特點的擾動策略

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

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

式（3）中：m為整數，k為當前迭代次數。

2.3 基于粒子集群智能的學習策略

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

2.4 改進的模擬退火算法步驟

將改進的模擬退火算法用于布爾函數的設計，固體退火過程就相當于布爾函數真值表的構建過程，粒子狀態則對應于布爾函數的真值表，最低能量下的粒子狀態便是設計的高非線性度的布爾函數的最優解，溫度則相當于控制參數，初始溫度即設定搜索空間能力的大小。因此，改進的模擬退火算法具體步驟如圖1 所示。

圖1 改進的SA 算法流程圖

綜上所述，改進的模擬退火算法能夠高效地搜索出具有良好密碼學性質的布爾函數。

4 實驗

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

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

表1 傳統模擬退火算法生成8 元布爾函數結果

表2 改進的模擬退火算法生成8 元布爾函數結果

第二次實驗旨在表明改進的模擬退火算法性能更優。分析圖2可知，使用本文提出的改進模擬退火算法產生的布爾函數的非線性度收斂至最優解的迭代次數遠遠小于傳統模擬退火算法的迭代次數，這說明改進后的模擬退火算法中加入學習策略有利于提升收斂速度，提高了算法的效率。

圖2 傳統模擬退火推算與改進模擬退火算法迭代曲線

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

5 總結

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