Monotone but Exciting: On Evolving Monotone Boolean Functions with High Nonlinearity
For researchers in Boolean function design and evolutionary computation, the paper demonstrates that evolutionary methods can effectively optimize monotone functions despite their structural constraints.
The paper investigates whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, finding that evolutionary search can discover functions with nonlinearities exceeding majority functions and approaching best-known values for dimensions n=5 to n=14.
Monotone Boolean functions are a structurally important class of Boolean functions, but their restricted form imposes strong limitations on achievable nonlinearity. In this paper, we investigate whether evolutionary computation can evolve monotone Boolean functions with high nonlinearity, both in the balanced and imbalanced settings. We consider three solution encodings: the standard truth table representation, a balanced truth table encoding that preserves Hamming weight, and a symbolic tree-based genetic programming representation. To guide the search toward monotone increasing functions, we introduce a non-monotonicity penalty and combine it with fitness functions targeting balancedness and nonlinearity. Experimental results are reported for dimensions from $n=5$ to $n=14$. The results show that evolutionary search can discover monotone Boolean functions with nonlinearities clearly exceeding those of majority functions, and in several cases approaching the best currently known values for monotone functions. At the same time, the experiments reveal substantial differences between encodings: the balanced truth table encoding performs poorly for larger dimensions, while the standard truth table and genetic programming encodings remain competitive, with genetic programming becoming especially relevant in the largest tested dimensions.