  In this paper, we consider the problem of finding perfectly balanced Boolean
functions with high non-linearity values. Such functions have extensive
applications in domains such as cryptography and error-correcting coding
theory. We provide an approach for finding such functions by a local search
method that exploits the structure of the underlying problem. Previous attempts
in this vein typically focused on using the properties of the fitness landscape
to guide the search. We opt for a different path in which we leverage the
phenotype landscape (the mapping from genotypes to phenotypes) instead. In the
context of the underlying problem, the phenotypes are represented by
Walsh-Hadamard spectra of the candidate solutions (Boolean functions). We
propose a novel selection criterion, under which the phenotypes are compared
directly, and test whether its use increases the convergence speed (measured by
the number of required spectra calculations) when compared to a competitive
fitness function used in the literature. The results reveal promising
convergence speed improvements for Boolean functions of sizes $N=6$ to $N=9$.
