Optimizing Genetic Algorithms Using the Binomial Distribution
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916504126095360 |
|---|---|
| author | Cicirello, Vincent A. |
| author_facet | Cicirello, Vincent A. |
| contents | Evolutionary algorithms rely very heavily on randomized behavior. Execution speed, therefore, depends strongly on how we implement randomness, such as our choice of pseudorandom number generator, or the algorithms used to map pseudorandom values to specific intervals or distributions. In this paper, we observe that the standard bit-flip mutation of a genetic algorithm (GA), uniform crossover, and the GA control loop that determines which pairs of parents to cross are all in essence binomial experiments. We then show how to optimize each of these by utilizing a binomial distribution and sampling algorithms to dramatically speed the runtime of a GA relative to the common implementation. We implement our approach in the open-source Java library Chips-n-Salsa. Our experiments validate that the approach is orders of magnitude faster than the common GA implementation, yet produces solutions that are statistically equivalent in solution quality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_02009 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing Genetic Algorithms Using the Binomial Distribution Cicirello, Vincent A. Neural and Evolutionary Computing 68W50, 68T05, 68T20, 68W20 I.2.8; F.2.2 Evolutionary algorithms rely very heavily on randomized behavior. Execution speed, therefore, depends strongly on how we implement randomness, such as our choice of pseudorandom number generator, or the algorithms used to map pseudorandom values to specific intervals or distributions. In this paper, we observe that the standard bit-flip mutation of a genetic algorithm (GA), uniform crossover, and the GA control loop that determines which pairs of parents to cross are all in essence binomial experiments. We then show how to optimize each of these by utilizing a binomial distribution and sampling algorithms to dramatically speed the runtime of a GA relative to the common implementation. We implement our approach in the open-source Java library Chips-n-Salsa. Our experiments validate that the approach is orders of magnitude faster than the common GA implementation, yet produces solutions that are statistically equivalent in solution quality. |
| title | Optimizing Genetic Algorithms Using the Binomial Distribution |
| topic | Neural and Evolutionary Computing 68W50, 68T05, 68T20, 68W20 I.2.8; F.2.2 |
| url | https://arxiv.org/abs/2412.02009 |