基于改进模拟退火的布尔函数生成算法

◆张思瑶

（北方工业大学 北京 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 总结

本文首先通过实验证明将传统的模拟退火算法应用于设计布尔函数时存在依赖于初始参数设置、易于陷入局部最优解和冗余迭代次数过多等问题，进而造成算法收敛速度低，且不易得出具有高非线性度、低自相关性的平衡的布尔函数。针对该问题，本文分别从摆脱初始参数设置依赖、增强跳出局部最优解能力以及减少高温冗余迭代三方面对传统的模拟退火算法进行优化，将混沌原理以及遗传算法中的变异策略与模拟退火算法结合并进行符合布尔函数的改进。通过大量实验证明，改进后的模拟退火算法在效率、跳出局部最优等方面优于传统的模拟退火算法，并能搜索出具有良好密码学性质的布尔函数。