A Markov Chain Analysis Of Fitness Proportional Mate Selection Schemes In Genetic Algorithm
Chien‐Feng Huang · 2002
els focus on problems where each individual's tness is independent of others. In (Huang, 2002a), simple mod-els that implement mate selection in GAs were introduced to model interdependent tnesses of population members. They have been studied by the Schema Theorem and some empirical results. In this paper, I conduct a Markov chain analysis to further investigate these models, based on the Markov model developed by Nix and Vose (1992). Al-though such models quickly become unwieldy with increas-ing population size or string length, they provide impor-tant insights into how mate selection plays a crucial role in GA's search power, and thus serve as guidelines for study-ing more realistic problems. In (Huang, 2002a), the implementation of the four mate se-lection schemes in the selection-for-mating step of a simple