RT Conference Proceedings
T1 Fourier Transform-based Surrogates for Permutation Problems
A1 Chicano-García, José-Francisco
A1 Derbel, Bilel
A1 Verel, Sébastien
K1 Computación evolutiva
AB In the context of pseudo-Boolean optimization, surrogate functions based on the Walsh-Hadamard transform have been recently proposed with great success. It has been shown that lower-order components of the Walsh-Hadamard transform have usually a larger influence on the value of the objective function. Thus, creating a surrogate model using the lower-order components of the transform can provide a good approximation to the objective function. The Walsh-Hadamard transform in pseudo-Boolean optimization is a particularization in the binary representation of a Fourier transform over a finite group, precisely defined in the framework of group representation theory. Using this more general definition, it is possible to define a Fourier transform for the functions over permutations. We propose in this paper the use of surrogate functions based on the Fourier transforms over the permutation space. We check how similar the proposed surrogate models are to the original objective function and we also apply regression to learn a surrogate model based on the Fourier transform. The experimental setting includes two permutation problems for which the exact Fourier transform is unknown based on the problem parameters: the Asteroid Routing Problem and the Single Machine Total Weighted Tardiness.
YR 2023
FD 2023
LK https://hdl.handle.net/10630/27373
UL https://hdl.handle.net/10630/27373
LA eng
NO Universidad de Málaga. Campus de Excelencia Internacional Andalucía Tech.Ministerio de Ciencia, Innovación y Universidades del Gobierno de España under grants PID 2020-116727RB-I00 and PRX21/00669, and by EU Horizon 2020 research and innovative program (grant 952215, TAILOR ICT-48 network). Thanks to the Supercomputing and Bioinnovation Center (SCBI) of Universidad de Málaga for their provision of computational resources and support.
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 4 mar 2026