Extremal Optimization Dynamics in Neutral Landscapes: The Royal Road Case

In recent years a new view of evolutionary dynamics has emerged based on both neutrality and balance between adaptation and exaptation. Differently from the canonical adaptive paradigm where the genotypic variability is strictly related to the change at fitness level, such a paradigm has raised awareness of the importance of both selective neutrality and co-option by exaptation. This paper investigates an innovative method based on Extremal Optimization, a coevolutionary algorithm successfully applied to NP-hard combinatorial problems, with the aim of exploring the ability of its extremal dynamics to face neutral fitness landscapes by exploiting co-option by exaptation. A comparison has been effected between Extremal Optimization and a Random Mutation Hill Climber on several problem instances of a wellknown neutral fitness landscape, i.e., the Royal Road.