Resolución del problema de la mochila mediante la metaheurística PSO acelerada con JAX

Abstract

Un problema muy desafiante de la matemática aplicada moderna es la optimización numérica de problemas NP duros. Muchos problemas de interés a las ciencias e ingenierías caen en esta categoría y resulta deseable contar con algoritmos de búsqueda e implementaciones computacionales, que puedan proporcionar soluciones de aceptable calidad, en tiempos compatibles con aplicaciones prácticas. Una combinación que ha demostrado buenas prestaciones en múltiples aplicaciones son las metaheurísticas aceleradas en placas gráficas (GPU). Sin embargo, las herramientas típicas que permiten la programación de aceleradores demandan mucho conocimiento del hardware por parte del usuario. En este trabajo se explora el desempeño de una implementación de la metaheurística PSO sobre hardware masivamente paralelo a través de un compilador “just in time” llamado JAX. Esta herramienta permite acelerar programas usando un lenguaje de programación orientado a la productividad tal como lo es Python. Se utiliza como caso de estudio el clásico problema de la mochila, el cual admite la generación de instancias arbitrariamente complejas de manera sencilla. Los resultados muestran que es posible lograr aceleraciones de hasta 83 veces empleando como plataforma arquitecturas de computadoras contemporáneas. Adicionalmente, se publican resultados en el uso de unidades tensoriales, los cuales muestran el potencial del uso de estos dispositivos.