Runtime analysis of convex evolutionary search algorithm with standard crossover
dc.contributor.author | Malalanirainy, T | |
dc.contributor.author | Moraglio, A | |
dc.date.accessioned | 2022-05-10T08:04:30Z | |
dc.date.issued | 2022-04-13 | |
dc.date.updated | 2022-04-05T08:27:55Z | |
dc.description.abstract | Evolutionary Algorithms (EAs) with no mutation can be generalized across representations as Convex Evolu- tionary 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. 𝑑-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 popu- lation sizes. In particular, the SES solves Leading Ones in at most 288 𝑛 ln [4 𝑛 (2 𝑛 + 1)] expected fitness evaluations when the population size is equal to 144 ln [4 𝑛 (2 𝑛 + 1)] . | en_GB |
dc.identifier.citation | Vol. 71, article 101078 | en_GB |
dc.identifier.doi | 10.1016/j.swevo.2022.101078 | |
dc.identifier.uri | http://hdl.handle.net/10871/129571 | |
dc.identifier | ORCID: 0000-0003-4782-6590 (Moraglio, Alberto) | |
dc.language.iso | en | en_GB |
dc.publisher | Elsevier | en_GB |
dc.rights | © 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/) | en_GB |
dc.subject | Convex evolutionary search | en_GB |
dc.subject | Quasi-concave landscapes | en_GB |
dc.subject | Runtime upper bound | en_GB |
dc.subject | Standard crossover | en_GB |
dc.subject | Unifying theory | en_GB |
dc.title | Runtime analysis of convex evolutionary search algorithm with standard crossover | en_GB |
dc.type | Article | en_GB |
dc.date.available | 2022-05-10T08:04:30Z | |
dc.identifier.issn | 2210-6510 | |
dc.description | This is the final version. Available on open access from Elsevier via the DOI in this record | en_GB |
dc.identifier.journal | Swarm and Evolutionary Computation | en_GB |
dc.relation.ispartof | Swarm and Evolutionary Computation | |
dc.rights.uri | https://creativecommons.org/licenses/by/4.0/ | en_GB |
dcterms.dateAccepted | 2022-04-02 | |
rioxxterms.version | VoR | en_GB |
rioxxterms.licenseref.startdate | 2022-04-13 | |
rioxxterms.type | Journal Article/Review | en_GB |
refterms.dateFCD | 2022-04-05T08:27:58Z | |
refterms.versionFCD | AM | |
refterms.dateFOA | 2022-05-10T08:07:19Z | |
refterms.panel | B | en_GB |
Files in this item
This item appears in the following Collection(s)
Except where otherwise noted, this item's licence is described as © 2022 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)