Complex Systems

A Method for Estimating Mean First-passage Time in Genetic Algorithms Download PDF

Hiroshi Furutani
Department of Information Science,
Kyoto University of Education,
Fushimi-ku, Kyoto, 612-8522 Japan


This paper presents a simple method for estimating the mean time at which the best solution, or optimum allele, appears for the first time in the search process of genetic algorithms. A set of equations modified from Eigen's evolution equation is used for calculating the mean first-passage time. The essential point of the method is that the optimum allele is considered as an absorbing state. It is shown that the theory can generally reproduce numerical experiments on three types of fitness landscapes.