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

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.