Grammar induction using bit masking oriented genetic algorithm and comparative analysis

Article


Pandey, H., Chaudhary, A. and Mehrotra, D. 2016. Grammar induction using bit masking oriented genetic algorithm and comparative analysis. Applied Soft Computing. 38, pp. 453-468. https://doi.org/10.1016/j.asoc.2015.09.044
TypeArticle
TitleGrammar induction using bit masking oriented genetic algorithm and comparative analysis
AuthorsPandey, H., Chaudhary, A. and Mehrotra, D.
Abstract

This paper presents bit masking oriented genetic algorithm (BMOGA) for context free grammar induction. It takes the advantages of crossover and mutation mask-fill operators together with a Boolean based procedure in two phases to guide the search process from ith generation to ( i + 1)th generation. Crossover and mutation mask-fill operations are performed to generate the proportionate amount of population in each generation. A parser has been implemented checks the validity of the grammar rules based on the acceptance or rejection of training data on the positive and negative strings of the language. Experiments are conducted on collection of context free and regular languages. Minimum description length principle has been used to generate a corpus of positive and negative samples as appropriate for the experiment. It was observed that the BMOGA produces successive generations of individuals, computes their fitness at each step and chooses the best when reached to threshold (termination) condition. As presented approach was found effective in handling premature convergence therefore results are compared with the approaches used to alleviate premature convergence. The analysis showed that the BMOGA performs better as compared to other algorithms such as: random offspring generation approach, dynamic allocation of reproduction operators, elite mating pool approach and the simple genetic algorithm. The term success ratio is used as a quality measure and its value shows the effectiveness of the BMOGA. Statistical tests indicate superiority of the BMOGA over other existing approaches implemented.

Research GroupArtificial Intelligence group
PublisherElsevier
JournalApplied Soft Computing
ISSN1568-4946
Publication dates
Online17 Oct 2015
Print01 Jan 2016
Publication process dates
Deposited01 Feb 2018
Accepted24 Sep 2015
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1016/j.asoc.2015.09.044
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/8767q

  • 26
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as