On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau

Standard

On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau. / Еремеев, Антон Валентинович.

In: Yugoslav Journal of Operations Research, 2025, p. 1-27.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{7a7116e351ec4774aa24b0d86bb609a5,

title = "On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau",

abstract = "The expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions Plateaur on the search space of binary strings of length n is considered asymptotically with unbounded n. The functions of this family have a plateau of second-best fitness in a Hamming ball of a constant radius r around a unique global optimum, while below the plateau the fitness equals the number of one-bits. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for non-elitist EAs with tournament selection, (?, ?)-selection and proportionate selection. We assume that these EAs are based on an unbiased mutation, in particular, the bitwise mutation. In the case of proportionate selection, the mutation probability is of order 1/n2. On the other hand, we show that the EA with fitness proportionate selection is inefficient even to search for approximate solutions if the bitwise mutation is used with the mutation probability greater than ln(2)/n.",

keywords = "Evolutionary algorithm, selection, runtime, Plateau, unbiased mutation",

author = "Еремеев, {Антон Валентинович}",

note = "Eremeev A. On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau // Yugoslav Journal of Operations Research. – 2025. – No. 00. – P. 42. – DOI 10.2298/yjor250715042e. – EDN ZLQJRZ. This research was funded by the Mathematical Center in Akademgorodok under the agreement № 075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation.",

year = "2025",

doi = "10.2298/yjor250715042e",

language = "English",

pages = "1--27",

journal = "Yugoslav Journal of Operations Research",

issn = "0354-0243",

publisher = "University of Belgrade",

}

RIS

TY - JOUR

T1 - On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau

AU - Еремеев, Антон Валентинович

N1 - Eremeev A. On runtime of non-elitist evolutionary algorithms optimizing fitness functions with a plateau // Yugoslav Journal of Operations Research. – 2025. – No. 00. – P. 42. – DOI 10.2298/yjor250715042e. – EDN ZLQJRZ. This research was funded by the Mathematical Center in Akademgorodok under the agreement № 075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2025

Y1 - 2025

N2 - The expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions Plateaur on the search space of binary strings of length n is considered asymptotically with unbounded n. The functions of this family have a plateau of second-best fitness in a Hamming ball of a constant radius r around a unique global optimum, while below the plateau the fitness equals the number of one-bits. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for non-elitist EAs with tournament selection, (?, ?)-selection and proportionate selection. We assume that these EAs are based on an unbiased mutation, in particular, the bitwise mutation. In the case of proportionate selection, the mutation probability is of order 1/n2. On the other hand, we show that the EA with fitness proportionate selection is inefficient even to search for approximate solutions if the bitwise mutation is used with the mutation probability greater than ln(2)/n.

AB - The expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions Plateaur on the search space of binary strings of length n is considered asymptotically with unbounded n. The functions of this family have a plateau of second-best fitness in a Hamming ball of a constant radius r around a unique global optimum, while below the plateau the fitness equals the number of one-bits. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for non-elitist EAs with tournament selection, (?, ?)-selection and proportionate selection. We assume that these EAs are based on an unbiased mutation, in particular, the bitwise mutation. In the case of proportionate selection, the mutation probability is of order 1/n2. On the other hand, we show that the EA with fitness proportionate selection is inefficient even to search for approximate solutions if the bitwise mutation is used with the mutation probability greater than ln(2)/n.

KW - Evolutionary algorithm

KW - selection

KW - runtime

KW - Plateau

KW - unbiased mutation

UR - https://www.scopus.com/pages/publications/105035081571

UR - https://www.elibrary.ru/item.asp?id=87978488

U2 - 10.2298/yjor250715042e

DO - 10.2298/yjor250715042e

M3 - Article

SP - 1

EP - 27

JO - Yugoslav Journal of Operations Research

JF - Yugoslav Journal of Operations Research

SN - 0354-0243

ER -

ID: 76001508