Latest revision as of 15:36, 26 November 2020

Resumen

El problema del Particionado de Grafos (gpp—Graph Partitioning Problem) es un problema NP-Difícil cuyo objetivo es particionar los nodos de un grafo en k conjuntos de forma que se minimice el número de aristas que unen vértices localizados en diferentes conjuntos, a la vez que se cumplen restricciones relativas al tamaño de los conjuntos. En los últimos años, el desarrollo de metaheurísticas poblacionales que incorporan un control explícito de la diversidad ha permitido realizar avances significativos al tratar diversos problemas de optimización combinatoria como el problema de coloreado de grafos o el de asignación de frecuencias. A pesar de que el gpp es un problema clásico, el desarrollo de metaheurísticas poblacionales con control de diversidad para el gpp es un tema prácticamente inexplorado. Por ello, a partir de la hipótesis de que un algoritmo memético con gestión de diversidad ayudaría a mejorar el estado del arte para el gpp, se desarrollaron nuevos algoritmos que efectivamente han permitido mejorar las soluciones encontradas hasta la fecha para una gran cantidad de casos. El trabajo presentado es un resumen de la tesis que ganó el Premio Mixbaal a la mejor tesis de licenciatura en matemáticas aplicadas, en la edición del año 2019. Este premio es otorgado por la Sociedad Mexicana de Computación Científica y Sus Aplicaciones.

Documento