跳到主要内容
返回时间线
arXiv来源发表:

弯曲函数不再直接搜真值表:改搜子空间族,8变量低次函数找到285个

核心概要

构造部分展布弯曲函数时,搜索对象从真值表换成底层子空间族,并用一种“拆掉冲突成员再精确重建”的算子修补。8变量下,展布集编码配合该算子对两类目标分别达到100%和74%成功率,而子空间编码与去掉该算子的展布集编码都找不到解;同一编码上带前瞻的贪心启发式在最难目标上成功率更高。

Source-provided article image: A Matter of Representation: Evolving Partial Spreads for Bent Functions
arXiv

深度剖析

弯曲函数这类与线性函数距离最大的布尔函数,可以不再直接搜索真值表,而是搜索支撑它的部分展布,即一族两两只在零向量相交的子空间。 此前用进化算法直接搜真值表或语法树时,基于真值表的进化策略和遗传算法在给定适应度预算内从未找到弯曲函数,而符号编码的遗传编程能可靠找到。 8变量下两种编码都100%收敛;10变量下只有展布集编码加拆建算子成功,对两类目标分别为100%和74%,其余配置在1800秒内一次也未找到部分展布。

做法是把每个子空间写成固定两个子空间之外的线性映射图,于是两个子空间是否只交于零向量,等价于对应矩阵之差是否可逆。 直接照搬二进制线性码的进化策略去优化一族生成矩阵,在8变量时就已经失败。 拆建算子按列逐个构造新矩阵,一旦某列使差值矩阵出现线性相关就回溯,因此能精确插入或证明不存在;10变量目标上成功运行的中位评估次数为241次。

把代数次数作为第二个目标后,基于MAP-Elites的质量-多样性变体比字典序变体更可靠地找到次数低于4的8变量函数。 字典序做法只保留最好的次数值,失败运行全部停在次数4,走进死胡同。 300秒内100次运行中,质量-多样性进化策略达到次数低于4的有90次和84次,字典序为47次和35次,前瞻贪心为27次;共得到285个不同函数,其中278个次数为3、7个次数为2。

启示与展望

实验覆盖8变量和10变量的两类部分展布目标,以及12变量这一极限实例;每个配置100次独立运行,比较时用实际运行时间对齐贪心基线。12变量下两种方法各跑16次、每次24小时均未找到部分展布,前瞻贪心每次都停在23个子空间。

10变量目标上进化策略的成功率为74%,失败运行结束时中位仍有2对冲突子空间;最难实例上重启的前瞻贪心成功率高于任何进化策略变体,用贪心族初始化也未能缩小差距。12变量下前瞻贪心每次约3770次尝试都停在23个子空间,进化策略的失败插入中有一部分是被节点预算截断的。