Los algoritmos evolutivos basan su funcionamiento en un mecanismo análogo a los procesos evolutivos naturales, con el objetivo de resolver problemas de búsqueda y optimización. En el caso de los algoritmos genéticos, durante el proceso se mantiene una población de soluciones que evolucionan de acuerdo a operaciones de selección, apareamiento, reemplazo y mutación, siguiendo la idea de la supervivencia de los individuos más aptos. El grado de adaptación de un individuo se evalúa de acuerdo al problema a resolver, mediante una función de adaptabilidad. Los algoritmos genéticos son una robusta herramienta de optimización que pueden ser utilizados para resolver un amplio abanico de problemas de manera eficiente y precisa. Son tres operadores básicos los que dirigen la búsqueda en los algoritmos genéticos. La función de selección predispone la búsqueda hacia soluciones prometedoras. La calidad de cada individuo viene dada por la función de adaptabilidad, que es específica al problema a ser resuelto. Las funciones de apareamiento y mutación introducen variación al combinar el conjunto actual de soluciones prometedoras.
Las técnicas de procesamiento paralelo y distribuido se aplican al modelo clásico de algoritmo genético con el objetivo de obtener mejoras desde el punto de vista de la eficiencia y para perfeccionar la calidad de la búsqueda genética. Desde la perspectiva de la eficiencia, paralelizar un algoritmo genético permite afrontar la lentitud de convergencia para problemas cuya dimensión motiva el uso de poblaciones numerosas, o múltiples evaluaciones de funciones de adaptación costosas. Desde el punto de vista algorítmico, los algoritmos genéticos paralelos pueden explotar el paralelismo intrínseco del mecanismo evolutivo, trabajando simultáneamente sobre varias poblaciones semi-independientes para resolver el mismo problema. Intercambios eventuales de soluciones o migraciones, introducen diversidad para evitar problemas de convergencia en óptimos locales. Complementariamente, los algoritmos genéticos paralelos pueden aprovechar características de paralelismo propias del problema, analizando concurrentemente diferentes secciones del espacio de búsqueda.
Los estudios recientes han demostrado que la paralelización puede mejorar significativamente el rendimiento de los algoritmos genéticos. Muchos operadores de búsqueda pueden ser distribuidos fácilmente, y obtenerse así grandes incrementos de velocidad en problemas difíciles. Existen dos enfoques generales para “paralelizar” algoritmos genéticos: el primero es conocido como maestro-esclavo y el segundo de grano grueso o fino. La arquitectura maestro-esclavo suele emplearse cuando la función de adaptabilidad, que determina la calidad de cada solución individual, es el operador más costoso. La función de evaluación se distribuye entre un número determinado de procesadores esclavos y todos los operadores restantes: mutación, apareamiento y selección, se ejecutan en el procesador maestro. En los algoritmos genéticos en paralelo de grano fino o de grano grueso, la población se divide en subpoblaciones organizadas en una red. Todos los operadores en cada subpoblación se ejecutan a través de un elemento de procesamiento separado que contiene a la subpoblación. Las diferentes subpoblaciones pueden comunicarse por medio de diversas topologías de red y patrones de comunicación.
Los algoritmos genéticos pueden clasificarse en dos grandes clases: (1) En la primera clase, los algoritmos genéticos en paralelo maestro-esclavo, distribuyen las funciones de adaptabilidad entre procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidato, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. (2) La segunda clase son los algoritmos genéticos en paralelo de grano fino y de grano grueso, donde la población se distribuye entre un número dado de procesadores. Cada procesador procesa su subpoblación. Se permite que las subpoblaciones se comuniquen entre sí e intercambien soluciones a algunos intervalos. Pueden usarse varias topologías de conexión y patrones de comunicación.
Los algoritmos genéticos de grano fino dividen la población en pequeñas subpoblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejilla. Los individuos se comunican únicamente con su vecindario. El propósito original de los algoritmos genéticos de grano fino era usar un gran número de pequeños procesadores, donde cada procesador procesaría una única solución. En los algoritmos genéticos de grano grueso, las subpoblaciones son más grandes y la comunicación se reduce al intercambio de soluciones sólo de vez en cuando o después de que los algoritmos hayan convergido. Varias topologías comunes para la comunicación incluyen anillos, rejillas, hipercubos, grafos fuertemente conexos y grafos aleatorios con un número fijo de enlaces para cada elemento de proceso. Cada una de las paralelizaciones puede representar una mejora significativa para algunos problemas. Si la función de adaptabilidad se lleva la mayoría de recursos computacionales, los algoritmos genéticos en paralelo maestro-esclavo suelen dar buenos resultados. Sin embargo, cuando la función de evaluación no requiere un tiempo significativamente mayor que los otros operadores, los algoritmos genéticos de grano fino o grueso pueden mejorar aún más el rendimiento. Como se ha mencionado, los algoritmos genéticos de grano fino fueron diseñados originalmente para ejecutarse en máquinas con un gran número de pequeños procesadores conectados en topología de rejilla. Mientras la optimización se realiza, se podría esperar que soluciones parciales de gran calidad se propaguen de un sitio a otro de la rejilla en un proceso parecido a la difusión. Este comportamiento es interesante en sí mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador. Estas son algunas razones que se utilizan a momento de elegir un algoritmo de grano fino.
En una implementación especifica de un algoritmo genético de grano fino, la población de soluciones candidato se ha acotado a una rejilla bidimensional, donde cada posición de la rejilla puede contener una solución particular o estar vacía. En cada iteración del algoritmo, todas las soluciones pasan por el operador de apareamiento, en el que el individuo se combina con un vecino escogido al azar de su vecindario. El individuo, pasa entonces por un operador de mutación que realiza una ligera modificación a la solución actual. Si el nuevo individuo es de una calidad mayor, entonces reemplaza al individuo original. Esto introduce la presión de selección que discrimina la búsqueda hacia soluciones de mayor calidad. A continuación, puede aplicarse un operador local de búsqueda para afinar la solución particular. De este modo, un algoritmo genético realiza una búsqueda global, mientras que el operador local de búsqueda trata de mejorar el individuo en algún pequeño vecindario.
Un programa es paralelo si en cualquier momento de su ejecución puede ejecutar más de un proceso. Para crear programas paralelos eficientes hay que crear, destruir y especificar procesos así como la interacción entre ellos. Básicamente existen tres formas de paralelizar un programa: (1) Paralelización de grano fino. La paralelización del programa se realiza a nivel de instrucción. Cada procesador hace una parte de cada paso del algoritmo, selección, apareamiento y mutación, sobre la población común. (2) Paralelización de grano medio. Los programas se paralelizan a nivel de bucle. Esta paralelización se realiza habitualmente de forma automática en los compiladores. (3) Paralelización de grano grueso. Se fundamentan en la descomposición del dominio de datos entre los procesadores, siendo cada uno de ellos el responsable de realizar los cálculos sobre sus datos locales. La paralelización de grano grueso tiene como atractivo la portabilidad, ya que se adapta perfectamente tanto a multiprocesadores de memoria distribuida como de memoria compartida.
Una de las principales ventajas de los algoritmos genéticos es que permite que sus operaciones se puedan ejecutar en paralelo. Debido a que la evolución natural trata con una población entera y no con individuos particulares, excepto para la fase de selección, durante la cual existe una competencia entre los individuos y en la fase de reproducción, en donde se presentan iteraciones entre los miembros de la población, cualquier otra operación de la población, en particular la evaluación de cada uno de los miembros de la población, pueden hacerse separadamente. Por lo tanto, casi todas las operaciones en los algoritmos genéticos son implícitamente paralelas. Se ha establecido que la eficiencia de los algoritmos genéticos para encontrar una solución optima, está determinada por el tamaño de la población. Por lo tanto, una población grande requiere de más memoria para ser almacenada. También se ha probado que toma mayor cantidad de tiempo para lograr la convergencia. Al utilizar computadoras en paralelo, no solamente se provee de más espacio de almacenamiento, sino también con el uso de ellos se podrán producir y evaluar más soluciones en un tiempo más pequeño. Debido al paralelismo, es posible incrementar el tamaño de la población, reducir el costo computacional y mejorar el desempeño de los algoritmos genéticos.
Las técnicas de procesamiento paralelo y distribuido se aplican al modelo clásico de algoritmo genético con el objetivo de obtener mejoras desde el punto de vista de la eficiencia y para perfeccionar la calidad de la búsqueda genética. Desde la perspectiva de la eficiencia, paralelizar un algoritmo genético permite afrontar la lentitud de convergencia para problemas cuya dimensión motiva el uso de poblaciones numerosas, o múltiples evaluaciones de funciones de adaptación costosas. Desde el punto de vista algorítmico, los algoritmos genéticos paralelos pueden explotar el paralelismo intrínseco del mecanismo evolutivo, trabajando simultáneamente sobre varias poblaciones semi-independientes para resolver el mismo problema. Intercambios eventuales de soluciones o migraciones, introducen diversidad para evitar problemas de convergencia en óptimos locales. Complementariamente, los algoritmos genéticos paralelos pueden aprovechar características de paralelismo propias del problema, analizando concurrentemente diferentes secciones del espacio de búsqueda.
Los estudios recientes han demostrado que la paralelización puede mejorar significativamente el rendimiento de los algoritmos genéticos. Muchos operadores de búsqueda pueden ser distribuidos fácilmente, y obtenerse así grandes incrementos de velocidad en problemas difíciles. Existen dos enfoques generales para “paralelizar” algoritmos genéticos: el primero es conocido como maestro-esclavo y el segundo de grano grueso o fino. La arquitectura maestro-esclavo suele emplearse cuando la función de adaptabilidad, que determina la calidad de cada solución individual, es el operador más costoso. La función de evaluación se distribuye entre un número determinado de procesadores esclavos y todos los operadores restantes: mutación, apareamiento y selección, se ejecutan en el procesador maestro. En los algoritmos genéticos en paralelo de grano fino o de grano grueso, la población se divide en subpoblaciones organizadas en una red. Todos los operadores en cada subpoblación se ejecutan a través de un elemento de procesamiento separado que contiene a la subpoblación. Las diferentes subpoblaciones pueden comunicarse por medio de diversas topologías de red y patrones de comunicación.
Los algoritmos genéticos pueden clasificarse en dos grandes clases: (1) En la primera clase, los algoritmos genéticos en paralelo maestro-esclavo, distribuyen las funciones de adaptabilidad entre procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidato, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. (2) La segunda clase son los algoritmos genéticos en paralelo de grano fino y de grano grueso, donde la población se distribuye entre un número dado de procesadores. Cada procesador procesa su subpoblación. Se permite que las subpoblaciones se comuniquen entre sí e intercambien soluciones a algunos intervalos. Pueden usarse varias topologías de conexión y patrones de comunicación.
Los algoritmos genéticos de grano fino dividen la población en pequeñas subpoblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejilla. Los individuos se comunican únicamente con su vecindario. El propósito original de los algoritmos genéticos de grano fino era usar un gran número de pequeños procesadores, donde cada procesador procesaría una única solución. En los algoritmos genéticos de grano grueso, las subpoblaciones son más grandes y la comunicación se reduce al intercambio de soluciones sólo de vez en cuando o después de que los algoritmos hayan convergido. Varias topologías comunes para la comunicación incluyen anillos, rejillas, hipercubos, grafos fuertemente conexos y grafos aleatorios con un número fijo de enlaces para cada elemento de proceso. Cada una de las paralelizaciones puede representar una mejora significativa para algunos problemas. Si la función de adaptabilidad se lleva la mayoría de recursos computacionales, los algoritmos genéticos en paralelo maestro-esclavo suelen dar buenos resultados. Sin embargo, cuando la función de evaluación no requiere un tiempo significativamente mayor que los otros operadores, los algoritmos genéticos de grano fino o grueso pueden mejorar aún más el rendimiento. Como se ha mencionado, los algoritmos genéticos de grano fino fueron diseñados originalmente para ejecutarse en máquinas con un gran número de pequeños procesadores conectados en topología de rejilla. Mientras la optimización se realiza, se podría esperar que soluciones parciales de gran calidad se propaguen de un sitio a otro de la rejilla en un proceso parecido a la difusión. Este comportamiento es interesante en sí mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador. Estas son algunas razones que se utilizan a momento de elegir un algoritmo de grano fino.
En una implementación especifica de un algoritmo genético de grano fino, la población de soluciones candidato se ha acotado a una rejilla bidimensional, donde cada posición de la rejilla puede contener una solución particular o estar vacía. En cada iteración del algoritmo, todas las soluciones pasan por el operador de apareamiento, en el que el individuo se combina con un vecino escogido al azar de su vecindario. El individuo, pasa entonces por un operador de mutación que realiza una ligera modificación a la solución actual. Si el nuevo individuo es de una calidad mayor, entonces reemplaza al individuo original. Esto introduce la presión de selección que discrimina la búsqueda hacia soluciones de mayor calidad. A continuación, puede aplicarse un operador local de búsqueda para afinar la solución particular. De este modo, un algoritmo genético realiza una búsqueda global, mientras que el operador local de búsqueda trata de mejorar el individuo en algún pequeño vecindario.
Un programa es paralelo si en cualquier momento de su ejecución puede ejecutar más de un proceso. Para crear programas paralelos eficientes hay que crear, destruir y especificar procesos así como la interacción entre ellos. Básicamente existen tres formas de paralelizar un programa: (1) Paralelización de grano fino. La paralelización del programa se realiza a nivel de instrucción. Cada procesador hace una parte de cada paso del algoritmo, selección, apareamiento y mutación, sobre la población común. (2) Paralelización de grano medio. Los programas se paralelizan a nivel de bucle. Esta paralelización se realiza habitualmente de forma automática en los compiladores. (3) Paralelización de grano grueso. Se fundamentan en la descomposición del dominio de datos entre los procesadores, siendo cada uno de ellos el responsable de realizar los cálculos sobre sus datos locales. La paralelización de grano grueso tiene como atractivo la portabilidad, ya que se adapta perfectamente tanto a multiprocesadores de memoria distribuida como de memoria compartida.
Una de las principales ventajas de los algoritmos genéticos es que permite que sus operaciones se puedan ejecutar en paralelo. Debido a que la evolución natural trata con una población entera y no con individuos particulares, excepto para la fase de selección, durante la cual existe una competencia entre los individuos y en la fase de reproducción, en donde se presentan iteraciones entre los miembros de la población, cualquier otra operación de la población, en particular la evaluación de cada uno de los miembros de la población, pueden hacerse separadamente. Por lo tanto, casi todas las operaciones en los algoritmos genéticos son implícitamente paralelas. Se ha establecido que la eficiencia de los algoritmos genéticos para encontrar una solución optima, está determinada por el tamaño de la población. Por lo tanto, una población grande requiere de más memoria para ser almacenada. También se ha probado que toma mayor cantidad de tiempo para lograr la convergencia. Al utilizar computadoras en paralelo, no solamente se provee de más espacio de almacenamiento, sino también con el uso de ellos se podrán producir y evaluar más soluciones en un tiempo más pequeño. Debido al paralelismo, es posible incrementar el tamaño de la población, reducir el costo computacional y mejorar el desempeño de los algoritmos genéticos.
No hay comentarios:
Publicar un comentario