Scuba search: when selection meets innovation

We proposed a search heuristic using the scuba diving metaphor. This approach is based on the concept of evolvability and tends to exploit neutrality in fitness landscape. Despite the fact that natural evolution does not directly select for evolvability, the basic idea behind the scuba search heuristic is to explicitly push evolvability to increases. Globally the search process switches between two phases: conquest-of-the-waters and invasion-of-the-land. A comparative study of the algorithm and standard local search heuristics on the NKq-landscapes has shown advantage and limit of the scuba search. To enlighten qualitative differences between neutral search processes, the space is transformed into a connected graph to visualize the pathways that the search is likely to follow.