| Revue: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000383494 |
| ISSN: | 1405-5546 |
| Autores: | Mexicano Santoyo, Adriana1 Pérez Ortega, Joaquín2 Reyes Salgado, Gerardo2 Almanza Ortega, Nelva Nely2 |
| Instituciones: | 1Instituto Tecnológico de Ciudad Victoria, Ciudad Victoria, Tamaulipas. México 2Centro Nacional de Investigación y Desarrollo Tecnológico, Cuernavaca, Morelos. México |
| Año: | 2015 |
| Periodo: | Abr-Jun |
| Volumen: | 19 |
| Número: | 2 |
| Paginación: | 295-308 |
| País: | México |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, descriptivo |
| Resumen en español | 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 |
| Resumen en inglés | This work presents a methodology for characterizing difficult instances of the Bin Packing Problem using Data Mining. Characteristics of such instances help to provide ideas for developing new strategies to find optimal solutions by improving the current solution algorithms or developing new ones. According to related work, in general, instance characterization has been used to make prediction of the algorithm that best solves an instance, or to improve one by associating the instance characteristics and performance of the algorithm that solves it. However, this work proposes the development of efficient solution algorithms guided by previous identification of characteristics that represent a greater impact on the difficulty of the instances. To validate our approach, we used a set of 1,615 instances, 6 well-known algorithms of the Bin Packing Problem, and 27 initial metrics. After applying our approach, 5 metrics were found relevant; these metrics helped to characterize 4 groups containing instances that could not be solved by any of the algorithms used in this work. Based on the gained knowledge from instance characterization, a new reduction method that helps to reduce the search space of a metaheuristic algorithm was proposed. Experimental results show that application of the reduction method allows finding more optimal solutions than those of best metaheuristics reported in the specialized literature |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Inteligencia artificial, Metaheurísticas, Minería de datos, Caracterización de instancias, Soluciones óptimas, Descubrimiento de conocimiento, Agrupamiento |
| Keyword: | Computer science, Artificial intelligence, Metaheuristics, Data mining, Instance characterization, Optimal solutions, Knowledge discovery, Clustering |
| Texte intégral: | Texto completo (Ver HTML) |
