Caracterización de instancias difíciles del problema de Bin Packing orientada a la mejora de algoritmos metaheurísticos

Resumen

En este trabajo se presenta una metodología para la caracterización de instancias difíciles del problema de Bin Packing usando Minería de Datos. El objetivo es que las características de las instancias proporcionen ideas para desarrollar nuevas estrategias para encontrar soluciones óptimas mediante la mejora de los algoritmos de solución actuales o mediante el desarrollo de nuevos. De acuerdo a la literatura especializada, en general, la caracterización de instancias ha sido utilizada para predecir qué algoritmo resuelve mejor una instancia o para mejorar el algoritmo asociando las características de la instancia con el desempeño de dicho algoritmo. A diferencia de los trabajos anteriores, este trabajo propone que el desarrollo de algoritmos de solución eficientes puede ser guiado por una previa identificación de las características que representan un alto impacto en la dificultad para obtener su solución. Para validar nuestro enfoque se utilizó un conjunto de 1,615 instancias, 6 algoritmos bien conocidos del problema de Bin Packing y 27 métricas iniciales. Después de aplicar técnicas de agrupamiento de Minería de Datos para la caracterización de las instancias, se encontraron 5 métricas que ayudaron a caracterizar 4 grupos con las instancias que no fueron resueltas por ninguno de los algoritmos usados en este trabajo. En base al conocimiento obtenido de la caracterización de las instancias, se propuso un nuevo método de reducción de instancias que contribuye a reducir el espacio de búsqueda de un algoritmo metaheurístico. Los resultados experimentales muestran que aplicando el método de reducción es posible encontrar más soluciones óptimas que las reportadas en el estado del arte por las mejores metaheurísticas.