Una representación categórica de metaheurísticas basadas en poblaciones
Palabras clave:
teoría de categorías, semántica composicional, mapas estocásticos finitos, algoritmos evolutivos multiobjetivo, brecha espectralResumen
Las metaheurísticas basadas en poblaciones suelen diseñarse como procedimientos monolíticos, lo que dificulta atribuir su desempeño a componentes algorítmicos específicos. Este artículo desarrolla un marco categórico composicional en el que los módulos primitivos se modelan como mapas estocásticos finitos en FinStoch y los algoritmos completos se ensamblan mediante diagramas de cableado en una categoría monoidal simétrica. Un funtor laxo monoidal de comportamiento Bhv : W → FinStoch asigna a cada diagrama de cableado un núcleo estocástico compuesto, de modo que el comportamiento de una tubería queda determinado por los comportamientos de sus módulos constitutivos. El marco se instancia para NSGA-II, SPEA2 y PESA-II, así como para una tubería de decisión MOEA + TOPSIS en dos etapas. Luego, un teorema de composición espectral acota la brecha espectral de un núcleo compuesto en términos de las brechas de sus componentes, obteniendo cotas de convergencia y un resultado de admisibilidad de horizonte finito. Un estudio de caso sobre producción con retrabajo vincula el marco con datos empíricos.
Descargas
Referencias
Auger, A., & Doerr, B. (Eds.). (2011). Theory of randomized search heuristics. World Scientific.
Baez, J. C., & Fong, B. (2015). A compositional framework for passive linear networks. Theory and Applications of Categories, 33(38), 1158-1222.
Corne, D. W., Jerram, N. R., Knowles, J. D., & Oates, M. J. (2001). PESA-II: Regionbased selection in evolutionary multiobjective optimization. In Proceedings of GECCO 2001 (pp. 283-290).
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
Fong, B. (2015). Decorated cospans. Theory and Applications of Categories, 30(33), 1096-1120.
Fong, B., & Spivak, D. I. (2019). An invitation to applied category theory. Cambridge University Press.
Fritz, T. (2020). A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics. Advances in Mathematics, 370, 107239.
Hwang, C. L., & Yoon, K. (1981). Multiple attribute decision making. Springer.
Levin, D. A., & Peres, Y. (2017). Markov chains and mixing times (Vol. 107). American Mathematical Society.
Miguel, F. M., Frutos, M., Méndez, M., Tohmé, F., & González, B. (2024). Comparison of MOEAs in an optimization-decision methodology for a joint order batching and picking system. Mathematics, 12(8), 1246.
Montenegro, R., & Tetali, P. (2006). Mathematical aspects of mixing times in Markov chains. Now Publishers.
Talbi, E. G. (2009). Metaheuristics: From design to implementation. Wiley.
Tohmé, F., & Rossit, D. (2025). Compositional scheduling in Industry 4.0 cyberphysical systems. Axioms, 14(5), 332.
Zitzler, E., Laumanns, M., & Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm (Technical Report 103). TIK, ETH Zürich.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2026 Mariano Frutos, Fernando Tohmé
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Acorde a estos términos, el material se puede compartir (copiar y redistribuir en cualquier medio o formato) y adaptar (remezclar, transformar y crear a partir del material otra obra), siempre que a) se cite la autoría y la fuente original de su publicación (revista y URL de la obra), b) no se use para fines comerciales y c) se mantengan los mismos términos de la licencia.
