Optimización de Corte de Material en Dos Dimensiones Mediante Hiperheurísticas Construidas con un Algoritmo Genético

Abstract

En la presente tesis se plantea explorar y aprovechar un enfoque reciente de bÚsqueda llamado Hiperheurística para resolver Problemas de Optimización de Corte de Material en Dos Dimensiones. Las hiperheurísticas son una combinación de heurísticas que en conjunto son capaces de encontrar mejores resultados que cada heurística simple. Actualmente varios de los enfoques para atacar este tipo de problemas de Optimización utilizan Algoritmos Genéticos los cuales se conforman de una codificación directa del problema en el cromosoma, sin embargo, a pesar de que los resultados obtenidos mediante estas técnicas no son ineficientes, no han gozado del suficiente éxito ya que requieren un alto grado de conocimiento específico del dominio y dicha representación genera que el espacio de bÚsqueda y el tiempo requerido para ejecutarlos crezca considerablemente conforme la entrada de los problemas crece. Una posible respuesta a estos inconvenientes es la codificación indirecta del problema, es decir, que los individuos no representen una solución al problema sino un proceso de solución. El presente trabajo propone utilizar una hiperheurística para tal fin de modo que se utilice un algoritmo genético para la construcción de una hiperheurística que solucione el problema. Existen métodos similares que ya han tenido éxito resolviendo otros problemas de Optimización como la Asignación de Horarios para Exámenes, Problemas de Acomodo de Cajas en Depósitos, entre otros. Tales resultados son un aliciente para la implantación de este nuevo enfoque que intenta eludir los inconvenientes que presenta la codificación directa y con esto poder evaluar su eficiencia para resolver una clase de problemas de tipo NP-completos que cuenta con mÚltiples aplicaciones industriales.