ECAI 2004 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

How to use the scuba diving metaphor to solve problem with neutrality ?

Philippe Collard, Sébastien Verel, Manuel Clergue

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 fitness landscapes. 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. A comparative study of the new algorithm and standard local search heuristics on the travelling salesman problem (TSP) has shown advantage and limit of the scuba search heuristic. In order to tune neutrality we use a TSP where cities are randomly placed on a lattice; and travel distance between cities is computed with the Manhattan metric. The amount of neutrality vary with the city concentration on the grid. Assuming the concentration below one, this TSP reasonably remains a NP-hard problem.

Keywords: Metaheuristic, Fitness Landscape, Neutrality

Citation: Philippe Collard, Sébastien Verel, Manuel Clergue: How to use the scuba diving metaphor to solve problem with neutrality ? . In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.166-170.

[prev] [tofc] [next]

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politčcnica de Valčncia on behalf of Asociación Espańola de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligčncia Artificial (ACIA).