Diseño e implementación de un algoritmo genético paralelo para la solución de problemas de optimización combinatoria

Abstract

El presente trabajo de título tiene por objetivo diseñar un algoritmo genético paralelo para la resoluci´on de problemas de optimización combinatoria. Para cumplir con el objetivo general es necesario contar con un problema de decisi´on complejo (NP-Hard), en este trabajo se selecciona el problema de localizaci´on de nodos presente en las redes inal´ambricas. Una vez definido el problema a resolver se desarrollan los principales componentes del algoritmo gen´etico como: la codificaci´on utilizada, la funci´on de fitness, los operadores gen´eticos, etc. Finalmente se realiza una comparaci´on entre el algoritmo propuesto y su versi´on secuencial. Para el desarrollo de este trabajo t´ıtulo se realiza una exhaustiva b´usqueda bibliogr´afica, que permite tener una visi´on actualizada sobre las caracter´ısticas y problemas presentes en las redes inal´ambricas, los distintos tipos de algoritmos gen´eticos, los frameworks que permiten la implementaci´on de metaheur´ısticas evolutivas y por ´ultimo una descripci´on de la computaci´on de alta performance. El problema de localizaci´on de nodos se resolvi´o por medio de tres algoritmos gen´eticos, el primero de ellos es un algoritmo gen´etico secuencial, el segundo es un algoritmo paralelo Maestro/Esclavo y el tercero es un algoritmo basado en un modelo de islas. Para los tres algoritmos desarrollados se implementaron la misma funci´on objetivo y operadores gen´eticos. Como los algoritmos gen´eticos son de naturaleza estoc´astica, para la comparaci´on entre ellos es necesario realizar un elevado n´umero de ejecuciones independientes sobre el problema planteado. Una vez obtenidos los resultados de las respectivas ejecuciones se realiza un an´alisis estad´ıstico que permite verificar si los resultados obtenidos (fitness) provienen de poblaciones distintas o iguales. Luego se realiza una comparaci´on del tiempo de procesamiento entre los distintos algoritmos utilizando el Speedup y la eficiencia. Los algoritmos modelos de islas son los que obtienen los mejores resultados en funci´on del tiempo de procesamiento. Respecto a los valores de fitness promedio obtenidos los algoritmos secuencial y los basados en modelos de islas son los que obtienen los mejores resultados.