Search papers, labs, and topics across Lattice.
This study explores the potential of evolutionary computation to evolve monotone Boolean functions with high nonlinearity, addressing the inherent limitations of their structure. By employing three distinct solution encodings and introducing a non-monotonicity penalty, the authors successfully guide the search towards functions that not only exceed the nonlinearity of majority functions but also approach the best-known values for monotone functions. The findings highlight significant differences in performance across encodings, with genetic programming proving particularly effective in larger dimensions.
Evolutionary algorithms can evolve monotone Boolean functions that achieve nonlinearities surpassing traditional majority functions, challenging existing limits in this domain.
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.
