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

Hari Pandey, Ankit Chaudhary, Deepti Mehrotra

Research output: Contribution to journalArticle

2 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
JournalInternational Journal of Bio-Inspired Computation
Volume12
Issue number1
Early online date29 Jun 2018
DOIs
Publication statusE-pub ahead of print - 29 Jun 2018

Fingerprint

Grammatical Inference
Premature Convergence
Mask
Masks
Genetic algorithms
Genetic Algorithm
Random Generation
Context free grammars
Context-free Languages
Formal languages
Context-free Grammar
Statistical tests
Regular Languages
Parameter Tuning
Statistical test
Operator
Simulated annealing
Simulated Annealing
Particle swarm optimization (PSO)
Search Space

Keywords

  • bit-masking oriented data structure
  • context free grammar
  • CFG
  • genetic algorithm
  • grammar inference
  • learning system

Cite this

@article{23c1f878054a4cdd947e30468e00cc1e,
title = "Bit mask-oriented genetic algorithm for grammatical inference and premature convergence",
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.",
keywords = "bit-masking oriented data structure, context free grammar, CFG, genetic algorithm, grammar inference, learning system",
author = "Hari Pandey and Ankit Chaudhary and Deepti Mehrotra",
year = "2018",
month = "6",
day = "29",
doi = "10.1504/IJBIC.2018.093339",
language = "English",
volume = "12",
pages = "54--69",
journal = "International Journal of Bio-Inspired Computation",
issn = "1758-0366",
publisher = "Inderscience Publishers",
number = "1",

}

Bit mask-oriented genetic algorithm for grammatical inference and premature convergence. / Pandey, Hari; Chaudhary, Ankit; Mehrotra, Deepti.

In: International Journal of Bio-Inspired Computation, Vol. 12, No. 1, 29.06.2018, p. 54-69.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Pandey, Hari

AU - Chaudhary, Ankit

AU - Mehrotra, Deepti

PY - 2018/6/29

Y1 - 2018/6/29

N2 - 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.

AB - 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.

KW - bit-masking oriented data structure

KW - context free grammar

KW - CFG

KW - genetic algorithm

KW - grammar inference

KW - learning system

UR - http://www.inderscience.com/offer.php?id=93339

U2 - 10.1504/IJBIC.2018.093339

DO - 10.1504/IJBIC.2018.093339

M3 - Article

VL - 12

SP - 54

EP - 69

JO - International Journal of Bio-Inspired Computation

JF - International Journal of Bio-Inspired Computation

SN - 1758-0366

IS - 1

ER -