# Discovering Non-Linear Boolean Functions by Evolving Walsh Transforms with Genetic Programming +
## 4 Proposed Approach
_Biased (toward balancedness) uncertainty filling_: a strategy that was presented in [38] to propose a technique that tries to improve or, eventually, preserve the balancedness when computing nearest Boolean functions. This strategy is based on the idea that uncertain positions can be exploited for the purpose of balancing \(\mathbf{\Omega}_{f}\). Let \(\hat{\mathbf{\Omega}}_{f}\) be the polar-form-based truth table of \(\hat{f}\). Let: \[v_{1} =|\{b\in\hat{\mathbf{\Omega}}_{f}\mid  
\[u_{1}=|\{b\in\mathbf{u}\mid b=-1\}|\] \[u_{0}=|\{b\in\mathbf{u}\mid b=1\}|\]  
Obviously, the balancedness degree is not affected by the way \(-1\) and \(1\) are sorted in \(\mathbf{u}^{*}\). Hence, a given type of \(\mathbf{u}^{*}\) can be computed deterministically (e.g., \(\mathbf{u}^{*}=[-1^{u_{1}},1^{u_{0}}]\)), and in order to enhance diversity, a random permutation of it can be performed. Finally, we obtain \(\mathbf{u}^{*}_{p}\in\{-1,\;1\}^{u}\), i.e., a permutation of \(\mathbf{u}^{*}\) retrieved by performing a random shuffle of it. We leverage \(\mathbf{u}^{*}_{p}\) to assign the uncertain entries of \(\mathbf{\Omega}_{f}\) as follows:  
\[f(\mathbf{x})= \begin{cases}1&\text{if }\tilde{f}(\mathbf{x})>0\\ -1&\text{if }\tilde{f}(\mathbf{x})<0\\ \mathbf{u}^{*}_{p}[ind(\mathbf{x})]&\text{if }\tilde{f}(\mathbf{x})=0\end{cases}  \tag{5}\]  
where \(\mathbf{u}^{*}_{p}[ind(\mathbf{x})]\) is the value in \(\mathbf{u}^{*}_{p}\) located at the position given by \(ind(\mathbf{x})\), where the latter represents an integer between \(0\) and \(u-1\). Specifically, the \(ind\) function is defined only for uncertain binary strings with respect to \(\hat{f}\) and provides the ranking in which these strings appear in \(\mathbf{\hat{\Omega}}_{f}\). Once the truth table \(\mathbf{\Omega}_{f}\) of the nearest Boolean function of \(\hat{f}\) is computed, Equation (1) can be applied to obtain the associated Walsh spectrum \(S_{f}\). The fitness function is a single-objective function consisting of the non-linearity \(\overline{\ell}\) Equation (4) evaluated on \(S_{f}\). The optimization algorithm is set to maximize as much as possible the fitness function. The optimization algorithm is tree-based GP [31] with a single-objective fitness function. We briefly describe the main steps of GP when evolved solutions represent symbolic formulae or trees:  
1. _Initialization_: generate an initial population of random symbolic formulae representing mathematical expressions and evaluate their fitness;
2. _Selection_: choose symbolic formulae from the current population as parents for the next generation based on their fitness, with some randomness to maintain diversity;
3. _Crossover (Recombination)_: create new symbolic formulae by swapping sub-parts of two parent formulae, combining them to form offspring;
4. _Mutation_: introduce random changes to offspring formula, which may involve adding, removing, or modifying sub-parts. Then, perform a novel evaluation of the fitness of the offspring and go back to the selection step so that the next generation begins. These steps are the core of GP (Figure 5), where symbolic formulae are evolved and refined over multiple generations to approximate or represent desired symbolic relationships or mathematical expressions. In our specific context, these symbolic formulae are refined to identify a representation of the Walsh transform characterized by a large non-linearity.