A Markov chain analysis of genetic algorithms with individuals having different birth and survival rates

Abstract

This article studies the convergence characteristics of a genetic algorithm (GA) in which individuals of different age groups in the population possess different survival and birth rates. The inclusion of this feature into the algorithm makes the algorithm mimic the natural evolutionary process more closely than the conventional GA. Although numerical experiments have demonstrated that the proposed algorithm tends to perform better than the conventional GA when used as a function optimizer, the population size of the algorithm is affected by the survival and birth rates of the individuals, which may lead to an unstable search process. Hence, this research develops the condition which governs the birth and survival rates for maintaining a stationary population size during the search process. The Markov chain approach is also used to analyze the convergence characteristics of the algorithm. The proposed algorithm is shown to converge to the global optimal solution if the best candidate solution is maintained over time. The mathematical analysis thus provides a theoretical foundation for the application of the proposed approach as a function optimizer. The performance of the proposed algorithm is tested by solving two benchmark test problems and the results are compared to those obtained by using the conventional GA. Indeed, comparison of the results clearly shows that the proposed approach is superior to the canonical genetic algorithm in terms of the quality of the final solution. The algorithm is described in some detail in the hope of thus stimulating the use of the proposed genetic approach to the solution of important problems in industrial engineering practice. © 2005 Taylor & Francis Group Ltd.