Se les invita a todos al seminario el próximo jueves Junio 1, 2017
Lugar: Raul Quintero
Nombre: Mario César López Locés
Título: Métodos de Optimización de Problemas NP-Hard Basados en Algoritmos de Procesamiento Celular
Resumen: En este proyecto se propone el uso de Algoritmos de Procesamiento Celular (CPA) y otros métodos exactos y aproximados para la solución de los problemas del Problema de Minimización del Ancho de Corte (CMP) y el Problema de Optimización de Compras por Internet (IShOP). El CPA se apoya en los tres pilares de la computación celular: simplicidad, alto grado de paralelismo y localidad. Para el CMP se implementó la versión heterogénea del CPA, que utilizó núcleos de procesamiento basados en versiones reducidas de los algoritmos ILS y GRASP. Para el IShOP se implementó una versión homogénea del CPA en el cual todos los núcleos de procesamiento fueron una variante simplificada del algoritmo ILS. Se comparó el rendimiento de los CPA propuestos contra los métodos del estado del arte de CMP y IShOP para evaluar su desempeño. Para ello, se resolvieron instancias de cada uno de los problemas de prueba considerados, CMP y IShOP. Los resultados experimentales mostraron que para el caso del CPA aplicado al CMP, el porcentaje de error promedio sobre los mejores valores conocidos en las instancias HB fue de 10.73 % para el CPA y de 7.85 % para el algoritmo del estado del arte, mientras que para las instancias Grids el porcentaje de error promedio sobre los valores óptimos fue de 4.90 % para el CPA y de 4.86 % para el algoritmo del estado del arte. En el caso de IShOP las pruebas experimentales muestran una diferencia media en el porcentaje de error de 10 % en los conjuntos de instancias de mayor tamaño. En los dos casos se determinó que resolver estos problemas utilizando un CPA tiene un rendimiento estadísticamente igual o superior al logrado por los algoritmos del estado del arte.
Bio: Investigador FIME-UANL
Ingeniero en Sistemas Computacionales, Instituto Tecnológico de Ciudad Madero, 2010, Maestría en Ciencias de la Computación, Instituto Tecnológico de Ciudad Madero, 2013Doctorado en Ciencias de la Computación, Tecnológico Nacional de México, Tijuana, 2017
Tesis Doctoral: Métodos de Optimización de Problemas NP-Hard Basados en Algoritmos de Procesamiento Celular
_______________________________________________
PISIS-L mailing list
PISIS-L(a)lists.uanl.mx
http://lists.uanl.mx/mailman/listinfo/pisis-l
