1
Download Algoritmos Evolutivos Paralelos
Document related concepts
Transcript
Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos Miguel Cárdenas Montes Centro de Investigaciones Energéticas Medioambientales y Tecnológicas, Madrid, Spain [email protected] 15-19 de Octubre de 2012 M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Temario del Curso • Introducción a la Computación Evolutiva. • Aplicaciones a Problemas Cientı́ficos y Tecnológicos. • Algoritmos Genéticos. • Algoritmos Basados en Evolución Diferencial. • Algoritmos Evolutivos para Problemas Multiobjetivo. • Modelos Basados en Adaptación Social: abejas, hormigas y enjambres. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Temario del Curso • Introducción a la Computación Evolutiva. • Aplicaciones a Problemas Cientı́ficos y Tecnológicos. • Algoritmos Genéticos. • Algoritmos Basados en Evolución Diferencial. • Algoritmos Evolutivos Paralelos. • Algoritmos Evolutivos para Problemas Multiobjetivo. • Modelos Basados en Adaptación Social: abejas, hormigas y enjambres. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Tabla de Contenidos 1 Tabla de Contenidos 2 Algoritmos Evolutivos Paralelos 3 Estructuras 4 Bibliografı́a M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos I • Para cualquier problema no trivial, ejecutar un ciclo de un EA con individuos muy complejos o una población grande, requiere una capacidad computacional elevada. • En general, evaluar el fitness de los individuos suele ser la parte más costosa del algoritmo. • En EA, el paralelismo emerge naturalmente cuando se está manejando poblaciones, puesto que cada individuo puede ser tratado como una unidad independiente. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos II • Debido a estas caracterı́sticas, el rendimiento de algoritmos basado en poblaciones mejora notablemente cuando son ejecutados en paralelo [1], [2], [3]. • Cuando los EA son paralelizados, no solo se ejecutan más rápidamente, sino que frecuentemente conducen a un rendimiento numérico superior. ¡No siempre cierto! En las siguientes transparencias más. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos III • Tres modelos básicos pueden ser distinguidos en EA paralelos [2]: • Modelo (A)sı́ncrono de Islas • Evaluación Paralela de la Población • Evaluación Distribuida de una Solución M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos IV Modelo (A)sı́ncrono de Islas. • Bajo este modelo, varios EA son desplegados simultáneamente para cooperar en la búsqueda de soluciones óptimas. • Estos EA pueden intercambiar individuos en modo sı́ncrono o ası́ncrono. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos V Modelo (A)sı́ncrono de Islas. • En el caso sı́ncrono, cada población en ejecución en un nodo de computación debe esperar por otras poblaciones. • Es necesario el intercambio de individuos entre poblaciones para favorecer la convergencia y la exploración del espacio de soluciones. • Normalmente los mejores y los más diversos individuos son los elegido para ser intercambiados. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos VI Modelo (A)sı́ncrono de Islas. • La capacidad de gestión de grandes poblaciones implican una mayor riqueza genética, y por lo tanto, una mayor probabilidad de obtener buenas soluciones. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos VII Modelo (A)sı́ncrono de Islas. • En el modo ası́ncrono, un repositorio central debe ser implementado para que las distintas poblaciones liberen sus mejores individuos y recojan los individuos liberados por otras poblaciones. • El uso del modo ası́ncrono es recomendado cuando los tiempos de ejecución son muy diferentes. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos VIII Evaluación Paralela de la Población. • Este modelo es especialmente útil cuando la evaluación de la población es el cuello de botella del algoritmo. • El servidor es responsable de las tareas de manipulación de la población. • Posteriormente el servidor distribuye los individuos entre los nodos para la evaluación. • Una vez terminada la evaluación, los resultados vuelven al servidor central. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos IX Evaluación Paralela de la Población. • La fortaleza de este modelo se basa en su capacidad para evaluar en paralelo la población completa. • La máxima aceleración teórica alcanzable corresponderı́a con el número de nodos implicados en la evaluación. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos X Evaluación Distribuida de una Solución. • En este modelo, la evaluación de cada solución es ejecutada en paralelo. • Este modelo esta recomendado cuando la función de fitness es intensiva en CPU y es paralelizable (función de fitness compuesta de varias funciones). M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos XI Evaluación Distribuida de una Solución. • En este caso, la función de fitness puede verse como un agregado de varias funciones parciales. • Cada una de estas funciones parciales es evaluada separadamente en una unidad de procesamiento. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Paralelos XII Evaluación Distribuida de una solución. • El principal beneficio obtenido con este modelo es sortear los cuellos de botella originados por la evaluación de funciones de fitness extremadamente intensivas en CPU. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Estructuras M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Panmı́ticos I • En EA es habitual encontrar algoritmos en los cuales la estructura de la población es panmı́tica, panmictic evolutionay algorithm [1]. • Con esta estructura, los procesos de selección son globales y puede incluir a cualquier individuo de la población. • Lo mismo se aplica a otros operadores como: mutación, reemplazo, etc. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Panmı́ticos II • Existen dos clases de algoritmos evolutivos panmı́ticos: • Generacionales (generational) en el cual una nueva generación reemplaza completamente a la anterior. • Estacionarios (steady state) en el cual uno o dos nuevos individuos son creados en cada iteración e insertado en la población, coexistiendo con sus padres. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Estructurados • Un modelo de selección alternativo se produce cuando los individuos se ordenan espacialmente, dando lugar a algoritmos evolutivos estructurados. Otros operadores también se adaptan a este modelo. • Existen muchos modelos de algoritmos evolutivos estructurados, pero los dos más comunes son: • modelos distribuidos (dEA) donde islas de EA son ejecutados e intercambian individuos periódicamente • modelos celulares (cEA) donde se distribuyen espacialmente las poblaciones con un ligero solape de las mismas. M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Algoritmos Evolutivos Estructurados Celulares Distribuidos • Se definen subpoblaciones. • Comunicación mediante intercambio de individuos. M. Cárdenas • Sólo hay una población. • Comunicación mediante vecindad de individuos. Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Bibliografı́a [1] Alba, E., Tomassini, M.: Parallelism and evolutionary algorithms. IEEE Trans. Evolutionary Computation 6(5) (2002) 443–462 [2] Melab, N., Cahon, S., Talbi, E.G.: Grid computing for parallel bioinspired algorithms. J. Parallel Distrib. Comput. 66(8) (2006) 1052–1061 [3] Luong, T.V., Melab, N., Talbi, E.G.: Gpu-based island model for evolutionary algorithms. In Pelikan, M., Branke, J., eds.: GECCO, ACM (2010) 1089–1096 M. Cárdenas Algoritmos Evolutivos Paralelos Tabla de Contenidos Algoritmos Evolutivos Paralelos Estructuras Bibliografı́a Gracias Gracias ¿Preguntas? ¿Más preguntas? M. Cárdenas Algoritmos Evolutivos Paralelos
