# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 4 Proposed Approach  
We adopt tree-based Genetic Programming (GP) [31] to evolve symbolic formulae. Especially, these formulae, or trees, express Walsh transforms of generic pseudo-Boolean functions, from which it is possible to discover actual Boolean functions. Specifically, a generic individual, or solution, can be adopted for calculating the Walsh transform coefficients. From now on, we are going to use the terms \"tree\" and \"formula\" interchangeably. A GP-based symbolic tree has a specific structure. In particular, a given tree is related to a specific function set and a specific terminal set. The function set contains the (mathematical) operators that can be used to fill the internal nodes of a tree. The terminal set contains the values that can be used to fill the leaves of the tree, which are typically variables and constants. In this work, we resume the tree configuration that has already been explored in [38] and provide a more in-depth comparison among different types of symbolic configurations. Specifically, we explore two types of function sets:  
\[\mathsf{F1}=\{+,\ \times,\ (.)^{2}\}\]  
\[\mathsf{F2}=\{+,\ -,\ \times,\ \%^{*},\ \text{even, odd}\}\]  
The module operator \(\%^{*}\) is protected to avoid cases in which the denominator is equal to zero:  
\[\%^{*}(a,b)=\mathtt{sign}(b)(a\ \%\ (|b|\ \text{if}\ b\
eq 0\ \text{else}\ 1))\]  
The even function outputs \(1\) if the input value is an even number and \(0\) otherwise. On the other hand, the odd function outputs \(1\) if the input value is an odd number and \(0\) otherwise. The input of a Walsh transform is a binary string of size \(n\). For this purpose, we examine in-depth three variations of the input encoding. This results in three different types of terminal sets:  
1. A terminal set of one variable representing an integer between \(0\) and \(2^{n}-1\), i.e., the integer encoded by a given binary string of size \(n\) (N);
2. A terminal set of \(n\) variables representing the binary positions of the input string (B);
3. A terminal set of \(n\) variables representing the binary positions of the input string in polar form (P). For each terminal set, we additionally test an extension that includes ephemeral random constants uniformly sampled between \(-1\) and \(1\) (ERC). The combination of a specific function set and a specific terminal set provides us with a particular tree structure, which we are going to denote with the notation \(\mathcal{S}^{\text{cterminal\_set}}_{\text{function\_set}}\). For instance, \(\mathcal{S}^{\text{N}}_{\text{F1}}\) refers to a structure with F1 as the function set and N as the terminal set, \(\mathcal{S}^{\text{P,ERC}}_{\text{F2}}\) refers to a structure with F2 as the function set and P with the addition of ephemeral random constants as the terminal set. Two examples of trees are shown in Figure 4.  
Under these conditions, a tree represents a generic \(\hat{F}\). A generic tree can thus be applied to each \(\mathbf{w}\in\mathbb{B}^{n}\) in a way so that a Walsh spectrum \(\hat{S}_{f}\in\mathbb{Z}^{2^{n}}\) can be retrieved. Precisely, the spectrum potentially contains real values that are eventually rounded to their corresponding integers. Then, by using the spectral inversion technique, Equation (2) can be applied to \(\hat{S}_{f}\) to obtain, in general, a pseudo-Boolean function \(\hat{f}\). The nearest Boolean function can be computed starting from \(\hat{f}\) by leveraging different strategies. These strategies differ among each other on the criterion that is adopted to assign the entries of \(\mathbf{\Omega}_{f}\), where \(\hat{f}(\mathbf{w})=0\) (large uncertainty on how to assign those entries). We explore two approaches, which we describe as follows:  
1. _Unbiased uncertainty filling_: the nearest Boolean function is retrieved with Equation (3). This approach was already explored in [13]. 2.