Los algoritmos genéticos son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización, basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más aptos, postulados por Charles Darwin. Por imitación de este proceso, los algoritmos genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Un algoritmo genético consiste en una función matemática que toma como entradas a los ejemplares y retorna como salidas cuáles de ellos deben generar descendencia para la nueva generación. Son tres operadores básicos los que dirigen la búsqueda en estos algoritmos. 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 será específica al problema a resolver. Las funciones de apareamiento y mutación introducen variaciones al realizar combinaciones en el conjunto actual de soluciones prometedoras.
Un algoritmo genético desarrolla una población de soluciones potenciales con vistas a resolver un problema dado. La primera población de soluciones se genera aleatoriamente. Se usa una medida de la calidad de las soluciones, expresada de forma usual en forma de una o varias funciones, para seleccionar las mejores soluciones de la población actual. Las soluciones seleccionadas pasan por los operadores de apareamiento y mutación para crear una población de nuevas soluciones. El proceso se repite hasta que se cumplan los criterios de finalización especificados por el usuario. Los algoritmos prosiguen discriminando de forma repetida la búsqueda de regiones de una mayor calidad, y combinando trozos prometedores de soluciones para formar combinaciones nuevas. De esta forma, los problemas que son descomponibles en problemas de dificultad definida se resuelven de manera eficiente, en tiempos cuadráticos o sub-cuadráticos. Muchos problemas difíciles pueden afrontarse en tiempo sub-cuadrático con respecto al número de variables. Sin embargo, para problemas muy grandes, incluso un tiempo sub-cuadrático puede llevar a enormes requisitos computacionales. Para resolver estos problemas de manera eficiente, se ha realizado un gran esfuerzo de investigación que ha llevado al estudio de la paralelización de algoritmos genéticos.
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. Los algoritmos genéticos paralelos pueden clasificarse en dos grandes clases. La primera clase es denominada algoritmos genéticos en paralelo maestro-esclavo, estos se encargan de distribuir las funciones de adaptabilidad entre los procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidatas, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. 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 sub-población. Se permite que las sub-poblaciones se comuniquen entre sí e intercambien soluciones en 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 sub-poblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejillas bidimensionales. 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 cambio en los algoritmos genéticos de grano grueso, las sub-poblaciones 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 antes, 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, uno 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 si mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador.
Un algoritmo genético desarrolla una población de soluciones potenciales con vistas a resolver un problema dado. La primera población de soluciones se genera aleatoriamente. Se usa una medida de la calidad de las soluciones, expresada de forma usual en forma de una o varias funciones, para seleccionar las mejores soluciones de la población actual. Las soluciones seleccionadas pasan por los operadores de apareamiento y mutación para crear una población de nuevas soluciones. El proceso se repite hasta que se cumplan los criterios de finalización especificados por el usuario. Los algoritmos prosiguen discriminando de forma repetida la búsqueda de regiones de una mayor calidad, y combinando trozos prometedores de soluciones para formar combinaciones nuevas. De esta forma, los problemas que son descomponibles en problemas de dificultad definida se resuelven de manera eficiente, en tiempos cuadráticos o sub-cuadráticos. Muchos problemas difíciles pueden afrontarse en tiempo sub-cuadrático con respecto al número de variables. Sin embargo, para problemas muy grandes, incluso un tiempo sub-cuadrático puede llevar a enormes requisitos computacionales. Para resolver estos problemas de manera eficiente, se ha realizado un gran esfuerzo de investigación que ha llevado al estudio de la paralelización de algoritmos genéticos.
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. Los algoritmos genéticos paralelos pueden clasificarse en dos grandes clases. La primera clase es denominada algoritmos genéticos en paralelo maestro-esclavo, estos se encargan de distribuir las funciones de adaptabilidad entre los procesadores esclavos. La información la recolecta el procesador maestro, que procesa la población de soluciones candidatas, aplicando operadores de selección, apareamiento y mutación. Posteriormente envía las nuevas soluciones a sus esclavos para que sean evaluadas. 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 sub-población. Se permite que las sub-poblaciones se comuniquen entre sí e intercambien soluciones en 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 sub-poblaciones que contienen sólo una o dos soluciones que están conectadas en topología de rejillas bidimensionales. 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 cambio en los algoritmos genéticos de grano grueso, las sub-poblaciones 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 antes, 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, uno 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 si mismo, y puede eliminar problemas de convergencia prematura, y puede también mejorar la ejecución del algoritmo en máquinas monoprocesador.
Un programa es paralelo si en cualquier momento de su ejecución puede realizar más de un proceso. Para crear programas paralelos eficientes se debe 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 un modo automático en los compiladores. (3) Paralelización de grano grueso. Se basa 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 computación paralela se ha convertido en una parte fundamental en todas las áreas de cálculo científico, ya que permite la mejora del rendimiento simplemente con la utilización de un mayor número de procesadores, memorias y la inclusión de elementos de comunicación que permitan a los procesadores trabajar conjuntamente para resolver un determinado problema.
Se puede decir que los algoritmos genéticos tienen una estructura que se adapta perfectamente a la paralelización. De hecho la evolución natural es en sí un proceso paralelo ya que evoluciona utilizando varios individuos. Los principales métodos de paralelización de los algoritmos genéticos consisten en la división de la población en varias sub-poblaciones. El tamaño y distribución de la población entre los distintos procesadores constituye uno de los factores fundamentales a la hora de paralelizar el algoritmo. Existen varias formas de paralelizar un algoritmo genético. La primera y más intuitiva es la global, que consiste básicamente en paralelizar la evaluación de los individuos manteniendo una población. Otra forma de paralelización global consiste en realizar una ejecución de distintos algoritmos genéticos secuenciales simultáneamente, siendo que estas dos formas de paralelización no cambian la estructura del algoritmo utilizado. El resto de aproximaciones sí cambian la estructura del algoritmo y dividen la población en sub-poblaciones que evolucionan por separado e intercambian individuos cada cierto número de generaciones. Si las poblaciones son pocas y grandes, se tiene la paralelización de grano grueso. Si el número de poblaciones es grande y con pocos individuos en cada población se tiene la paralelización de grano fino. Por último, existen algoritmos que mezclan propiedades de estos dos últimos y que se denominan mixtos.
Además de conseguir tiempos de ejecución bastante pequeños, al paralelizar un algoritmo genético se está modificando el comportamiento algorítmico, y esto hace que se pueda obtener otras soluciones y experimentar con las distintas posibilidades de implementación y los distintos factores que influyen en ella. Estas poblaciones van evolucionando por separado para detenerse en un momento determinado e intercambiar los mejores individuos entre ellas. Técnicamente existen tres características importantes que influyen en la eficiencia de un algoritmo genético paralelo: (1) La topología que define la comunicación entre sub-poblaciones. (2) La proporción de intercambio, referida al número de individuos a intercambiar. (3) Los intervalos de migración, que se refiera a la periodicidad con que se intercambian los individuos.
Además de conseguir tiempos de ejecución bastante pequeños, al paralelizar un algoritmo genético se está modificando el comportamiento algorítmico, y esto hace que se pueda obtener otras soluciones y experimentar con las distintas posibilidades de implementación y los distintos factores que influyen en ella. Estas poblaciones van evolucionando por separado para detenerse en un momento determinado e intercambiar los mejores individuos entre ellas. Técnicamente existen tres características importantes que influyen en la eficiencia de un algoritmo genético paralelo: (1) La topología que define la comunicación entre sub-poblaciones. (2) La proporción de intercambio, referida al número de individuos a intercambiar. (3) Los intervalos de migración, que se refiera a la periodicidad con que se intercambian los individuos.
Para conocer más acerca del Doctor Choque y sus publicaciones, haz clic en el siguiente vínculo:
No hay comentarios:
Publicar un comentario