Representación de permutaciones y su influencia en la optimización

M. Malagón, H. F. Iñigo, E. Irurozki, J. A. Lozano Alonso, J. Ceberio

Muchos problemas de optimización combinatoria están definidos sobre el espacio de permutaciones. Ejemplos paradigmáticos son el problema del viajante de comercio o el problema de asignación cuadrática. La resolución de estos problemas mediante algoritmos metaheurísticos que muestrean distribuciones de probabilidad, como los algoritmos de estimación de distribuciones, se enfrentan a muchas dificultades a la hora de codificar eficientemente las distribuciones debido a las restricciones de exclusividad mutua de las permutaciones (cada índice solo puede aparecer una única vez en la permutación). En este trabajo abordamos la representación de permutaciones mediante vectores de inversión. Éstos eliminan las restricciones anteriormente mencionadas y facilitan la codificación de distribuciones de probabilidad en el espacio de permutaciones. Equipados con estas representaciones analizamos su repercusión en el resultado final de la optimización.

Keywords: Problemas de optimización combinatoria, metaheurísticos, permutaciones

Heuristics and Metaheuristics I
June 10, 2025  3:30 PM
MR 1

J. Serrano Roig, A. Martinez Gavara, M. Reula Martin

J. Sánchez Díaz, S. Cavero, E. G. Pardo

X. Benavides Canta, L. Hernando Rodriguez, J. Ceberio Uribe, J. A. Lozano Alonso

M. Robles Rodríguez, S. Cavero, E. G. Pardo