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

Hari Pandey, Ankit Chaudhary, Deepti Mehrotra

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

In this paper, a bit mask-oriented genetic algorithm (BMOGA) is presented for grammatical inference (GI). GI is techniques to infer context free grammar from a set of corpora. The BMOGA combines the traditional genetic algorithm with a bit-mask oriented data structure and Boolean-based procedure (uses Boolean operators) that can exploit an optimum offspring. Extensive parameters tuning is done that makes the BMOGA more robust, statistically sound, and quickly convergent. The BMOGA is applied over the context free as well as regular languages of varying complexities. The results show that BMOGA finds optimal or close-to-optimal solution. The Boolean operators introduce diversity in the population that helps in exploring the search space adequately that helps to alleviate premature convergence. First, we evaluate the performance of the BMOGA against three algorithms: the genetic algorithm, particle swarm optimisation and simulated annealing. Then, the BMOGA is tested against 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.
Original languageEnglish
Pages (from-to)54-69
Number of pages16
JournalInternational Journal of Bio-Inspired Computation
Volume12
Issue number1
Early online date29 Jun 2018
DOIs
Publication statusPublished - 2018

Keywords

  • bit-masking oriented data structure
  • context free grammar
  • CFG
  • genetic algorithm
  • grammar inference
  • learning system
  • Bit-masking oriented data structure
  • Grammar inference
  • Genetic algorithm
  • Context free grammar
  • Learning system

Fingerprint Dive into the research topics of 'Bit mask-oriented genetic algorithm for grammatical inference and premature convergence'. Together they form a unique fingerprint.

  • Research Output

    • 5 Citations
    • 1 Book

    State of the art on grammatical inference using evolutionary method

    PANDEY, HARI. MOHAN., 18 Sep 2019, (Accepted/In press) Elsevier. 230 p.

    Research output: Book/ReportBook

  • Cite this