  We proposed a new search heuristic using the scuba diving metaphor. This
approach is based on the concept of evolvability and tends to exploit
neutrality which exists in many real-world problems. 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
increase. A comparative study of the scuba algorithm and standard local search
heuristics has shown the advantage and the limitation of the scuba search. In
order to tune neutrality, we use the NKq fitness landscapes and a family of
travelling salesman problems (TSP) where cities are randomly placed on a
lattice and where travel distance between cities is computed with the Manhattan
metric. In this last problem the amount of neutrality varies with the city
concentration on the grid ; assuming the concentration below one, this TSP
reasonably remains a NP-hard problem.
