Lévy flights in neutral fitness landscapes

• Neutrality is common in biological and artificial evolutionary fitness landscapes.
• Hill-climbing techniques are not effective on regions of equal fitness.
• Neighbor-to-neighbor random drift is useful to escape neutral plateaus and to reach higher fitness ones.
• Lévy flights always outperform random drift on model neutral landscapes NKpNKp and NKqNKq.

Regions of equal or close fitness are common in biological and artificial evolutionary systems. Customary hill-climbing optimizing paradigms turn out to be unsuitable to walk and search such large neutral networks. Here we propose a new technique to quickly jump out of neutral networks and to reach better fitness regions. The algorithm, based on Lévy flights, is compared to an established nearest neighbors random drift technique on two families of constructive neutral landscapes called the NKqNKq and the NKpNKp ensembles. The results of our numerical simulations clearly show that the new algorithm performs better than the nearest neighbors random drift for all studied landscapes. We conclude with some explanations of the observed behavior and some suggestions for the use of Lévy flights in more general search and optimization heuristics.