Convergence measurement in evolutionary computation using Price's theorem

摘要

Evolutionary computations are naturally inspired stochastic algorithms that are capable of running perpetually. When deployed as optimization tools, it is imperative to prescribe a set of definitive stopping criteria that if satisfied, the evolutionary process could be brought to a halt. User specified limits on maximum evaluations or generations are the common measures used to stop the evolution due to resource constraints that might directly/indirectly be imposed on the system. Conversely, we propose a novel convergence detection mechanism that monitors the contribution of the genetic operators on the fitness progress and the diversity profile of the population via the ±σ crossover envelope. This adaptively terminates the evolution as convergence sets in. Extended Price''s theorem is utilized to estimate the dynamical contributions of the individual genetic operators. Experimental results show that under standard parameter settings with binary tournament selection, the proposed technique is robust and could be a promising alternative to the conventional similarity measure-based methods for convergence detection.