Optimizando la implementación de algoritmos evolutivos
J.J. Merelo, Pedro Castillo,Juan L. Jiménez Laredo, Maribel García Arenas
GeNeura team: http://geneura.wordpress.comDepto. de Arquitectura y Tecnología de Computadores:
http://atc.ugr.es Universidad d Granada: http://www.ugr.es
Mejorando los algoritmos evolutivos
Usar una metodología de prueba y evaluación seguida por la aplicación de técnicas de
programación comunes
Prestar atención a la optimización de las aplicaciones
El hardware cada vez es más potente y rápido,
aún así, se deben optimizar las implementaciones
En cuanto a la implementación de los algoritmos evolutivos
Se pueden diseñar mejores algoritmos y obtener
mejoras sustanciales tanto algorítmicas como de
tiempo de ejecución
Herramientas que nos ayudarán
MonitoresTiempo de ejecución, memoria usada, consumo de recursos
ProfilersTiempo invertido y número de ejecuciones reales de fragmentos de código
En este trabajo...
Partir de la implementación de un AE sencilloProgramado en Perl con Algorithm::EvolutionaryAnalizar el programa con las herramientasAplicar cambios para optimizar la implementaciónEstudiar las mejoras
Planteamiento del problema
Fitness = MaxOnesAlgoritmo genético canónico, con élitePoblación y longitud variable
Software libre: http://bit.ly/bOk3z3
Posibles mejoras al programa
Mejoras en el cálculo del fitness:Usar una cachéCambio del cálculo del fitness
Detección de cuellos de botella:Usar un profiler para detectarlosCambio de la función de ordenación
El tamaño siempre importa
Caché para la función fitness
Uso de la función de Perl tr para cálculo del fitness
básica
caché
básica
usar tr
Cuantos más semos... más tardaremos
Uso de un profiler para localización de cuello de botella: función sort
Cambio por Sort::Key
(mejora del comportamiento
peor caso)
básica
Sort::Key
mergesort
Conclusiones
Mejoras del tiempo de ejecución de un programa mediante mejoras en la implementación.
Conviene aplicar técnicas de programación habituales y buenas prácticas.
Trabajo futuro: incorporación de técnicas en Algorithm::Evolutionary, librería de algoritmos evolutivos en Perl.