Estimation of Hitting Time by Hitting Probability for Elitist Evolutionary Algorithms
提出一种基于命中概率的漂移分析方法，通过计算命中概率来估计精英进化算法的命中时间上下界，并用于比较背包问题中两种约束处理技术的性能。
Drift analysis is one of the main tools for analyzing the time complexity of evolutionary algorithms. However, it requires manual construction of drift functions to bound hitting time for each specific algorithm and problem. To address this limitation, linear drift functions were introduced for elitist evolutionary algorithms. But calculating good linear bound coefficients remains a problem. This paper proposes a new method called drift analysis of hitting probability to compute these coefficients. Each coefficient is interpreted as a bound on the hitting probability of a fitness level, transforming the task of estimating hitting time into estimating hitting probability. A new drift analysis method is then developed to estimate hitting probability, where paths are introduced to handle multimodal fitness landscapes. Explicit expressions are constructed to compute hitting probability, significantly simplifying the estimation process. An advantage of the proposed method is its ability to estimate both the lower and upper bounds of hitting time and to compare the performance of two algorithms in terms of hitting time. To demonstrate this application, two algorithms for the knapsack problem, each incorporating feasibility rules and greedy repair respectively, are compared. The analysis indicates that neither constraint handling technique consistently outperforms the other.