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.

翻译：找到平衡、 高度非线性布林函数是一个困难的问题, 因为不知道什么是非线性值可以普遍达到的。 同时, 进化计算被成功地用于演进特定的布林函数实例, 但对于更大的布林函数大小来说, 方法无法轻易地缩放。 事实上, 虽然演进较小的布林函数几乎微不足道, 更大的规模越来越难, 进化算法也具有亚超性。 在这项工作中, 我们问基因程序( GP) 是否能够进化构造, 导致平衡的布林函数和高非线性。 这个问题特别有趣, 因为只有少数已知的布林函数。 我们的结果显示, GP 能够找到非常通用的构造, 也就是说, 导致多重测试大小所需的功能。 此外, 我们显示, GP 在不同的合成表达方式下, 许多相等的构造会演化。 有趣的是, GP 发现的最简单解决方案是众所周知的间接总和构造的特例 。