∗ Algorithms and Complexity Group

Abstract—Motivated by neutrality observed in natural evolu-tion often redundant encodings are used in evolutionary algo-rithms. Many experimental studies have been carried out on this topic. In this paper we present a first rigorous runtime analysis on the effect of using neutrality. We consider a simple model where a layer of constant fitness is distributed in the search space and point out situations where the use of neutrality significantly influence the runtime of an evolutionary algorithm. I