4.7 Article

Runtime analysis of convex evolutionary search algorithm with standard crossover

期刊

SWARM AND EVOLUTIONARY COMPUTATION
卷 71, 期 -, 页码 -

出版社

ELSEVIER
DOI: 10.1016/j.swevo.2022.101078

关键词

Convex evolutionary search; Quasi-concave landscapes; Runtime upper bound; Standard crossover; Unifying theory

向作者/读者索取更多资源

This article introduces an evolutionary algorithm and improves it to adapt to different representations. The authors propose a more faithful generalization by introducing a new crossover operator. The article also discusses the application of this algorithm in specific metric spaces and provides a polynomial expected runtime upper bound for certain problems.
Evolutionary Algorithms (EAs) with no mutation can be generalized across representations as Convex Evolutionary Search algorithms (CSs). However, the crossover operator used by CSs does not faithfully generalize the standard two-parents crossover: it samples a convex hull instead of a segment. Segmentwise Evolutionary Search algorithms (SESs) are defined as a more faithful generalization, equipped with a crossover operator that samples the metric segment of two parents. In metric spaces where the union of all possible segments of a given set is always a convex set, a SES is a particular CS. Consequently, the representation-free analysis of the CS on quasi-concave landscapes can be extended to the SES in these particular metric spaces. When instantiated to binary strings of the Hamming space (resp. d-ary strings of the Manhattan space), a polynomial expected runtime upper bound is obtained for quasi-concave landscapes with at most polynomially many level sets for well-chosen population sizes. In particular, the SES solves Leading Ones in at most 288n ln[4n(2n + 1)] expected fitness evaluations when the population size is equal to 144 ln[4n(2n + 1)].

作者

我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。

评论

主要评分

4.7
评分不足

次要评分

新颖性
-
重要性
-
科学严谨性
-
评价这篇论文

推荐

暂无数据
暂无数据