![]() ![]() |
![]() | ![]() ![]() ![]() |
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.
![]() ![]() ![]() |