Genetic algorithms: Concepts, issues and a case study of grammar induction

Authors: Pandey, H.M., Dixit, A. and Mehrotra, D.

Journal: ACM International Conference Proceeding Series

Pages: 263-271

ISBN: 9781450311854

DOI: 10.1145/2381716.2381766


This paper discusses a case study of grammar induction. Grammar induction is the process of learning grammar from a set of training data of the positive (S +) and negative (S -) strings. An algorithm has been designed and implemented for the induction of context free grammar (CFG). Special bit mask oriented data structures have been used to apply the crossover and mutation operations. The aim is to establish the applicability of the genetic algorithms (GAs) for different engineering problems. The paper lays a concrete foundation to formulating problems in the genetic algorithm framework. In addition, the basic principles of standard genetic algorithm, such as encoding techniques, selection techniques, operators (crossover and mutation), and the issues raised in the relevant literature have been discussed to establish the applicability of the genetic algorithm. Copyright 2012 ACM.

Source: Scopus