Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions

Boolean functions are mathematical objects with numerous applications in domains like coding theory, cryptography, and telecommunications. Finding Boolean functions with specific properties is a complex combinatorial optimization problem where the search space grows super-exponentially with the number of input variables. One common property of interest is the nonlinearity of Boolean functions. Constructing highly nonlinear Boolean functions is difficult as it is not always known what nonlinearity values can be reached in practice. In this paper, we investigate the effects of the genetic operators for bit-string encoding in optimizing nonlinearity. While several mutation and crossover operators have commonly been used, the link between the genotype they operate on and the resulting phenotype changes is mostly obscure. By observing the range of possible changes an operator can provide, as well as relative probabilities of specific transitions in the objective space, one can use this information to design a more effective combination of genetic operators. The analysis reveals interesting insights into operator effectiveness and indicates how algorithm design may improve convergence compared to an operator-agnostic genetic algorithm.