Inteligencia artificial
Páginas: 7 (1699 palabras)
Publicado: 26 de noviembre de 2009
Paralelización de algoritmos genéticos
Los Algoritmos Genéticos necesitan generalmente de mucho tiempo de procesamiento para llegar a buenos resultados. Una solución a este problema es la paralelización del Algoritmo Genético, dividiendo el problema global en subproblemas que son asignados a varios procesadores de un sistema computacional. De esta forma, estos procesadores realizarán lacomputación del problema asignado obteniendo resultados parciales que serán transmitidos a los otros procesadores, colaborando todos para llegar a la solución global del problema.
Paralelización global
El método más simple de paralelizar un algoritmo genético es la llamada paralelización global.
En este caso, solo hay una población, como en el algoritmo genético convencional, pero la evaluaciónde los individuos y los operadores genéticos se paralelizan de forma explicita.
Puesto que solo hay una población, la selección considera a todos los individuos y cada individuo tiene oportunidad de aparearse con cualquier otro (o sea, hay apareamiento aleatorio). Por lo tanto, el comportamiento del algoritmo genético simple permanece sin cambios.
La paralelización global es un métodorelativamente fácil de implementar y puede obtenerse un incremento significativo de velocidad si los costos de comunicación no dominan los costos de procesamiento.
A la paralelización global también se le conoce como algoritmo genético panmítico, pues se cuenta con un solo depósito de material genético (gene pool), o sea con una sola población.
Los algoritmos genéticos panmíticos son útiles cuandoel costo de evaluar la función de aptitud es elevado (por ejemplo, una simulación). En el algoritmo genético panmítico no se requieren nuevos operadores ni nuevos parámetros y la solución encontrada será la misma que la producida con un algoritmo genético convencional (o sea, serial).
Es importante hacer notar que aunque el paralelismo global normalmente es síncrono (o sea, que el programa sedetiene y espera a recibir los valores de aptitud de toda la población antes de proceder a producir la siguiente generación), puede implementarse también de forma asíncrona, aunque en ese caso, su funcionamiento ya no resultara equivalente al de un algoritmo genético convencional.
Además de paralelizarse la evaluación de la función de aptitud, en
el paralelismo global es posible incluir tambiénlos operadores genéticos, pero dada la simplicidad de estos, no suelen paralelizarse, pues los costos de comunicación disiparían cualquier mejora en el desempeño del programa.
Paralelización de grano grueso
Una idea mas sofisticada es usar los llamados algoritmo genéticos de grano grueso. En este caso, la población del algoritmo genético se divide en múltiples subpoblaciones o demes queevolucionan de manera aislada la mayor parte del tiempo, aunque intercambian individuos ocasionalmente.
A este intercambio de individuos se le llama migración, y se considera como un nuevo operador genético. Además de requerirse parámetros adicionales en este caso, el comportamiento de un algoritmo genético de grano grueso es diferente del de un algoritmo genético convencional. A los algoritmosgenéticos de grano grueso se les suele llamar también algoritmos genéticos distribuidos, porque suelen implementarse en computadoras MIMD con memoria distribuida. Asimismo, algunos autores los llaman también algoritmos genéticos de isla, haciendo alusión a un modelo poblacional usado en genética en el cual se consideran demes relativamente aislados. A este modelo se le conoce como modelo de isla.Los algoritmos genéticos de grano grueso son muy populares debido a varias razones:
• Son una extensión muy simple de los algoritmos genéticos seriales.
Simplemente se toman unos cuantos algoritmos genéticos convencionales
(Seriales), se corre cada uno de ellos en un procesador diferente
y, a ciertos intervalos de tiempo, se intercambian unos cuantos individuos entre ellos.
•...
Los Algoritmos Genéticos necesitan generalmente de mucho tiempo de procesamiento para llegar a buenos resultados. Una solución a este problema es la paralelización del Algoritmo Genético, dividiendo el problema global en subproblemas que son asignados a varios procesadores de un sistema computacional. De esta forma, estos procesadores realizarán lacomputación del problema asignado obteniendo resultados parciales que serán transmitidos a los otros procesadores, colaborando todos para llegar a la solución global del problema.
Paralelización global
El método más simple de paralelizar un algoritmo genético es la llamada paralelización global.
En este caso, solo hay una población, como en el algoritmo genético convencional, pero la evaluaciónde los individuos y los operadores genéticos se paralelizan de forma explicita.
Puesto que solo hay una población, la selección considera a todos los individuos y cada individuo tiene oportunidad de aparearse con cualquier otro (o sea, hay apareamiento aleatorio). Por lo tanto, el comportamiento del algoritmo genético simple permanece sin cambios.
La paralelización global es un métodorelativamente fácil de implementar y puede obtenerse un incremento significativo de velocidad si los costos de comunicación no dominan los costos de procesamiento.
A la paralelización global también se le conoce como algoritmo genético panmítico, pues se cuenta con un solo depósito de material genético (gene pool), o sea con una sola población.
Los algoritmos genéticos panmíticos son útiles cuandoel costo de evaluar la función de aptitud es elevado (por ejemplo, una simulación). En el algoritmo genético panmítico no se requieren nuevos operadores ni nuevos parámetros y la solución encontrada será la misma que la producida con un algoritmo genético convencional (o sea, serial).
Es importante hacer notar que aunque el paralelismo global normalmente es síncrono (o sea, que el programa sedetiene y espera a recibir los valores de aptitud de toda la población antes de proceder a producir la siguiente generación), puede implementarse también de forma asíncrona, aunque en ese caso, su funcionamiento ya no resultara equivalente al de un algoritmo genético convencional.
Además de paralelizarse la evaluación de la función de aptitud, en
el paralelismo global es posible incluir tambiénlos operadores genéticos, pero dada la simplicidad de estos, no suelen paralelizarse, pues los costos de comunicación disiparían cualquier mejora en el desempeño del programa.
Paralelización de grano grueso
Una idea mas sofisticada es usar los llamados algoritmo genéticos de grano grueso. En este caso, la población del algoritmo genético se divide en múltiples subpoblaciones o demes queevolucionan de manera aislada la mayor parte del tiempo, aunque intercambian individuos ocasionalmente.
A este intercambio de individuos se le llama migración, y se considera como un nuevo operador genético. Además de requerirse parámetros adicionales en este caso, el comportamiento de un algoritmo genético de grano grueso es diferente del de un algoritmo genético convencional. A los algoritmosgenéticos de grano grueso se les suele llamar también algoritmos genéticos distribuidos, porque suelen implementarse en computadoras MIMD con memoria distribuida. Asimismo, algunos autores los llaman también algoritmos genéticos de isla, haciendo alusión a un modelo poblacional usado en genética en el cual se consideran demes relativamente aislados. A este modelo se le conoce como modelo de isla.Los algoritmos genéticos de grano grueso son muy populares debido a varias razones:
• Son una extensión muy simple de los algoritmos genéticos seriales.
Simplemente se toman unos cuantos algoritmos genéticos convencionales
(Seriales), se corre cada uno de ellos en un procesador diferente
y, a ciertos intervalos de tiempo, se intercambian unos cuantos individuos entre ellos.
•...
Leer documento completo
Regístrate para leer el documento completo.