Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913762627289088 |
|---|---|
| author | Adak, Sumit Witt, Carsten |
| author_facet | Adak, Sumit Witt, Carsten |
| contents | Recent research in the runtime analysis of estimation of distribution algorithms (EDAs) has focused on univariate EDAs for multi-valued decision variables. In particular, the runtime of the multi-valued cGA (r-cGA) and UMDA on multi-valued functions has been a significant area of study. Adak and Witt (PPSN 2024) and Hamano et al. (ECJ 2024) independently performed a first runtime analysis of the r-cGA on the r-valued OneMax function (r-OneMax). Adak and Witt also introduced a different r-valued OneMax function called G-OneMax. However, for that function, only empirical results were provided so far due to the increased complexity of its runtime analysis, since r-OneMax involves categorical values of two types only, while G-OneMax encompasses all possible values.
In this paper, we present the first theoretical runtime analysis of the r-cGA on the G-OneMax function. We demonstrate that the runtime is O(nr^3 log^2 n log r) with high probability. Additionally, we refine the previously established runtime analysis of the r-cGA on r-OneMax, improving the previous bound to O(nr log n log r), which improves the state of the art by an asymptotic factor of log n and is tight for the binary case. Moreover, we for the first time include the case of frequency borders. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21439 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems Adak, Sumit Witt, Carsten Neural and Evolutionary Computing Recent research in the runtime analysis of estimation of distribution algorithms (EDAs) has focused on univariate EDAs for multi-valued decision variables. In particular, the runtime of the multi-valued cGA (r-cGA) and UMDA on multi-valued functions has been a significant area of study. Adak and Witt (PPSN 2024) and Hamano et al. (ECJ 2024) independently performed a first runtime analysis of the r-cGA on the r-valued OneMax function (r-OneMax). Adak and Witt also introduced a different r-valued OneMax function called G-OneMax. However, for that function, only empirical results were provided so far due to the increased complexity of its runtime analysis, since r-OneMax involves categorical values of two types only, while G-OneMax encompasses all possible values. In this paper, we present the first theoretical runtime analysis of the r-cGA on the G-OneMax function. We demonstrate that the runtime is O(nr^3 log^2 n log r) with high probability. Additionally, we refine the previously established runtime analysis of the r-cGA on r-OneMax, improving the previous bound to O(nr log n log r), which improves the state of the art by an asymptotic factor of log n and is tight for the binary case. Moreover, we for the first time include the case of frequency borders. |
| title | Improved Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Two Generalized OneMax Problems |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2503.21439 |