Hybridizing Genetic Algorithm and Beam Search for Solving Optimization Problems

Abstract

Genetic Algorithm (GA) is the search-based approach that mimics the idea of natural selection and the genetics of living beings. Due to the finite population size, GA suffers from the problem of genetic drift and premature convergence. To solve these problems, hybridization between the Genetic Algorithm and local search, i.e. Memetic Algorithm (MA) is used. MA minimizes the search time by reducing the computation and preventing premature convergence. In this paper, a proposal of new memetic algorithm has been given in which Beam search is applied in the selection process of a Genetic Algorithm to enhance the performance of a simple Genetic Algorithm. Experiments have been conducted using four benchmark functions, and the whole implementation is carried out using Python. Results demonstrate that the proposed hybrid algorithm provides better output than a simple Genetic Algorithm and maintains a state of equilibrium between exploration and exploitation within the search space.