Genetic local search for rule learning

ABSTRACT

The performance of Evolutionary Algorithms for combinatorial problems can be significantly improved by adding Local Search, thus obtaining a Genetic Local Search (GLS) also called Memetic Algorithm. In this work, we adapt a previous Stochastic Local Search (SLS) algorithm and embed it into a GBML system. The adapted SLS algorithm works as a module of the system that tries to improve a random individual in the population. We perform experiments to evaluate this adapted SLS procedure and results show that this new GLS system is very effective, not losing in any of the 10 UCI datasets tested when compared to the system without the SLS procedure. The system either obtained significantly more accurate concepts using lower number of rules and features or it achieved the same accuracy as the system without the SLS procedure, but reduced the number of rules and features, and also the time taken to develop the solution.

REFERENCES

• 1: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 2: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 3: Ulrich Rückert and Stefan Kramer. "Stochastic local search in k-term DNF learning." In Proc. Of the 20th ICML, pages 648--655, 2003.
• 4: Cristiano Pitangui , Gerson Zaverucha, Genetic Based Machine Learning: Merging Pittsburgh and Michigan, an Implicit Feature Selection Mechanism and a New Crossover Operator, Proceedings of the Sixth International Conference on Hybrid Intelligent Systems, p.58, December 13-15, 2006 [doi>10.1109/HIS.2006.28]
• 5: Kenneth A. De Jong , William M. Spears , Diana F. Gordon, Using Genetic Algorithms for Concept Learning, Machine Learning, v.13 n.2-3, p.161-188, Nov./Dec. 1993 [doi>10.1007/BF00993042]
• 6: Jesús S. Aguilar-Ruiz and J.C. Riquelme. "Improving the Evolutionary Coding for Machine Learning Tasks". European Conference on Artificial Intelligence, IOS Press, Lyon, France 2002, pp 173--177
• 7: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993
• 8: Blake, C.L. and Merz, C.J., "UCI Repository of machine learning databases", Irvine, CA: University of California, Department of Information and Computer Science, 1998. (http://archive.ics.uci.edu/ml/)
• 9: U. M. Fayyad and K. B. Irani. "Multi-interval discretization of continuous valued attributes for classification learning", Proceedings of the 13th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, Chambery, France, 1993, pp. 1022--1027.
• 10: Claude Nadeau , Yoshua Bengio, Inference for the Generalization Error, Machine Learning, v.52 n.3, p.239-281, September 2003 [doi>10.1023/A:1024068626366]
• 11: Pitangui, C., Zaverucha, G. Improved Natural Crossover Operators in GBML. In: IEEE Congress on Evolutionary Computation (CEC), 2007, Singapore, 2007. p. 2157--2164.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Concept learning

General Terms:
Algorithms, Experimentation, Performance

Keywords:
genetic algorithm, rule learning, stochastic local search