Bit mask-oriented genetic algorithm for grammatical inference and premature convergence


Pandey, H., Chaudhary, A. and Mehrotra, D. 2018. Bit mask-oriented genetic algorithm for grammatical inference and premature convergence. International Journal of Bio-Inspired Computation. 12 (1), pp. 54-69.
TitleBit mask-oriented genetic algorithm for grammatical inference and premature convergence
AuthorsPandey, H., Chaudhary, A. and Mehrotra, D.

In this paper, a Bit Mask Oriented Genetic Algorithm (BMOGA) is proposed for Grammatical Inference (GI). GI is techniques to infer a context free grammar from a set of positive and negative samples. The BMOGA combines the traditional genetic algorithm, which has a powerful global exploration capability, with a Bit Mask Oriented Data Structure (BMODS) and Boolean based procedure (uses Boolean operators) that can exploit an optimum offspring. The evolutionary operations are performed in two phases: mask-fill for both crossover and mutation and then a Boolean operator based procedure. A vector function is utilized with arguments such as crossover, mutation masks and a couple of parents strings. The arguments crossover and mutation mask helps in replacing various mating rules and therefore no strict rules are to be designed to select an appropriate crossover mechanism. An extensive parameter tuning is done that makes the proposed algorithm more robust, statistically sound, and quickly convergent. The proposed BMOGA is effectively applied over the context free as well as regular languages of varying complexities. The computational experiments show that the proposed BMOGA finds optimal or close-to-optimal grammar with the best fitness value. The Boolean operators introduce diversity in the population that helps in exploring the search space adequately. First, we evaluate the performance of the BMOGA against three algorithms: the genetic algorithm, particle swarm optimization and simulated annealing. Then, the BMOGA is tested with two different offspring generation algorithms: random offspring generation and elite mating pool approach. Statistical tests are conducted that indicate the superiority of the proposed algorithm over others. Overall, a genetic algorithm based tool is developed for the GI, which greatly improves the results, robustness and alleviate premature convergence.

Research GroupArtificial Intelligence group
Foundations of Computing group
PublisherInderscience Publishers
JournalInternational Journal of Bio-Inspired Computation
Publication dates
Print29 Jun 2018
Publication process dates
Deposited05 Feb 2018
Submitted30 Aug 2015
Accepted06 Jan 2017
Output statusPublished
Digital Object Identifier (DOI)
Permalink -

  • 33
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as