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

Created by W.Langdon from gp-bibliography.bib Revision:1.8229

@InProceedings{carlet:2025:EuroGP,

• author = "Claude Carlet and Marko Durasevic and Domagoj Jakobovic and Stjepan Picek and Luca Mariot",
• title = "A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes",
• booktitle = "European Conference on Genetic Programming, EuroGP 2025",
• year = "2025",
• editor = "Bing Xue and Luca Manzoni and Illya Bakurov",
• series = "LNCS",
• address = "Trieste",
• month = "23-25 " # apr,
• publisher = "Springer Nature",
• note = "Forthcoming",
• keywords = "genetic algorithms, genetic programming, Boolean functions, nonlinearity, evolutionary algorithms, odd dimension, encodings",
• 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 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 GP outperforms other EA in evolving highly nonlinear functions. Nevertheless, 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.",
• notes = "also known as \cite{paper_144_nonlinear_boolean_functions_in_odd_sizes}

  Part of \cite{Xue:2025:GP} EuroGP'2025 held in conjunction with EvoCOP2025, EvoMusArt2025 and EvoApplications2025",

}

Genetic Programming entries for Claude Carlet Marko Durasevic Domagoj Jakobovic Stjepan Picek Luca Mariot

Citations