Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
<|reference_start|>Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization: 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+\lambda)$-EA and $(1+1)$-EA and increase the feasible region of the search space incrementally in order to deal with the considered submodular problems.<|reference_end|>
@article{neumann2024archive-based,
    title={Archive-based Single-Objective Evolutionary Algorithms for Submodular
  Optimization},
    author={Frank Neumann and G"unter Rudolph},
    journal={arXiv preprint arXiv:2406.13414},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.13414},
    primaryClass={cs.NE cs.AI}
}