Spectral Walsh analysis and surrogate-assisted optimization: example of the bus stops spacing problem

Using surrogate-assisted optimization is an efficient way to deal with computationally expensive black-box problems. This method guides the search towards promising solutions and therefore reduces the time needed to find good solutions. In this paper, we focus on surrogates based on Walsh functions that are effective to solve pseudo-Boolean problems. An example is given with the bus stops spacing problem on single and multiple bus lines. One of the main issues with surrogate-assisted optimization is the growth of the number of terms of the model when the dimension gets high. To address this problem, we use a sparse model using only a small amount of relevant terms that is simpler to optimize. To choose the relevant terms, we use in this paper a spectral analysis that allows us to identify main terms and quantify their importance. An asynchronous surrogate-assisted master-workers optimization algorithm is also proposed to tackle this problem.