Estimation of hitting time by hitting probability for elitist evolutionary algorithms

He, J ORCID: https://orcid.org/0000-0002-5616-4691, Chong, SY and Yao, X, 2025. Estimation of hitting time by hitting probability for elitist evolutionary algorithms. IEEE Transactions on Evolutionary Computation. ISSN 1089-778X

Preview

Text 2555358_He.pdf - Post-print Download (7MB) | Preview

Abstract

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.

Item Type:	Journal article
Publication Title:	IEEE Transactions on Evolutionary Computation
Creators:	He, J., Chong, S.Y. and Yao, X.
Publisher:	Institute of Electrical and Electronics Engineers (IEEE)
Date:	12 November 2025
ISSN:	1089-778X
Identifiers:	Number Type 10.1109/tevc.2025.3632072 DOI 2555358 Other
Rights:	© 2025 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Divisions:	Schools > School of Science and Technology
Record created by:	Laura Borcherds
Date Added:	05 Feb 2026 08:48
Last Modified:	05 Feb 2026 08:48
URI:	https://irep.ntu.ac.uk/id/eprint/55183

Actions (login required)

Edit View

Statistics

Views

Downloads