A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929684401356800 |
|---|---|
| author | Adak, Sumit Witt, Carsten |
| author_facet | Adak, Sumit Witt, Carsten |
| contents | In the literature on runtime analyses of estimation of distribution algorithms (EDAs), researchers have recently explored univariate EDAs for multi-valued decision variables. Particularly, Jedidia et al. gave the first runtime analysis of the multi-valued UMDA on the r-valued LeadingOnes (r-LeadingOnes) functions and Adak et al. gave the first runtime analysis of the multi-valued cGA (r-cGA) on the r-valued OneMax function. We utilize their framework to conduct an analysis of the multi-valued cGA on the r-valued LeadingOnes function. Even for the binary case, a runtime analysis of the classical cGA on LeadingOnes was not yet available. In this work, we show that the runtime of the r-cGA on r-LeadingOnes is O(n^2r^2 log^3 n log^2 r) with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_09514 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes Adak, Sumit Witt, Carsten Neural and Evolutionary Computing In the literature on runtime analyses of estimation of distribution algorithms (EDAs), researchers have recently explored univariate EDAs for multi-valued decision variables. Particularly, Jedidia et al. gave the first runtime analysis of the multi-valued UMDA on the r-valued LeadingOnes (r-LeadingOnes) functions and Adak et al. gave the first runtime analysis of the multi-valued cGA (r-cGA) on the r-valued OneMax function. We utilize their framework to conduct an analysis of the multi-valued cGA on the r-valued LeadingOnes function. Even for the binary case, a runtime analysis of the classical cGA on LeadingOnes was not yet available. In this work, we show that the runtime of the r-cGA on r-LeadingOnes is O(n^2r^2 log^3 n log^2 r) with high probability. |
| title | A Runtime Analysis of the Multi-Valued Compact Genetic Algorithm on Generalized LeadingOnes |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2501.09514 |