Evolving constructions for balanced, highly nonlinear boolean functions
Evolving constructions for balanced, highly nonlinear boolean functions
复制标题
平衡、高度非线性布尔函数的演化结构
DOI：
10.1145/3512290.3528871
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
S. Picek
中科院分区：
文献类型：
--
作者：
C. Carlet;Marko Djurasevic;D. Jakobović;L. Mariot;S. Picek
寻找平衡的，高度非线性的布尔函数是一个困难的问题，它是不知道什么样的非线性值是可能达到的一般。同时，进化计算被成功地用于进化特定的布尔函数实例，但该方法不能容易地扩展到更大的布尔函数大小。事实上，虽然进化较小的布尔函数几乎是微不足道的，但更大的尺寸变得越来越困难，并且进化算法的性能次优。在这项工作中，我们问遗传编程（GP）是否可以发展结构，导致平衡的布尔函数具有高非线性。这个问题特别有趣，因为只有少数已知的这样的结构。我们的结果表明，GP可以找到推广良好的结构，即，产生多种测试尺寸所需的功能。此外，我们还发现GP在不同的句法表征下演化出许多等价的构式。有趣的是，GP找到的最简单的解决方案是众所周知的间接和构造的一个特殊情况。
Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally. In this work, we ask whether genetic programming (GP) can evolve constructions resulting in balanced Boolean functions with high nonlinearity. This question is especially interesting as there are only a few known such constructions. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Further, we show that GP evolves many equivalent constructions under different syntactic representations. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.