Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916257254604800 |
|---|---|
| author | Dang, Duc-Cuong Opris, Andre Sudholt, Dirk |
| author_facet | Dang, Duc-Cuong Opris, Andre Sudholt, Dirk |
| contents | Runtime analysis has recently been applied to popular evolutionary multi-objective (EMO) algorithms like NSGA-II in order to establish a rigorous theoretical foundation. However, most analyses showed that these algorithms have the same performance guarantee as the simple (G)SEMO algorithm. To our knowledge, there are no runtime analyses showing an advantage of a popular EMO algorithm over the simple algorithm for deterministic problems.
We propose such a problem and use it to showcase the superiority of popular EMO algorithms over (G)SEMO: OneTrapZeroTrap is a straightforward generalization of the well-known Trap function to two objectives. We prove that, while GSEMO requires at least $n^n$ expected fitness evaluations to optimise OneTrapZeroTrap, popular EMO algorithms NSGA-II, NSGA-III and SMS-EMOA, all enhanced with a mild diversity mechanism of avoiding genotype duplication, only require $O(n \log n)$ expected fitness evaluations. Our analysis reveals the importance of the key components in each of these sophisticated algorithms and contributes to a better understanding of their capabilities. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13572 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis Dang, Duc-Cuong Opris, Andre Sudholt, Dirk Neural and Evolutionary Computing F.2.0; I.2.8 Runtime analysis has recently been applied to popular evolutionary multi-objective (EMO) algorithms like NSGA-II in order to establish a rigorous theoretical foundation. However, most analyses showed that these algorithms have the same performance guarantee as the simple (G)SEMO algorithm. To our knowledge, there are no runtime analyses showing an advantage of a popular EMO algorithm over the simple algorithm for deterministic problems. We propose such a problem and use it to showcase the superiority of popular EMO algorithms over (G)SEMO: OneTrapZeroTrap is a straightforward generalization of the well-known Trap function to two objectives. We prove that, while GSEMO requires at least $n^n$ expected fitness evaluations to optimise OneTrapZeroTrap, popular EMO algorithms NSGA-II, NSGA-III and SMS-EMOA, all enhanced with a mild diversity mechanism of avoiding genotype duplication, only require $O(n \log n)$ expected fitness evaluations. Our analysis reveals the importance of the key components in each of these sophisticated algorithms and contributes to a better understanding of their capabilities. |
| title | Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis |
| topic | Neural and Evolutionary Computing F.2.0; I.2.8 |
| url | https://arxiv.org/abs/2405.13572 |