Fast Pareto Optimization Using Sliding Window Selection
This work addresses runtime issues in evolutionary multi-objective algorithms for researchers and practitioners in optimization, though it is incremental as it builds on recent algorithms.
The paper tackles the runtime inefficiency in Pareto optimization for constrained submodular problems by introducing a sliding window technique, which eliminates population size as a bottleneck and achieves the same theoretical guarantees with less computation time, as confirmed by experiments on maximum coverage instances.
Pareto optimization using evolutionary multi-objective algorithms has been widely applied to solve constrained submodular optimization problems. A crucial factor determining the runtime of the used evolutionary algorithms to obtain good approximations is the population size of the algorithms which grows with the number of trade-offs that the algorithms encounter. In this paper, we introduce a sliding window speed up technique for recently introduced algorithms. We prove that our technique eliminates the population size as a crucial factor negatively impacting the runtime and achieves the same theoretical performance guarantees as previous approaches within less computation time. Our experimental investigations for the classical maximum coverage problem confirms that our sliding window technique clearly leads to better results for a wide range of instances and constraint settings.