Sparse Surrogate Model for Optimization: Example of the Bus Stops Spacing Problem

Combinatorial optimization problems can involve computationaly expensive fitness function, making their resolution challenging. Surrogate models are one of the effective techniques used to solve such black-box problems by guiding the search towards potentially good solutions. In this paper, we focus on the use of surrogate based on multinomial approaches, particularly based on Walsh functions, to tackle pseudo-Boolean problems. Although this approach can be effective, a potential drawback is the growth of the polynomial expansion with problem dimension. We introduce a method for analyzing real-world combinatorial black-box problems defined through numerical simulation. This method combines Walsh spectral analysis and polynomial regression. Consequently, we propose a sparse surrogate model that incorporates selected, relevant terms and is simpler to optimize. To demonstrate our approach, we apply it to the bus stop spacing problem, an exemplary combinatorial pseudo-Boolean challenge.