Searching for Search Algorithms: Experiments in Meta-search [PDF]
B.J. Ross, December 2002.
The conventional approach to solving optimization and search problems is to apply a variety of search algorithms to the problem at hand, in order to discover a technique that is well-adapted to the search space being explored. This paper investigates an alternative approach, in which search algorithms are automatically synthesized for particular optimization problem instances. A language composed of potentially useful basic search primitives is derived. This search language is then used with genetic programming to derive search algorithms. The genetic programming system evaluates the fitness of each search algorithm by applying it to a binary-encoded optimization problem (Traveling Salesman), and measuring the relative performance of that algorithm in finding a solution to the problem. It is shown that the evolved search algorithms often display consistent characteristics with respect to the corresponding problem instance to which they are applied. For example, some problem instances are best suited to hill-climbing, while others are better adapted to conventional genetic algorithms. As is to be expected, the search algorithm derived is strongly dependent the scale and representation of the problem explored, the amount of computational effort allotted to the overall search, and the search primitives available for the algorithm. Additionally, some insights are gained into issues of genetic algorithm search. A novel "memetic crossover" operator was evolved during the course of this research.