Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913882064289792 |
|---|---|
| author | Zheng, Weijie Doerr, Benjamin |
| author_facet | Zheng, Weijie Doerr, Benjamin |
| contents | This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart of the bi-objective OJZJ benchmark. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of $O(μM n^k)$ iterations, where $n$ denotes the problem size (length of the bit-string representation), $k$ the gap size (a difficulty parameter of the problem), $M=(2n/m-2k+3)^{m/2}$ the size of the Pareto front, and $μ$ the population size (at least the same size as the largest incomparable set). This result together with the existing negative result for the original NSGA-II shows that, in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies.
We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective \ojzj benchmark, a recently proposed stochastic population update often does not help for its many-objective counterpart. It at most results in a speed-up by a factor of order $2^{k} / μ$, which is $Θ(1)$ for large $m$, such as $m>k$. On the positive side, we prove that heavy-tailed mutation irrespective of the number $m$ of objectives results in a speed-up of order $k^{0.5+k-β}/e^k$. Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic OMM and LOTZ and show that the SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II.
Our main technical insight, a general condition ensuring that the SMS-EMOA does not lose Pareto-optimal objective values, promises to be useful also in other runtime analyses of this algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_10290 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Runtime Analysis of the SMS-EMOA for Many-Objective Optimization Zheng, Weijie Doerr, Benjamin Neural and Evolutionary Computing This paper conducts the first rigorous runtime analysis of the SMS-EMOA for many-objective optimization. To this aim, we first propose a many-objective counterpart of the bi-objective OJZJ benchmark. We prove that SMS-EMOA computes the full Pareto front of this benchmark in an expected number of $O(μM n^k)$ iterations, where $n$ denotes the problem size (length of the bit-string representation), $k$ the gap size (a difficulty parameter of the problem), $M=(2n/m-2k+3)^{m/2}$ the size of the Pareto front, and $μ$ the population size (at least the same size as the largest incomparable set). This result together with the existing negative result for the original NSGA-II shows that, in principle, the general approach of the NSGA-II is suitable for many-objective optimization, but the crowding distance as tie-breaker has deficiencies. We obtain three additional insights on the SMS-EMOA. Different from a recent result for the bi-objective \ojzj benchmark, a recently proposed stochastic population update often does not help for its many-objective counterpart. It at most results in a speed-up by a factor of order $2^{k} / μ$, which is $Θ(1)$ for large $m$, such as $m>k$. On the positive side, we prove that heavy-tailed mutation irrespective of the number $m$ of objectives results in a speed-up of order $k^{0.5+k-β}/e^k$. Finally, we conduct the first runtime analyses of the SMS-EMOA on the classic OMM and LOTZ and show that the SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II. Our main technical insight, a general condition ensuring that the SMS-EMOA does not lose Pareto-optimal objective values, promises to be useful also in other runtime analyses of this algorithm. |
| title | Runtime Analysis of the SMS-EMOA for Many-Objective Optimization |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2312.10290 |