Regresar

Análisis de factibilidad del uso de unidades de procesamiento gráfico en algoritmos de optimización meta-heurísticos

Abstract:

Actualmente, varios problemas de optimización del mundo real se han modelado matemáticamente. El proceso de modelado toma en cuenta la mayor cantidad de información posible para que el modelo obtenido sea lo más próximo a la realidad. Sin embargo, a medida que aumenta la información, la complejidad también aumenta. En consecuencia, se necesita una mayor capacidad computacional para resolver problemas complejos y escalables. Los métodos de optimización exactos o matemáticos son considerados de búsqueda exhaustiva, lo que para problemas multi-dimensionales no resulta práctico. Como resultado, se han desarrollado algoritmos meta-heurísticos para resolver problemas complejos de optimización. Estos algoritmos se usan comúnmente para problemas de dos o más dimensiones, en los que intervienen operaciones de vectores y matrices. Por lo tanto, para resolver este tipo de problema, es útil llevar a cabo procesos paralelos que reducen el tiempo de ejecución. Actualmente, existen unidades de procesamiento central (Central Processing Unit (CPU)) de múltiples núcleos que logran resolver fácilmente pequeños problemas con cálculos paralelos. Sin embargo, la unidad de procesamiento de gráficos (Graphics P rocessing U nit (GPU)) o frece l a p osibilidad de mejorar el rendimiento porque incorpora una mayor cantidad de núcleos que la CPU, lo cual es muy útil para problemas con varios procesos en paralelo. Un problema clásico en la comunidad de investigación de sistemas de energía eléctrica es el Planeamiento de la Expansión del Sistema Eléctrico de Transmisión (PET). En el departamento de Ingeniería Eléctrica, Electrónica y Telecomunicaciones, en el proyecto “Uso del modelo de corriente alterna para la planificación i ntegrada multietapa d e l a e xpansión de líneas de transmisión/subtransmisión y fuentes de potencia reactiva en sistemas de energía eléctrica” se trata de mejorar el desempeño del problema PET. En el proyecto, se busca reducir el tiempo de cálculo mejorando los algoritmos meta-heurísticos. En este trabajo de titulación, como complemento al proyecto mencionado precedentemente, se analizó la factibilidad de reducir el tiempo de ejecución, implementando los algoritmos meta-heurísticos usando una GPU. Para lo cual, previamente a la implementación del problema PET, se analizó el uso de la GPU en problemas paralelizables y la implementación de un algoritmo meta-heurístico en un problema bidimensional. Lo cual ha sido favorable para motivar el uso de la GPU.