Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910495181635584 |
|---|---|
| author | Neumann, Frank Rudolph, Günter |
| author_facet | Neumann, Frank Rudolph, Günter |
| contents | Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the $(1+1)$-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the $(1+λ)$-EA and $(1+1)$-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_13414 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization Neumann, Frank Rudolph, Günter Neural and Evolutionary Computing Artificial Intelligence Constrained submodular optimization problems play a key role in the area of combinatorial optimization as they capture many NP-hard optimization problems. So far, Pareto optimization approaches using multi-objective formulations have been shown to be successful to tackle these problems while single-objective formulations lead to difficulties for algorithms such as the $(1+1)$-EA due to the presence of local optima. We introduce for the first time single-objective algorithms that are provably successful for different classes of constrained submodular maximization problems. Our algorithms are variants of the $(1+λ)$-EA and $(1+1)$-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems. |
| title | Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization |
| topic | Neural and Evolutionary Computing Artificial Intelligence |
| url | https://arxiv.org/abs/2406.13414 |