Estimate Hitting Time by Hitting Probability for Elitist Evolutionary Algorithms

A team of researchers including Jun He, Siang Yew Chong, and Xin Yao has published a significant advancement in evolutionary algorithm analysis in IEEE Transactions on Evolutionary Computation. Their paper, 'Estimate Hitting Time by Hitting Probability for Elitist Evolutionary Algorithms,' addresses a long-standing limitation in drift analysis—the manual construction of drift functions for each specific algorithm and problem. The researchers propose transforming the complex task of estimating hitting time (how long an algorithm takes to find a solution) into the more tractable problem of estimating hitting probability, using a novel path-based approach that handles multimodal fitness landscapes where traditional methods struggle.

The technical breakthrough involves interpreting drift coefficients as bounds on hitting probability at specific fitness levels, then developing explicit expressions to compute these probabilities. This method enables both lower and upper bound estimation of hitting time and allows direct performance comparison between different algorithms. To demonstrate practical application, the researchers compared two knapsack problem algorithms—one using feasibility rules and another using greedy repair—finding neither technique consistently outperformed the other. The approach significantly simplifies performance analysis for evolutionary algorithms used in optimization, machine learning, and AI system design.