On the convergence rate and expected first fitting time of elitist evolutionary algorithms

Abstract

This article studies theoretical topics of finite absorbing Markov chains describing evolutionary algorithms (EAs in short) coupled with elitism. Firstly, by means of spectrum analysis we generalize the conclusion that the convergence rate of an EA is determined by the revised spectral radius of corresponding transition matrix. Beyond relatively strict assumptions of previous works, the determination holds if 1 is the strictly maximal module eigenvalue and has equal algebraic and geometric multiplicities. As an application, a case with multiple recurrent classes is analyzed. Secondly, we drive a direct relation about both exact expressions of the expected first hitting time (EFHT) and convergence rates under another measurement. Also, bounds of EFHT are evaluated with simple forms. The feasibleness is verified by several EAs on Trap problem. © 2012 International Information Institute.