Resumen

Los problemas de subconjuntos (partición de conjuntos, empaquetamiento y cobertura) son modelos formales de muchos problemas prácticos de optimización. Un problema de partición de conjuntos determina cómo se pueden dividir los elementos de un conjunto (S) en subconjuntos más pequeños. Todos los elementos de S deben estar contenidos en una y sólo una partición. Los problemas relacionados son el empaquetamiento de conjuntos (todos los elementos deben estar contenidos en cero o una partición) y la cobertura de conjuntos (todos los elementos deben estar contenidos en al menos una partición). Aquí presentamos un solucionador híbrido basado en la optimización de colonias de hormigas (ACO) combinada con la consistencia de arco para resolver este tipo de problemas. ACO es una metaheurística de inteligencia de enjambre inspirada en el comportamiento de las hormigas cuando buscan comida. Permite resolver problemas combinatorios complejos para los que las técnicas matemáticas tradicionales pueden fallar. Por otro lado, en la programación con restricciones, el proceso de resolución de problemas de satisfacción de restricciones puede reducir drásticamente el espacio de búsqueda por medio de la coherencia de arcos, reforzando la coherencia de las restricciones antes o durante la búsqueda. Nuestro enfoque híbrido se probó con conjuntos de datos de cobertura y partición de conjuntos. Se observó que el rendimiento de ACO había mejorado al integrar esta técnica de filtrado en su fase constructiva.

• Materias:Matemáticas Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:mathematics Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:artículos, aco, consistencia de arco, muchos problemas prácticos de optimización, problemas de satisfacción de restricciones, optimización de colonia de hormigas, problemas combinatorios complejos, metaheurística de inteligencia de enjambre, técnicas matemáticas tradicionales, partición
• Keywords:items, aco, arc consistency, many practical optimization problems, constraint satisfaction problems, ant colony optimization, complex combinatorial problems, swarm intelligence metaheuristic, traditional mathematical techniques, partition