  We continue the study of Genetic Algorithms (GA) on combinatorial
optimization problems where the candidate solutions need to satisfy a
balancedness constraint. It has been observed that the reduction of the search
space size granted by ad-hoc crossover and mutation operators does not usually
translate to a substantial improvement of the GA performances. There is still
no clear explanation of this phenomenon, although it is suspected that a
balanced representation might yield a more irregular fitness landscape, where
it could be more difficult for GA to converge to a global optimum. In this
paper, we investigate this issue by adding a local search step to a GA with
balanced operators, and use it to evolve highly nonlinear balanced Boolean
functions. In particular, we organize our experiments around two research
questions, namely if local search (1) improves the convergence speed of GA, and
(2) decreases the population diversity. Surprisingly, while our results answer
affirmatively the first question, they also show that adding local search
actually \emph{increases} the diversity among the individuals in the
population. We link these findings to some recent results on fitness landscape
analysis for problems on Boolean functions.
