A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes

• URL: http://arxiv.org/abs/2402.09937v1
• Date: Thu, 15 Feb 2024 13:39:34 GMT
• Title: A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes
• Authors: Claude Carlet, Marko {\DH}urasevic, Domagoj Jakobovic, Stjepan Picek, Luca Mariot
• Abstract summary: We consider the problem of evolving highly nonlinear Boolean functions in odd sizes. Finding optimal solutions is impossible except for the smallest tested size. We find a Boolean function in nine inputs with nonlinearity 241.
• Score: 35.305121158674964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Boolean functions are mathematical objects used in diverse applications. Different applications also have different requirements, making the research on Boolean functions very active. In the last 30 years, evolutionary algorithms have been shown to be a strong option for evolving Boolean functions in different sizes and with different properties. Still, most of those works consider similar settings and provide results that are mostly interesting from the evolutionary algorithm's perspective. This work considers the problem of evolving highly nonlinear Boolean functions in odd sizes. While the problem formulation sounds simple, the problem is remarkably difficult, and the related work is extremely scarce. We consider three solutions encodings and four Boolean function sizes and run a detailed experimental analysis. Our results show that the problem is challenging, and finding optimal solutions is impossible except for the smallest tested size. However, once we added local search to the evolutionary algorithm, we managed to find a Boolean function in nine inputs with nonlinearity 241, which, to our knowledge, had never been accomplished before with evolutionary algorithms.

Related papers

• Look into the Mirror: Evolving Self-Dual Bent Boolean Functions [35.305121158674964]
  This paper experiments with evolutionary algorithms with the goal of evolving (anti-)self-dual bent Boolean functions. We successfully construct self-dual bent functions for each dimension. We also tried evolving secondary constructions for self-dual bent functions, but this direction provided no successful results.
  arXiv  Detail & Related papers  (2023-11-20T16:20:16Z)
• A New Angle: On Evolving Rotation Symmetric Boolean Functions [32.90791284928444]
  This paper uses several evolutionary algorithms to evolve rotation symmetric Boolean functions with different properties. Surprisingly, we find bitstring and floating point encodings work better than the tree encoding.
  arXiv  Detail & Related papers  (2023-11-20T16:16:45Z)
• The Clock and the Pizza: Two Stories in Mechanistic Explanation of Neural Networks [59.26515696183751]
  We show that algorithm discovery in neural networks is sometimes more complex. We show that even simple learning problems can admit a surprising diversity of solutions.
  arXiv  Detail & Related papers  (2023-06-30T17:59:13Z)
• Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions [8.382710169577447]
  We investigate the effects of genetic operators for bit-string encoding in optimizing nonlinearity. By observing the range of possible changes an operator can provide, one can use this information to design a more effective combination of genetic operators.
  arXiv  Detail & Related papers  (2023-02-12T10:34:01Z)
• Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions [37.84234862910533]
  We show that genetic programming can evolve constructions resulting in balanced Boolean functions with high nonlinearity. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.
  arXiv  Detail & Related papers  (2022-02-17T16:33:24Z)
• Searching for a practical evidence of the No Free Lunch theorems [0.0]
  According to the No Free Lunch (NFL) theorems all black-box algorithms perform equally well when compared over the entire set of optimization problems. We will evolve test functions for which a given algorithm A is better than another given algorithm B.
  arXiv  Detail & Related papers  (2021-08-21T19:28:48Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Task-Agnostic Morphology Evolution [94.97384298872286]
  Current approaches that co-adapt morphology and behavior use a specific task's reward as a signal for morphology optimization. This often requires expensive policy optimization and results in task-dependent morphologies that are not built to generalize. We propose a new approach, Task-Agnostic Morphology Evolution (TAME), to alleviate both of these issues.
  arXiv  Detail & Related papers  (2021-02-25T18:59:21Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.