文章基本信息

标题：Caracterización de instancias difíciles del problema de Bin Packing orientada a la mejora de algoritmos metaheurísticos
本地全文：下载
作者：Adriana Mexicano Santoyo ; Joaquín Pérez Ortega ; Gerardo Reyes Salgado 等
期刊名称：Computación y Sistemas
印刷版ISSN：1405-5546
出版年度：2015
卷号：19
期号：2
页码：295-308
语种：Spanish
出版社：Instituto Politécnico Nacional
摘要：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 d e 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 des empeñ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 difi cultad 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 soluc iones óptimas que las reportadas en el estado del arte por las mejores metaheurísticas.
其他摘要：This work presents a methodology for characterizing difficult instances of the Bin Packing P roblem using Data Mining . C haracteristics of such instances help to provide ideas for developing new strategies to find optimal solutions by improving the current solution algorithms or develop ing new ones. According to related work, in general, instance characterization has been used to make prediction of the algorithm that best solves an instance, o r 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; th e s e 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.
关键词：Metaheuristicas; bin paking; caracterización; agrupamiento; reducción; descubrimiento de conocimiento
其他关键词：Characterization; clustering; metaheuristics; bin packing problem; reduction; knowledge d iscovery .