Sparse Surrogate Model for Optimization: Example of the Bus Stops Spacing Problem - Laboratoire d'Informatique Signal et Image de la Côte d'Opale Access content directly
Conference Papers Year : 2024

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

Abstract

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.
Fichier principal
Vignette du fichier
bus-stops-problem_evo24.pdf (845.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
licence : CC BY - Attribution

Dates and versions

hal-04502943 , version 1 (13-03-2024)

Licence

Attribution - NonCommercial

Identifiers

  • HAL Id : hal-04502943 , version 1

Cite

Valentin Vendi, Sébastien Verel, Cyril Fonlupt. Sparse Surrogate Model for Optimization: Example of the Bus Stops Spacing Problem. Evolutionary Computation in Combinatorial Optimization Conference (evoCOP), Apr 2024, Aberystwyth, Wales, United Kingdom. ⟨hal-04502943⟩
18 View
19 Download

Share

Gmail Facebook X LinkedIn More