Resumen:Muchos problemas de optimización combinatoria esconden estructuras algebraicas que, una vez expuestas, reducen el espacio de búsqueda y mejoran las posibilidades de encontrar la solución óptima global. Presentamos un marco general que (i) identifica la estructura algebraica, (ii) formaliza operaciones, (iii) construye espacios cocientes que colapsan representaciones redundantes y (iv) optimiza directamente sobre estos espacios reducidos. En una amplia familia de tareas de combinación de reglas (p. ej., descubrimiento de subgrupos de pacientes y detección molecular basada en reglas), las reglas conjuntivas forman un monoide. A través de una codificación de vector característico, demostramos un isomorfismo del hipercubo booleano ${0,1}^n$ con OR bit a bit, por lo que el AND lógico en las reglas se convierte en OR bit a bit en la codificación. Esto produce una formulación de espacio-cociente basada en principios que agrupa reglas funcionalmente equivalentes y guía la búsqueda consciente de la estructura. Sobre la base de datos clínicos reales y puntos de referencia sintéticos, los algoritmos genéticos que tienen en cuenta el espacio de cociente recuperan el óptimo global en entre el 48% y el 77% de las ejecuciones, frente al 35% y el 37% de los enfoques estándar, al tiempo que mantienen la diversidad entre las clases de equivalencia. Estos resultados muestran que exponer y explotar la estructura algebraica ofrece una ruta general simple hacia una optimización combinatoria más eficiente.
Publicado originalmente en export.arxiv.org el 7 de abril de 2026.
Ver fuente original
