A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911039387336704 |
|---|---|
| author | Opris, Andre |
| author_facet | Opris, Andre |
| contents | This paper presents a first mathematical runtime analysis of PAES-25, an enhanced version of the original Pareto Archived Evolution Strategy (PAES) coming from the study of telecommunication problems over two decades ago to understand the dynamics of local search of MOEAs on many-objective fitness landscapes. We derive tight expected runtime bounds of PAES-25 with one-bit mutation on $m$-LOTZ until the entire Pareto front is found: $Θ(n^3)$ iterations if $m=2$, $Θ(n^3 \log^2(n))$ iterations if $m=4$ and $Θ(n(2n/m)^{m/2} \log(n/m))$ iterations if $m>4$ where $n$ is the problem size and $m$ the number of objectives. To the best of our knowledge, these are the first known tight runtime bounds for an MOEA outperforming the best known upper bound of $O(n^{m+1})$ for (G)SEMO on $m$-LOTZ when $m$ is at least $4$. We also show that archivers, such as the Adaptive Grid Archiver (AGA), Hypervolume Archiver (HVA) or Multi-Level Grid Archiver (MGA), help to distribute the set of solutions across the Pareto front of $m$-LOTZ efficiently. We also show that PAES-25 with standard bit mutation optimizes the bi-objective LOTZ benchmark in expected $O(n^4)$ iterations, and we discuss its limitations on other benchmarks such as OMM or COCZ. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_03666 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy Opris, Andre Neural and Evolutionary Computing 68W50, 68W32, 68W20, 68Q87, 68Q25 F.2.2; G.3 This paper presents a first mathematical runtime analysis of PAES-25, an enhanced version of the original Pareto Archived Evolution Strategy (PAES) coming from the study of telecommunication problems over two decades ago to understand the dynamics of local search of MOEAs on many-objective fitness landscapes. We derive tight expected runtime bounds of PAES-25 with one-bit mutation on $m$-LOTZ until the entire Pareto front is found: $Θ(n^3)$ iterations if $m=2$, $Θ(n^3 \log^2(n))$ iterations if $m=4$ and $Θ(n(2n/m)^{m/2} \log(n/m))$ iterations if $m>4$ where $n$ is the problem size and $m$ the number of objectives. To the best of our knowledge, these are the first known tight runtime bounds for an MOEA outperforming the best known upper bound of $O(n^{m+1})$ for (G)SEMO on $m$-LOTZ when $m$ is at least $4$. We also show that archivers, such as the Adaptive Grid Archiver (AGA), Hypervolume Archiver (HVA) or Multi-Level Grid Archiver (MGA), help to distribute the set of solutions across the Pareto front of $m$-LOTZ efficiently. We also show that PAES-25 with standard bit mutation optimizes the bi-objective LOTZ benchmark in expected $O(n^4)$ iterations, and we discuss its limitations on other benchmarks such as OMM or COCZ. |
| title | A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy |
| topic | Neural and Evolutionary Computing 68W50, 68W32, 68W20, 68Q87, 68Q25 F.2.2; G.3 |
| url | https://arxiv.org/abs/2507.03666 |