Habiendo implementado un algoritmo genético simple (en particular una minimización de la función valle de Rosenbrock) con el fin de utilizarlo como benchmark, puedo destacar ciertas conclusiones.
El método de paralelización utilizado fue el básico para estos casos, es decir, el monolítico en términos de algoritmos genéticos, o sea, es decir existirá una sola población global que evoluciona. Este mecanismo no es el mejor desde el punto de vista del paralelismo, pero la intención es utilizarlo como benchmark, por lo que pude relajar la exigencia.
Las operaciones que se paralelizaron fueron:
- Evaluación del Fitness
- Crossover y Mutación
Mientras que las operaciones que quedaron seriales fueron:
- Inicialización
- Selección
No se utilizó una condición de optimalidad, ya que la idea fue implementar algo comparativo, por lo que se forzó siempre la ejecución de 100.000 generaciones, aunque en la mayoría de los casos, antes de las 2.000 generaciones se había alcanzado un valor más que aceptable.
Por otro lado, dado que la representación para los cromosomas fue la clásica tira de bits, no se representó un contínuo, sino una discretización del mismo, quedando excluido el punto en donde se halla el mínimo global de la función (1,1). De esta manera el algoritmo explora una franja con forma de banana que se da en la representación tridimensional de la función donde se encuentran los valores mínimos de la misma.
Por tanto debe quedar claro que el objetivo no fue optimizar la función de Rosenbrock, sino implementar un algoritmo genético paralelo comparable con fines de benchmark.
La parametrización de las corridas ha sido la siguiente:
POBLACION_SIZE 200
MAX_GENERACIONES 100000
CROSSOVER_PROBABILITY 0,65
MUTATION_PROBABILITY 0,035
El resultado arrojado por la versión serial en un dual core (2Ghz) con 2Gb RAM fue:
| Operación | Tiempo en ms | % |
| Inicializacion | 0 | 0,00% |
| Computo del Fitness | 728085 | 78,69% |
| Operaciones Geneticas (Cross+Mut+Reempl) | 191311 | 20,68% |
| Seleccion | 5880 | 0,64% |
| 925276 |
Cabe destacar que una corrida serial en un procesador i7 con 8Gb de RAM toma 70 segundos (aproximadamente el 8% respecto a la corrida descripta).
Las corridas paralelas han arrojado los siguientes resultados:
| Nodos | Workers | Tiempo Total | Inicializacion | Computo del Fitness | Operaciones Geneticas | Seleccion |
| 1 | 0 | 925276 | 0 | 728085 | 191311 | 5880 |
| 2 | 1 | 457484 | 0,077 | 347019 | 104263 | 6085 |
| 3 | 2 | 548708 | 0,082 | 349236 | 192929 | 6432 |
| 4 | 3 | 502676 | 0,082 | 318536 | 177568 | 6458 |
| 5 | 4 | 489597 | 0,081 | 288175 | 194847 | 6445 |
| 6 | 5 | 494720 | 0,116 | 281966 | 206180 | 6464 |
| 7 | 6 | 349025 | 0,082 | 206147 | 136326 | 6432 |
| 8 | 7 | 349025 | 0,082 | 206147 | 136326 | 6432 |
| 9 | 8 | 294204 | 0,077 | 171204 | 116748 | 6137 |
| 10 | 9 | 286247 | 0,077 | 162048 | 117613 | 6471 |
| 11 | 10 | 407975 | 0,078 | 236078 | 165234 | 6494 |
| 12 | 11 | 468207 | 0,078 | 267160 | 194435 | 6449 |
| 13 | 12 | 582009 | 0,078 | 340445 | 234938 | 6439 |
Con respecto a los tiempos de las operaciones genéticas en paralelo vemos que no se evidencia un incremento en la performance que sea beneficioso en términos reales. Esto puede deberse a que las operaciones genéticas, en este caso, son operaciones a nivel de bits, que suelen ser sumamente eficientes a nivel de procesamiento; y que, por otro lado, implican una transferencia de datos importantes: se envían 2 individuos (en este caso cabe recordar que cada individuo consiste en un arreglo de 13 bytes) y se devuelven 2 individuos, por tanto cada operación implica una transferencia de 52 bytes entre master y worker. Por tanto, la mejora en términos de procesamiento no compite con el consumo de recursos de red provocado por esta estrategia.
En cambio, en la evaluación del fitness se da otro escenario, favorable al paralelismo. En este caso, por cada individuo se envían 13 bytes y se reciben 4 bytes. En esta operación, el consumo de CPU tiene un peso más significativo que el overhead provocado por la utilización de la red (hasta cierto punto). Con la presente configuración, se encontró un mínimo tiempo de procesamiento con 10 nodos (9 workers) para la evaluación del fitness, como para el tiempo global, de una magnitud de 4,5 y 3,23 veces respectivamente.
Como conclusión general se puede extraer:
- En GA simples, las operaciones genéticas consumen poco procesador respecto al consumo de red de enviar 2 individuos y recibir otros dos individuos.
- La operación que más fácilmente se paraleliza es el cálculo del fitness.
- La paralelización es muy sensible a los parámetros: Cambiará mucho si el tamaño del individuo se multiplica por 100 (vuelva totalmente inviable la paralelización de las operaciones genéticas), o si el tamaño de la población se multiplica, podríamos empezar a obtener buenos resultados paralelizando las operaciones genéticas. Otro dato sensible es el consumo de procesador durante la evaluación del fitness. Si este consumo se multiplica por 100, el rendimiento del paralelismo incrementará, dado que es la función más fácilmente paralelizable.
- El ancho de banda es un impedimento para la escalabilidad de la solución en paralelo con MPI (GA simple y monolítico). Más aún si el GA consume o genera datos centralizados.
