Saved in:
| Main Author: | |
|---|---|
| Format: | Artículo científico |
| Language: | es |
| Published: |
Instituto Politécnico Nacional
2015
|
| Subjects: | |
| Online Access: | https://www.redalyc.org/articulo.oa?id=61539886008 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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 Nelva Nely Almanza Ortega Computación reducción bin paking agrupamiento Metaheuristicas caracterización 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. 2015 artículo científico 1405-5546 https://www.redalyc.org/articulo.oa?id=61539886008 es http://www.redalyc.org/revista.oa?id=615 Computación y Sistemas application/pdf Instituto Politécnico Nacional Computación y Sistemas (México) Num.2 Vol.19