Searching for Search Algorithms: Experiments in Meta-Search

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Brian J. Ross: Searching for Search Algorithms: Experiments in Meta-Search. Brock COSC TR CS-02-23, December 2002.



The conventional approach to solving optimization and search problems is to ap- ply 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 in- vestigates 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 program- ming system evaluates the fitness of each search algorithm by applying it to a binary-encoded optimization problem (Traveling Salesman), and measuring the rel- ative 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.

Extended Abstract


Used References

[1] P.J. Angeline. Two Self-Adaptive Crossover Operators for Genetic Programming. In P.J. Angeline and K.E. Kinnear, editors, Advances in Genetic Programming II, pages 89–110. MIT Press, 1996.

[2] J.C. Culberson. On the Futility of Blind Search: An Algorithmic View of ’No Free Lunch’. Evolutionary Computation, 6(2):109–127, 1998.

[3] B. Edmonds. Meta-Genetic Programming: Co-evolving the Operators of Variation. Electrik, 9:13–29, 2001.

[4] T.C. Fogarty. Varying the Probability of Mutation in the Genetic Algorithm. In J. Shaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 104–109. Morgan Kaufmann, 1989.

[5] M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman, New York, 1979.

[6] G. Gutin and A.P. Punnen. Traveling Salesman Problem and Its Variations. Kluwer Academic Publishers, 2002.

[7] H. Iba and H. de Garis. Extending Genetic Programming with Recombinative Guidance. In P.J. Angeline and K.E. Kinnear, editors, Advances in Genetic Programming II, pages 69–88. MIT Press, 1996.

[8] J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, 1992.

[9] N. Krasnogor. Studies on the Theory and Design Space of Memetic Algorithms. PhD thesis, Faculty of Computing, Engineering and Mathematical Sciences, University of the West of England, Bristol, 2002.

[10] K. H. Liang, X. Yao, and C. S. Newton. Adapting self-adaptive parameters in evolutionary algorithms. Applied Intelligence, 15(3):171–180, November/December 2001.

[11] Z. Michalewicz and D.B. Fogel. How to Solve It: Modern Heuristics. Springer Verlag, 2002.

[12] D.J. Montana. Strongly Typed Genetic Programming. Computation, 3(2):199–230, 1995. Evolutionary

[13] B.M. Ombuki, M. Nakamura, and K. Onaga. An Evolutionary Scheduling Scheme Based on gkGA Approach to the Job Shop Scheduling Problem. IEICE Trans. Fundamentals, E81-A(6):1063–1071, June 1998.

[14] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 1995.

[15] L. Spector and A. Robinson. Genetic Programming and Autoconstructive Evolution with the Push Programming Language. Genetic Programming and Evolvable Machines, 3(1):7–40, March 2002.

[16] H. Tamaki, H. Kita, N. Shimizu, K. Maekawa, and Y. Nishikawa. A Comparison Study of Genetic Codings for the Traveling Salesman Problem. In Proceedings of the First IEEE Conference on Evolutionary Computation, pages 1–6. IEEE Press, June 1994.

[17] A. Teller. Evolving Programmers: the Co-evolution of Intelligent Recombination Operators. In P. Angeline and K.E. Kinnear, editors, Advances in Genetic Programming II, pages 45–68. MIT Press, 1996.

[18] J.L. Wallis and S.K. Houghten. Comparative Study of Search Techniques Applied to the Minimum Distance Problem of BCH Codes. In Proceedings 6th IASTED International Conference on Artificial Intelligence and Soft Computing, pages 164–169, Banff, Alberta, July 2002.

[19] P. H. Winston. Artificial Intelligence. Addison Wesley, 1992.

[20] D.H. Wolpert and W.G. Macready. No Free Lunch Theorems for Search. Technical Report SFI-TR-95-02-010, The Santa Fe Institute, February 1996.

[21] D.H. Wolpert and W.G. Macready. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation, 1(1):67–82, 1997.

[22] D. Zongker and B. Punch. lil-gp 1.0 User’s Manual. Dept. of Computer Science, Michigan State University, 1995.


Full Text

intern file

Sonstige Links