Una visión unificada de transformaciones biyectivas en la optimización de problemas de permutaciones

• Mikel Malagón Azpeitia ; Aimar Barrena ^[1] ; Hugo Federico Íñigo Arroyo ; Josu Ceberio Uribe ; Ekhine Irurozki ; José Antonio Lozano Alonso
  1. [1] Universidad del País Vasco/Euskal Herriko Unibertsitatea

     Universidad del País Vasco/Euskal Herriko Unibertsitatea

     Leioa, España

     
• Localización: Actas del XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados: (MAEB 2025) 28-30 de mayo, Donostia/San Sebastián / coord. por Leticia Hernando Rodríguez , Josu Ceberio Uribe , Jon Vadillo Jueguen, 2025, ISBN 978-84-1319-656-5, págs. 169-178
• Idioma: español
• Enlaces
  • Texto Completo Libro
• Resumen

  • Muchos problemas de optimización utilizan permutaciones para representar solu- ciones. Sin embargo, a pesar de su aparente simplicidad, las permutaciones pre- sentan desafíos significativos para los métodos de optimización, especialmente para los algoritmos Global Random Search (GRS). En particular, la restricción de exclusividad mutua presente en las permutaciones plantea un reto importante tanto para el aprendizaje como para el muestreo de distribuciones de probabilidad.

    Un enfoque alternativo implica el uso de funciones biyectivas sobre el espacio de permutaciones (Sn) que permite transformar las soluciones codificadas como permutaciones en representaciones de vectores enteros, conocidas como inversion vectors. Aunque los inversion vectors existen desde hace décadas, carecen de un marco general que proporcione una notación unificada y completa. En este artículo, presentamos una notación unificada que permite recodificar todos los posibles inversion vectors, y que sienta las bases para su caracterización. Por último, estudiamos el comportamiento de los algoritmos GRS cuando se utilizan diferentes inversion vectors en diversos problemas de permutaciones.