Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem Article Swipe

PDF

Benjamin Doerr , Dimitri Korkotashvili , Martin S. Krejca ·

YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2411.10017

The NSGA-II is the most prominent multi-objective evolutionary algorithm (cited more than 50,000 times). Very recently, a mathematical runtime analysis has proven that this algorithm can have enormous difficulties when the number of objectives is larger than two (Zheng, Doerr. IEEE Transactions on Evolutionary Computation (2024)). However, this result was shown only for the OneMinMax benchmark problem, which has the particularity that all solutions are on the Pareto front, a fact heavily exploited in the proof of this result. In this work, we show a comparable result for the LeadingOnesTrailingZeroes benchmark. This popular benchmark problem appears more natural in that most of its solutions are not on the Pareto front. With a careful analysis of the population dynamics of the NGSA-II optimizing this benchmark, we manage to show that when the population grows on the Pareto front, then it does so much faster by creating known Pareto optima than by spreading out on the Pareto front. Consequently, already when still a constant fraction of the Pareto front is unexplored, the crowding distance becomes the crucial selection mechanism, and thus the same problems arise as in the optimization of OneMinMax. With these and some further arguments, we show that the NSGA-II, with a population size by at most a constant factor larger than the Pareto front, cannot compute the Pareto front in less than exponential time.

Related Topics

Computer Science

Economics

Concepts

Computer science Mathematical economics Economics

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2411.10017
PDF: https://arxiv.org/pdf/2411.10017
OA Status: green
Cited By: 1
Related Works: 10
OpenAlex ID: https://openalex.org/W4404569394

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W4404569394

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2411.10017

Digital Object Identifier
Title: Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2024

Year of publication
Publication date: 2024-11-15

Full publication date if available
Authors: Benjamin Doerr, Dimitri Korkotashvili, Martin S. Krejca

List of authors in order
Landing page: https://arxiv.org/abs/2411.10017

Publisher landing page
PDF URL: https://arxiv.org/pdf/2411.10017

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2411.10017

Direct OA link when available
Concepts: Computer science, Mathematical economics, Economics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 1

Total citation count in OpenAlex
Citations by year (recent): 2025: 1

Per-year citation counts (last 5 years)
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W4404569394
doi	https://doi.org/10.48550/arxiv.2411.10017
ids.doi	https://doi.org/10.48550/arxiv.2411.10017
ids.openalex	https://openalex.org/W4404569394
fwci
type	preprint
title	Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C41008148
concepts[0].level	0
concepts[0].score	0.4197843074798584
concepts[0].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[0].display_name	Computer science
concepts[1].id	https://openalex.org/C144237770
concepts[1].level	1
concepts[1].score	0.32284238934516907
concepts[1].wikidata	https://www.wikidata.org/wiki/Q747534
concepts[1].display_name	Mathematical economics
concepts[2].id	https://openalex.org/C162324750
concepts[2].level	0
concepts[2].score	0.3135160207748413
concepts[2].wikidata	https://www.wikidata.org/wiki/Q8134
concepts[2].display_name	Economics
keywords[0].id	https://openalex.org/keywords/computer-science
keywords[0].score	0.4197843074798584
keywords[0].display_name	Computer science
keywords[1].id	https://openalex.org/keywords/mathematical-economics
keywords[1].score	0.32284238934516907
keywords[1].display_name	Mathematical economics
keywords[2].id	https://openalex.org/keywords/economics
keywords[2].score	0.3135160207748413
keywords[2].display_name	Economics
language	en
locations[0].id	pmh:oai:arXiv.org:2411.10017
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2411.10017
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2411.10017
locations[1].id	doi:10.48550/arxiv.2411.10017
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2411.10017
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5105520300
authorships[0].author.orcid	https://orcid.org/0000-0001-5283-4208
authorships[0].author.display_name	Benjamin Doerr
authorships[0].author_position	first
authorships[0].raw_author_name	Doerr, Benjamin
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5114729907
authorships[1].author.orcid
authorships[1].author.display_name	Dimitri Korkotashvili
authorships[1].author_position	middle
authorships[1].raw_author_name	Korkotashvili, Dimitri
authorships[1].is_corresponding	False
authorships[2].author.id	https://openalex.org/A5056585957
authorships[2].author.orcid	https://orcid.org/0000-0002-1765-1219
authorships[2].author.display_name	Martin S. Krejca
authorships[2].author_position	last
authorships[2].raw_author_name	Krejca, Martin S.
authorships[2].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2411.10017
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic
related_works	https://openalex.org/W2899084033, https://openalex.org/W2748952813, https://openalex.org/W4391375266, https://openalex.org/W2390279801, https://openalex.org/W4391913857, https://openalex.org/W2358668433, https://openalex.org/W4396701345, https://openalex.org/W2376932109, https://openalex.org/W2001405890, https://openalex.org/W4396696052
cited_by_count	1
counts_by_year[0].year	2025
counts_by_year[0].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2411.10017
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2411.10017
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2411.10017
primary_location.id	pmh:oai:arXiv.org:2411.10017
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2411.10017
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2411.10017
publication_date	2024-11-15
publication_year	2024
referenced_works_count	0
abstract_inverted_index.a	16, 69, 84, 111, 160, 201, 207
abstract_inverted_index.In	79
abstract_inverted_index.as	183
abstract_inverted_index.at	205
abstract_inverted_index.by	143, 149, 204
abstract_inverted_index.in	73, 98, 184, 220
abstract_inverted_index.is	2, 34, 167
abstract_inverted_index.it	138
abstract_inverted_index.of	32, 76, 101, 114, 118, 163, 187
abstract_inverted_index.on	42, 65, 106, 133, 152
abstract_inverted_index.so	140
abstract_inverted_index.to	126
abstract_inverted_index.we	82, 124, 195
abstract_inverted_index.The	0
abstract_inverted_index.all	62
abstract_inverted_index.and	177, 191
abstract_inverted_index.are	64, 104
abstract_inverted_index.can	25
abstract_inverted_index.for	52, 87
abstract_inverted_index.has	20, 58
abstract_inverted_index.its	102
abstract_inverted_index.not	105
abstract_inverted_index.out	151
abstract_inverted_index.the	3, 30, 53, 59, 66, 74, 88, 107, 115, 119, 130, 134, 153, 164, 169, 173, 179, 185, 198, 212, 217
abstract_inverted_index.two	37
abstract_inverted_index.was	49
abstract_inverted_index.IEEE	40
abstract_inverted_index.This	91
abstract_inverted_index.Very	14
abstract_inverted_index.With	110, 189
abstract_inverted_index.does	139
abstract_inverted_index.fact	70
abstract_inverted_index.have	26
abstract_inverted_index.less	221
abstract_inverted_index.more	10, 96
abstract_inverted_index.most	4, 100, 206
abstract_inverted_index.much	141
abstract_inverted_index.only	51
abstract_inverted_index.same	180
abstract_inverted_index.show	83, 127, 196
abstract_inverted_index.size	203
abstract_inverted_index.some	192
abstract_inverted_index.than	11, 36, 148, 211, 222
abstract_inverted_index.that	22, 61, 99, 128, 197
abstract_inverted_index.then	137
abstract_inverted_index.this	23, 47, 77, 80, 122
abstract_inverted_index.thus	178
abstract_inverted_index.when	29, 129, 158
abstract_inverted_index.with	200
abstract_inverted_index.arise	182
abstract_inverted_index.front	166, 219
abstract_inverted_index.grows	132
abstract_inverted_index.known	145
abstract_inverted_index.proof	75
abstract_inverted_index.shown	50
abstract_inverted_index.still	159
abstract_inverted_index.these	190
abstract_inverted_index.time.	224
abstract_inverted_index.which	57
abstract_inverted_index.work,	81
abstract_inverted_index.(cited	9
abstract_inverted_index.50,000	12
abstract_inverted_index.Doerr.	39
abstract_inverted_index.Pareto	67, 108, 135, 146, 154, 165, 213, 218
abstract_inverted_index.cannot	215
abstract_inverted_index.factor	209
abstract_inverted_index.faster	142
abstract_inverted_index.front,	68, 136, 214
abstract_inverted_index.front.	109, 155
abstract_inverted_index.larger	35, 210
abstract_inverted_index.manage	125
abstract_inverted_index.number	31
abstract_inverted_index.optima	147
abstract_inverted_index.proven	21
abstract_inverted_index.result	48, 86
abstract_inverted_index.(Zheng,	38
abstract_inverted_index.NGSA-II	120
abstract_inverted_index.NSGA-II	1
abstract_inverted_index.already	157
abstract_inverted_index.appears	95
abstract_inverted_index.becomes	172
abstract_inverted_index.careful	112
abstract_inverted_index.compute	216
abstract_inverted_index.crucial	174
abstract_inverted_index.further	193
abstract_inverted_index.heavily	71
abstract_inverted_index.natural	97
abstract_inverted_index.popular	92
abstract_inverted_index.problem	94
abstract_inverted_index.result.	78
abstract_inverted_index.runtime	18
abstract_inverted_index.times).	13
abstract_inverted_index.(2024)).	45
abstract_inverted_index.However,	46
abstract_inverted_index.NSGA-II,	199
abstract_inverted_index.analysis	19, 113
abstract_inverted_index.constant	161, 208
abstract_inverted_index.creating	144
abstract_inverted_index.crowding	170
abstract_inverted_index.distance	171
abstract_inverted_index.dynamics	117
abstract_inverted_index.enormous	27
abstract_inverted_index.fraction	162
abstract_inverted_index.problem,	56
abstract_inverted_index.problems	181
abstract_inverted_index.OneMinMax	54
abstract_inverted_index.algorithm	8, 24
abstract_inverted_index.benchmark	55, 93
abstract_inverted_index.exploited	72
abstract_inverted_index.prominent	5
abstract_inverted_index.recently,	15
abstract_inverted_index.selection	175
abstract_inverted_index.solutions	63, 103
abstract_inverted_index.spreading	150
abstract_inverted_index.OneMinMax.	188
abstract_inverted_index.arguments,	194
abstract_inverted_index.benchmark,	123
abstract_inverted_index.benchmark.	90
abstract_inverted_index.comparable	85
abstract_inverted_index.mechanism,	176
abstract_inverted_index.objectives	33
abstract_inverted_index.optimizing	121
abstract_inverted_index.population	116, 131, 202
abstract_inverted_index.Computation	44
abstract_inverted_index.exponential	223
abstract_inverted_index.unexplored,	168
abstract_inverted_index.Evolutionary	43
abstract_inverted_index.Transactions	41
abstract_inverted_index.difficulties	28
abstract_inverted_index.evolutionary	7
abstract_inverted_index.mathematical	17
abstract_inverted_index.optimization	186
abstract_inverted_index.Consequently,	156
abstract_inverted_index.particularity	60
abstract_inverted_index.multi-objective	6
abstract_inverted_index.LeadingOnesTrailingZeroes	89
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	3
citation_normalized_percentile