New insights on neutral binary representations for evolutionary optimization

• Definition of neutral binary representations based on the formulation of error control codes.
• Presentation of properties as connectivity, synonymity, locality and topology of representations.
• An (1+1)-ES is modeled using Markov chains and is applied to NK fitness landscapes.
• Representations with better performance in NK landscapes do not exhibit extreme values of properties.
• This conclusion is contrary to what is expect taking into account the literature recommendations.

This paper studies a family of redundant binary representations NNg(ℓ,k)NNg(ℓ,k), which are based on the mathematical formulation of error control codes, in particular, on linear block codes, which are used to add redundancy and neutrality to the representations. The analysis of the properties of uniformity, connectivity, synonymity, locality and topology of the NNg(ℓ,k)NNg(ℓ,k) representations is presented, as well as the way an (1+1)-ES can be modeled using Markov chains and applied to NK fitness landscapes with adjacent neighborhood.The results show that it is possible to design synonymously redundant representations that allow an increase of the connectivity between phenotypes. For easy problems, synonymously NNg(ℓ,k)NNg(ℓ,k) representations, with high locality, and where it is not necessary to present high values of connectivity are the most suitable for an efficient evolutionary search. On the contrary, for difficult problems, NNg(ℓ,k)NNg(ℓ,k) representations with low locality, which present connectivity between intermediate to high and with intermediate values of synonymity are the best ones. These results allow to conclude that NNg(ℓ,k)NNg(ℓ,k) representations with better performance in NK fitness landscapes with adjacent neighborhood do not exhibit extreme values of any of the properties commonly considered in the literature of evolutionary computation. This conclusion is contrary to what one would expect when taking into account the literature recommendations. This may help understand the current difficulty to formulate redundant representations, which are proven to be successful in evolutionary computation.