Evaluating Genetic Algorithms through the Approximability Hierarchy
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913218945875968 |
|---|---|
| author | Muñoz, Alba Rubio, Fernando |
| author_facet | Muñoz, Alba Rubio, Fernando |
| contents | Optimization problems frequently appear in any scientific domain. Most of the times, the corresponding decision problem turns out to be NP-hard, and in these cases genetic algorithms are often used to obtain approximated solutions. However, the difficulty to approximate different NP-hard problems can vary a lot. In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00444 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Evaluating Genetic Algorithms through the Approximability Hierarchy Muñoz, Alba Rubio, Fernando Neural and Evolutionary Computing Optimization problems frequently appear in any scientific domain. Most of the times, the corresponding decision problem turns out to be NP-hard, and in these cases genetic algorithms are often used to obtain approximated solutions. However, the difficulty to approximate different NP-hard problems can vary a lot. In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy |
| title | Evaluating Genetic Algorithms through the Approximability Hierarchy |
| topic | Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2402.00444 |