Drift analysis with fitness levels for elitist evolutionary algorithms

He, J ORCID: https://orcid.org/0000-0002-5616-4691 and Zhou, Y, 2024. Drift analysis with fitness levels for elitist evolutionary algorithms. Evolutionary Computation. ISSN 1063-6560

Preview

Text 1881665_He.pdf - Post-print Download (350kB) | Preview

Abstract

The fitness level method is a popular tool for analyzing the hitting time of elitist evolutionary algorithms. Its idea is to divide the search space into multiple fitness levels and estimate lower and upper bounds on the hitting time using transition probabilities between fitness levels. However, the lower bound generated by this method is often loose. An open question regarding the fitness level method is what are the tightest lower and upper time bounds that can be constructed based on transition probabilities between fitness levels. To answer this question, we combine drift analysis with fitness levels and define the tightest bound problem as a constrained multi-objective optimization problem subject to fitness levels. The tightest metric bounds by fitness levels are constructed and proven for the first time. Then linear bounds are derived from metric bounds and a framework is established that can be used to develop different fitness level methods for different types of linear bounds. The framework is generic and promising, as it can be used to draw tight time bounds on both fitness landscapes with and without shortcuts. This is demonstrated in the example of the (1+1) EA maximizing the TwoMax1 function.

Item Type:	Journal article
Publication Title:	Evolutionary Computation
Creators:	He, J. and Zhou, Y.
Publisher:	MIT Press
Date:	22 March 2024
ISSN:	1063-6560
Identifiers:	Number Type 10.1162/evco_a_00349 DOI 1881665 Other
Rights:	Accepted for publication in Evolutionary Computation. This manuscript is the author's final version.
Divisions:	Schools > School of Science and Technology
Record created by:	Laura Ward
Date Added:	04 Apr 2024 15:48
Last Modified:	04 Apr 2024 15:48
URI:	https://irep.ntu.ac.uk/id/eprint/51195

Actions (login required)

Edit View

Statistics

Views

Downloads